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!

The aspect ratio of a polygon A is defined as:

asp(A) := diam(A)^2 / ar开发者_运维知识库ea(A)

---

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).

• The number of edge pairs in which the cut may be placed is quadratically in the number of vertices (1/2 n (n-1) ): (lines mark edge pairs, by connecting the starting vertices of each pair)

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:

- 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]

• 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)

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

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

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).

• 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.

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

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

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

• Here is the result for the minimization procedure for an area ratio of 1. The green curve is the aspect ratio for the green polygon (+ added area depending on mu) and the red curve is the aspect ratio for the red polygon (+ added area depending on mu).

• And here, finally, is your 'most pleasing' polygon cut:

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

---

I'll write down a sketched answer first, and probably expand it if you are interested in going along these lines. I've a program running to compute this in Mathematica, (with some restrictions), and I'll also post it if I get some time to finish it.

The problem has actually two parts:

• Find the polygon partitions which yields your desired area ratio
• Select from them the one that minimizes the aspect ratio

Let's see the first problem first. You could do something like:

Consider each pair of sides, like in the following figure

And for each pair, consider the three following areas:

So, the maximal and minimal ratios that you may get for partitioning the polygon with a line crossing these two sides are the Min() and Max[] of the following set:

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

If your desired ratio is not between the Max and Min of this set, discard the pair.

NB: For calculating areas you may use this formula

Once you get all the candidate pair of sides, the problem is to find a function of only one parameter that describes all possible partitions of the quadrilateral that respects the desired ratio.

If you parametrize both sides with an equation like

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

you will be able to get something like this:

And you can find the green area using the same formula, depending upon the two parameters (one for each side). I uploaded it to ideone, just because it is too clumsy to post here

The next step is reducing the problem to only one parameter. This is done taking into account that you desire a certain area ratio for your complete polygon.

From that two equations you get a relationship (an hyperbola) between both parameters for each pair of sides. All those cuts have the desired area ratio.

Next thing is calculating the aspect ratio, and selecting the minimum. As the functions are pretty smooth, all you need to do is to program an extreme finder.

here you can see the results for the aspect ratio for an hexagon, taking one vertex as a split point like this:

And the aspect ratio plot for each area is:

Where each unit in the x axis corresponds to one side.

Let me know if you want more details ...