Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!synoptics!mips!swrinde!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!dali.cs.montana.edu!milton!uw-beaver!cornell!vax5.cit.cornell.edu!nujy
From: nujy@vax5.cit.cornell.edu
Newsgroups: comp.graphics
Subject: Re: HELP - intersection of 2 circles
Message-ID: <1990Nov17.151429.1071@vax5.cit.cornell.edu>
Date: 17 Nov 90 19:14:29 GMT
References: <GLEICHER.90Nov16004901@OREO.GRAPHICS.CS.CMU.EDU>
Distribution: comp
Lines: 59

The number of intersections is easy.  Given the circles (x1,y1) radius r1
and (x2,y2) radius r2 (where r2 > r1), then the distance between
the centers is d=sqrt((x2-x1)^2+(y2-y1)^2) and:
  abs(d-r2) > r1  --> 0 intersections
  abs(d-r2) = r1  --> 1 intersection (2 degenerate intersections)
  abs(d-r2) < r1  --> 2 intersections
abs(d-r2) is the distance from the center of the smaller circle to the
nearest point on the larger circle.

Finding the actual intersections is a bit harder.  The points must lie
on a line (Lp) perpendicular to the line connecting the centers of the
circles (Lc).
                 / <-- C2
            ___ |            + : center of a circle
  C1 --> _--   -*_           * : intersection
        /      |!           ! : perpendicular line (Lp)
       |     +-|!--|-------+
        _     |!_/    ^--- Lc         That's not too confusing, is it?
          --___-*
                |      Fig. 1
                 
Furthermore these points are the same distance from Lc, call it h.  This
proof is left as an exercise for the reader (LEFR).  Now all we need to
find is the location of the intersection of Lp and Lc (x',y'), and h.

Figure 2 shows the geometry of one case.  We need to solve for p1.
                *_
            r1 /! --__ r2
              / !h    --__
             +-------------+   Fig. 2
             |p1|<---p2--->|
             |<-----d----->|
  r1^2 - p1^2 = h^2            (1) Pythagorean Thm.
  r2^2 - p2^2 = h^2            (2) Ditto
  p1^2 - p2^2 = r1^2 - r2^2    (3) from 1 & 2
  p1 - p2 = (r1^2 - r2^2) / d  (4) from 3 and p1+p2=d
  p1 = (d^2 + r1^2 - r2^2) / 2d        (5) add d to 4, isolate x1

Using the parametric equation of a line, and letting t=p1/d:
  x' = x1 + (x2-x1)*p1 / d,
  y' = y1 + (y2-y1)*p1 / d.
The intersections are at:
  (x'+x",y'+y"), (x'-x",y'-y"),
where
  x" = h*(y2-y1) / d,
  y" = h*(x1-x2) / d,
is LEFR.
The other possible configuration is:
                *_
                !--__ r2
               h! r1--__
                ---+-------+
                |p |<--d-->|
However, the above solution also applies here.  Isn't that nice.
-Chris

  Chris Schoeneman                  |  "I was neat, clean, shaved, and sober,
   nujy@vax5.ccs.cornell.edu        |    and I didn't care who knew it."
                                    |               - Raymond Chandler