2D Nearest Neighbor Search
An answer to this question on Stack Overflow.
Question
Starting from the green square, I want an efficient algorithm to find the nearest 3 x 3 window with no red squares, only blue squares. The algorithm doesn't need to find exactly the closest 3 x 3 window, but it should find a 3 x 3 all-blue window close to the green square (assuming one exists). I thought about implementing this as a recursive breadth-first search, but that solution would involve re-checking the same square many times. Posting this to see if someone knows of a more efficient solution. Cost to check a given 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 involve finding a 3x3 "clear" / all-blue window within a much larger 2D search area).
Here's an example solution, but I don't think it's optimal. It's actually a depth-first search that I will have to restructure to convert to a breadth-first, but I need to think a bit more about how to do that (one way would be to make each point an object that expands to neighboring points, then iterate multiple times across those points to children, visit those children before allowing those children to generate more children). Point is that I think there's a more efficient and common way to do this so I'm trying to avoid reinventing the wheel.
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: Distance measure is not that important, but for simplicity, let's minimize Manhattan distance.
Here's a better algorithm that does not use recursion and will be guaranteed to find the closest solution (or one of the closest solutions if there is a tie). It needs a grid greater than 5 x 5 to work properly, but if you want to search a grid smaller than that, there's probably a more efficient algorithm that can be used. Assumes lowest x-index is 0 and lowest y-index is also 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
What you're trying to find in a more general sense is a kind of morphological filter of your array.
We can define the filter as a 3x3 sliding window which sets the center of the window to the sum of the array elements within the window. Let blue squares be represented by 1 and red squares be represented by 0.
In this situation, you're trying to find the closest element with a sum value of 9.
Note that one way of solving this problem is slide a 3x3 window across your array so that it covers all possible locations. In this case, you would look at 9*width*height elements. You could then find the nearest sum value of 9 using a breadth-first search in, at most, width*height checks. So the naive time of your algorithm is proportional to 10*width*height
You can reduce this by ensuring that your filter only has to look at one value per focal cell, rather than 9. To do so, generate a summed-area table. Now your time is proportional to 2*width*height.
An example of a summed-area table
You can might be able to make this faster. Each time you find a value of 9, compare it against the location of your green cell at that moment. If most cells are not 9s, this reduces your time to some proportional to width*height.
Hensley et al. (2005)'s paper Fast Summed-Area Table Generation and its Applications explains how to use graphics hardware to generate the summed-area table in O(log n) time. So it's possible to really reduce run-times on this. Nehab et al. (2011)'s paper GPU-efficient recursive filtering and summed-area tables might also be useful (source code): their work suggests that for small windows, such as yours, the direct approach may be most efficient.