如何通过线段分割一般封闭多边形

Question

我需要一个好的（健壮的）算法，通过线段将多边形分成两组（左/右）。我的多边形表示只是一个整数坐标列表（按顺时针顺序排列，不相交），线段由起点和终点表示。线段始终从多边形外部开始和结束，即与多边形相交次数为偶数。

以下是示例：

输出应该是两组（顺时针旅行）：

左侧：HABCH、FGDEF

右侧：HCDGH、BAB、FEF

我可以通过迭代多边形并检查多边形线段是否穿过线来识别A-H点，注意要考虑边界情况。我也可以确定每个多线属于哪一侧。但是，我无法决定如何将这些线段连接在一起。

在您建议通用剪辑库之前：我正在使用boost polygon，它非常擅长剪辑多边形，但我没有找到任何可以让您剪辑多边形与线段，并且通常不可能将线段转换为可以裁剪的多边形的库。

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

- bgp2000

---

我对这个问题很着迷。我也很好奇这个陈述：“通常情况下无法将线段转换为多边形”。为什么呢？难道一条线段不就是一个宽度为0的矩形吗？也许存在一个最小的非零宽度，可以在所有与理想线段相同的位置进行裁剪？ - Austin Mullins

你可以将线段转换为零宽度的矩形，但这有用吗？我不确定如果你使用异或运算符将多边形与原始图形进行异或运算会发生什么。我将使用boost polygon尝试并告诉你结果。 - bgp2000

这与半平面裁剪有何不同？该直线将平面分为两个部分，你想要多边形在左侧和右侧平面中的那一部分。 - dhke

想象一下，线段将从 C 和 F 之间开始。 - bgp2000

为什么FEF不是右侧集合中的多边形？[为什么左侧的多边形在图片的右侧？] - Dale Wilson

FEF 应该在其中。那是一个疏忽。左右是相对于线的方向的。 - bgp2000

Answer 1

好的，这里是一个相当简单的步骤，可以得出答案:

从按顺时针方向行进的轮廓相交点集开始:

• ABCDEFGH

根据距离起始线的距离对它们进行排序:

• HCFEDGBA

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

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

- bgp2000

Answer 2

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?

- Dale Wilson

---

你关于多边形不是左或右（或两者都是）的说法是完全正确的。因此，将其分成两个集合是不可能的。算法的其余部分听起来大致正确。我需要按照从线段起点开始递增的距离对点A-H进行排序，以便将线段HC、FE、DG和BA放入“对于新点集中每一对点”。然后，我必须依赖于我的polygon::contains(point)函数始终能够识别位于边界上的点。我会尝试这个方法。 - bgp2000

这个方法可能是可行的，但是对于非凸多边形来说，“如果线段在多边形内部”这一步骤相当耗费时间。我添加了一个答案，只需要将每个多边形线段与该线段进行一次比较即可。 - bgp2000

Answer 3

我曾经解决过类似的问题，但放弃了试图变得聪明。

1. 绕着所有的顶点跑一圈，将它们变成相连的线段，在每次与切割线相交时用新的点开始一个新的线段。
2. 找到所有共享端点的线段，并将它们连接成更长的线段。
3. 连接所有开放的端点。

- Andy Newman

---

但是我怎么知道GH段需要连接到CD段才能形成HCDGH呢？ - bgp2000

真的是个好问题 - 不确定为什么我从来没有遇到过。我会沿着切割线并连接交叉点对 - 只要你的多边形不自相交，切割器在通过时必须进入.离开.进入.离开.进入.离开，并且每个都是一条线段。 - Andy Newman

好的，我已经弄清楚并将其作为单独的答案添加了进去。 - bgp2000