c# - 确定多边形何时被新边封闭

Question

我的程序有一个 List<Vector3>每次用户绘制唯一线(1、2、3、...)时创建的唯一点(A、B、C、...)。行存储在 List<int> 中其中每两个整数是每个点的索引以形成一条线。任何两条线都不能有相同的两个点，任何点都不能占据相同的位置，允许有杂散线。

Diagram

Points: {A, B, C, D, E} //Each letter represents a 2d or 3d position
Sides: {0,1,1,2,1,3,3,4,4,2} //(Each int is an index in Points, every pair is a side)

我正在尝试找到一种有效的方法来确定新线(绿色，5)何时闭合具有任意边数的多边形。我有一种方法可以做到这一点:遍历连接到新线(以及所有后续线)每一侧的每条线，直到它们共享一个点 (D)。

Completed Polygon

我唯一的问题是，多边形的边越多，我需要做的检查就越多(多边形上每增加两条边，我就会在所有连接的边上检查一层更深)。

有没有办法减少关闭多边形所需的检查次数？

与Cycles in an Undirected Graph不完全相同.这知道至少有一个循环存在并连接到给定的一侧，并且正在寻找可能连接到该侧的最小循环。其他方面无关紧要，应该避免。

Answer 1

这完全取决于您需要的优化级别。对于简单的图片(有些小于 10 - 100k 行)，您可以每次都运行 BFS。

高级算法:

首先，您需要使用 Graph representation 之一来存储图表。 .然后，每当用户画一条线时，您将取两个点中的任何一个并执行 BFS在这一点上。

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

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