Path: utzoo!utgpu!news-server.csri.toronto.edu!dgp.toronto.edu!stam Newsgroups: comp.graphics From: stam@dgp.toronto.edu (Jos Stam) Subject: Re: HELP - intersection of 2 circles Message-ID: <1990Nov16.125308.18816@jarvis.csri.toronto.edu> Organization: DGP, Dynamic Graphics Project, University of Toronto References: Distribution: comp Date: 16 Nov 90 17:53:08 GMT Lines: 43 In article gleicher@CS.CMU.EDU (Michael Gleicher) writes: > >Help! I can't seem to find a good way to do this. > >I have 2 circles in the plane (x1,y1,r1) and (x2,y2,r2), I know they aren't >the same. >I would like to know how many intersection points they have (0,1 or 2) and >where these intersection points are. I'd like an analytic solution (closed >form). I believe that one should exist, but i can't seem to work out the >geometry. Any help would be GREATLY appreciated (a reference, a sketch of a >proof, an equation, some C code, ...). > >Thanks, > Mike Your problem can be stated more generally as: find the intersections (common roots) of two algebraic curves: F(x,y) = 0 G(x,y) = 0 If F is of degree n and G is of degree m, then there are nm solutions by Bezout's theorem (counting complex roots and roots "at infinity"). Of course assuming F and G have no common components... There are several methods to solve the above system, one way is to calculate the resultant, which can be given by the determinant of the Sylvester matrix of F and G. Kajiya has applied this stuff to ray-trace parametric patches: J.T. Kajiya, "Ray Tracing Parametric Patches", SIGGRAPH 82 Proceedings, 245-259. In the case of your circles, the resultant will be a polynomial of degree 4 in y (or x). Solving the polynomial will give you y_1 and y_2 (you are only interested in real solutions I assume...). Plugging these values back in the circle equations will give you the corresponding x_1 and x_2. As I'm lazy I will not calculate the resultant for you. good luck. Jos (there is probably a more clever way to do things for your special case...)