Intersection of conics using matrix representation [closed]

I came across a very interesting section of a wikipedia article on conics: http://en.wikipedia.org/wiki/Conic_section#Intersecting_two_conics

I am trying to work out a couple of examples to add to the page.

Example 1 - (this one turns out to be quite straight forward - see Example 2 below for a more general case):

Take these two hyperbolas, Q1 and Q2: Q1: $$x^2 - y^2 - 2 = 0$$ and Q2: $$.5x^2 - y^2 - 1 = 0$$

Their graphs which show that they have 2 real intersections are here: http://www.wolframalpha.com/input/?i=plot%28x^2+-+y^2+-+2+%3D+0+and+.5x^2+-+y^2+-+1+%3D+0%29

First, we construct their matrices: $$Q_1 = \begin{bmatrix}1 & 0 & 0\\0 & -1 & 0\\0 & 0 & -2\end{bmatrix}$$ $$Q_2 = \begin{bmatrix}1/2 & 0 & 0\\0 & -1 & 0\\0 & 0 & -1\end{bmatrix}$$

Then, we set $$det(\lambda Q_1 + \mu Q_2) = 0.$$

Expanding this determinant, we get the equation: $$(\lambda + \frac{\mu}{2})(-\lambda-\mu)(-2\lambda-\mu) = 0$$

Here, each of the 3 factors can be independently set equal to zero to find the 3 solutions: $$\mu = -2\lambda,$$ $$\mu = -\lambda,$$ and $$\mu = -2\lambda,$$ respectively.

Alternatively, we could immediately set $\lambda=1$ and solve $\mu^3/2+(5 \mu^2)/2+4 \mu+2$ algorithmically.

There three degenerate conics? I.e. if we take one of the solutions ($\mu = -\lambda$), and use it to compute a particular linear combination (plugging into the linear combination equation $\lambda C_1 + \mu C_2$), we get:

$$\lambda C_1 -\lambda C_2$$

which is still an expression with an unknown? Does it mean we can choose any $\lambda$ to obtain a degenerate conic? That is, set $\lambda=1$ to get:

$$C_0 = \begin{bmatrix}.5 & 0 & 0\\0 & 0 & 0\\0 & 0 & -1\end{bmatrix}$$

Now we identify two coincident lines constituting this degenerate conic. We set $x^T C_0 x$ equal to zero, and we get $$.5x^2 - 1=0.$$ We see that $$x=\pm \sqrt{2}$$ (a pair of vertical lines). Intersecting these lines with the conics will give the intersection points of the original conics. Here, since the lines are vertical we can simply substitute the values $$x=\sqrt{2}$$ and $$x=-\sqrt{2}$$ to obtain the intersections (there are only 2 in this problem, but there can be up to 4):

From Q_1: $$(\sqrt{2})^2 - y^2 - 2 = 0 \rightarrow y=0$$ $$(-\sqrt{2})^2 - y^2 - 2 = 0 \rightarrow y=0$$

we get intersection points $$(\sqrt{2}, 0)$$ and $$(-\sqrt{2},0).$$

From Q_2: $$.5(\sqrt{2})^2 - y^2 - 1 = 0 \rightarrow y=0$$ $$.5(-\sqrt{2})^2 - y^2 - 1 = 0 \rightarrow y=0$$

we get intersection points $$(\sqrt{2}, 0)$$ and $$(-\sqrt{2},0).$$

Example #2

Take these two hyperbolas, Q1 and Q2: Q1: $$.5x^2 - y^2 + .1xy + 1 = 0$$ and Q2: $$-x^2 + y^2 + 1 = 0$$

Their graphs which show that they have 4 real intersections are here:

First, we construct their matrices: $$Q_1 = \begin{bmatrix}.5 & .05 & 0\\.05 & -1 & 0\\0 & 0 & 1\end{bmatrix}$$ $$Q_2 = \begin{bmatrix}-1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{bmatrix}$$

Then, we set $$det(\lambda Q_1 + \mu Q_2) = 0.$$

Expanding this determinant, we get the equation: $$-.5\lambda^3 + \lambda^2\mu +.5\lambda\mu^2-\mu^3 - .0025\lambda^3 - .0025\lambda^2\mu.$$

Arbitrarily setting $\lambda=1$ and expanding, we get the equation $$-\mu^3+.5\mu^2+.9975\mu-.5025=0.$$

The 3 (approximate) solutions are: $$\mu = -1,$$ $$\mu = .505,$$ and $$\mu = .99495,$$ respectively.

Going back and constructing the degenerate conic matrix (with $\lambda=1$ and $\mu=-1$), we have (Can you just pick one of the 3 solutions that comes from the determinant equation as I did?)

$$C_0 = \begin{bmatrix}1.5 & .05 & 0\\.05 & -2 & 0\\0 & 0 & 0\end{bmatrix}$$

Now $$x^T C_0 x = 0 = $$ we get $$1.5x^2 + .1xy-2y^2 = 0.$$

Solving for $y$, we see that the two lines are $$y=−0.841386x$$ and $$y=0.891386x.$$

These lines intersect the conics at exactly the intersection points of the conics, as seen here: http://www.wolframalpha.com/input/?i=plot%28.5x^2-y^2%2B.1xy%2B1%3D0+and+-x^2%2By^2%2B1%3D0+and+y+%3D+%E2%88%920.841386x+and+y%3D0.891386x%29

The intersection points can be found by substituting the equation of both lines in to the equation of both conics. For example, substituting $$y=−0.841386x$$ into $$.5x^2 - y^2 + .1xy + 1 = 0$$ we get $$x=1.8505$$ Plugging this into the equation of the line $y=−0.841386x$, we see that one intersection point is $(1.8505, -1.5569)$. The other 3 intersection points can be found identically.

Solution 1:

hope I can help you out improving these examples. I am the author of that brief description of how to intesect two conics that is giving you headaches!

I will first concentrate on example 1. You actually used two tangent hyperbolae. That might gives some numerical error when computing the intersection using a numerical algorithm (like the one I wrote for Matlab www.mathworks.it/matlabcentral/fileexchange/28318-conics-intersection).

Let's consider two well intersecting parabolae like: $$C_1 = \begin{bmatrix}1 & 0 & 0\\0 & 0 & -1/2\\0 & -1/2 & 0\end{bmatrix}$$ $$C_2 = \begin{bmatrix}3 & 0 & 0\\0 & 0 & -1/2\\0 & -1/2 & -2\end{bmatrix}$$

whose equations are $x^2 - y = 0$ and $3x^2 - y - 2 = 0$ respectively. The intersection can be seen in the following plot:

It is possible to verify that these two conics intersects in two points $$p_1 = \begin{bmatrix}-1 & 1 & 1\end{bmatrix}$$ $$p_2 = \begin{bmatrix} 1 & 1 & 1\end{bmatrix}$$ expressed in homogeneous coordinates.

Let's now estimate the intersection numerically. For this reason we are going to build a pencil of conics that contains both C1 and C2, i.e.

$$C_\lambda = C_1 + \lambda C_2 $$

Notice that the intersection points lie on $C_\lambda$ for any value of $\lambda$, i.e:

$$ p_1^T C_\lambda p_1 = 0 \quad \forall \lambda $$ $$ p_2^T C_\lambda p_2 = 0 \quad \forall \lambda $$

We are going to exploit this properties by detecting an "easy to handle" conic that belongs to the pencil. In particular we exploit the conic of the pencil that is represented by straight lines intersecting both $p_1$ and $p_2$. This is a degenerate conic (indeed is a set of straight lines) whose conic matrix deterimant is vanishing.

Thus we are looking for the value $\lambda$ such that $det(C_\lambda) = 0$. $\lambda$ is sought by using the characteristic polynomial of the pencil of conics.

We initially transform the pencil of conics as:

$$ -(C_1 + \lambda C_2) \cdot (-C_2)^{-1} = \lambda I - C_1 \cdot (-C_2)^{-1} = \lambda I - A$$

Solving $det(C_1 + \lambda C_2) = 0$ is equivalent to solve $det(\lambda I - A) = 0$. In this new formulation, though, $\lambda$ represents the eigenvalue of matrix A and $det(\lambda I - A)$ is the characteristic polynomial of A.

In our example $$A = C_1 \cdot (-C_2)^{-1} = \begin{bmatrix}-1/3 & 0 & 0\\0 & -1 & 0\\0 & 4 & -1\end{bmatrix}$$

We then solve the characteristic polynomial (a 3rd degree polynom) for $\lambda$ $$det(\lambda I - A) = 0$$ This characteristic polynomial of A (a 3x3 matrix) can be written as: $$-\lambda^3 + \lambda^2 trace(A) - \lambda (det(A_{12}) + det(A_{23}) +det(A_{13})) +det(A) = 0$$

In our case the solutions of $$-\lambda^3 + 7/3 \lambda^2 - 5/3 \lambda - 1/3 = 0$$ are (-1, -1, -1/3). Since these are all real values we can select one and use it to identify our degenerate conic of the pencil. In particular $\lambda = -1$ gives

$$C_d = C_1 -1 \cdot C_2 = \begin{bmatrix}-2 & 0 & 0\\0 & 0 & 0\\0 & 0 & 2\end{bmatrix}$$

whose determinant is indeed zero.

As we said $C_d$ represent a degenerate conic. In particular it can be decomposed as the multiplication of two straight lines m and l: $$C_d = m \cdot l^T + l \cdot m^T $$

(here are the details on how to perform the Decomposition of a degenerate conic)

In particular in our case $$l = \begin{bmatrix}1 & 0 & 1\end{bmatrix}$$ $$m = \begin{bmatrix} -1 & 0 & 1\end{bmatrix}$$ represent two vertical lines.

By intersecting the two lines with one of the two conics (say $C_1$) we get the two intersection points $p_1$ and $p_2$. This is done by solving the systems:

$$ \left\{ \begin{align} p_1^T \cdot C_1 \cdot p_1 &= 0 \\ l \cdot p_1 &= 0 \\ \end{align} \right. $$

$$ \left\{ \begin{align} p_2^T \cdot C_1 \cdot p_2 &= 0 \\ m \cdot p_2 &= 0 \\ \end{align} \right. $$