查找最大凸面积

Question

我的问题与Plow的问题非常相似，但有所不同：

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

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

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

- Zakhar

---

注意：已在http://math.stackexchange.com/q/455687/35416上发布。 - MvG

区域是如何定义的？它是任意的非凸区域吗？ - Rob Watts

@RobWatts 为了简单起见，首先考虑一个任意的（非多边形）无洞非凸区域。 - Zakhar

Answer 1

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

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

简单的做法是建立一个递归方案来尝试所有可能的线路组合。这意味着时间复杂度为O(n^m)，其中n是顶点数，m是运行次数。更为精细的方法是利用这样一个事实：不与形状内任何其他线相交的线可以从其他线中独立选择。对于在形状内互不相交的线组也是如此。一些线路的选择会完全削减掉另一个运行，使得对于那个运行所做出的选择变得无关紧要。因此，这里有大量的潜力可供聪明的算法利用，具体取决于您可以投入多少工作以及需要什么性能。

如果您的输入是多边形，则触及非凸顶点的直线不必与多边形的进入或出去边重合，而是可以在这两个限制之间任意旋转。对于这种情况，上述方法可能产生非最优解。但由于您在评论中指出我们可以假设是“非多边形”形状，我认为这意味着“平滑”。在这种情况下，每个点都有一个定义良好的切线，并且每个切线将合理接近多边形逼近的一个边缘。

与我最初的想法相反，上述方法对于带有洞的形状也适用，因为凸洞的边界会导致形状本身出现非凸的运行轨迹。因此，该运行轨迹将确保您调查去除洞的所有可能方式。对于非凸洞也是如此：相关的运行轨迹也将确保您切除它们，而不会失去任何凸解。

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

非凸点集用红色标记，最佳线段用蓝色标记，结果区域用绿色标记。该多边形共有269个顶点。实现采用Java语言完成，性能方面考虑较少，采用暴力递归搜索所有可能的组合，并对一些假设进行了处理，这些假设在此输入数据中有效，但在一般情况下可能会失败。

- MvG

---

如何将过程扩展到一般情况？（如果我更改代码以使其适用于其他地区，哪些部分应更改？- 我非常新于Java编程！从中我写了一封信并发送给您） - Zakhar

@ZiaPandorra：我选择了Java，因为它可以直接进行区域相交。我将列出一些我所知道的隐含假设。多边形的起始点将位于凸面内，在与“inflectionPoints”相关的几个地方都假定了这一点。对“pts”的循环解释假定没有空洞。用1200个任意长度来近似表示半平面的正方形可能需要调整。如果整体方向被反转，“findInflections”需要进行一些符号变换。这个列表可能不完整。为了提高性能，请放弃Java并重新开始使用C ++。 - MvG

哦！对你来说，删掉Java代码很容易，但对我来说不是！坐标怎么样？你一个一个地插入它们吗？！ - Zakhar

@Zia：这段代码太丑了，无法直接复制使用。请将其视为解释如何操作的手段，尝试理解并在你熟悉的编程语言中按照说明进行操作。至于坐标：我将你的图像导入inkscape中，将其追踪成代表黑色轮廓的填充区域，取其中的内部边界，获取其SVG描述，使用Emacs宏进行转换，最后手动微调一些细节，例如应用来自层的全局y偏移量。如果你了解SVG，你可能会认识到路径数据中c和C之间的区别。 - MvG