如何计算2D中点序列形成的多边形数量？

Question

正如您可以看到下面的示例图片,我的问题是如何确定由一系列点形成的多边形.

1. 在左图中,点的系列是{A,B,C,D,E,A},因此它只形成1个多边形{A,B,C,D,E}.

2. 在图片的右侧,一系列点是{A,B,C,D,E,F,A}.它创建了2个多边形{A,F,G }和{B,C,D,E,G },其中G是来自线AB和FE的交点.

我不仅对多边形的数量感兴趣,而且我还想知道从它创建的多边形信息(多边形的一系列点).

该算法将在移动设备中实时使用,因此必须足够快才能进行计算.哦,一系列点将由用户的拖动触摸点生成.

假设:

1. 仅由2个共线点组成
2. 它并不总是闭链多边形.例如,从右边的图片中,一系列点是{A,B,C,D,E,F},没有边缘FA.

我一直在考虑解决方案,并且为了查看交叉点,我坚持使用O(N ^ 2)解,N =边数.我可以做的优化是在一些区域内维护线组,所以我只是最小化可以相互计算的总线数.

至于提取形成多边形的解决方案,我仍然卡住了.

Answer 1

首先，找到线段交叉的所有点并创建以该点结束的新线段，以便线段不再交叉（除了它们的末端）。然后将其视为一个图，并删除每个 1 度的顶点，直到所有这些顶点都消失。

将所有段的所有边标记为未访问。对于路段步行S的每个未访问侧，始终选择最靠近您一侧的转弯（角度排序最小值或最大值）。您刚刚找到了一个多边形。这将为您提供一个额外的多边形，即“平面上的所有其余多边形”。(A, B)A, B, C, ..., AS

总体复杂度为 O(n^2)。