2D最近邻搜索

Question

从绿色方块开始，我想要一个有效的算法来找到最近的3x3窗口，没有红色的方块，只有蓝色的方块。该算法不需要找到最接近的3x3窗口，但是它应该在绿色方格附近找到一个3x3全蓝色的窗口(假设有一个窗口)。我考虑将其实现为递归广度优先搜索，但该解决方案将涉及多次重新检查同一个方格。张贴这篇文章，看看是否有人知道一个更有效的解决方案。检查给定方格的成本是恒定的，而且很便宜，但我希望尽可能减少算法的执行时间(实际应用将涉及到在更大的2D搜索区域内找到一个3x3“清晰”/全蓝色窗口)。

​

​

这里有一个例子解决方案，但我不认为它是最优的。这实际上是一种深度优先的搜索，我必须先对其进行重构才能转换为广度优先，但我需要更多地思考如何做到这一点(一种方法是使每个点都扩展到相邻点，然后在这些点上迭代多次，然后访问这些孩子，然后让这些孩子生成更多的孩子)。重点是，我认为有一个更有效和常见的方式来做到这一点，所以我试图避免重新发明车轮。

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;
    }
}

更新：距离测量并不那么重要，但是为了简单起见，让我们最小化曼哈顿距离。

这里有一个更好的算法，它不使用递归，并且可以保证找到最接近的解决方案(如果有领带，也可以找到最近的解决方案之一)。它需要一个大于5x5的网格才能正常工作，但是如果你想搜索一个比这更小的网格，可能有一个更有效的算法可以使用。假设最低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时，请检查p周围的3x3环境。

对于环境中的每个红色像素r，将r的3x3环境设置为选中。

如果环境中没有红色像素，则可以找到解决方案。

Answer 3

从更普遍的意义上来说，你想要找到的是阵列的一种形态过滤器。

我们可以将过滤器定义为3x3滑动窗口，它将窗口的中心设置为窗口内的数组元素之和。让蓝色方块用1表示，红色方块用0表示。

在这种情况下，您试图找到和值为9的最接近的元素。

请注意，解决此问题的一种方法是在数组中滑动一个3x3窗口，以便覆盖所有可能的位置。在本例中，您将查看9*宽度*高度元素。然后，您可以使用宽度优先搜索找到最接近的和值9，最多是宽度*高度检查。因此，算法的初始时间与10*宽*高度成正比。

您可以通过确保您的过滤器只需要查看每个焦点单元格的一个值而不是9个来减少这一点。为此，生成一个总和面积表。现在你的时间与2*宽*高度成正比。

​

​

求和面积表的一个例子

你也许能让这个更快。每次您找到一个值9，比较它与您的绿色细胞的位置在那个时刻。如果大多数单元格不是9s，这会将您的时间减少到与宽度*高度成比例的时间。

Hensley等人(2005年)的论文快速求和-面积表生成及其应用解释了如何使用图形硬件在O(log )时间内生成相加面积表。因此，在这方面真正减少运行次数是可能的。Nehab等人(2011)的论文GPU-高效递归过滤和和面积表可能也很有用(源代码)：他们的工作表明，对于像您这样的小窗口，直接方法可能是最有效的。