In homogeneous space (so 3 coordinates for each point) I have:

  • A conic C, defined by a symmetric 3x3 matrix of real values. The conic actually should have only imaginary points (don't know if this is important).
  • A line l, defined by a vector of 3 real values

How do I find the intersection of the two?

I think I shoud be able to find the intersection (I expect two complex solutions), but I'm having troubles doing it.

Solving it with the classic pen&paper leads me to a solution X=(x, y, 1) with x and y complex such that, when I try to verify that the point belongs to C (by cheching if XCX' = 0, where the ' stands for transposed), it seems that it does NOT belong to C.

For those who know computer vision stuff: C is actually the image of the absolute conic, estimated from a picture, while l is a vanishing line of a plane. I'm trying to intersect the two in order to find the circular points, and then do a metric rectification of the plane in the image.


The matrix

$$L=\hat l=\begin{pmatrix}0&-l_3&l_2\\l_3&0&-l_1\\-l_2&l_1&0\end{pmatrix}$$

can be used to describe a cross product with $l$: $Lg=l\times g$.

Now consider $D = L^T\cdot C\cdot L$. It is a degenerate conic which you best interpret dually as a pair of points, namely the points of intersection. A line $g$ is tangent to that conic if its intersection with $l$, which can be computed as $l\times g=Lg$, lies on $C$, i.e. if $(l\times g)^TC(l\times g)=0$.

All you have to do is decompose that conic $D$ into its components. You already have $\operatorname{rank}(D)=2$. Now consider $P=D+\lambda L$. For some suitable $\lambda$, this matrix will have rank $1$. Simply look at any $2\times 2$ subdeterminant, and choose $\lambda$ in such a way that it becomes zero. You will have two possible choices which only differ by sign. Either one will do.

Once you have this, $P=pq^T$ is a matrix of rank $1$. You can choose any non-zero column and call that $p$, and any non-zero row will be $q$ (up to scalar multiples). So I'd look for the greatest absolute value in that matrix and choose its row and column as the two points of intersection.

  • $\begingroup$ Great answer. I'm wondering about the why/how the decomposition of D works. I've asked that question here: scicomp.stackexchange.com/questions/26938/… Would love to get your input on it. $\endgroup$ – CADJunkie May 24 '17 at 19:38
  • $\begingroup$ @CADJunkie For one thing, $D$ is a scalar multiple of $pq^T+q^Tp$. $\endgroup$ – amd Jul 17 '17 at 20:09

First find the pole (point) of the line ${\bf L}=\pmatrix{a \\ b \\ c}$ using the conic $\mathtt{C}=\left[ \matrix{A & C & D \\ C & B & E \\ D & E& F} \right]$. This is found using the inverse of the conic

$$ \mathbf{P} = \mathtt{C}^{-1} \mathbf{L} = \pmatrix{u \\ v \\ w}$$

Since we will use the inverse again, set

$$\mathtt{C}^{-1}=\left[ \matrix{a & c & d \\ c & b & e \\ d & e& f} \right]$$

The pencil of lines through $\bf P$ is parametrically defined as

$$\mathbf{T}(\psi) = \pmatrix{-w \sin \psi \\ w \cos \psi \\ u \sin \psi - v \cos \psi}$$

Now if you find a line $\mathbf{T}$ that is tangent to the conic, it will have $\mathbf{T}^\top \mathtt{C}^{-1} \mathbf{T}=0$ and the tangent point $\mathbf{Q}=\mathtt{C}^{-1} \mathbf{T}$ lies on $\mathbf{L}$. So $\mathbf{Q}$ is an intersection point.

To solve $\mathbf{T}^\top \mathtt{C}^{-1} \mathbf{T}=0$ for $\psi$ involves solving an equation of the form $$K_0 + K_1 \sin(2 \psi) + K_2 \cos(2 \psi)=0$$ with $$\begin{align} K_0 & = a w^2-2 d u w + f u^2 \\ K_1 & = -2 ( c w^2-w (d v+e u)+f u v)\\ K_2 &= w^2 (b-a)+2 w (d u-e v) + f (v^2-u^2) \end{align}$$

There are two solutions to the above trig equation

$$ \psi = \begin{cases} \frac{1}{2} \left( \tan^{-1} \left( \frac{K_1}{K_2} \right) - \sin^{-1} \left( \frac{2 K_0 + K_2}{\sqrt{K_1^2+K_2^2}} \right) -\frac{\pi}{2}\right) & \mbox{solution 1}\\ \frac{1}{2} \left( \tan^{-1} \left( \frac{K_1}{K_2} \right) + \sin^{-1} \left( \frac{2 K_0 + K_2}{\sqrt{K_1^2+K_2^2}} \right) +\frac{\pi}{2}\right) & \mbox{solution 2} \end{cases} $$

In the end the two intersection points are defined by $\mathbf{Q} = \mathtt{C}^{-1} \mathbf{T}(\psi) $

$$ \mathbf{Q} = \pmatrix{ (c w-d v) \cos \psi + (d u-a w) \sin \psi \\ (b w-e v) \cos \psi + (e u-c w) \sin \psi \\ (e w-f v) \cos \psi + (f u-d w) \sin \psi } $$


Conic $\mathtt{C} = \left[ \matrix{1 & -\tfrac{7}{6} & -3 \\ -\tfrac{7}{6} & 4 & 1 \\ -3 & 1 & \tfrac{13}{6} } \right] $ and line $\mathbf{L} = \pmatrix{3 \\ -2 \\ -7}$. The polar point is $$\mathbf{P} = \mathtt{C}^{-1} \mathbf{L} = \pmatrix{u \\ v \\ w} = \pmatrix{ \tfrac{11208}{5245} \\ \tfrac{1134}{5245} \\ -\tfrac{390}{1049} } $$

The tangent lines are thus $$\mathbf{T}(\psi) = \pmatrix{ \tfrac{390}{1049} \sin\psi \\ -\tfrac{390}{1049} \cos\psi \\ \tfrac{11208}{5245} \sin\psi - \frac{1134}{5245} \cos\psi }$$

The tangency equation $\mathbf{T}^\top \mathtt{C}^{-1} \mathbf{T}=0$ simplifis to the following:

$$ 1.26602894762909 \cos^2 \psi+0.330351717237625 \cos\psi \sin \psi-1.24876309636214=0 $$

with solution

$$ \begin{cases} \psi = 0.299923260411840 & \mbox{solution 1} \\ \psi =-0.0446792696983973 & \mbox{solution 2} \end{cases} $$

The intersection points are

$$ \begin{align} \mathbf{Q} &= \pmatrix{ -0.231100412938826 \\ -0.141550789771816 \\-0.0585999513246922} & \mathbf{Q} &= \pmatrix{ 0.136962490550640 \\-0.0727785333232919 \\0.0794920768997864 } \end{align} $$



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.