algorithm - 将一个多边形拆分为另一个多边形

Question

我需要一种算法来分割(凸)多边形(我们称之为基础多边形)。多边形应该被另一个多边形的边分割成几个更小的多边形(我们称这个多边形为分割多边形)。我知道存在用于裁剪 多边形的算法(例如 Sutherland-Hodgman 算法)，但这些算法会丢弃位于分割多边形之外的顶点，而不是用它们创建新的多边形。我不想剪辑多边形，我想把它分成几个小部分。我知道答案似乎很明显，因为我只需要扩展现有算法即可。问题是我想不出一个好的、高效的方法来做这件事。是否存在描述如何以高效方式最好地分割多边形的现有算法？这个问题必须有一个简单的解决方案，我现在还想不出来。

Answer 1

您可以将此问题视为寻找主题多边形与窗口多边形的补充 的交集。所以你可以使用标准 Surtherland-Hodgman为此目的的算法，采取两个预防措施:

1. 交换主题和窗口的角色(实际上你的窗口不是凸的，因为你认为它的补充，只有主题是凸的)，

2. 将窗口多边形嵌入覆盖两个多边形的大边界框，并将该框视为带孔的多边形。

   

示例:主体多边形为矩形，窗口为五边形。形成绿色多边形(带孔的较大矩形)并将其夹在矩形(凸)窗口内。剪裁的结果是蓝色的。

如果格外小心，应该可以不使用大边界框。