math - 如何在给定的一组点和边中找到多边形？

Question

考虑以下问题:

给定平面中的 N 个点和连接它们的 M 条线段，找出内部不包含任何其他多边形的所有多边形(凸面或凹面)。

例如:


建立了 5 个多边形:

1 - 2 - 5 - 6

2 - 3 - 5

3 - 4 - 5

7 - 8 - 9

10 - 13 - 20 - 12 - 11

如何识别这些多边形以及相应的顶点和边？什么是最快的解决方案？

Answer 1

以线段结束为顶点，线段为边构建图，然后使用 DFS 找到循环.

请注意，相同的边可能属于多个循环(多边形)，例如您的 2-5并且可能有许多变体来选择周期。要排除歧义，您可以构建 fundamental set of cycles

编辑。正如韦斯顿在评论中注意到的那样，结果多边形可能包含其他多边形。所以更多几何方法的草图:

为图构建邻接列表。
按极角对 ever 列表中的边进行排序。
选择最底部的顶点 A。
如果度数为0，则删除顶点，如果为1，则删除顶点和边。
否则从该顶点获得角度最小的边 E。

步行到配对顶点 B。
从 B 中选择最左边的边 F。
沿 F 边移动到 C。
如果死胡同，移除 F 和顶点 C 并返回到 B。

使用左手规则重复移动，直到遇到顶点 A 或死角顶点。
在步行过程中，从度数为 2 的顶点中移除出边或将它们标记为已使用。