algorithm - 如何相交多个多边形？

Question

我正在寻找具有以下输入和输出的算法：

输入：平面中的一组多边形。例如 P1...Pn 和 S。（P1...Pn 可能是凹的，S 是凸的。）

输出：这个平面上多边形集合的面积等于 S 的差和 P1...Pn 的并集。

我找到了相交或合并两个多边形的算法。但是由于这些操作中的每一个都可能产生几个多边形，如果我天真地做的话，我会创建大量的多边形。

那么：如何处理多个多边形的交集？

没关系，如果所有多边形都连接在一起，因为只有该区域是我所追求的。我的想法是使用有向多边形来模拟孔，但后来我又遇到了一个问题，即我是否有一个“最小表示”，因为 n 可能会爆炸。【你明白我在说什么吗？真是奇怪……）

Answer 1

您可以将所有边缘组合成扫描线算法。它可能不是最优的（？），但至少你会得到你正在寻找的最小表示。

Answer 2

一种解决方案是将每个多边形转换成一堆三角形。一旦你这样做了，就很容易找到一组区域之间的联合/交叉/差异，因为你可以在一个三角形上简单地执行相同的功能（两个三角形的结果可能包括多达 6 个三角形）。

Answer 3

最直接的方法是将凹多边形分解为凸多边形。然后相交两个凸多边形几乎是微不足道的。