1
$\begingroup$

I was reading about ellipse-ellipse intersection and I came across this article:

https://math.stackexchange.com/questions/679622/intersection-between-conic-and-line-in-homogeneous-space/867428#867428

I wrote a program that implements this method and it works, but now I'm working to understand why. I understand how $D = L^T C L$ is constructed, but I don't understand how/why the decomposition $P = D + λ L$ works. It seems that the author seems to be solving for one of the eigenvalues of $D$, but I don't immediately recognize if this is a standard method or not (i.e. if it only works for conics, or only when decomposing from rank 2 to rank 1 matrices, etc). Any reference material or help understanding the theory here is greatly appreciated.

EDIT: I realized I mentioned ellipse-ellipse intersections, and the article is about conic-line intersections. To erase some of the confusion, the method of determining ellipse-ellipse intersection basically comes down to constructing a pencil of conics and with that pencil finding a pair of lines that intersect the ellipses at the same points that the ellipses intersect each other. That article can be found here for those interested.

For clarity, here is some explanation of the conic-line problem and some of the equations from the line-conic article.

The general Cartesian equation for a conic section $Ax^2+Bxy+Cy^2+Dx+Ey+F=0$ can be rewritten as $p^TQp = 0$, where: $$p = \left [ \begin{matrix} x \\ y \\ 1 \\ \end{matrix} \right ],\,\, Q = \left [ \begin{matrix} A & B/2 & D/2 \\ B/2 & C & E/2 \\ D/2 & E/2 & F\end{matrix} \right ]$$ The point $p$ is in homogeneous coordinates. Here I use the letter Q to differentiate from C which is used as a coefficient in the conic equation (the article calls this matrix C). The implicit formula for a line $ax+by+c=0$ can be rewritten as expressed as $l\cdot p = 0$ where $l = [a,b,c]$ and $p=[x,y,1]^T$ as above. Additionally, the place where a line $l=(a_1,b_1,c_1)$ so defined intersects another line $g=(a_2,b_2,c_2)$ can be calculated using the cross product $l \times g = q$, where $q$ is expressed in homogeneous coordinates. The method for determining the intersection of the line and general conic is given in the article mentioned originally.

In the article, the matrix $L$ is the skew-symmetric matrix such that $Lg=l\times g$. If we define $R=L^TQL$ (the article calls this matrix D), then $g^TRg=0$ is the equation of all lines that intersect $l$ at points on the conic, since $(Lg)^TQ(Lg) = 0$ (but the article says the lines are tangent to the conic). The article also says that $R$ is a degenerate conic that consists of the 2 points where the line and conic intersect (which I also don't understand).

My question is the decomposition of the matrix $R$, which should have rank 2. We construct a matrix $P=R+\lambda L$ and find a $\lambda$ to make $P$ rank 1. Then, $P=uv^T$, where $u$ and $v$ are the intersection points in homogeneous coordinates. I just don't understand how the decomposition works, why it works, and if that's a general method I can use (range of applicability).

$\endgroup$
  • 1
    $\begingroup$ Can you rewrite some of the equations in the question please? $\endgroup$ – nicoguaro May 22 '17 at 13:53
  • $\begingroup$ @nicoguaro I rewrote the equations and added more exposition about the problem itself. $\endgroup$ – CADJunkie May 24 '17 at 17:29
0
$\begingroup$

After some searching, I found the explanation in "Perspectives on Projective Geometry" by Richter-Gebert.

The problem is finding a line $g$ such that $g^TRg=0$, and $R=L^TQL$ where $Q$ describes the ellipse. The transformation with $L$ makes $R$ a dual conic consisting of two points of intersection and a double line that passes through them. $R$ is also a degenerate conic, so it has rank 1 or 2. For the rank 2 case, if R is symmetric (which I think it always is) it can be rewritten as $R = uv^T + vu^T$ (up to a scalar multiple), where $u, v$ are points where the line intersects the original conic. $uv^T$ alone can describe the degenerate conic since $$0 = \langle g,u \rangle \cdot \langle g, v \rangle = (g^Tu)(v^Tg)= g^T(uv^T)g$$ with $\langle g, u \rangle=0$ and $\langle g, v \rangle=0$ if $u$ and $v$ are on $g$, respectively. The product $uv^T$ is rank-1, so we need to find a matrix $W$ such that $g^T(R+W)g=0$ and $(R+W)$ is rank-1. If $W$ is skew-symmetric, it will satisfy the first condition. The matrix sum then becomes: $$R+W=\left ( \begin{matrix} a&b&d\\b&c&e\\d&e&f\end{matrix} \right )+\left ( \begin{matrix}0&\tau&-\mu\\-\tau&0&\lambda\\\mu&-\lambda&0 \end{matrix} \right )$$ Notice that $M_w\,q=w \times q$ for any vector $q$ and the vector $w=[\lambda,\mu,\tau]^T$. We now need to solve for $w$ so that $(R+W)$ is rank-1. Notice that if the line $l$ passes through $u$ and $v$, $u \times v=\alpha l$, where $\alpha$ is a scalar we can choose. If we consider the sum $uv^T-vu^T$, we can see through expanding and analyzing the elements that: $$uv^T-vu^T = \alpha M_{u\times v}=M_{\alpha l}=\alpha M_l$$ Thus, $R+\alpha M_l = 2 uv^T$. Thus, we can then choose $\alpha$ to make $R+\alpha M_l$ rank-1. Since $L = M_l$, then we can say: $$L^TQL+\alpha L = uv^T$$ Since $u$ and $v$ are in homogeneous coordinates, any scalar multiples don't affect the points when we project them back into $\mathbb{R}^2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.