algorithm - 在无向图中查找唯一环

Question

我目前正在为 Unity 开发基于节点的房屋 build 器。该系统的工作流程非常简单:用户可以创建节点(简单的立方体)，并将它们相互连接以创建墙。网格处理已经完成，效果很好很流畅。

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

在第一张图片中，循环是

(1,5,3,4), (1,2,6,8,7,5), (6,9,12,11,10,8), (8,10,14,13) and (10,11,17,16,15,14).

第二个是

(1,2,5,6,8,7), (2,3,4,14,13,6,5), (6,13,12,11,10) and (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)

对于此方向，边界面将具有与所有其他面不同的符号。实际符号取决于您在边遍历过程中使用的是逆时针顺序还是顺时针顺序。