Find all inscribed ellipses in a given convex quadrilateral passing through a given internal point

Question

Given a convex quadrilateral, and a point inside it, I want to find all ellipses that are inscribed in the quadrilateral and passing through the given point.

My attempt: is outlined in my solution below

Your comments, hints, and answers are highly appreciated.

Answer 1

This is more a comment to provide a quick way to solve numerically the problem.

Given a set of points defining a convex quadrilateral, $P_i$ we can define a set of lines along the sides of this quadrilateral as

$$ \cases{ L_i\to q = P_i + \lambda_i\vec v_i\\ \vec v_i = P_{i+1}-P_i,\ \ i = \{1,2,3\},\ \ \ \vec v_4 = P_1-P_4 } $$

so the ellipse $(q-p_0)\cdot Q\cdot(q-p_0)=1$ should be tangent to all $L_i$. Here $q=(x,y)$ represents a generic point in the plane. The ellipse should verify

$$ (P_i-p_0+\lambda_i\vec v_i)\cdot Q\cdot(P_i-p_0+\lambda_i\vec v_i)-c^2=(P_i-p_0)\cdot Q\cdot(P_i-p_0)+2\lambda_i(P_i-p_0)\cdot Q\cdot\vec v_i +\lambda_i^2\vec v_i\cdot Q\cdot\vec v_i - 1 = 0 $$

due to tangency we should have

$$ \left((P_i-p_0)\cdot Q\cdot\vec v_i\right)^2-\left(\vec v_i\cdot Q\cdot\vec v_i\right)\left((P_i-p_0)\cdot Q\cdot(P_i-p_0)-1\right) = 0 $$

Given now that the ellipses should cross in a point $p$ we have all conditions:

$$ \cases{ \left((P_i-p_0)\cdot Q\cdot\vec v_i\right)^2-\left(\vec v_i\cdot Q\cdot\vec v_i\right)\left((P_i-p_0)\cdot Q\cdot(P_i-p_0)-1\right)=0\\ (q-p_0)\cdot Q\cdot(q-p_0)-1 = 0\\ } $$

$5$ equations on the unknowns $q_{11},q_{12},q_{22},x_0,y_0$. Follows a MATHEMATICA script to perform those operations

Clear[P0, V]
Q = {{q11, q12}, {q12, q22}};
p = {13, 9};
q = {x, y};
p0 = {x0, y0};
P0 = {{11, 0}, {15, 0}, {15, 10}, {8, 10}};
V = {P0[[2]] - P0[[1]], P0[[3]] - P0[[2]], P0[[4]] - P0[[3]], P0[[1]] - P0[[4]]};
equs = Table[((P0[[k]] - p0).Q.V[[k]])^2 - V[[k]].Q.V[[k]] ((P0[[k]] - p0).Q.(P0[[k]] - p0) - 1), {k, 1, 4}];
equs = Join[equs, {(p - p0).Q.(p - p0) - 1}] // FullSimplify;
sols1 = Quiet@Solve[N[equs] == 0, {q11, q12, q22, x0, y0}];
ellipses = Table[(q - p0).Q.(q - p0) - 1 /. sols1
gr0 = ListLinePlot[Join[P0, {P0[[1]]}], PlotStyle -> {Thick, Blue}];
gr1 = Graphics[{Red, PointSize[0.02], Point[p]}];
Show[gr0, 
ContourPlot[ellipses[[1]] == 0, {x, 0, 15}, {y, 0, 15}, PlotPoints -> 50], 
ContourPlot[ellipses[[2]] == 0, {x, 0, 15}, {y, 0, 15}, PlotPoints -> 50], gr1, AspectRatio -> 1, Axes -> False]

Answer 2

It is well-known that there's an infinite number of inscribed ellipses in a given convex quadrilateral.

The equation of such an inscribed ellipse is of the form

$ (r - r_0)^T Q (r - r_0) = 1 \hspace{26pt}(1) $

which is also equivalent to the following form

$ r^T Q r + r^T b + c = 0 \hspace{26pt}(2)$

where $ r = [x, y]^T $, $r_0$ is the center of the ellipse, $Q$ is a $2 \times 2 $ positive definite symmetric matrix. In the second form we have $ b = - 2 Q r_0 $ and $ c = r_0^T Q r_0 - 1 $.

Equation $(2)$ can be written compactly as follows:

$ w^T Q_0 w = 0 \hspace{26pt}(3)$

where $ w = \begin{bmatrix} r \\ 1 \end{bmatrix} $ is a $3 \times 1$ vector. And the $3 \times 3 $ matrix $Q_0$ is specified by

$ Q_0 = \begin{bmatrix} Q && \dfrac{1}{2}b \\ \dfrac{1}{2} b^T && c \end{bmatrix} \tag{4} $

Using the methods of projective geometry, it is known that if the line

$ u_1 x + u_2 y + u_3 = 0 $

is tangent to the conic specified by $(3)$ then $ u = [u_1, u_2, u_3]^T$ satifies,

$$ u^T Q_0^{-1} u = 0 \tag{5}$$

And this is our starting point. Using the four given vertices of the quadrilateral, we'll construct the equations of four sides of the quadrilateral, and use those in equation (5), to determine $Q^{-1}$.

Determining the equation of the line between vertex $P_i$ and $P_{i+1}$ is performed as follows. Define the vector

$ v_i = P_{i+1} - P_i $

Then the equation of the line connecting $P_{i} $ with $P_{i+1}$ is

$ (E v_i)^T ( \mathbf{r} - P_i ) = 0 $

where $ E = \begin{bmatrix} 0 && 1 \\ -1 && 0 \end{bmatrix} $

So that the first two entries of vector $u_i$ are given by $E v_i$ and the third entry is $( - (E v_i)^T P_i ) $.

So for each of the four sides, we have thus calculated the vector $u_i, i = 1, 2, 3, 4$

The quadratic form given by equation $(5)$ when expanded becomes:

$ A_{11} u_1^2 + A_{22} u_2^2 + A_{33} u_3^2 + 2 A_{12} u_1 u_2 + 2 A_{13} u_1 u_3 + 2 A_{23} u_2 u_3 = 0 \tag{6}$

where matrix $A = Q_0^{-1}$

There are six unknowns in this equation, which are the $A_{ij}'s$. Using the four $u_i$'s for the four sides, we can write $4$ of these equations. The solution of this $4 \times 6$ system is as follows

$ X = [A_{11}, A_{22}, A_{33}, A_{12}, A_{13}, A_{23} ] = \lambda ( X_0 + t X_1) \tag{7}$

The scalar $\lambda$ does not affect the calculation of $Q$, and can be taken as unity.

We thus have matrix $A = A_0 + t A_1$, from which we calculate $Q_0 = A^{-1} = (A_0 + t A_1)^{-1}$.

Now comes the part where we impose the restriction that this ellipse passes through the given internal point. Let this point be $r_1$, then we want

$ r_1^T Q_0 r_1 = 0\tag{8}$

i.e.

$ r_1^T (A_0 + t A_1)^{-1} r_1 = 0\tag{9} $

from which

$ r_1^T \dfrac{\text{adj}( A_0 + t A_1 ) }{| A_0 + t A_1 |} r_1 = 0 \tag{10} $

and this gives,

$ r_1^T \text{adj}( A_0 + t A_1 ) r_1 = 0 \tag{11}$

The adjugate matrix, $\text{adj}( A_0 + t A_1 )$ has entries that can computed from the entries of $A_0$ and $A_1$, and they will be all quadratic polynomials in $t$.

Thus equation $(11)$ will give a quadratic polynomial in $t$, which can have no solution, one solution, or two solutions. Once we find the solutions (if any), then we've determined $A$ and from it, $Q_0$.

Matrix $Q_0$ found, is a scalar multiple of the actual $Q_0$, i.e.

$ Q_0 = \begin{bmatrix} s Q && \dfrac{1}{2} s b \\ \dfrac{1}{2} s b^T && s c \end{bmatrix} $

The scalar $s$ is unknown. Using matrix $Q_0$, we can find the center of the ellipse as follows

$ r_0 = - \dfrac{1}{2} (s Q) ^{-1} (s b) = - \dfrac{1}{2} Q ^{-1} b$

Note that in the above calculation we're using $(sQ)$ and $(sb)$ which we have.

Having found the center $r_0$, the equation of the ellipse is

$ (r - r_0)^T (s Q) (r - r_0) = s c + r_0^T(s Q) r_0 $

Therefore,

$ (r - r_0)^T \left( \dfrac{ s Q }{ s c + r_0^T (s Q) r_0 } \right) (r - r_0) = 1 $

Comparing this to

$ (r - r_0)^T Q (r - r_0) = 1 $

We get our $Q$ as

$ Q = \dfrac{ s Q }{ s c + r_0^T (s Q) r_0 } $

Finally to obtain the parameters of this ellipse, diagonalize $Q$ as follows

$ Q = R \ D \ R^T $

The diagonal entries of $D$ are the reciprocal of the square of the semi-major and semi-minor axes (in some order), and $R$ is the rotation matrix whose columns are unit vectors that point in the direction of these axes.

As a numerical example, I took the vertices of the quadrilateral to be

$ P_1 (11,0), P_2 (15, 0), P_3(15, 10), P_4(8, 10) $

and $r_1 = (14,8) $

Applying the method above, I found two solutions. This is shown in the figure below.

Using the same quadrilateral, but with $r_1 = (12, 8)$ I also got two solutions, and they shown below.

As a third example, using the same quadrilateral, but with $r_1 = (14, 6), I obtained the following inscribed ellipses.

As a fourth example, consider the quadrilateral with vertices $(2, 3), (5, 9), (14,6), (9, 2) $ and $r_1 = (5, 8) $

The figure below depicts this quadrilateral, the point $r_1$, and the two possible inscribed ellipses.

Answer 3

Here's an alternate approach, based on the fact that any convex quadrilateral can be mapped to a square by some projective transformation.

Let then $ABCD$ be the given quadrilateral, with a given point $P$ inside it, and $A'B'C'D'$ a square with side of length $2$, which is the image of $ABCD$. To construct the image $P'$ of $P$ we can join $P$ with the intersections $E$ and $F$ of the opposite sides of the quadrilateral. If $H$ and $K$ are the intersections of $PE$ and $PF$ with $AB$ and $BC$, then we can construct $H'$ and $K'$ using the invariance of the cross ratio for projective transformations. Taking points $EBHA$, for instance, the invariance of cross ratio gives: $$ {EH\cdot AB\over BH\cdot AE}={A'B'\over B'H'} $$ and analogously for $FBKC$: $$ {FK\cdot BC\over BK\cdot FC}={B'C'\over B'K'}. $$ From these we can get $B'H'$, $B'K'$ and construct $H'$, $K'$. The parallels to the sides of the square through $H'$ and $K'$ meet then at $P'$. We can now find the ellipses through $P'$ inscribed in the square and map them back to $ABCD$.

Let then $V'$ be the tangency point on $C'D'$ of an inscribed ellipse. The other tangency points can be found as reflections of $V'$ about the diagonals of the square and the center $O'$ of the square. If $M$ is the projection of $V'$ on $A'C'$ and $Q$ on $O'C'$ is a vertex of the ellipse, we have: $$ O'Q^2=O'M\cdot O'C'= D'V' $$ and analogously for the other vertex: $$ O'R^2= C'V' $$ (remember that we chose $A'B'=2$). Inserting these into $$ {P'X^2\over O'Q^2}+{P'Y^2\over O'R^2}=1, $$ where $X$ and $Y$ are the projections of $P'$ on the diagonals of the square, we find a quadratic equation for $C'V'$, with solution: $$ C'V'=2-D'V'=1-{P'X^2-P'Y^2\over2}\pm \sqrt{{(P'X^2-P'Y^2)^2\over4}+1-P'X^2-P'Y^2}. $$ Once we have the tangency points on the sides of the square, we can map them back to the quadrilateral $ABCD$, using again the invariance of cross ratio. From the four tangency points and point $P$ we can thus find the equations of both inscribed ellipses, as shown in figure below.