如何在给定的一组点和边中找到多边形? [英] How to find polygons in a given set of points and edges?

问题描述

考虑以下问题:

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

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.

例如:

建立了5个多边形:

1 - 2 - 5 - 6

1 - 2 - 5 - 6

2 - 3 - 5

3 - 4 - 5

7 - 8 - 9

10 - 13 - 20 - 12 - 11

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?

推荐答案

构建以线段末端为顶点，线段为边的图，然后使用 DFS.

Build graph with segment ends as vertices and segments as edges, then find cycles using DFS.

请注意，相同的边可能属于多个循环(多边形)，例如您的 2-5，并且选择循环可能有很多变体.为了排除歧义，您可以构建基本循环集

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:

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

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.

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

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.

使用左手规则重复移动，直到遇到顶点 A 或死角顶点.
在 walk 过程中，移除从 2 次顶点出边的边或将其标记为已使用.

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屋！