convex - 求最大凸面积

Question

我的问题与 Plow's Question 非常相似;但有这个区别:

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

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



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

Answer 1

我写了 an answer to this question on the Mathematics Stack Exchange ，并包含了我使用概念验证实现创建的图像。用于此的方法可能适用于许多实际应用程序，因此我将在此处更详细地描述它。

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

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

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

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

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



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