convex - 找到最大凸面积

Question

我的问题与Plough 的问题非常相似；但有这个区别：

如何找到可以适合非凸区域的最大凸区域？

例如，考虑这个非凸区域：

任何想法或解决方案将不胜感激，谢谢。

Answer 1

我在数学堆栈交换上写了这个问题的答案，并附上了我使用概念验证实现创建的图像。用于此的方法可能适用于许多实际应用，因此我将在这里更详细地描述它。

取你的形状，并使用多边形近似它。识别内角 > 180° 的连续顶点的运行。对于每次这样的运行，迭代所有可能的切线。连线的切线是连接两个连续顶点的线，其中至少一个位于连线内。这意味着第一行由运行前的最后一个顶点和运行的第一个顶点定义。取由这条线定义的向内半平面，并将其与您的形状相交，然后计算面积并将其与迄今为止找到的最佳解决方案进行比较。

在一种简单的方法中，您只需设置一个递归方案来尝试所有可能的行组合。这意味着时间复杂度为 O( n ^m )，其中n是顶点数，m是运行次数。在更精细的方法中，您可以利用这样一个事实，即可以独立于这些其他线选择不与形状内的任何其他线相交的线。对于在形状内部不相交的线组也是如此。某些行的选择将完全切断不同的运行，因此为该运行所做的选择变得无关紧要。所以这里有很多聪明的算法的潜力，这取决于你可以投入多少精力和你需要什么样的性能。

如果您的输入是多边形，那么接触非凸顶点的线不必与多边形的传入或传出边重合，但可以在这两个限制之间任意旋转。对于这种情况，上述方法可能会产生非最佳解决方案。但既然你在评论中说我们可以假设“非多边形”形状，我认为这意味着“平滑”。在这种情况下，您在每个点都有一个明确定义的切线，并且每个切线都将合理地接近多边形近似的边缘。

与我最初的想法相反，以上内容也适用于有孔的形状，因为凸孔的边界会导致形状本身的非凸运行。因此，该运行将确保您调查所有可能的方法来切掉这个洞。非凸孔类似：相关运行将确保您也将它们切掉，而不会丢失任何凸解决方案。

应用于您的示例图像，该算法产生以下结果：

顶点的非凸运行是红色的，最好的线集是蓝色的，产生的区域是绿色的。这后面的多边形有 269 个顶点。该实现是在 Java 中完成的，几乎不考虑性能，对所有可能的组合进行强力递归搜索，以及一些适用于该输入数据但通常可能失败的假设。