我在数学堆栈交换中写了这个问题的答案,并包含了我使用概念验证实现创建的图像.用于此的方法可能适用于许多实际应用,因此我将在这里更详细地描述它.
塑造你的形状,并使用多边形来近似它.识别内角> 180°的连续顶点的运行.对于每个这样的运行,迭代所有可能的切线.运行的切线是连接两个连续顶点的线,其中至少有一个位于运行中.这意味着第一行由运行之前的最后一个顶点和运行的第一个顶点定义.取这条线定义的向内指向的半平面,并将其与您的形状相交,然后计算该区域并将其与目前为止找到的最佳解决方案进行比较.
在一个简单的方法中,您只需设置一个递归方案来尝试所有可能的行组合.这意味着时间复杂度为O(n m),其中n是顶点数,m是运行次数.在更精细的方法中,您可以利用这样的事实:可以独立于这些其他线选择与形状内的任何其他线不相交的线.对于在形状内彼此不相交的线组也是如此.一些线条的选择将完全消除不同的运行,使得为该运行做出的选择变得无关紧要.因此,这里有很多聪明算法的潜力,具体取决于您可以投入多少精力以及您需要的性能.
如果您的输入是多边形,则接触非凸顶点的线不一定与多边形的输入或输出边缘重合,但可能在这两个限制之间任意旋转.对于这种情况,上述方法可能会产生非最佳解决方案.但是,既然你在评论中说我们可能会假设"非多边形"形状,我认为这意味着"平滑".在这种情况下,每个点都有一个明确定义的切线,并且每个切线都将合理地接近多边形近似的边缘.
与我最初认为的相反,上述情况也适用于带孔的形状,因为凸孔的边界会导致形状本身的非凸形运行.因此,运行将确保您调查所有可能的方法来切除漏洞.非凸孔的SImilar:相关的运行将确保您切出它们,而不会丢失任何凸起的解决方案.
应用于您的示例图像,算法产生以下结果:
非凸的顶点运行为红色,最佳的蓝色线条和绿色的结果区域.这背后的多边形有269个顶点.实现是在Java中完成的,很少考虑性能,对所有可能的组合进行强力递归搜索,以及一些适用于此输入数据的假设,但一般可能会失败.