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

Question

我想使用直线将凸多边形切割成具有给定面积比的两个,使得两个子多边形的较大纵横比最小化.

我现在的方法是选择一个随机起点,计算将多边形分成目标区域的适当终点,然后计算两个纵横比中较大的一个.然后重复这么多次,直到我足够接近最小!

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

asp(A) := diam(A)^2 / area(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的等式,找到mu值,将lambda设置为0或1,反之亦然.

• 作为最后一步,我最小化两个区域的宽高比函数的最大值.在Mathematica语言中:

  NMinimize[{Max[aspectRatio[area1tot], aspectRatio[area2tot]], \[Mu]range[[1]] <= \[Mu] <= \[Mu]range[[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) }

如果您所需的比率不在此设置的最大值和最小值之间,请丢弃该对.

注意:对于计算区域,您可以使用此公式

一旦获得所有候选对,问题就是找到一个只有一个参数的函数,该参数描述了四边形的所有可能的分区,它们都遵循所需的比率.

如果你使用像这样的等式对两边进行参数化

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

你将能够得到这样的东西:

您可以使用相同的公式找到绿色区域,具体取决于两个参数(每侧一个).我将它上传到ideone,只是因为它在这里发布太笨拙了

下一步是将问题减少到只有一个参数.这是在考虑到您希望完整多边形的某个面积比时完成的.

从这两个方程式中,您可以获得每对边的两个参数之间的关系(双曲线).所有这些切口都具有所需的面积比.

接下来是计算宽高比,并选择最小值.由于功能非常流畅,您需要做的就是编写一个极端的查找程序.

在这里你可以看到六边形的宽高比的结果,将一个顶点作为一个分裂点,如下所示:

每个区域的宽高比图是:

其中x轴上的每个单元对应于一侧.

如果您想了解更多细节,请告诉我们......