Finding non-empty grid cell in 2-dimensional array

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 i开发者_如何学Pythonncreasing 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

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.

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.

It depends on how many lines / cols you expect to contain non-0 values. If you expect for the grid of 1000x1000 to have < 100 locations filled you should store the information of what row & column is non-0 while generating the values.

If thats not an option use somthing like this:

public void foo() {
    int[][]matrix = new int[1000][1000];
    int x = 0,y = 0;
    if(matrix[x][y] != 0) return;
    int min = 0, max=0;
    boolean cont = true;
    foreverloop:
    while(cont) {
        min--;max++;
        for(int ii = min; ii < max; ii++) {
            // secure that min and max dont exeed matrix here.
            cont = false;
            int[] higherEnd = Arrays.copyOf(matrix[ii], max);
            int[] trunk = Arrays.copyOf(higherEnd, higherEnd.length-min);
            Arrays.sort(trunk);
            if(trunk[trunk.length-1] != 0) {
                // HIT! we search this distance but no further.
                trunk = Arrays.copyOf(higherEnd, higherEnd.length-min);
                int source = trunk.length;
                for(int distance = 0; ;distance++) {
                    if(source-distance>0) {
                        if(trunk[source-distance] != 0) {
                            // SCORE!
                            scoreHit(x+ii,y+source-distance);
                            break foreverloop;
                        }
                    }
                    if(source+distance<trunk.length) {
                        if(trunk[source+distance] != 0) {
                            // SCORE!
                            scoreHit(x+ii,y+source-distance);
                            break foreverloop;
                        }
                    }
                }
            }
        }
    }
}

public void scoreHit(int x, int y) {
    // there could be several in nearly the same distances
}

you could optimize that by filtering out areas that you already searched, but I think that would make a difference only at higher distances from x,y