在2D网格中查找所有循环/封闭形状

Question

在2D网格中查找所有循环/封闭形状

13

我有一个“无限”的二维网格，我想检测封闭/完整的“结构”-任何形状的区域都被四面环绕。但是，我需要识别每个单独的封闭回路-包括更大的形状（如果有的话）。

在研究中，我发现了循环检测算法，但我没有看到将大电路与小电路分开的干净/有效的方法。

例如，给出以下两个“完整”的结构：

0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1

第一个例子是一个由8个“墙壁”包围的单个单元格。使用循环检测可以轻松检测到这一点。

第二个例子由两个示例一的副本组成，但它们共享一堵墙。我关心三个独立电路 - 左房间，右房间和整体结构。

多次运行循环算法可能有效，但我必须确保没有重新跟踪已经找到的形状。

我也看过洪水填充算法，但似乎假设您已经知道了有界区域内部的某个点。对于无限2D网格，如果它不在有效结构中，我需要一个大小限制来强制它放弃。

我只会在添加边界值时执行此“检查”。使用上面的示例，如果我将任何0更改为1，则可能创建一个新的循环，并运行该逻辑。我不关心识别不同的结构，并且始终会有一个起点坐标。

我一直在研究这里发布的解决方案，但它们都基于已经知道哪些节点连接到其他节点的假设。我已经玩过了识别每条“线”的逻辑，我可以从那里继续，但它感觉是冗余的。

- helion3

它怎么是无限的？我的意思是，如果有一个由1组成的正方形在右边一百万个位置处，你怎么知道呢？你只是存储了1的位置吗？ - Kevin

我所说的“无限”，是指这些“结构”可以是任何形状、合理大小，并且可以出现在“无限”的二维网格上——在这种情况下，它是一个程序生成的二维瓦片地图。 - helion3

请查看这篇优秀的论文：“使用轮廓跟踪技术的线性时间组件标记算法”作者为Fu Chang，Chun-Jen Chen和Chi-Jen Lu。我猜你可以通过绕着起始像素进行初始扫描来将该方法适应于无限网格的情况。 - user1196549

也许泛洪填充是你想要的 - meowgoesthedog

1

这个问题由于缺少太多细节而无法回答。请看我两天前的评论。你甚至没有定义你所说的结构、电路等是什么。如果你计算每个唯一电路，数量将会激增。 - maraca

显示剩余4条评论

6个回答

4

这是一个轮廓发现问题。

其中一种可能的算法由Satoshi Suzuki和Keiichi Abe在1985年的论文《Topological Structural Analysis of Digitized Binary Images by Border Following》中描述。但它并不简单。但是你可以使用OpenCV，它的cv2.findContours()函数实现了这个算法。

如果选择使用OpenCV，解决方案很简单。您提取轮廓及其层次结构。至少有一个子元素（孔）的轮廓及其子轮廓是您要查找的对象。下面是使用经过管理的OpenCV包装器OpenCvSharp的示例：

byte[,] a = new byte[7, 6]
{
    { 0, 1, 1, 1, 0, 0 },
    { 0, 1, 0, 1, 0, 0 },
    { 0, 1, 1, 1, 0, 0 },
    { 0, 0, 0, 0, 0, 0 },
    { 0, 1, 1, 1, 1, 1 },
    { 0, 1, 0, 1, 0, 1 },
    { 0, 1, 1, 1, 1, 1 }
};
// Clone the matrix if you want to keep original array unmodified.
using (var mat = new MatOfByte(a.GetLength(0), a.GetLength(1), a))
{
    // Turn 1 pixel values into 255.
    Cv2.Threshold(mat, mat, thresh: 0, maxval: 255, type: ThresholdTypes.Binary);
    // Note that in OpenCV Point.X is a matrix column index and Point.Y is a row index.
    Point[][] contours;
    HierarchyIndex[] hierarchy;
    Cv2.FindContours(mat, out contours, out hierarchy, RetrievalModes.CComp, ContourApproximationModes.ApproxNone);
    for (var i = 0; i < contours.Length; ++i)
    {
        var hasHole = hierarchy[i].Child > -1;
        if (hasHole)
        {
            var externalContour = contours[i];
            // Process external contour.
            var holeIndex = hierarchy[i].Child;
            do
            {
                var hole = contours[holeIndex];
                // Process hole.
                holeIndex = hierarchy[holeIndex].Next;
            }
            while (holeIndex > -1);
        }
    }
}

- Leonid Vasilev

2

从图论的角度来看，您可以将地图中的每个0解释为一个节点，相邻的0之间用一条边连接起来。在我看来，您想要做的是计算这个图的连通分量（也许还要通过1值来确定它们的连通性，以找到相同结构的“相邻房间”）。

如果您只想计算一次这些信息，那么使用并查集数据结构的直接方法就足够了，其中每条边应用一次union操作。

如果您想要动态编辑地图，则基于图模型的最佳方法可能是一些支持split或de-union操作的动态数据结构，请参见here或here。

- Tobias Ribizel

2

您可以尝试列出一系列的点，并验证哪些是相互关联的。

class PointList : List<Point>
{
    /// <summary>
    /// Adds the point to the list and checks for perimeters
    /// </summary>
    /// <param name="point"></param>
    /// <returns>Returns true if it created at least one structure</returns>
    public bool AddAndVerify(Point point)
    {
        this.Add(point);

        bool result = LookForPerimeter(point, point, point);
        Console.WriteLine(result);
        return result;
    }

    private bool LookForPerimeter(Point point, Point last, Point original)
    {
        foreach (Point linked in this.Where(p => 
            (p.X == point.X -1 && p.Y == point.Y)
            || (p.X == point.X + 1 && p.Y == point.Y)
            || (p.X == point.X && p.Y == point.Y - 1)
            || (p.X == point.X && p.Y == point.Y + 1)
        ))
        {
            if (!linked.Equals(last))
            {
                if (linked == original) return true;

                bool subResult = LookForPerimeter(linked, point, original);
                if (subResult) return true;
            }
        }

        return false;
    }
}

这段代码旨在作为起点，可能存在错误，并且未考虑没有0的周长。

使用示例：

class Program
{
    static void Main(string[] args)
    {
        PointList list = new PointList();

        list.AddAndVerify(new Point() { X = 0, Y = 0 }); //returns false
        list.AddAndVerify(new Point() { X = 0, Y = 1 }); //returns false
        list.AddAndVerify(new Point() { X = 0, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 1, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 2 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 1 }); //returns false
        list.AddAndVerify(new Point() { X = 2, Y = 0 }); //returns false
        list.AddAndVerify(new Point() { X = 1, Y = 0 }); //returns True
    }
}

- Eric Beaulieu

1

我曾经遇到过类似的问题，尝试在2D街道地图图形中找到所有圆形（以SVG文件形式给出）。就像您所说的那样，我也无法找到相关算法。

但是我找到了以下解决方案。

假设

网格布局： 网格中的每个“1”处于以下状态之一（或其同构）：

1.   0      2.   0      3.   0      4.   0      5.   0      6.   1
   0 1 0       1 1 0       1 1 0       1 1 1       1 1 1       1 1 1
     0           0           1           0           1           1

只有示例3到6对于连接的墙才有意义，因为在连接的墙中，每个“1”在其邻域中至少有两个“1”。

- 示例3表示一个角落。这个角落最多容纳一个结构。 - 示例4表示一条直线。它可以是零、一个或两个结构的墙。 - 示例5表示T形墙。它可以是零、一个、两个或三个结构的墙。 - 示例6表示十字墙。它可以是零、一个、两个、三个或四个结构的角落。

算法

思路

假设上面所述，该算法通过查找“1”并进行深度优先搜索来标记所有连接的“1”。如果深度优先搜索到达起始位置或已标记的位置，则仅标记遍历的“1”。

实现

我将在接下来的几天内发布一个实现。

- R. Q.

0

重新发布我的解决方案，附带说明和一些代码。

在任何答案发布之前，我花了几天时间尝试找到一个解决方案，并相信我已经找到了一个非常适合我的需求的解决方案。

由于我总是有一个起点，所以我从该点走边并每次路径“分支”时分叉访问点列表 - 这使我能够找到多个循环。

给定一个二维网格，其中单元格中要么为1，要么为0：

0 1 1 1 1 1
0 1 0 1 0 1
0 1 1 1 1 1

从我已知为1的单元格开始，我开始搜索：

对于当前有效点：
1. 将其添加到“已访问”列表中
2. 查找任何有效邻居（除了我访问过的最后一个点，以避免无限循环）
对于每个有效邻居：
1. 克隆我们到达这个新点的“路径”点列表
2. 使用邻居点调用步骤1

克隆使得每个“分支”成为一个独特的循环而不混合点。

我还没有运行任何性能分析，但是在我尝试的例子中它表现得非常好。

有可能给我两个循环的副本。例如，如果我从西北角开始，在东边和南边的单元格都有有效的路径可供跟随。它们都被视为新路径并被跟随，但它们只是同一个循环的镜像。目前，我只是修剪这些循环 - 它们具有完全相同的点，只要忽略它们的顺序即可。

还涉及一些过滤 - 比如对于问题＃1，如果终点匹配了一个不是我们起点的访问点，则修剪点。我认为这几乎是不可避免的，也不是什么大问题，但如果有一种干净的方法可以避免这种情况，那就更好了。不过在找到新循环的“开始”之前，我无法知道它是什么，所以你知道，线性时间流再次袭来。

public class CycleDetection {
    // Cache found cycles
    List<Cycle> cycles = new List<Cycle>();

    // Provide public readonly access to our cycle list
    public ReadOnlyCollection<Cycle> Cycles {
        get { return new ReadOnlyCollection<Cycle>(cycles); }
    }

    // Steps/slopes that determine how we iterate grid points
    public Point[] Steps = new Point[] {
        new Point(1, 0),
        new Point(0, 1),
        new Point(-1, 0),
        new Point(0, -1)
    };

    // Cache our starting position
    Point origin;

    // Cache the validation function
    Func<Point, bool> validator;

    public CycleDetection(Point origin, Func<Point, bool> validator) {
        this.origin = origin;
        this.validator = validator;

        this.Scan();
    }

    // Activate a new scan.
    public void Scan() {
        cycles.Clear();

        if (validator(origin)) {
            Scan(new List<Point>(), origin);
        }
    }

    // Add a cycle to our final list.
    // This ensures the cycle doesn't already exist (compares points, ignoring order).
    void AddCycle(Cycle cycle) {
        // Cycles have reached some existing point in the trail, but not necessarily
        // the exact starting point. To filter out "strands" we find the index of
        // the actual starting point and skip points that came before it
        var index = cycle.Points.IndexOf(cycle.Points[cycle.Points.Count - 1]);

        // Make a new object with only the points forming the exact cycle
        // If the end point is the actual starting point, this has no effect.
        cycle = new Cycle(cycle.Points.Skip(index).ToList());

        // Add unless duplicate
        if (!cycles.Contains(cycle)) {
            cycles.Add(cycle);
        }
    }

    // Scan a new point and follow any valid new trails.
    void Scan(List<Point> trail, Point start) {
        // Cycle completed?
        if (trail.Contains(start)) {
            // Add this position as the end point
            trail.Add(start);

            // Add the finished cycle
            AddCycle(new Cycle(trail));

            return;
        }

        trail.Add(start);

        // Look for neighbors
        foreach (var step in Steps) {
            var neighbor = start + step;

            // Make sure the neighbor isn't the last point we were on... that'd be an infinite loop
            if (trail.Count >= 2 && neighbor.Equals(trail[trail.Count - 2])) {
                continue;
            }

            // If neighbor is new and matches
            if (validator(neighbor)) {
                // Continue the trail with the neighbor
                Scan(new List<Point>(trail), neighbor);
            }
        }
    }
}

我已经在这里发布了完整的源代码：https://github.com/OutpostOmni/OmniGraph（还包括一些不相关的图形工具）

- helion3

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Spektre · Accepted Answer

我会这样做：

我会用这种方式：

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 0 1 0 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

fill the background with 2

to determine if you are in background just cast a ray and count consequent zeores. Once you find location where the ray length is bigger then circuit size limit you got your start point.
```
[0]0-0-0-0-0-0
 0 1 1 1 1 1 0
 0 1 0 1 0 1 0
 0 1 1 1 1 1 0
 0 0 0 0 0 0 0

 2 2 2 2 2 2 2
 2 1 1 1 1 1 2
 2 1 0 1 0 1 2
 2 1 1 1 1 1 2
 2 2 2 2 2 2 2
```
Do not use unbound recursive flood fills for this !!! because for "infinite" area you will stack overflow. You can limit the recursion level and if reached instead of recursion add point to some que for further processing latter. This usually speeds thing up a lot and limits the stack usage...

find first 0

 2 2 2 2 2 2 2
 2 1 1 1 1 1 2
 2 1[0]1 0 1 2
 2 1 1 1 1 1 2
 2 2 2 2 2 2 2

flood fill it with 3

 2 2 2 2 2 2 2
 2 1 1 1 1 1 2
 2 1 3 1 0 1 2
 2 1 1 1 1 1 2
 2 2 2 2 2 2 2

select all 1 near 3

this is your circuit. If you remember the bbox while filling #3 then you need to scan only area enlarged by one cell on each side... Selected cells are your circuit.
```
 2 2 2 2 2 2 2
 2 * * * 1 1 2
 2 * 3 * 0 1 2
 2 * * * 1 1 2
 2 2 2 2 2 2 2
```

flood fill 3 with 2

this will avoid of usage already processed circuits

 2 2 2 2 2 2 2
 2 1 1 1 1 1 2
 2 1 2 1 0 1 2
 2 1 1 1 1 1 2
 2 2 2 2 2 2 2

loop #2 while any 0 found

change all 2 back to 0

 0 0 0 0 0 0 0
 0 1 1 1 1 1 0
 0 1 0 1 0 1 0
 0 1 1 1 1 1 0
 0 0 0 0 0 0 0