如何用线段分割一般的闭合多边形

Question

我需要一个好的（稳健的）算法来通过线段将多边形分成两组 (left/right)。我的多边形表示只是一个整数坐标列表（顺时针排序，从不自相交），线段由起点和终点表示。该线始终在多边形之外开始和结束，即与多边形相交偶数次。

这是一个例子：

算法的输出应该是两组（顺时针方向）：

左：HABCH、FGDEF
右：HCDGH、BAB、FEF

我可以通过迭代多边形并检查多边形线段是否穿过线来识别点 A-H，同时注意遵守边界情况。我还可以确定每条多线属于哪一侧。不过，我这辈子都无法决定如何将这些片段串在一起。

在你建议一个通用的裁剪库之前：我正在使用 boost polygon，它非常擅长相互裁剪多边形，但我还没有找到任何库可以让你根据线段裁剪多边形并且它通常不可能将线段变成我可以剪辑的多边形。

编辑：我错过了 FEF 以及多边形可以在线段两侧都有部分的事实。

Answer 1

For each intersection of the polygon border with the line segment:
    Add a new point to the polygon.
    Remember the new points in a new-point set.

Add the original polygon to the polygon set.

For each pair of points in the new-point set:
    For each polygon in the current polygon set:
        If the line segment between the points is completely inside the polygon.
           Replace the polygon in the polygon set with two polygons 
           generated by dividing the original polygon along the line 
           segment between the points.

For each polygon in the polygon set:
    Add it to the Left result set or the Right result set.
    (Note this may not be possible.  
        Consider your example of the segment starting between C and F: 
        You will end up with a polygon (GABCFG) that touches both 
        sides of the dividing segment.  Is that a Left or a Right?

Answer 2

我已经解决过一次类似的问题，我放弃了自作聪明

运行将所有顶点绕成相连的线段，每次相交时用一个新点开始一个新线段切割线.
找到共享一个终点的所有线段并将它们重新连接成一个更长的线段。
连接所有的开放端。

Answer 3

好的，这是一个相当简单的方法来得出答案：

从按顺时针方向移动轮廓的交点集开始：

ABCDEFGH

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

HCFEDGBA

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

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

如何用线段分割一般的闭合多边形

How to split a general closed polygon by a line segment

c++

algorithm

boost

polygon

boost-polygon