hel*_*on3 10 c# algorithm grid 2d
我有一个"无限"的2D网格,我想要检测封闭/完整的"结构" - 任何形状的区域,四周都是封闭的.但是,我需要确定每个闭路 - 包括更大的形状,如果有的话.
在研究这个时,我发现了循环检测算法,但我没有看到一个干净/有效的方法将较大的电路与较小的电路分开.
例如,给出以下两个"完整"结构:
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,可能已经创建了一个新的循环,我将运行逻辑.我不关心识别单独的结构,并且总是有一个原点坐标.
我一直在研究这里发布的解决方案,但它们都基于已经知道哪些节点连接到其他节点.我已经玩弄了识别每条"线"的逻辑,我可以继续从那里开始,但感觉多余.
我会这样做：
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
要确定您是否在背景中，只需投射光线并计算随后的零点。一旦你找到光线长度大于电路尺寸限制的位置，你就得到了起点。
[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
不要为此使用未绑定的递归洪水填充！！！因为对于“无限”区域，您将堆栈溢出。您可以限制递归级别，如果达到而不是递归添加点到某个队列以供以后进一步处理。这通常会大大加快速度并限制堆栈使用...
先找 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
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
选择所有1附近3
这是你的电路。如果您在填充#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
洪水填充3用2
这将避免使用已经处理过的电路
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
循环＃2，而任何0找到
全部改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