From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math,comp.graphics.algorithms
Subject: Re: Detecting ellipse intersection
Date: 1 Dec 1995 22:33:21 GMT
On Thu, 30 Nov 1995, Richard Cox wrote:
> Can anyone please tell me how to determine whether 2 ellipses
> intersect?
to which Jordan Elias Massad responded:
>The straightforward way is to solve the 2 equations of the ellipses for x
>& y (or whatever the variables are). If the solutions are real, the
>ellipses should intersect at the resolved coordinates.
Then in article <49ne0p$lio@nntp.crl.com>, wrote:
>Which means solving a quartic equation, which is not a lot of fun.
>There is a reasonable approach, which reduces to something less nasty
>than a general quartic, but I don't have the reference at hand.
>Perhaps some Real Mathematician would take pity and provide a reference
>here?
Hmm, Real Mathematician? Well, I'll have a go anyway, since I just wrote some
details to the original poster.
Basically: the previous posters are correct, you do have to decide if
a quartic has real roots, but this is not all that hard if you don't
need to _find_ the roots, just ascertain their existence.
By suitably translating and scaling, the question reduces to determining
whether or not the ellipse (x-h)^2/a^2 + (y-k)^2/b^2 = 1 meets the
unit circle x^2+y^2=1. If you crank up Maple, you find that this does
indeed amount to determining whether or not a quartic has real roots.
(The roots of the quartic are the x-coordinates of the points of intersection;
the y-coordinates are rational functions of x, a, b, h, and k.)
Interestingly, the resulting quartic is _not_ "generic", that is,
by considering all combinations of a, b, h, k we do _not_ get all
quartics, or even all those in some open set, since the set of collections of
roots of quartics is a variety of dimension 4, whereas the set of collections
of x-coordinates of intersections of ellipses with the circle is a variety
of dimension 3 (Proof: pick any 3 points on the circle: there is a linear
collection of ellipses meeting at those three points, namely a collection of
the form (eq1 + A*(x^2+y^2-1)=0) for a fixed ellipse eq1. If you try to
specify the fourth point as well, you find a unique enclosing ellipse, namely
the original circle.)
On the other hand, given any quartic there is a substitution x -> c*x
which renders the quartic into one which arises from the intersection
of the unit circle and some ellipse. Therefore, I would have to say
that there is _no_ method of determining whether two ellipses
intersect which is simpler than determining if a general quartic has
real roots.
For this problem, all solutions must be isomorphic to: Sturm
sequences. There are three polynomials one can form from the
coefficients of the quartic, one of which is the discriminant D,
with the property that
there are two real roots iff D<0
there are four real roots iff D>0 and the other two polynomials
are also positive.
This is not particularly ugly, unless you try to express the polynomials
algebraically in terms of the coefficients of the quartic, and leave
the quartic in the original general form.
It seems to work better to write the generic ellipse as the solution set
to an equation y=Ax^2+By^2+Cx+D. Then the intersection of the ellipse
with the circle happens where x^2+y^2=1 and y=Ax^2+B(1-x^2)+Cx+D, so that
1 = x^2 + ((A-B)x^2 + Cx + (D+B) )^2.
(You should find it easier now to examine the extent to which this is
a "generic" quartic.)
From this it is not hard to multiply out the coefficients of the quartic,
compute the discriminant as well as the other two polynomials, and check
signs. Life is actually a bit simpler if you perform a linear transformation
on x to remove the coefficient of x^3. But these are all just ways to
break up the calculations into smaller transformations rather than writing
out massive polynomials in a, b, h, and k -- the computations are easier
but the theory is the same.
Frankly, it may be easier in practice simply to find the roots of the
derivative of the quartic and see if at any of those (1 or 3) points
the quartic is negative; this is equivalent to determining if the
quartic has real roots. The first root can be found quickly by
Newton's method, say, and if there are others they can then be found
with the quadratic formula.
Incidentally, I did _not_ say that one could reduce to the first
circular-rectangular configuration by translation, scaling, _and
rotation_, which would be correct, because the original poster
indicated privately that he intended only to consider ellipses with
axes aligned with the coordinate axes. Moreover, his input data was
not quite in the standard form; rather, the ellipse is defined by
giving a pair of opposing vertices of the smallest enclosing rectangle
with horizontal and vertical sides. This makes the formulas a tad
messier yet if one does not reduce to the standard equations for an
ellipse, so that yet another round of transformations is needed at the
beginning.
To recap: given two pairs of opposite vertices of the rectangles,
(1) translate and scale to land at the origin
(2) compute the center and axes of the ellipse
(3) rewrite the ellipse as y=Ax^2+By^2+Cx+D
(4) compute the quartic to be studied
(5) compute its derivative
(6) compute the discriminant, or the value of (4) at the roots of (5)
(7) decide if the quartic (4) has any real roots
Thus you have decided if the ellipses intersect.
dave
==============================================================================
From: kenhill@indirect.com (Ken Hill)
Newsgroups: sci.math,comp.graphics.algorithms
Subject: Re: Detecting ellipse intersection
Date: Sun, 03 Dec 1995 20:19:21 GMT
rusin@washington.math.niu.edu (Dave Rusin) wrote:
> <>
>To recap: given two pairs of opposite vertices of the rectangles,
> (1) translate and scale to land at the origin
> (2) compute the center and axes of the ellipse
> (3) rewrite the ellipse as y=Ax^2+By^2+Cx+D
> (4) compute the quartic to be studied
> (5) compute its derivative
> (6) compute the discriminant, or the value of (4) at the roots of (5)
> (7) decide if the quartic (4) has any real roots
>Thus you have decided if the ellipses intersect.
It's much easier than that folks!
Look, let's take the matrix form of the conic equation. If the conic
is given by A x^2 + 2 B x y + C y^2 + 2 D x + 3 E y + F = 0, then the
equivalent matrix equation is:
[ A B D ] [ x ]
[x y 1] [ B C E ] [ y ] = [ 0 ]
[ D E F ] [ 1 ]
The symetric 3 x 3 matrix in the middle is called the characteristic
matrix of the conic. Let C1 and C2 be the charactersistic matrices of
the two conics in question. We'll also refer to the two conics as C1
and C2, which is a forgivable abuse of notation. Suppose a point X*
is on C1 and also C2. Then, it is easy to show that X* must also be
on a linear combination of C1 and C2, say C1 - t C2. So C1 - t C2 is
the characteristic matrix of a third conic which contains the
intersections of C1 and C2. Now choose t so that C1 - t C2 is
degenerate. That happens when Det(C1 - t C2) = 0. This should remind
you of an eigenvalue problem, right? For the three eigenvalues t1,
t2, t3, C1 - t C2 represents a system of lines (degenerate conics).
The intersection points all must lie on these lines, and thus the
problem is reduced to finding the intersection points of these lines
with C1 or C2, which is easy.
As I mentioned in a previous post, the details are spelled out in my
paper "Matrix-based Ellipse Geometry" in Graphics Gems V. There's
even C source to do the job.
-Ken Hill
kenhill@indirect.com
kenhill@anvil5k.com
"E. E. Cummings" -e. e. cumming's editor.
==============================================================================
From: kenhill@indirect.com (Ken Hill)
Newsgroups: sci.math,comp.graphics.algorithms
Subject: Re: Detecting ellipse intersection
Date: Sun, 03 Dec 1995 20:32:43 GMT
>The intersection points all must lie on these lines, and thus the
>problem is reduced to finding the intersection points of these lines
>with C1 or C2, which is easy.
I neglected to mention that you could get extranious intersections, so
you need to check them all against both conics. Again, this is easy.
-Ken
kenhill@indirect.com
kenhill@anvil5k.com
"E. E. Cummings" -e. e. cumming's editor.
==============================================================================
From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math,comp.graphics.algorithms
Subject: Re: Detecting ellipse intersection
Date: 5 Dec 1995 17:02:50 GMT
In article <49t0if$3of@globe.indirect.com>,
Ken Hill wrote:
>rusin@washington.math.niu.edu (Dave Rusin) wrote:
>
>> <>
>
>>To recap: given two pairs of opposite vertices of the rectangles,
>> (1) translate and scale to land at the origin
>> (2) compute the center and axes of the ellipse
>> (3) rewrite the ellipse as y=Ax^2+By^2+Cx+D
>> (4) compute the quartic to be studied
>> (5) compute its derivative
>> (6) compute the discriminant, or the value of (4) at the roots of (5)
>> (7) decide if the quartic (4) has any real roots
>>Thus you have decided if the ellipses intersect.
>
>
>It's much easier than that folks!
...and proceeded to give a solution which has the geometric elegance I was
hoping for. Just to clarify the relation with the method I proposed, let me
observe that his method asks that we
> Now choose t so that C1 - t C2 is
>degenerate. That happens when Det(C1 - t C2) = 0. This should remind
>you of an eigenvalue problem, right? For the three eigenvalues t1,
>t2, t3, C1 - t C2 represents a system of lines (degenerate conics).
(etc.)
So one has to solve a cubic and then see if there are points of intersection.
Well, that's no different from testing to see if a quartic has real roots
by evaluating it at the roots of its derivative and looking for a sign change;
that's what I called step (6) above. For individual pairs of ellipses, this
is fine, whereas if you need to work symbolically or for some other reason
wish to avoid floating-point calculations, it is possible to draw the
same conclusions without computing the roots by checking the sign of the
discriminant -- that's what I meant by the other option in (6).
So I think Hill's presentation does a nice job of organizing the goals
of the procedure, and saves some of the computational details, but
ultimately comes to the same kind of decision procedure.
I pursued this because when I realized that all quartics could result from
some pair of ellipses, that meant that any approach to determining the
existence of intersections would be equivalent to determining the existence
of real roots for an arbitrary quartic. I haven't done this yet but I
hope to look at Hill's technique to describe how one can geometrically
solve arbitrary quartics. I would imagine this has been done already,
since this was a cottage industry among Arab mathematicians much earlier in
this millenium. I know there were several methods of solving cubic equations
graphically, and real quartics tend to behave like cubics.
dave
==============================================================================
From: kenhill@indirect.com (Ken Hill)
Newsgroups: sci.math,comp.graphics.algorithms
Subject: Re: Detecting ellipse intersection
Date: Wed, 06 Dec 1995 06:09:11 GMT
rusin@washington.math.niu.edu (Dave Rusin) wrote:
>I pursued this because when I realized that all quartics could result from
>some pair of ellipses, that meant that any approach to determining the
>existence of intersections would be equivalent to determining the existence
>of real roots for an arbitrary quartic. I haven't done this yet but I
>hope to look at Hill's technique to describe how one can geometrically
>solve arbitrary quartics. I would imagine this has been done already,
>since this was a cottage industry among Arab mathematicians much earlier in
>this millenium. I know there were several methods of solving cubic equations
>graphically, and real quartics tend to behave like cubics.
Interesting, I hadn't thought about it in that light. I regarded the
technique simply as an applications of quadratic forms. I look
forward to your analysis should you choose to post it.
Regards,
Ken Hill
kenhill@indirect.com
kenhill@anvil5k.com
"E. E. Cummings" -e. e. cumming's editor.