减法后计算剩余多边形的算法

Question

我有一个大的多边形(Pa).在多边形内部有许多小"洞",如图所示:

以下是这些洞的一些条件:

1. 孔不能彼此重叠
2. 这些孔不能超出外多边形
3. 但是,孔可以接触外部多边形边缘

如何以有效的方式获得剩余的多边形(或多边形列表)？最简单的方法(蛮力方式)是Pa通过减去孔来逐渐计算剩余的多边形.虽然这个想法是可行的,但我怀疑有一个更有效的算法.

编辑:我不是在询问如何执行多边形裁剪(或减法)算法!事实上,这是我将通过蛮力做的事情.我问除了多边形裁剪方法(取主要多边形,然后逐渐将洞夹出),还有其他更有效的方法吗？

Answer 1

以一般方式这是很难做到的。您可以在此处找到解决方案的源代码：

通用多边形裁剪器 (GPC)