algorithm - 如何最小化两个子多边形的最大纵横比？

Question

我想用一条直线将一个凸多边形按给定的面积比切成两半，这样两个子多边形的较大的纵横比就会最小。

我目前的方法包括选择一个随机起点，计算将多边形分割成目标区域的适当终点，然后计算两个纵横比中较大的一个。然后重复很多次，直到我足够接近最小值!

多边形A的纵横比定义为:

asp(A) := 直径(A)^2/面积(A)

Answer 1

我一直在研究的方法与 Belisarius 非常相似，所以我只会分享一些关于我的想法的笔记(我使用的是 Mathematica)。

• 可以放置切割的边对的数量是顶点数量的二次方 (1/2 n (n-1) ):(线标记边对，通过连接每对的起始顶点)

黄色区域标记了可以找到切口的区域:

因此，在对所有组合进行大量计算之前，最好先清除无效候选。这里显示了一些面积比，剩下的对:

- 正如 belisarius 所说，您可以找到上述每种情况的面积比范围，但简单地取最小值和最大值是不正确的。当您反转面积比中的两个区域时，您得到的两个范围可能会分离。我使用 Mathematica 的 Interval算术来为我处理这个:

检查给定的面积比是否也用舒适的区间函数处理:

containsRatioQ[area1_, area2_, areaBetween_, ratio_] := 
 IntervalMemberQ[areaRatioInterval[area1, area2, areaBetween], ratio]

• 确定通过第一条边的切割位置的参数 labda 的值作为 mu 的函数(确定第二条边位置的参数)

  \[Lambda] -> (2*aL + givenAreaRatio*(-2*
aR + (p1y - p3y)*(p2x - p4x) - (p1x - p3x)*(p2y - p4y)) + (1 +
givenAreaRatio)*(p1x*p3y - p3y*p4x + p1y*(-p3x + p4x) -
p1x*p4y + p3x*p4y)*\[Mu])/
((1 + givenAreaRatio)*((-p2x)*p4y +
p1x*(-p2y + p4y) + (p1x - p2x)*(p3y - p4y)*\[Mu] +
p1y*(p2x + p4x*(-1 + \[Mu]) - p3x*\[Mu]) +
p2y*(p4x + p3x*\[Mu] - p4x*\[Mu])))

或 mu 作为 labda 的函数:

\[Mu] -> (-2*aL + givenAreaRatio*(2*
       aR - (p1y - p3y)*(p2x - p4x) + (p1x - p3x)*(p2y - p4y)) + (1 + 
      givenAreaRatio)*((-p1x)*p2y + p1y*(p2x - p4x) + p2y*p4x + 
      p1x*p4y - p2x*p4y)*\[Lambda])/
   ((1 + givenAreaRatio)*((-p3y)*p4x + p3x*p4y + 
     p1y*(p3x - p4x)*(-1 + \[Lambda]) - 
     p1x*(p3y - p4y)*(-1 + \[Lambda]) + ((-p2y)*p3x + p2x*p3y + 
        p2y*p4x - p2x*p4y)*\[Lambda]))

p1、p2、p3、p4 是包含切割区域的坐标，aL 是“绿色”多边形的区域，aR 是“红色”多边形的区域(参见本文底部的图)。

• 并非一条边上的每个点总能给出另一条边上的解，反之亦然。我检查 lambda 的等式以找到将 lambda 设置为 0 或 1 的 mu 值，反之亦然。

• 作为最后一步，我将两个区域的纵横比函数的最大值最小化。在 Mathematica 语言中:

  NMinimize[{Max[aspectRatio[area1tot], aspectRatio[area2tot]], \[Mu]range[[1]] <= \[Mu] <= \[Mu]range[[2]]}, \[Mu]]

are1tot 和 area2tot 是由 mu 和 lambda 参数化的两半的总面积，其中 lambda 被上述 lambda 的等式替换为 mu。现在我们只剩下一个参数了

• 这是面积比为 1 的最小化程序的结果。绿色曲线是绿色多边形的纵横比(+ 添加的面积取决于 mu)，红色曲线是红色多边形的纵横比( + 根据亩增加面积)。

• 最后，这是您“最满意”的多边形切割:

我有一个 Mathematica 笔记本，我会根据要求发送。只需给我发一封电子邮件。