确定多边形何时被新边闭合

Question

我的程序有一个List<Vector3>独特的点（A、B、C、...），每次用户绘制一条独特的线（1、2、3...）时都会创建这些点。线存储在 a 中List<int>，其中每两个整数是每个点的索引，以形成一条线。任何两条线都不能有相同的两个点，任何点都不能占据相同的位置，允许有杂散线。Points: {A, B, C, D, E} //Each letter represents a 2d or 3d positionSides: {0,1,1,2,1,3,3,4,4,2} //(Each int is an index in Points, every pair is a side)我试图找到一种有效的方法来确定新线（绿色，5）何时关闭具有任意数量边的多边形。我有一种方法可以做到这一点：遍历连接到新线（以及所有后续线）每一侧的每条线，直到它们共享一个点（D）。我唯一的问题是多边形的边越多，我需要做更多的检查（多边形上每增加两个边都会使我在所有连接的边上检查一层更深）。有没有办法减少关闭多边形所需的检查次数？与无向图中的 Cycles不完全相同。这知道至少存在一个循环并连接到给定的一侧，并且只寻找连接到该侧的最小循环。其他方面无关紧要，应该避免它们。

Answer 1

这一切都取决于您需要的优化级别。对于简单的图片（例如< 10 - 100k 行），您每次都可以运行 BFS。

高级算法：

首先，您需要使用Graph 表示之一来存储图形。然后，每当用户画一条线时，您就取两个点中的任何一个并在该点上进行BFS。

如果您可以使用 BFS 到达同一点并且路径长度 > 2，那么您就有了一个多边形。

问题是，由于图形是双向的，因此您在遍历它时需要小心。不要重新访问您已经访问过的节点。