请考虑以下问题：
给定平面中的N个点和连接它们的M个线段，找到内部不包含任何其他多边形的所有多边形（凸面或凹面） .
例如：
Build 了5个多边形：
1 - 2 - 5 - 6
2 - 3 - 5
3 - 4 - 5
7 - 8 - 9
10 - 13 - 20 - 12 - 11
如何识别这些多边形以及相应的顶点和边缘？什么是最快的解决方案？
构建图表，其中段结束为顶点，段为边，然后使用DFS查找循环 .
请注意，相同的边可能属于多个周期（多边形），如 2-5 ，并且可能有许多变体来选择周期 . 要排除歧义，您可以构建fundamental set of cycles
2-5
编辑 . 正如韦斯顿在评论中所注意到的，结果多边形可能包含其他多边形 . 所以更多几何方法的草图：
构建图的邻接列表 .按极角对列表中的边缘进行排序 .选择最底部的顶点A.如果它的度数为0，则删除顶点，如果为1，则删除顶点和边缘 .否则从该顶点获得具有最小角度的边E.
走到顶点对B.从B中选择最左边的F.沿着F边缘移动到C.如果死胡同，删除F和顶点C并返回B.
使用左手规则重复移动，直到遇到顶点A或死角顶点 .在步行过程中，从2度顶点移除边缘或将其标记为已使用 .
1 回答
构建图表，其中段结束为顶点，段为边，然后使用DFS查找循环 .
请注意，相同的边可能属于多个周期（多边形），如
2-5，并且可能有许多变体来选择周期 . 要排除歧义，您可以构建fundamental set of cycles编辑 . 正如韦斯顿在评论中所注意到的，结果多边形可能包含其他多边形 . 所以更多几何方法的草图：
构建图的邻接列表 .
按极角对列表中的边缘进行排序 .
选择最底部的顶点A.
如果它的度数为0，则删除顶点，如果为1，则删除顶点和边缘 .
否则从该顶点获得具有最小角度的边E.
走到顶点对B.
从B中选择最左边的F.
沿着F边缘移动到C.
如果死胡同，删除F和顶点C并返回B.
使用左手规则重复移动，直到遇到顶点A或死角顶点 .
在步行过程中，从2度顶点移除边缘或将其标记为已使用 .