如何使用 BFS 算法只保留外部点？

Question

假设我有一个 500x500 的二维网格（从 -250 到 250）。

网格的每个单元格都有一个特定的值，从 0 到 100。

我一直在尝试做的是保留一个列表，其中包含从点 (0, 0) 开始的值低于 50 的所有单元格，但我不想保留所有点，但只保留外部点（周长、边界、值小于 50 的单元格没有 4 个相邻单元格的值小于 50）。

我实现算法的方式，我保留了所有点的列表。我应该如何修改它？如果可能我想优化代码（我可以有更大的网格），所以我不想再次迭代。

pointList pointsWithValueBelow50; // The list of points with a value below 50
map<point, bool> pointDiscovered; // A map of the points we already passed through
point a = {0,0};
point b;
int value;
Queue q;

q.enqueue(a);
pointDiscovered[a] = true;
while(!q.isEmpty())
{
    a = q.dequeue(a)
    value = calculateValue(a); // Random method that verify if the points has a value below 50 in the grid
    if (value < 50)
    {
         pointsWithValueBelow50.add(a);
         b[0] = a[0]+1;
         b[1] = a[1];
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointDiscovered[b] = true;
         }
         b[0] = a[0]-1;
         b[1] = a[1];
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointDiscovered[b] = true;
         }
         b[0] = a[0];
         b[1] = a[1]+1;
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointDiscovered[b] = true;
         }
         b[0] = a[0];
         b[1] = a[1]-1;
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointDiscovered[b] = true;
         }
    }     
}

如您所见，我在列表中保留了值低于 50 的所有点，而不是外部点。我该如何修改这段代码？我应该使用其他算法吗？

Answer 1

抱歉，我忘了添加我的解决方案。不幸的是，我认为它的内存很重，所以任何新的答案都会很高兴被接受！

pointList pointsWithValueBelow50; // The list of points with a value below 50
pointList pointsBorder;
map<point, bool> pointDiscovered; // A map of the points we already passed through
map<point, bool> pointVisible; // The final visible points
map<point, point> pointParent; // A map of the parent point
point a = {0,0};
point b;
int value;
Queue q;

q.enqueue(a);
pointDiscovered[a] = true;
while(!q.isEmpty())
{
    a = q.dequeue(a)
    value = calculateValue(a); // Random method that verify if the points has a value below 50 in the grid
    if (value < 50)
    {
         pointsWithValueBelow50.add(a);
         b[0] = a[0]+1;
         b[1] = a[1];
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointParent[b] = a
             pointDiscovered[b] = true;
         }
         b[0] = a[0]-1;
         b[1] = a[1];
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointParent[b] = a
             pointDiscovered[b] = true;
         }
         b[0] = a[0];
         b[1] = a[1]+1;
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointParent[b] = a
             pointDiscovered[b] = true;
         }
         b[0] = a[0];
         b[1] = a[1]-1;
         if(pointDiscovered[b] == false)
         {
             q.enqueue(b)
             pointParent[b] = a
             pointDiscovered[b] = true;
         }
    }
    else     
    {
        if(pointVisible[pointParent[a]] == false)
        {
            pointVisible[pointParent[a]] = true;
            pointsBorder.add(poinParent[a]);
        }
    }
}

这个想法很简单，如果我在一个值高于 50 的点，我们让父点知道他必须可见，因为他是 "border" 点。

Answer 2

让我们将元胞数组视为灰度图像（其中元胞值是像素强度）。您正在尝试做的事情 ("find borders") 是图形中的一个常见问题，并且有一个众所周知的算法 (Marching Squares) 可以找到列表这样的边界（附加属性列表的顺序，因此当您遍历列表时，您将绕过包含感兴趣区域的多边形的顶点。

行进正方形是 O(cells)（在最坏的情况下它只需要查看每个单元邻域一次），并且可以并行化以获得更高的性能。有很多变体，基于什么被认为是相关的转换以及您是否只想找到 one 边界或 all 边界。

那里有很多实现。我读过的最干净的书之一是 here（LGPL；returns 所有边界；可配置的阈值）——将它从 Java 翻译成 C++ 应该相对简单。

如何使用 BFS 算法只保留外部点？

How to use the BFS algorithm to keep only the outer points?

c++

algorithm

breadth-first-search

path-finding