Finding non-empty grid cell in 2-dimensional array

Question

I have a 2-dimensional integer array (say 1000 by 1000), let's call it matrix. Each cell in this matrix has a X- and Y-coordinate (each from 0 to 999 in this example). Initially all grid cells have a value of 0. During program runtime, some of the matrix cells are set to another value <> 0.

Now I need a fast function (algorithm) that takes some X and Y values and returns the value of the matrix at that coordinates. However, if the matrix at the specified X/Y location is 0, then the algorithm should determine a non-zero value within the matrix that is as close to the original X/Y location as possible.

I have thought about looping around the original X/Y position with increasing offset at each loop cycle, but I am not sure whether this is really the fastest algorithm...

Any ideas? I would prefer Java code, but any pseudo-code is also fine :)

Thanks in advance for your help! Kind regards, Matthias

Answer 1

If the array is relatively sparse and the number of tests is high relative to the number of inserts, the naive approach could take a long time.

The alternative is to build a spatial-partition tree such as a quadtree or k-d tree. Nearest-neighbor search is O(ln N) at the cost of O(ln N) insert times.

Answer 2

If you don't have any assumptions on how the matrix looks like, you must use brute force method to look at all values near the [X, Y] position.

1. just set 3x3 square with the [X, Y] position in the centre and test all values on the square perimeter
2. if you don't find the non-zero value, just continue with square 5x5, 7x7, etc., until you find something. You must handle the border of the big matrix.

It is just a work with for cycles, indices and proper ifs :-) There is no faster algorithm, because you don't have any information, guideline.