如何使用BFS算法只保留外点？ [英] How to use the BFS algorithm to keep only the outer points?

问题描述

让我们说我有一个500×500的二维网格（从-250到250）。

Let's say I have a 500x500 2D grid (from -250 to 250).

网格的每个单元具有一定的价值，从0到100

Each cell of the grid has a certain value, from 0 to 100.

我一直试图做的是让所有的小区的列表值低于50时开始在点（0，0），但我想不会把所有的点，但只有外点（周长，边界，其值低于50不具有4个相邻的细胞与值低于50的小区）。

What I've been trying to do is keep a list of all the cell with a value lower than 50 starting at the point (0, 0), but I would like not to keep all the points, but only the outer points (perimeter, bounds, a cell with a value lower than 50 that does not have 4 adjacent cells with a value lower than 50).

我实现的算法的方式，我把所有的点的列表。我应该如何修改呢？我想优化code如果可能的话（我可以有更大的网格），所以我想preFER不要再重复。

The way I implemented the algorithm, I keep a list of all the points. How should I modify it? I would like to optimize the code if possible (I can have bigger grids), so I would prefer not to iterate again.

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的数值，而不是外部点。我怎么能修改此code？我应该用另一种算法？

As you can see, I keep in my list all the points with a value below 50, instead of the outer points. How can I modify this code? Should I use another algorithm?

推荐答案

让我们考虑的单元阵列为灰度图像（其中，单元格的值是像素强度）。你所试图做的（查找边缘）是图形一个常见的​​问题，并且有一个著名的算法（步操广场）找到这样的边界为列表（以列表的附加属性被命令，这样，当你遍历列表，你绕来绕去，它包含了有趣的领域多边形的顶点。

Let us consider the cell array as a grey-scale image (where cell values are pixel intensities). What you are attempting to do ("find borders") is a common problem in graphics, and there is a well-known algorithm (Marching Squares) to find such borders as lists (with the additional property of the lists being ordered, so that when you traverse the list, you are going around the vertexes of a polygon that contains the interesting area.

步操正方形是O（细胞）（它只需要看每个小区附近一旦在最坏的情况下），并且可以并行为更高的性能。有许多变化，基于什么考虑相关的过渡，无论你想只找到的一个的边界或所有的边界。

Marching squares is O(cells) (it only needs to look at each cell-neighbourhood once in the worst case), and can be parallelized for even greater performance. There are many variations, based on what is considered a relevant transition and whether you want to find only one boundary or all boundaries.

有多种实现在那里。其中一个是我看过最干净的是<一个href="https://github.com/e-ucm/ead/blob/master/engine/core/src/main/java/es/eucm/ead/engine/utils/MarchingSquares.java"相对=nofollow>此处（LGPL;返回所有的边界;配置的阈值） - 从Java转换到C ++应该是比较简单的。

There are many implementations out there. One of the cleanest that I have read is here (LGPL; returns all boundaries; configurable threshold) - translating it from Java to C++ should be relatively straightforward.

这篇关于如何使用BFS算法只保留外点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！