Date: Fri, 1 Dec 95 10:02:04 GMT
From: [Permission pending]
Subject: Intersecting ellipses
To: rusin@math.niu.edu
Dave
Many thanks for your response.
The data I have is..well my situation is this
I am trying to write a program in prolog to parse set diagrams (eg
Euler's circles) . This is for a study comparing graphical and
non-graphical methods of problem solving.
I have a reliable built-in routine to detect whether any point is in a
box. Box here refers to ellipse's enclosing rectangle.
I can also derive easily the co-ords of the encl rects. top left
corner, its width and depth.
My problem is in handling situations where two ellipses might be
close, not overlapping but where their enclosing rectangles overlap..
I only want to detect 'real' ellipse overlap , not situation where
enclosing rects overlap but not the ellipses contained...
n.b. ellipses in my system can only be drawn along x or y , no
'sloping' ellipses are involved here...
Regards,
[sig deleted -- djr]
==============================================================================
Date: Fri, 1 Dec 95 12:48:33 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: Intersecting ellipses
Interesting. Let me see if I've got this.
You have a rectangle, having vertices (u,v) and (z,w) (and then also
(u,w) and (z,v) ).
Inside you draw the ellipse touching all four sides. This I can convert
easily to standard notation. The center of your box, and thus of your
ellipse, is ( (u+z)/2, (v+w)/2 ). The distances to the sides of the box,
which are then the semi-axes of the ellipse, are |z-u|/2, |w-v|/2.
The equation of the ellipse is then
(x-(u+z)/2)^2/((z-u)/2)^2 + (y-(v+w)/2)^2/((v-w)/2)^2 = 1.
Then you take two such equations and see if there is a common solution (x,y).
[Warning: I am assuming you really want to know if the ellipses intersect. If
you want to know if their _interiors_ intersect, that would allow for the
additional possibility that one ellipse is completely contained within the
other. I'm going to ignore that condition since it is easy to look for
visually unless one ellipse is much smaller than the other.]
Well, finding an intersection takes some doing. To clear up some of
the numerical mess, I would say the following to a fellow math guy:
"Let's translate one of the centers to the origin and rescale the axes
so that one of the ellipses is the unit circle -- and then use
Maple". Here's the result of that:
sun subshell 1 > maple
|\^/| Maple V Release 3 (N I U)
._|\| |/|_. Copyright (c) 1981-1994 by Waterloo Maple Software and the
\ MAPLE / University of Waterloo. All rights reserved. Maple and Maple V
<____ ____> are registered trademarks of Waterloo Maple Software.
| Type ? for help.
> f:=(x-h)^2/a^2+(y-k)^2/b^2=1;
2 2
(x - h) (y - k)
f := -------- + -------- = 1
2 2
a b
> g:=x^2+y^2=1;
2 2
g := x + y = 1
> solve({f,g},{x,y});
2 2 2 2 2 2 2 2 2 2 2 2
- %1 b + %1 a + 2 %1 b h - b h - a k + a b - a
{y = - 1/2 ----------------------------------------------------------, x = %1}
2
a k
2 2 4 4 4 2 2 4 3 4
%1 := RootOf((- 2 a b + b + a ) _Z + (4 b h a - 4 b h) _Z + (- 2 a
4 2 2 2 2 2 2 4 2 2 2 2 4 2
- 2 b a + 2 b a k + 2 a b + 2 a b - 2 b h a + 6 b h
4 2 2 2 2 4 2 2 2 2 4 3
+ 2 a k ) _Z + (- 4 b h a + 4 b h a - 4 b h a k - 4 b h ) _Z
4 2 2 2 2 2 4 2 2 2 4 2 2 4 2
- 2 a k + 2 b h a k + a + 2 b h a - 2 b h a - 2 a b
4 2 2 4 4 4 4 4 4
- 2 a k b + b h + a k + a b )
This tells you that you can easily find the y-coordinate of the points
of intersection if you can get the x-coordinate, but that finding those
requires solving a 4-th degree polynomial, which may or may not have real
solutions, of course.
Indeed, there is a technique known as Sturm sequences which can
determine whether or not a quartic has a real root. I'm not really
sure you want to see this but it is precisely what characterizes the
presence of intersections. There is a polynomial D such that if it is
negative, there are two points where the ellipses overlap. If it is
positive, then the number of intersections is 4 or zero depending on
whether or not two other (similar but simpler) expressions are also
positive -- I won't write them down unless you tell me you need it,
since I think it will be clear from the picture when two ellipses
overlap so much there are four points of intersection.
Now that I had Maple compute the polynomial for me, I'm not sure it
makes any sense even to write this all out. There are 19 lines of
output which say D =
2 2 6 8 2 4 4 4 6 8
(- 2 a b - 2 a - 2 a b + k b ... - 4 a k + a )
(If you decide you do really want this let me know or ask Maple to
compute it for you if you have access to it.)
So here's what I would advise if you need to carry out this procedure:
(1) Write out the two equations of the ellipses as above.
(2) If your equations now have the forms (x-h_i)^2/a_i^2 + (y-k_i)^2/b_i^2=1,
then let h=(h1-h2)/a2, k=(k1-k2)/b2, a=a1/a2, b=b1/b2
(3) Write down the quartic polynomial above and see if it has a real root:
(3a) either compute the Sturm sequences as above to decide, or
(3b) use calculus to see if the minimum of the quartic is negative, or
(3c) turn to any prepackaged root-finder to look for real roots.
If it has a root, then the ellipses intersect; otherwise, not.
I have to say I was surprised to find out how cumbersome the answer is.
The first two steps are pretty natural -- they amount to adjusting things
so you have one unit square centered at the origin, and one other rectangle.
The rest is conceptually easy, but surprisingly inelegant in practice.
dave
==============================================================================
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, [Permission pending] 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.
==============================================================================