2D Nearest Neighbor Search

Question

Starting with a green square, I want an efficient algorithm to find the closest 3 x 3 window without red squares, only blue squares. The algorithm does not have to find exactly the nearest 3 x 3 window, but it has to find a 3 x 3 completely blue window next to the green square (assuming it exists). I thought about implementing this as a recursive width search, but this solution would require re-checking the same square many times. Conducting this to find out if anyone knows a more effective solution. The cost of checking this square is constant and cheap, but I want to minimize the execution time of the algorithm as much as possible (practical application of this will require searching for a 3x3 “clear” / all-blue window in a much larger 2D search region).

, . , , , , ( , , , , ). , , , .

public class Search2D {
    private TreeSet<Point> centerpointscheckedsofar;

    private Point Search(Point centerpoint) {
        if(centerpointscheckedsofar.contains(centerpoint)) {
            return null;
        }
        if(isWithinBounds(centerpoint)) {
            if(checkCenterPoint(centerpoint)) {
                centerpointscheckedsofar.add(centerpoint);
                return null;
            }
            Point result = Search(getPoint(-1, -1, centerpoint));
            if(result != null) return result;
            result = Search(getPoint(-1, 0, centerpoint));
            if(result != null) return result;
            result = Search(getPoint(-1, 1, centerpoint));
            if(result != null) return result;
            result = Search(getPoint(0, -1, centerpoint));
            if(result != null) return result;
            result = Search(getPoint(0, 1, centerpoint));
            if(result != null) return result;
            result = Search(getPoint(1, -1, centerpoint));
            if(result != null) return result;
            result = Search(getPoint(1, 0, centerpoint));
            if(result != null) return result;
            result = Search(getPoint(1, 1, centerpoint));
            if(result != null) return result;
        }
        return null;
    }

    private Point getPoint(int x, int y, Point centerpoint) {
        return new Point(centerpoint.x + x, centerpoint.y + y);
    }

    private boolean checkCenterPoint(Point centerpoint) {
        //check here to see if point is valid
        return false;
    }

    private boolean isWithinBounds(Point startPoint) {
        //check here to see if point and all neighboring points of 3 x 3 window falls within bounds
        return false;
    }
}

UPDATE: , .

, ( , ). 5 5, , , , . , x 0, y 0.

import java.awt.Point;

public class Search2D_v2 {
    private boolean[][] bitgrid;

    public Search2D_v2() {
        bitgrid = new boolean[20][20];
    }

    public Point search(int centerx, int centery, int maxx, int maxy, int maxsearchsteps) { 
        //check starting point first, if it works, we're done
        if(checkPoint(centerx, centery)) {
            return new Point(centerx, centery);
        }

        int westbound = centerx-1;
        boolean keepgoingwest = true;
        int eastbound = centerx+1;
        boolean keepgoingeast = true;
        int southbound = centery-1;
        boolean keepgoingsouth = true;
        int northbound = centery+1;
        boolean keepgoingnorth = true;

        //stay within bounds, may move initial search square by 1 east and 1 west
        if(westbound <= 0) {
            eastbound = 3;
            westbound = 1;
        }
        if(eastbound >= maxx) {
            eastbound = maxx - 1;
            westbound = maxx - 3;
        }
        if(southbound == 0) {
            northbound = 3;
            southbound = 1;
        }
        if(northbound == maxy) {
            northbound = maxy - 1;
            southbound = maxy - 3;
        }

        //always search boundary, we've already searched inside the boundary on previous iterations, expand boundary by 1 step / square for each iteration
        for(int i = 0; i < maxsearchsteps && (keepgoingwest || keepgoingeast || keepgoingsouth || keepgoingnorth); i++) {
            //search top row
            if(keepgoingnorth) { //if we have already hit the north bound, stop searching the top row
                for(int x = westbound; x <= eastbound; x++) {
                    if(checkPoint(x, northbound)) {
                        return new Point(x, northbound);
                    }
                }
            }

            //search bottom row
            if(keepgoingsouth) {
                for(int x = westbound; x <= eastbound; x++) {
                    if(checkPoint(x, southbound)) {
                        return new Point(x, southbound);
                    }
                }
            }

            //search westbound
            if(keepgoingwest) {
                for(int y = southbound; y <= northbound; y++) {
                    if(checkPoint(westbound, northbound)) {
                        return new Point(westbound, y);
                    }
                }
            }

            //search eastbound
            if(keepgoingeast) {
                for(int y = southbound; y <= northbound; y++) {
                    if(checkPoint(eastbound, northbound)) {
                        return new Point(eastbound, y);
                    }
                }
            }

            //expand search area by one square on each side
            if(westbound - 2 >= 0) {
                westbound--;
            }
            else {
                keepgoingwest = false;
            }

            if(eastbound + 2 <= maxx) {
                eastbound++;
            }
            else {
                keepgoingeast = false;
            }

            if(southbound - 2 >= 0) {
                southbound--;
            }
            else {
                keepgoingsouth = false;
            }

            if(northbound + 2 <= maxy) {
                northbound++;
            }
            else {
                keepgoingnorth = false;
            }
        }
        return null; //failed to find a point
    }

    private boolean checkPoint(int centerx, int centery) {
        return !bitgrid[centerx][centery] && //center
                    !bitgrid[centerx-1][centery-1] && //left lower
                    !bitgrid[centerx-1][centery] && //left middle
                    !bitgrid[centerx-1][centery+1] && //left upper
                    !bitgrid[centerx][centery-1] && //middle lower
                    !bitgrid[centerx][centery+1] && //middle upper
                    !bitgrid[centerx+1][centery-1] && //right lower
                    !bitgrid[centerx+1][centery] && //right middle
                    !bitgrid[centerx+1][centery+1]; //right upper
    }
}

Answer 1

, . , .

, , , , , , . , BFS DFS.

- " ".

Answer 2

. , p, , 3x3 p.

r 3x3 r.

, .

Answer 3

, , .

3x3, . 1, - 0.

9.

, 3x3 , . * * width * height. 9, , , * . , 10 * width * height

, , , 9. , summed -. 2 * * .

, . , 9, . 9, * .

Hensley et al. (2005) , O (log n) . , . Nehab et al. (2011) ( ): , , , .

Answer 4

I think the easiest way is to use a slightly modified width search.

If we talk about the distance of Manhattan, then each square will have a maximum of 4 neighbors. At each step, we check if the number of neighbors is 3 (the fourth neighbor is the square from which we came). If so, we check the diagonals. Else - continue your search.

public class Field3x3 {

    private static class Point {
        int x, y, distance;
        Point previous;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
            this.distance = 0;
            this.previous = this;
        }
        public Point(int x, int y, Point previous) {
            this.x = x;
            this.y = y;
            this.previous = previous;
            this.distance = previous.distance + 1;
        }
        @Override
        public String toString() {
            return "{x: " + x +", y: " + y + ", distance:" + distance +'}';
        }
    }

    private static Point traverse(int[][] field, int x, int y) {
        int i = 0;
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));
        while (!q.isEmpty()) {
            Point p = q.remove();
            System.out.print(i++ + ". current: " + p);
            if (field[p.y][p.x] == 1) {
                field[p.y][p.x] = 2;
                List<Point> neighbors = getNeighbors(p, field);
                System.out.println(", neighbors: " + neighbors);
                if (neighbors.size() == 3 && checkDiagonals(p, field)) return p;
                for (Point neighbor : neighbors) {
                    if (field[neighbor.y][neighbor.x] == 1) {
                        q.add(neighbor);
                    }
                }
            } else System.out.println(", already visited");
        }
        return null;
    }

    private static boolean checkDiagonals(Point p, int[][] field) {
        return field[p.y - 1][p.x - 1] > 0 && field[p.y + 1][p.x - 1] > 0
                && field[p.y - 1][p.x + 1] > 0 && field[p.y + 1][p.x + 1] > 0;
    }

    private static List<Point> getNeighbors(Point p, int[][] field) {
        List<Point> neighbors = new ArrayList<>();
        if (p.y > 0 && field[p.y - 1][p.x] > 0 && p.y <= p.previous.y)
            neighbors.add(new Point(p.x, p.y - 1, p));
        if (p.y < field.length - 1 && field[p.y + 1][p.x] > 0 && p.y >= p.previous.y)
            neighbors.add(new Point(p.x, p.y + 1, p));
        if (p.x > 0 && field[p.y][p.x - 1] > 0 && p.x <= p.previous.x)
            neighbors.add(new Point(p.x - 1, p.y, p));
        if (p.x < field[p.y].length - 1 && field[p.y][p.x + 1] > 0 && p.x >= p.previous.x)
            neighbors.add(new Point(p.x + 1, p.y, p));
        return neighbors;
    }

    public static void main(String[] args){
        int[][] field = {{1,0,0,1,1,0,1,1,1},
                         {1,1,1,1,1,1,1,0,1},
                         {1,1,1,0,1,0,1,1,1},
                         {0,1,1,1,1,1,1,1,0},
                         {1,1,1,0,0,1,1,1,0},
                         {1,0,1,1,1,1,0,1,0},
                         {1,1,1,1,0,1,1,1,0},
                         {1,1,1,0,1,1,1,1,0},
                         {1,1,1,1,0,1,1,1,0}};
        System.out.println("Answer: " + traverse(field, 1, 2));
    }
}