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

Question

我想使用直线将凸多边形切成给定面积比的两部分，以使两个子多边形的较大纵横比最小化。

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

多边形 A 的长宽比定义为：

asp(A) := diam(A)^2 / area(A)

Answer 1

我一直在研究的方法与 Belisarius 非常相似，所以我只会分享一些关于我的想法的注释（我正在使用 Mathematica）。

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

黄色区域标记了可以定位剪切的区域：

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

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

检查给定的是否面积比也可以使用舒适的间隔函数来处理：

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

• 参数 Labda 的值，该参数确定通过第一条边的切割位置，作为 mu 的函数（确定第二条边的位置的参数）

  <代码>\[Lambda] -> (2*aL + 给定面积比*(-2*
  aR + (p1y - p3y)*(p2x - p4x) - (p1x - p3x)*(p2y - p4y)) + (1 +
  给定面积比)*(p1x*p3y - p3y*p4x + p1y*(-p3x + p4x) -
  p1x*p4y + p3x*p4y)*\[Mu])/
  ((1 + 给定面积比)*((-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]范围[[1]] <= \[Mu] <= \[Mu]范围[[2 ]]}, \[Mu]]

其中are1tot和area2tot是由mu和lambda参数化的两半的总面积，其中lambda被上述以 mu 表示的 lambda 方程所取代。现在我们只剩下一个参数

• 这是面积比为 1 的最小化过程的结果。绿色曲线是绿色多边形的长宽比（+ 取决于 mu 的添加面积），红色曲线是红色多边形（+ 取决于 mu 的添加面积）。

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

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

Answer 2

我会先写下一个粗略的答案，如果您有兴趣沿着这些思路进行下去，我可能会扩展它。我有一个程序在 Mathematica 中运行来计算这个（有一些限制），如果我有时间完成它，我也会发布它。

该问题实际上有两个部分：

• 找到产生所需面积比的多边形分区
• 从它们中选择使纵横比最小化的多边形分区

让我们先看第一个问题。您可以这样做：

考虑每一对边，如下图所示

对于每一对，考虑以下三个区域：

因此，您可以使用以下方法分割多边形时获得的最大和最小比率穿过这两条边的线是以下集合的 Min() 和 Max[]：

 { (S1+S2)/S3, S3/(S1+S2), (S2+S3)/S1, S1/(S2+S3) }

如果您所需的比率不在该集合的 Max 和 Min 之间，则丢弃该对。

注意：要计算面积，您可以使用此公式

一旦获得所有候选边对，问题就是找到一个仅包含一个参数的函数，该函数描述符合所需比率的四边形的所有可能分区。

如果你用等式对两边进行参数化，

{x, y} = {A} + t {B- A} 

你将能够得到这样的结果：

你可以根据两个参数（每边一个），使用相同的公式计算绿色面积。我上传到ideone，只是因为太笨拙，无法在这里

发布第一步是将问题减少到只有一个参数。这样做是考虑到您希望完整的多边形具有一定的面积​​比。

从这两个方程中，您可以得到每对边的两个参数之间的关系（双曲线）。所有这些切口都具有所需的面积比。

接下来是计算纵横比，并选择最小值。由于功能非常流畅，您只需编写一个极限查找器即可。

在这里，您可以看到六边形的纵横比结果，将一个顶点作为分割点，如下所示：

每个区域的纵横比图为：

其中 x 轴中的每个单位对应于一个边。

如果您想了解更多详细信息，请告诉我...