有没有用凸多边形覆盖凹多边形(包含洞)的算法？

Question

这可以通过两种方式来实现：

i)通过将给定多边形划分为凸多边形，使得凸多边形之间不存在重叠

ii)通过使用凸多边形覆盖给定的多边形，使得它们的并集给出原始多边形。在这种情况下，凸面之间可能会有重叠

虽然划分覆盖了整个多边形，但可以通过第二种方法减少凸多边形的数量。同样众所周知的是，用最少数量的凸多边形覆盖一个凹多边形(第二种方法)是NP难的。

我特别在寻找基于上面提到的第二种方法的算法，但凸多边形的数量可能不是最小的。

Answer 1

正如MBo和Yves Daoust在对您的问题的评论中所提到的那样。多边形分解为凸多边形可以通过三角剖分(或梯形分解)来完成。这将导致n个顶点简单多边形P具有n-2个(内部)三角形，即在顶点数量上是线性的。

构造凸分解的另一种方法是使用广义motorcycle graph。不过，我认为一定有更简单的方法！主要思想是为P中的每个反射顶点r启动一辆摩托车m。每辆摩托车m在给定的方向上以给定的速度行驶，并在后面留下痕迹。如果另一辆摩托车遇到这样的痕迹，它就会崩溃，即停止，但留下痕迹。泛化是指嵌入在P中，多边形边界用作摩托车也发生碰撞的墙壁。此外，如果两辆摩托车在同一点相遇，我们必须启动另一辆，或者在这种情况下，只需继续一辆并停止另一辆。在所有的摩托车都坠毁后，有一个轨迹图，实际上是P的一个凸面镶嵌。有几篇论文(one here)关于这一点，但实现起来会很困难。这导致了覆盖P内部的O(r)凸多边形。

我认为最简单的方法是三角剖分或梯形分解。这些都经过了很好的研究，并在许多库中作为实现提供。

在评论中也提到:可以产生强制O(n)多边形的输入。试想一个有n/2个反射顶点的星形多边形(内角>π)。