geometry - 如何用一条线切割一个简单的多边形

Question

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

总是导致 2 个子多边形的基本凸情况很容易，但是我将如何处理复杂的凹形状？以“E”形多边形为例。一个垂直切片可以产生 4 个多边形。我如何确定哪些顶点构成了这些子多边形中的每一个？

定义多边形:我在这里有两个选择。我的多边形可以是一个有序的顶点列表，也可以是一个三角形数组。我更喜欢使用三角形数组的解决方案。遍历每个三角形并在它们相交时将其切片应该很容易。但是我不知道如何将这些三角形分组到产生的子多边形中。

伪代码甚至一般建议都很好； C# 实现是理想的。

Answer 1

我的库中有这个算法 PolyK .这是the demo .如果您了解 Javascript，我相信将其重写为您的编程语言会很容易。