Liq*_*uid 6 geometry polygon line slice computational-geometry
我有一个简单的多边形(凸面或凹面,但没有孔),我需要切割成具有线段的部分.我不确定如何实际确定切片后多少个多边形结果,或者如何对顶点进行分组.
基本凸面情况总是导致2个子多边形很容易,但我如何处理复杂的凹形？以"E"形多边形为例.垂直切片可以产生4个多边形.如何确定哪些顶点构成每个子多边形？
定义多边形:我有两个选择.我的多边形可以是有序的顶点列表,也可以是三角形数组.我更喜欢使用三角形数组的解决方案.循环遍历每个三角形并且如果它们相交则用线切割它应该非常容易.但后来我不知道如何将这些三角形分组为产生的子多边形.
伪代码甚至一般建议都是好的; C#实现是理想的.
不久前，我对一个有些不同的问题给出了这个答案。
这个答案给出了一种建立形状轮廓的方法，给定该形状的三角形分解。
基本思想是将所有三角形的边视为有向向量，然后抵消相等但方向相反的边。
在你的例子中，你会有一堆代表原始形状的三角形。您可以用线切割各个三角形。然后，您可以使用上面概述的方法将三角形重新聚集成形状，但切片边缘不会取消。
上面提到的答案中有详细信息和图片。但总结一下步骤是
执行三角形分割
对于每个生成的三角形，将三个有向边添加到一个集合中。要确定顺时针顺序，请查看此问题的答案。
遍历边缘集，删除相等但相反的边缘对（除非它们是切片边缘）
在集合中选择一条边，然后找到尾部与第一条边的头部相匹配的边。然后重复该边缘，直到到达起始边缘。当您到达边缘组时，将其从边缘集中移除。每当到达起始边缘时，就会有一个代表结果多边形之一的闭环。
执行步骤 4，直到没有剩余边缘。
所有这些都满足您从多边形三角测量开始的愿望。但正如您最初问题的评论者之一所指出的那样，您可能需要考虑在从切割多边形 (2D) 生成新多边形中给出的替代方案。