c# - 在二维网格中查找所有循环/封闭形状

Question

我有一个“无限”二维网格，我想检测封闭/完整的“结构”——任何形状的区域，这些区域被四面包围。但是，我需要识别每个单独的闭合电路 - 包括较大的形状(如果有的话)。

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

例如给定以下两个“完整”结构:

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 个“墙”包围的单个单元格。循环检测使得检测这一点变得微不足道。

第二个示例包含示例一个的两个副本，但它们共用一堵墙。我关心的是三个独立的电路 - 左室、右室和整体结构。

循环算法的多次通过可能有效，但我必须确保我没有回溯已经找到的形状。

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

是否有我遗漏的解决方案或我的想法遗漏了什么？

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

我一直在研究解决方案posted here但它们都是基于已经知道哪些节点连接到其他节点。我已经玩弄了识别每个单独“行”的逻辑，我可以从那里继续前进，但感觉是多余的。

Answer 1

我会这样做:

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

1. 用2填充背景

   要确定您是否在背景中，只需转换光线并计算随之而来的 zeores。一旦找到射线长度大于电路尺寸限制的位置，您就得到了起点。

   [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
   

   不要为此使用未绑定(bind)的递归泛洪填充!!! 因为对于“无限” 区域您将堆栈溢出。您可以限制递归级别，如果达到而不是递归，则将点添加到某些队列以供以后进一步处理。这通常会大大加快速度并限制堆栈使用...

2. 首先找到 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
   

3. 用 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
   

4. 选择 3 附近的所有 1

   这是你的电路。如果您在填充 #3 时记得 bbox，那么您只需要扫描每侧放大一个单元格的区域...选定的单元格就是您的电路。

    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
   

5. 用 2 填充 3

   这将避免使用已经处理过的电路

    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
   

6. 在找到任何 0 时循环 #2

7. 将所有 2 改回 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