Path: utzoo!attcan!uunet!wuarchive!csus.edu!ucdavis!ucbvax!pasteur!miro.Berkeley.EDU!ph From: ph@miro.Berkeley.EDU (Paul Heckbert) Newsgroups: comp.graphics Subject: Re: HELP - intersection of 2 circles Message-ID: <8982@pasteur.Berkeley.EDU> Date: 16 Nov 90 23:33:00 GMT References: Sender: news@pasteur.Berkeley.EDU Reply-To: ph@miro.Berkeley.EDU (Paul Heckbert) Distribution: comp Organization: University of California at Berkeley Lines: 34 In article gleicher@CS.CMU.EDU (Michael Gleicher) writes: >I have 2 circles in the plane (x1,y1,r1) and (x2,y2,r2). >I would like to [find their intersection points]. Hi Mike. A simple approach is to first rotate and translate to a new coordinate system (u,v) where circle 1 is centered at (0,0) and circle 2 is centered at (u2,0), where u2 is the distance between circle centers: u2^2=(x2-x1)^2+(y2-y1)^2. Now we solve u^2+v^2=r1^2, (u-u2)^2+v^2=r2^2. Subtracting these two equations, the u^2 and v^2 terms drop and we're left with a linear equation for u: u = u2/2 + (r1^2-r2^2)/(2*u2). v can then be found as +-sqrt(r1^2-u^2) and you'll get 0, 1, or 2 intersection points when r1^2-u^2 is <0, =0, or >0, respectively. It should be possible to do the transformations without trig. A second, nearly equivalent way to set up the problem is to note that you know the three side lengths of the triangle defined by the two centers and one of the intersection points, so you could use the law of cosines to find the angles and do a little trig to compute the answer. A third approach is to crank through the algebra explicitly from the original equations: (x-x1)^2+(y-y1)^2=r1^2, (x-x2)^2+(y-y2)^2=r2^2. Solve for y in one equation, substitute into the other, expand the squares, move the remaining sqrt term to one side of the equation, yielding sqrt(quadratic in x)=(linear in x), so if you square both sides you'll get a quadratic equation which you can solve for x. Paul Heckbert, Computer Science Dept. 570 Evans Hall, UC Berkeley INTERNET: ph@miro.berkeley.edu Berkeley, CA 94720 UUCP: ucbvax!miro.berkeley.edu!ph ps: we don't need no stinkin' resultants.