algorithm - 具有自相交的多边形分解

Question

如何将具有自相交的多边形分解为一组简单多边形？

输入多边形 P = {p1, ... pn} 由具有 CCW 方向的 n 个顶点的集合给出。我想对一组 m 个多边形 P1，...，Pm 执行分解。

从交叉路口到下一个路口的路段简单步行不会带来任何效果；有 2 个线段具有相同的起点，由交点表示。

可能，一些词典排序的边缘可能会有所帮助......

Answer 1

计算所有交点，创建新节点并在交点处划分边，为每个节点创建相邻边的列表。

从某个点开始。从当前顶点（相对于最后一条边）使用最逆时针边走。将遍历的边添加到多边形并删除它们（或标记）。当您返回相同的顶点时，关闭多边形。

从仍然有边的第一个顶点重复。