如何尽量减少两个子多边形的最大长宽比？ [英] How do I minimise the maximum aspect ratio of two subpolygons?

问题描述

我想切割凸多边形分成两个与使用一条直线，使得两个子多边形的较大长宽比为最小的区域给定比率

I'd like to cut a convex polygon into two with a given ratio of areas using a straight line, such that the larger aspect ratio of the two subpolygons is minimised.

我此刻方法涉及选择随机起点，计算相应的终点一个分割多边形​​进入目标区域，然后计算两个纵横比的大。然后重复这个很多次，直到我足够接近最低！

My approach at the moment involves choosing a random starting point, computing the appropriate end point that splits the polygon into the target areas, then calculating the larger of the two aspect ratios. Then repeating this lots of times until I'm close enough to a minimum!

一个多边形A的纵横比被定义为：

The aspect ratio of a polygon A is defined as:

ASP（A）：=直径（A）^ 2 /区域（A）

推荐答案

我一直在工作的方法是非常相似的贝利撒留，所以我只能分享我的想法的几个注意事项（我使用Mathematica） 。

The method I've been working on is very similar to Belisarius, so I'll only share a few notes about my thinking (I'm using Mathematica).

• ，其中，切口可以被置于边缘对的数目是在二次顶点（1/2为n（n-1））的数目：（线标记边缘对，通过连接每一对的起始顶点）

在黄色区域标记该区域是人们可以找到切口：

The yellow areas mark the area were one could locate the cut:

这样做很多计算上的所有组合之前，这是很好的割离无效的候选人。这里显示了一些面积比对什么是左：

so before doing many calculations on all combinations it's good to mow away invalid candidates. Here is shown for some area ratios what pairs are left:

  - 作为贝利萨留说，你可以找到面积比的范围为每个上述情况，而是简单地把该最小和最大不正确。在两个范围你当你扭转你的面积比，也许间断的两个领域。我使用Mathematica的间隔算法来处理这​​对我来说：

- As belisarius says you can find the range of area ratios for each of the above situations, but simply taking the Min and Max is incorrect. The two ranges you get when you reverse the two areas in your area ratio maybe disjunct. I use Mathematica's Interval arithmetic to handle this for me:

检查是否一个给定的面积比也有舒适区间函数处理：

Checking whether a given area ratio is also handled with a comfortable Interval function:

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

• 的paramater labda的值，通过第一边缘确定切口的位置作为亩的函数（即确定了第二边缘的位置的参数）

  • The value of the paramater labda that determines the location of the cut through the first edge as a function of mu (the parameter that determined the position for the second edge)

    \的λ - ＆GT; （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）* \μ）/    （（1 + givenAreaRatio）*（（ - P2X）* P4Y +      P1X *（ - P2Y + P4Y）+（P1X - P2X）*（P3Y - P4Y）* \ [木] +      P1Y *​​（P2X + P4X *（ - 1 + \ [穆]） - P3X * \μ）+      P2Y *（P4X + P3X * \ [木] - P4X * \μ）））

    \[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])))

    或亩作为labda的功能：

    or mu as a function of 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的拥抱红色多边形切割和'绿色'的多边形的人的区域和AR领域的区域的坐标（见图在这个岗​​位的底部）。

    with p1, p2, p3, p4 the coordinates of the area embracing the cut and aL the area of the 'green' polygon and aR the area of the 'red' polygon (see figure at the bottom of this post).

    • 未在一个边缘上的每一个点总是给在另一边缘的溶液，反之亦然。我检查了方程的lambda找到亩里面设置拉姆达为0或1，反之亦然值。

    • Not every point on one edge always gives a solution on the other edge and vice versa. I check the equation for lambda to find values of mu which set lambda at 0 or 1, and vice versa.

    作为最后步骤I最小化的两个区域的高宽比的功能的最大值。在数学语言：

    As a last step I minimize the maximum value of the aspect ratio functions of the two areas. In Mathematica language:

    NMinimize [{最大值[的aspectRatio [area1tot]的aspectRatio [area2tot]，\微米范围[[1]]＆LT; = \ [木]＆LT; = \微米范围[[2]]} \ [木]]

    与ar​​e1tot和area2tot是总面积由万亩和lambda并在拉姆达被替换上述equestion的拉姆达在万亩方面参数化两部分。现在，我们已经离开只有一个参数

    with are1tot and area2tot being the total areas for both halves parametrized by mu and lambda and where lambda is replaced by the above equestion for lambda in terms of mu. Now we have only one parameter left

    • 下面是结果为1.绿色曲线的面积比的最小化过程在长宽比为绿色多边形（+取决于亩添加区），红色曲线的纵横比为红多边形（ +取决于亩添加区）。

    

    • 在这里，最后，是你的最赏心悦目的多边形切割：

    

    我有一个数学的笔记本电脑，我会送的请求。只是给我一个电子邮件。

    I have a Mathematica notebook that I will send on request. Just send me an e-mail.

    这篇关于如何尽量减少两个子多边形的最大长宽比？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！