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.