6
$\begingroup$

From 5 points on an ellipse I can get the ellipse characteristics (center, radii, angle) by solving a $5\times5$ system (the ellipse equation applied on each point).

But this is costly when called billion times per second, plus in my case I only want the ellipse center. -> Is there a cheaper way to get the ellipse center only (either geometric, algebraic or numeric), without solving the full $5\times5$ system ?

NB: for now (see end part of here) I am using an iterative solution finding the 2 most distant points, i.e. the main axis, and taking the middle. But it is still costly, and of course inelegant.

EDIT 1: if it helps, I could also provide the tangents at points.

EDIT 2: note that the full ellipse equation is not a quadratic form (since not centred at (0,0)).

$\endgroup$
  • 1
    $\begingroup$ You are assuming the ellipse is in general position, ie. possibly rotated axes? $\endgroup$ – hardmath Dec 9 '15 at 2:29
  • 1
    $\begingroup$ Yes. real world 2D ellipses, with their full 5 degrees of freedom. $\endgroup$ – Fabrice NEYRET Dec 9 '15 at 3:07
  • $\begingroup$ I wonder if the set of triangles that could be made with the five points would be helpful... $\endgroup$ – abiessu Dec 9 '15 at 3:18
  • $\begingroup$ EDIT: if it helps, I could also provide the tangents at points. $\endgroup$ – Fabrice NEYRET Dec 9 '15 at 3:55
  • 1
    $\begingroup$ @FabriceNEYRET: If you do have five tangents, then you can do what I described in my answer using the coordinates of these tangents (i.e. the vector $(a,b,c)^T$ for a line $ax+by+c=0$) and then you can avoid the dialization step but simply take the matrix as it is and multiply it with $(0,0,1)$. $\endgroup$ – MvG Dec 9 '15 at 4:34
4
$\begingroup$

Here is how I compute a conic without $5\times5$ equations, based on my background in projective geometry.

Finding the matrix

Start with homogeneous coordinates, i.e. you have five points

$$ A=\begin{pmatrix}A_x\\A_y\\1\end{pmatrix} \qquad\cdots\qquad E=\begin{pmatrix}E_x\\E_y\\1\end{pmatrix} $$

Now a point $P$ lies on the conic with these five points iff

$$[A,C,E][B,D,E][A,D,P][B,C,P] - [A,D,E][B,C,E][A,C,P][B,D,P] = 0$$

where I use $[\cdot,\cdot,\cdot]$ to denote a determinant. Now you may know that you can write a $3\times3$ matrix as a triple product, e.g.

$$[A,D,P] = \langle A\times D,P\rangle$$

Combine two of these and you have a quadratic form with a rank 1 matrix in the center:

$$[A,D,P][B,C,P] = \langle P,A\times D\rangle\cdot\langle B\times C,P\rangle = P^T\cdot(A\times D)\cdot(B\times C)^T\cdot P$$

So the original equation boils down to $P^TMP=0$ using the following matrix:

\begin{align*} M &=\phantom+ [A,C,E][B,D,E]\cdot(A\times D)\cdot(B\times C)^T \\ &\phantom=- [A,D,E][B,C,E]\cdot(A\times C)\cdot(B\times D)^T \end{align*}

You probably should symmetrize your final result as well, i.e. compute $M+M^T$.

So you have to compute four determinants, four cross products, two outer products, two scalar times matrix products, one matrix subtraction and one matrix addition. But all of the vectors and matrices will be $3\times 3$ only, and you never have to pivot, never have to make any case distinctions. If you work with the homogeneous coordinates using the representatives given above, many numbers in your computations will be equal to $1$, which can be used to further simplify an implementation.

You may notice that the determinants in the left part of each line are just $E$ plugged into the quadratic form you get from the right part of the other line. So if evaluating quadratic forms is any easier for you than computing determinants, go ahead and re-use the matrices you need for the right hand side in any case.

Finding the center

Now you want the center of that beast. The center is the pole of the line at infinity. For that you need the dual matrix, which algebraically is cheapest to compute using the classical adjoint. Multiply that matrix by $(0,0,1)$ and you have the homogeneous coordinates of the center. Divide the first two coordinates by the third to get back to inhomogeneous coordinates.

$\endgroup$
  • $\begingroup$ Oh yes, in homogeneous coordinates we do have a quadratic form ! $\endgroup$ – Fabrice NEYRET Dec 9 '15 at 4:13
  • $\begingroup$ All this is pretty neat, thanks a lot ! Though, I still have to digest some parts: why symmetrising M ? shouldn't it come already symmetric if the points are on an ellipse ? Finding the center: I got the how, but not the why: what represent the inverse of the matrix ( quadric form $3\times 3$) ? I understand that the matrix $Q_3$ is composed of $[[Q_2,Q_2\cdot C],[{}^t(Q_2\cdot C), {}^tCQ_2\cdot C]]$. Also, I'm curious: what is the geometric interpretation of the iff conditions expressed as 5 det - 5 det = 0 ? (maybe a ref would do it ?). thanks ! $\endgroup$ – Fabrice NEYRET Dec 9 '15 at 4:35
  • $\begingroup$ For in-depth discussion I suggest Perspectives in Projective Geometry. $M$ isn't symmetric up front since the rank 1 matrices from which it got build were insymmetric. The inverse of a conic corresponding to $P^T\cdot M\cdot P=0$ is a dual conic $g^T\cdot M^{-1}\cdot g=0$ describing all the tangent lines $g$ to the conic with points $P$. Also check pole and polar. The basic equation can be understood in several ways, e.g. using cross ratios, or a pencil spanned by two degenerate conics. New question. $\endgroup$ – MvG Dec 9 '15 at 4:41
  • $\begingroup$ ok I see, any $[[Q_2,X],[{}^tY,{}^tC⋅Q_2⋅C]]$ would do, as long as $X+Y=2Q_2⋅C$, which your symmetrization $\frac{M+{}^tM}2$ exactly does. So, the unique ellipse equation in 2D could corresponds to several different $3\times 3$ matrices. It's funny that the iff condition, yielding to a unique $3\times 3$ matrix, does not "choose" the symmetric one. But I guess it has deep reason one can understand if mastering projective geometry ;-) $\endgroup$ – Fabrice NEYRET Dec 9 '15 at 4:59

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.