如何在一组给定的点和边上找到多边形？ [英] 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 ，并且可能会有多种选择周期的变体。为排除歧义，您可以构建基本周期套餐
<编辑>。正如Weston在评论中注意到的，结果多边形可能包含其他多边形。因此，更多几何方法的草图：
生成图形邻接的列表。
以极坐标对列表中的边缘进行排序。
选择最底部的顶点A.
如果度数为0，则删除顶点，如果为1，则移除顶点和边。
否则从此角度获得角E最小的边E顶点。
步行来搭配顶点B.
从B选择最左边的F。
沿F边移动到C.
如果死胡同，删除F和顶点C并返回B.使用左手规则重复移动，直到遇到顶点A或
在步行过程中，删除从2度顶点出来的边或将其标记为已使用。
Consider the following problem:
Given N points in plane and M line segments connecting them, find all polygons (convex or concave) that do not contain any other polygons inside.
For instance:
There are 5 polygons founded:
1 - 2 - 5 - 6
2 - 3 - 5
3 - 4 - 5
7 - 8 - 9
10 - 13 - 20 - 12 - 11
How can I identify these polygons and there corresponding vertices and edges? And what is the fastest solution for this?
Build graph with segment ends as vertices and segments as edges, then find cycles using DFS.
Note that the same edges might belong to multiple cycles (polygons) like your 2-5 and there might be many variants to select cycles. To exclude ambiguity, you can build fundamental set of cycles
Edit. As weston noticed in comments, resulted polygons might contains others. So sketch of more geometric approach:
Build lists of adjacency for graph.
Sort edges in ever list by polar angle.
Choose the most bottom vertex A.
If it's degree is 0, remove vertex, if 1, remove vertex and edge.
Otherwise get edge E with the smallest angle from this vertex.
Walk to pair vertex B.
Choose the most left edge F from B.
Move along to F edge into C.
If dead end, remove F and vertex C and return to B.
Repeat moving using left-hand rule until meet vertex A or dead end vertex.
In the walk process remove edges outgoing from vertices of degree 2 or mark them as used.
这篇关于如何在一组给定的点和边上找到多边形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
