如何在一组给定的点和边中找到多边形？
How to find polygons in a given set of points and edges?
考虑以下问题：
给定平面上的 N 个点和连接它们的 M 条线段，找出内部不包含任何其他多边形的所有多边形（凸或凹）。
例如：
已建立 5 个多边形：
1 - 2 - 5 - 6
2 - 3 - 5
3 - 4 - 5
7 - 8 - 9
10 - 13 - 20 - 12 - 11
如何识别这些多边形及其对应的顶点和边？最快的解决方案是什么？
以线段端点为顶点，线段为边构建图，然后使用 DFS.
求环
请注意，相同的边可能像您的 2-5 一样属于多个循环（多边形），并且 select 循环可能有很多变体。为了排除歧义，您可以构建 fundamental set of cycles
编辑。正如韦斯顿在评论中注意到的那样，生成的多边形可能包含其他多边形。所以更多几何方法的素描：
构建图的邻接列表。
按极角对曾经列表中的边进行排序。
选择最底端的顶点A.
如果度数为0，则删除顶点，如果为1，则删除顶点和边。
否则得到与该顶点的角度最小的边 E。
走到对顶点B。
从B中选择最左边的F。
沿F边移动进入C.
如果是死胡同，移除 F 和顶点 C，然后 return 到 B。
使用左手法则重复移动，直到遇到顶点 A 或死角顶点。
在行走过程中移除从度数为 2 的顶点传出的边或将它们标记为已使用。
考虑以下问题：
给定平面上的 N 个点和连接它们的 M 条线段，找出内部不包含任何其他多边形的所有多边形（凸或凹）。
例如：
已建立 5 个多边形：
1 - 2 - 5 - 6
2 - 3 - 5
3 - 4 - 5
7 - 8 - 9
10 - 13 - 20 - 12 - 11
如何识别这些多边形及其对应的顶点和边？最快的解决方案是什么？
以线段端点为顶点，线段为边构建图，然后使用 DFS.
求环请注意，相同的边可能像您的 2-5 一样属于多个循环（多边形），并且 select 循环可能有很多变体。为了排除歧义，您可以构建 fundamental set of cycles
编辑。正如韦斯顿在评论中注意到的那样，生成的多边形可能包含其他多边形。所以更多几何方法的素描：
构建图的邻接列表。
按极角对曾经列表中的边进行排序。
选择最底端的顶点A.
如果度数为0，则删除顶点，如果为1，则删除顶点和边。
否则得到与该顶点的角度最小的边 E。
走到对顶点B。
从B中选择最左边的F。
沿F边移动进入C.
如果是死胡同，移除 F 和顶点 C，然后 return 到 B。
使用左手法则重复移动，直到遇到顶点 A 或死角顶点。
在行走过程中移除从度数为 2 的顶点传出的边或将它们标记为已使用。