如何通过线段拆分一般闭合多边形

Question

我需要一个好的(稳健的)算法,用于将一个多边形分成两组(左/右)一个线段.我的多边形表示只是一个整数坐标列表(顺序时钟顺序,从不自相交),线段由起点和终点表示.该线始终在多边形外部开始和结束,即与多边形相交偶数次.

这是一个例子:

算法的输出应该是两组(顺时针行进):

• 左:HABCH,FGDEF
• 右:HCDGH,BAB,FEF

我可以通过迭代多边形并检查多边形线是否穿过线来识别点AH,注意尊重边界情况.我还可以确定每条多线所属的哪一侧.但是,对于我的生活,我不能决定如何将这些片段串在一起.

在你建议使用通用剪辑库之前:我正在使用提升多边形,它非常擅长将多边形相互修剪,但是我没有找到任何可以让你在一个线段上剪切多边形的库,一般来说它是不可能的将线段转换为我可以剪辑的多边形.

编辑:我错过了FEF以及多边形可以在线段两侧都有零件的事实.

Answer 1

好的，这里有一个相当简单的方法来说明如何得出答案：

从顺时针移动轮廓排序的交点集开始：

• ABCDEFGH

根据距行首的距离对它们进行排序：

• HCFEDGBA

我们还需要记住每个点是从左到右还是从右到左的交叉点。

• 从任意一点开始。假设 G。顺时针跟随轮廓并将 GH 添加到当前多边形。
• 现在我们需要沿着这条线行驶。方向取决于我们位于线的哪一边。我们在右侧，因此我们需要在排序集中选取 H 右侧的值： C. 将 HC 添加到当前多边形。
• 顺时针跟随轮廓并将 CD 添加到当前多边形。
• 我们在右侧，因此我们需要在排序集中选取 D 右侧的值：G。将 DG 添加到当前多边形。
• 我们现在已经到达起点，所以让我们保存多边形（GHCDG）并从列表中删除使用的点。
• 从另一点开始。