What is the best algorithm to find the center of a wave on a matrix?
Finding the first non-zero value only works when the signal is symmetric and contain no rotation. Consider the following example borrowed from Internet (zero = blue, max = red), note the first-non-zero value is somewhere by the top right corner:
(source: mathworks.com)
You might want to have a look at gradient descent. The general algorithm is defined for continuous functions (yours is discrete), but you can still use it.
It basically gets initialized somewhere in your matrix, looks for the gradient at that point and moves in that direction, then repeat until it converges. You can initialize it by sampling randomly (pick a random cell until you get to a non-zero value, you could expect this to be faster than traversing and finding a non zero value in average, naturally depending on your matrix and signal size)
Some properties:
- Generally faster than an exhaustive search (iterating whole matrix)
- The bigger the search space gets (matrix) the faster it is comparatively with an exhaustive search.
- You are still fine even when the signal is not symmetric and centred (first non-zero aligned with the maximum value), can handle more complex signals!
- The same method can be used for 1 dimensional signals or scale to n-dimensions (which is kind-of cool if you think about it, and quite useful too :] )
Limitations:
- It can oscillate forever without converge to a value, specially on a discrete function, you need to handle this case in your code.
- You are not guaranteed to find the global maximum (can get caught in a local one, there are methods to overcome this)
- You need to either interpolate your function (not all, just a few cells, not a difficult thing to do, I wouldn't use linear interpolation) or make some adaptations to the algorithm (calculating the gradient in a discrete function vs. a continuous one, not difficult)
This might be an overkill for you, it might be appropriate, I don't know, you don't provide more detail but it might be worth it to have a look at it. Note that there's a whole family of algorithms, with many variations and optimizations. Have a look at the Wikipedia article first ;)
First split the entire matrix into 7x7 small matrices as overlaps among the matrices are minimized.
Once split the matrix into small matrices, traverse or randomly pick some points of each small matrix to check whether there exists non-zero values.
If you find any non-zero values from a small matrix, find # from that non-zero value.
You probably won't be able to avoid scanning the entire matrix in the worst case, but you might be able to shave off some run time in the average case by scanning at progressively increasing resolution.
So for example, you'd start out by taking samples at some (arbitrarily chosen) large distance, leaving you with 2 possibilities:
you either have found a point with non-zero value -> then you can use some other technique to "home in" locally on the peak as necessary (like the "gradient ascent" as mentioned in some of the other answers)
your search comes up empty -> that means the scan resolution was too large, the wave "fell through the cracks", as it were. Then your algorithm would reduce the resolution (say, by halving it) and run another scan (if done cleverly, you could even skip those points you already sampled in the previous run), just finer grained
So you'd keep scanning at progressively smaller resolutions until you find what you're looking for - the first few "rough" scans would be faster, but have a smaller chance of being successful, but (depending on some factors, like the size of the full matrix compared to the size of the "wavelets") you will, on average, have a good chance to find the target before you have to reduce the resolution far enough to have to scan the entire matrix element-by-element.
To illustrate:
First scan:
#-------#-------
----------------
----------------
----------------
----------------
----------------
----------------
----------------
#-------#-------
----------------
----------------
----------------
----------------
----------------
----------------
----------------
Second scan:
o---#---o---#---
----------------
----------------
----------------
#---#---#---#---
----------------
----------------
----------------
o---#---o---#---
----------------
----------------
----------------
#---#---#---#---
----------------
----------------
----------------
Third scan:
o-#-o-#-o-#-o-#-
----------------
#-#-#-#-#-#-#-#-
----------------
o-#-o-#-o-#-o-#-
----------------
#-#-#-#-#-#-#-#-
----------------
o-#-o-#-o-#-o-#-
----------------
#-#-#-#-#-#-#-#-
----------------
o-#-o-#-o-#-o-#-
----------------
#-#-#-#-#-#-#-#-
----------------
And so on (with '#' being the newly sampled cells, and 'o' being previously sampled cells, which can be skipped)...