Finding the largest ellipse that will fit in a polygon

In summary, the conversation discusses the process of finding the largest ellipse inscribed in a given polygon. This involves setting up a set of half-plane representations for the polygon and representing the ellipse using an affine transformation. The goal is to minimize the determinant of the transformation matrix, which is equivalent to maximizing the area of the ellipse. This can be done by minimizing the trace of the matrix, which can be achieved by minimizing the sum of the logarithms of the eigenvalues of the matrix. This method can be implemented using Mathematica.
  • #1
aheight
321
109
Summary:: Questions about finding largest ellipse in polygon

Was wondering if someone could help me understand two concepts involved with finding largest ellipse in a polygon? Some background:

First, I set up a set of half-plane representations for the example polygon below and as you can see my ellipse is not fitting too well in the polygon:
$$
\mathcal{P}=\begin{cases}
\begin{aligned}
-x+y&\leq 5/2 \\
-1/6x+y&\leq 5/6 \\
2 x+y&\leq 3 \\
-1/10x-y&\leq 4/5
\end{aligned}
\end{cases}
$$
or in matrix form:
$$
\begin{bmatrix}
-1 & 1 \\
-1/6 & 1\\
2 & 1 \\
-1/10& -1
\end{bmatrix}
\begin{bmatrix}
x \\
y
\end{bmatrix}
\leq
\begin{bmatrix}
5/2 \\
5/6 \\
3 \\
4/5
\end{bmatrix}
$$
or
$$\textbf{Ax}\leq\textbf{b}
$$
Next, I represent the ellipse with an affine transformation using a symmetric definite matrix:
$$
\mathcal{E}=\{(x,y): x=\textbf{C}u+d
$$
or:
$$
\begin{bmatrix}
x \\
y
\end{bmatrix}
=\begin{bmatrix}
c & d\\
d & f
\end{bmatrix}
\begin{bmatrix}
\cos(t) \\
\sin(t)
\end{bmatrix}
+\begin{bmatrix}
a \\
b
\end{bmatrix}
$$
I don't understand the following:

(1) According to the Python reference Python link to John-ellipsoid, in order for the ellipse to be inside the polygon or ##\mathcal{E}\subset \mathcal{P}##, we must have ##\textbf{A}(\textbf{C}u+d)\leq b##.

(2) According to the Matheamtica reference (under Geometry applications) ConicOptimication in Mathematica, to maximize the area is equivalent to minimizing ##-\log(\text{Det}\textbf{C})## which is equivalent to minimizing ##-\text{Tr}(\textbf{C})##.

Would like to understand how (1) assures the ellipse is in the polygon and how (2) maximizes it's size and was hoping someone could help me.

Thanks!

[Moderator's note: Moved from a technical forum and thus no template.]
 

Attachments

  • ellipseinpolygon.jpg
    ellipseinpolygon.jpg
    9.6 KB · Views: 156
Last edited by a moderator:
Physics news on Phys.org
  • #2
(1) seems pretty straightforward. Let x be a point in the ellipse. Then it's of the form Cu+d. If it's in the polygon, ##Ax \leq b##. Plugging in Cu+d for x gives the result.

For part 2, do you know why the area of the ellipse is proportional to det(C)?
 
  • Like
Likes aheight
  • #3
Office_Shredder said:
(1) seems pretty straightforward. Let x be a point in the ellipse. Then it's of the form Cu+d. If it's in the polygon, Ax≤b. Plugging in Cu+d for x gives the result.

For part 2, do you know why the area of the ellipse is proportional to det(C)?

Thanks, (1) is obvious now.

Regarding (2): I know the area of the ellipse is ##A=\pi(ab)## with a and b the major and minor axes. Also I know (2) has something to do with definite positive symmetric matrices and for square matrices, ##\text{det}(\textbf{C})=\lambda_1\lambda_2## which since positive definite, both eigenvalues will be positive so looks like ##A=\pi ab=k\; \text{det}(\textbf{C})##. Is that correct?

And if I want to maximize ##A=k\;\text{det}(\textbf{C})## then that's equivalent to minimizing the ratio ##\displaystyle\frac{1}{\text{det}(\textbf{C})}##.

Ok, since ##\textbf{C}## is a square matrix of a linear operator, we have ##\text{tr}(\textbf{C})=\lambda_1+\lambda_2## and it looks like, since the eigenvalues are both positive ( and ##\log## is monotonic), minimizing ##\log(\text{det}\textbf{C})=\log(\lambda_1)+\log(\lambda_2)## is equivalent to minimizing their sum or ##\text{tr}(\textbf{C})##. Is that correct?
 
Last edited:
  • #4
Every ellipse starts with a circle of radius 1, which just gives the identity matrix. The area of that is ##\pi\det(C)## by trivial math.

You then scale each axis by changing the value The area is proportional to the scaling, and the determinant is also proportional to the scaling. You then rotate it by applying a rotation matrix to C. The determinant and the area are both unchanged.

You then shift it by adding d, which also leaves both the area and determinant unchanged.

I agree with everything you said then up to the last step. Now that we are there, I'm confused why minimizing ##\log(\lambda_1) + \log(\lambda_2)## is the same as minimizing ##\lambda_1+\lambda_2##.

Did they mean to say they are minimizing the trace of ##log(C)##? I feel like there's probably something obvious here and someone else will make me look dumb by identifying it.
 
  • #5
Office_Shredder said:
Now that we are there, I'm confused why minimizing ##\log(\lambda_1) + \log(\lambda_2)## is the same as minimizing ##\lambda_1+\lambda_2##.

That was my proposition. Here's my proof:

Let ##\lambda_1\lambda_2=u>0## since both eigenvalues are positive. First note ##\log(1/u)## is monotonic decreasing for ##u>0## so we can write:
$$
\text{min}\left[-\log(\lambda_1\lambda_2)\right]=\text{min}\left[-(\log(\lambda_1)+\log(\lambda_2)\right]
$$
and since ##\log(x)<x## for ##x>0##, then we may write:
$$
\text{min}\left[-(\log(\lambda_1)+\log(\lambda_2))\right]\lt \text{min}\left[-(\lambda_1+\lambda_2)\right]=\text{min}\left[-\text{tr}(\textbf{C})\right]
$$

Here's the Mathematica code used to find the inscribed ellipse of the polygon using this method:
Mathematica:
rp = RegionPlot[{
   y - x <= 5/2  &&
     y - 1/6 x <= 5/6  &&
     y + 2 x <= 3 &&
    -y - 1/10 x <= 4/5}, {x, -3, 2}, {y, -2, 2}, PlotRange -> 4]

polyA = {{-1, 1},
   {-1/6, 1},
   {2, 1},
   {-1/10, -1}};

polyB = {5/2, 5/6, 3, 4/5};

constraints =
  Table[Norm[polyA[[i]].c] + polyA[[i]].d <= polyB[[i]], {i,
    Length[polyA]}];
{cEllipse, dEllipse} = {c, d} /.
  ConicOptimization[-Tr[c],
   constraints, {c \[Element] Matrices[{2, 2}], d}]
aFine[d_, m_, t_] := d + m[[All, 1]] Cos[t] + m[[All, 2]] Sin[t];
ePlot = ParametricPlot[aFine[dEllipse, cEllipse, t], {t, 0, 2 Pi}];
Show[{rp, ePlot}, Axes -> True, PlotRange -> 4]
 

Attachments

  • inscribedEllipse.jpg
    inscribedEllipse.jpg
    8.7 KB · Views: 113
Last edited:
  • Like
Likes Filip Larsen

1. What is an ellipse?

An ellipse is a geometric shape that resembles a flattened circle. It is defined as a set of points in a plane, such that the sum of the distances from any point on the ellipse to two fixed points (called the foci) is constant.

2. How do you determine the largest ellipse that will fit in a polygon?

To determine the largest ellipse that will fit in a polygon, we use a mathematical algorithm that calculates the dimensions of the ellipse based on the vertices of the polygon. This algorithm takes into account the shape and size of the polygon to find the largest possible ellipse that can fit inside it.

3. Can an ellipse fit perfectly inside any polygon?

No, it is not always possible for an ellipse to fit perfectly inside a polygon. This is because the shape and size of the polygon may not allow for an ellipse to fit without overlapping or extending beyond the boundaries of the polygon.

4. What factors affect the size of the largest ellipse that can fit in a polygon?

The size and shape of the polygon, as well as the distance between its vertices, are the main factors that affect the size of the largest ellipse that can fit inside it. The larger and more irregular the polygon, the more difficult it may be to find an ellipse that fits perfectly inside it.

5. Can this algorithm be used for any type of polygon?

Yes, this algorithm can be used for any type of polygon, including regular and irregular polygons. The only requirement is that the polygon must have at least three vertices in order for an ellipse to fit inside it.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
927
  • Calculus and Beyond Homework Help
Replies
14
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
515
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
2K
  • Calculus and Beyond Homework Help
Replies
14
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
265
  • Calculus and Beyond Homework Help
Replies
5
Views
4K
  • Calculus and Beyond Homework Help
Replies
14
Views
571
  • Calculus and Beyond Homework Help
Replies
3
Views
890
Back
Top