在无向图中寻找独特的循环

Question

我目前正在为Unity开发基于节点的房屋建造者。该系统的工作流程非常简单：用户可以创建简单的立方体节点，并将它们相互连接以创建墙壁。网格处理已经完成，它工作得很好，平稳。

我现在要做的是检测已创建了多少封闭房间以及每个房间中包含了哪些顶点。可能的输入可以看出，在以下图象：

在第一张照片，环将是

（1,5,3,4），（1， （6,9,12,11,10,8），（8,10,14,13）和（10,11,17,16,15,14）。

在第二个他们会

（1,2,5,6,8,7），（2,3,4,14,13,6,5）， （6,13,12,11,10）和（8,6,10,9）。

每个节点最多可连接四个其他节点，每个基数一个，每个链路都存储在两侧。我不需要节点以任何特定的顺序进来。

我想我可以使用通用的循环检测算法并递归搜索子循环，直到找到的循环没有内部连接，但这会非常耗费资源。必须有一些属性可以用来检测没有内部连接的循环，而无需迭代图表多次，但我一直无法找到它。

你有什么建议吗？

Answer 1

对于下面的算法工作，你需要以下条件：

• 边缘的一个独特的方向（你可能已经有了）
• 两个标志用于指定如果边缘一直逢缘在向前和向后方向
• 顶点列表用于与未使用的边缘

然后想法如下。采取任何有未使用边缘的节点，并沿着任何未使用的边缘去邻居（记住方向）。这样做时，立即按照使用的相应方向标出边缘。在这个邻居，你知道你来的方向。按照逆时针顺序查看，直到找到第一个未使用的边（再次注意边的方向）。您也可以按顺时针顺序搜索，这将定义所有输出面的顺序。例如。如果您从左边缘出来，则分别检查底部，右侧，顶部边缘。穿过这条边（标记为已用）并重复，直到到达起始顶点。所有访问过的顶点形成你的房间。

这样做，您应该相应地更新未使用边的顶点列表。

最终，您还将为边框创建一个面。你可以检测到这个通过计算其取向：

v1 x v2 + v2 x v3 + v3 x v4 + ... + vn x v1 

，其中v是顶点的位置和x表示叉积的z分量（其表示脸部朝向）：

(x1, y1) x (x2, y2) = (x1 * y2) - (x2 * y1) 

边界面对于这个方向将会有一个不同于其他所有面孔的符号。实际符号取决于您在边缘遍历期间是使用逆时针还是顺时针顺序。

Answer 2

这只是第一个问题的答案，但它可能会帮助第二个问题。关闭房间的数量实际上有一个闭合公式： 1 - V + E其中V是顶点的数量，E是边的数量。在第二个例子中，有14个顶点，17个边和4个房间。 数学有点复杂，但关键词是Euler characteristic。