Search for a non-empty mesh cell in a two-dimensional array

Question

I have a 2-dimensional integer array (say 1000 per 1000), let me call it a matrix. Each cell in this matrix has X- and Y-coordinates (each of which is from 0 to 999 in this example). Initially, all grid cells have a value of 0. During program execution, some of the matrix cells are set to a different value <> 0.

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

I thought about going around the original X / Y position with an increase in the offset in each cycle of the cycle, but I'm not sure if this is really the fastest algorithm ...

Any ideas? I would prefer Java code, but any pseudo code is good too :)

Thanks in advance for your help! Regards, Matthias

Answer 1

If the array is relatively sparse and the number of tests is large relative to the number of inserts, the naive approach can take a lot of time.

An alternative is to create a spatial separation tree, such as a quadtree or kd tree. The search for the nearest neighbor is O (ln N) due to the insertion time O (ln N).

Answer 2

- , , [X, Y].

• 3x3 [X, Y]
• , 5x5, 7x7 .., -. .

, ifs:-) , , .

Answer 3

, / -0 . , 1000x1000 < 100 , 0. .

, - :

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
}

, , , , x, y