如何用一条直线切割一个简单多边形

Question

我有一个简单的多边形（凸或凹，但没有孔），我需要用一条线段将其切分成若干部分。 我不确定在切割后会得到多少个多边形，也不知道如何分组顶点。

基本凸情况总是会产生2个子多边形，很容易处理，但是如何处理复杂的凹形状呢？以"E"形多边形为例，垂直切片可以产生4个多边形。 我该如何确定哪些顶点组成了每个子多边形？

定义多边形：我有两个选项。我的多边形可以是顶点的有序列表，也可以是三角形数组。 我希望使用三角形数组的解决方案。循环遍历每个三角形并与线段相交进行切割应该很容易。 但是我不知道如何将这些三角形分组成结果的子多边形。

伪代码或一般性建议都可以； C＃实现是理想的。

- Liquid

---

这有帮助吗？https://dev59.com/j3I-5IYBdhLWcg3wm5hG - fredley

Answer 1

我在我的库PolyK中有这个算法。这里是演示。如果你懂Javascript，我相信将其重写为你的编程语言会很容易。

- Ivan Kuckir

---

你好 @Ivan Kuckir，它能轻松地与谷歌地图一起使用吗？ - Umar Niazi

Answer 2

不久前，我回答了一个有点不同的问题，这个答案提供了一种方法，可以在给定形状的三角分解的情况下建立该形状的轮廓。

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

在您的情况下，您将有一堆代表原始形状的三角形。您将使用该上述方法将各个三角形切片。您将通过以下规定重新收集三角形以形成形状，即切片边缘不会取消。

上面引用的答案中有详细的细节和图片。但总结步骤如下：

1. 执行三角形拆分 2. 对于每个生成的三角形，请将三个有向边添加到集合中。要确定顺时针顺序，请查看此问题的答案. 3. 遍历边缘集并删除相等但相反的边对（除非它们是切片边） 4. 选择集合中的一条边，然后找到其尾部与第一条边的头部匹配的边。然后重复该过程，直到到达开始边缘。在到达每个边缘时，从边缘集中删除该边缘。每当您到达起始边缘时，您就有一个代表结果多边形之一的闭合循环。 5. 重复步骤4，直到没有边缘剩余。

所有这些都适用于您希望从多边形的三角剖分开始的情况。但是，正如您原始问题的某个评论者指出的那样，您可能要考虑从切割多边形生成新多边形（2D）提供的替代方案。

- brainjam

---

不错的方法。但我还是有点迷惑如何实现它。你能提供一些具体细节吗？循环逻辑怎么运行？1）取随机三角形A和B。2）将A的每条边与B匹配。3）如果任何A的边+任何B的边=零，则删除该边？但是当我们处理点时，如何删除一条边呢？4）现在我有一个正方形C。我现在要通过将正方形C与随机三角形D的并集来再次循环吗？然后我如何进入第二个子多边形？ - Liquid

@Liquid，你所说的循环逻辑是什么意思？ - brainjam

我必须实际编写一个循环，遍历我的数组中的每个三角形，并执行您建议的所有比较。最终，我需要将单个三角形数组拆分为切片后产生的多少个多边形。 - Liquid

@Liquid，我添加了一些更详细的内容。您需要循环遍历多边形以创建边集，然后通过边集运行以获取结果多边形。 - brainjam

谢谢! 我现在唯一的问题是，如何将三角形数据转换为三个逆时针边。我有两个数组，一个包含每个多边形点的x、y顶点坐标，然后我有一个三角形数组，每个三角形都是一个由顶点数组映射的三部分指定。例如: Tri [0,1,2] 将指定多边形上的第一个、第二个和第三个顶点，每个顶点都是一个带有x和y分量的Vector2。如何将其转换为逆时针边以进行边缘比较？ - Liquid