如何用线切割简单多边形

Question

我有一个简单的多边形（凸或凹，但没有孔），我需要用线段切片成部分。我不确定如何实际确定在切片之后产生多少个多边形，或者如何对顶点进行分组。

基本的凸形案例总是会导致2个子多边形很容易，但是如何处理复杂的凹形？以“E”形多边形为例。垂直切片可以产生4个多边形。我怎样才能确定哪些顶点组成了每个子多边形？

定义多边形：我在这里有两个选项。我的多边形可以是顶点的有序列表，也可以是三角形的数组。我更喜欢使用三角形阵列的解决方案。如果它们相交，应该很容易遍历每个三角形并将它与线条分开。但是，我不知道如何将这些三角形分组为这些结果的子多边形。

伪代码甚至一般的建议是好的;一个C＃实现是理想的。

Answer 1

后来我给了this answer一个有点不同的问题。

这个答案给出了一种建立形状轮廓的方法，给定了该形状的三角形分解。

其基本思想是将所有三角形的边缘视为有向矢量，然后抵消相等但相反的边缘。

就你而言，你会有一堆代表原始形状的三角形。你会用线条分割各个三角形。然后，您将使用上述方法将三角形重新组合为几何形状，但条件是切片边不会取消。

上面提到的答案中有细节和图片。但是总结的步骤将是

1. 执行三角形分割

2. 对于每个得到的三角形，三个向边添加到一组。要确定顺时针顺序，请查看the the answers to this question。

3. 经过边缘设置除去边缘的对是相等但相反的（除非它们是切片边缘）

4. 接在该组的边缘，然后查找其尾部的头部相匹配的边缘第一个边缘。然后重复该边缘，直到到达开始边缘。按照您的要求从边缘设置中移除每个边缘。每当你到达开始边时，你都有一个闭合的循环来表示结果多边形之一。

5. 执行步骤4，直到没有剩下的边。

所有这些都适合您希望从多边形的三角测量开始。但正如您原始问题的评论者之一所指出的那样，您可能需要考虑在Generate new polygons from a cut polygon (2D)处给出的替代方案。

Answer 2

我在我的库PolyK中有这个算法。这里是the demo。如果你理解Javascript，我相信很容易将它重写成你的编程语言。