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. ==============================================================================