src/2geom/circle-circle.cpp

   1 /* circle_circle_intersection() *
   2  * Determine the points where 2 circles in a common plane intersect.
   3  *
   4  * int circle_circle_intersection(
   5  *                                // center and radius of 1st circle
   6  *                                double x0, double y0, double r0,
   7  *                                // center and radius of 2nd circle
   8  *                                double x1, double y1, double r1,
   9  *                                // 1st intersection point
  10  *                                double *xi, double *yi,
  11  *                                // 2nd intersection point
  12  *                                double *xi_prime, double *yi_prime)
  13  *
  14  * This is a public domain work. 3/26/2005 Tim Voght
  15  * Ported to lib2geom, 2006 Nathan Hurst
  16  *
  17  * Copyright 2006 Nathan Hurst <njh@mail.csse.monash.edu.au>
  18  *
  19  * This library is free software; you can redistribute it and/or
  20  * modify it either under the terms of the GNU Lesser General Public
  21  * License version 2.1 as published by the Free Software Foundation
  22  * (the "LGPL") or, at your option, under the terms of the Mozilla
  23  * Public License Version 1.1 (the "MPL"). If you do not alter this
  24  * notice, a recipient may use your version of this file under either
  25  * the MPL or the LGPL.
  26  *
  27  * You should have received a copy of the LGPL along with this library
  28  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  29  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  30  * You should have received a copy of the MPL along with this library
  31  * in the file COPYING-MPL-1.1
  32  *
  33  * The contents of this file are subject to the Mozilla Public License
  34  * Version 1.1 (the "License"); you may not use this file except in
  35  * compliance with the License. You may obtain a copy of the License at
  36  * http://www.mozilla.org/MPL/
  37  *
  38  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  39  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  40  * the specific language governing rights and limitations.
  41  *
  42  */
  43 #include <stdio.h>
  44 #include <math.h>
  45 #include <2geom/point.h>
  46
  47 namespace Geom{
  48
  49 int circle_circle_intersection(Point X0, double r0,
  50                                Point X1, double r1,
  51                                Point & p0, Point & p1)
  52 {
  53   /* dx and dy are the vertical and horizontal distances between
  54    * the circle centers.
  55    */
  56   Point D = X1 - X0;
  57
  58   /* Determine the straight-line distance between the centers. */
  59   double d = L2(D);
  60
  61   /* Check for solvability. */
  62   if (d > (r0 + r1))
  63   {
  64     /* no solution. circles do not intersect. */
  65     return 0;
  66   }
  67   if (d <= fabs(r0 - r1))
  68   {
  69     /* no solution. one circle is contained in the other */
  70     return 1;
  71   }
  72
  73   /* 'point 2' is the point where the line through the circle
  74    * intersection points crosses the line between the circle
  75    * centers.
  76    */
  77
  78   /* Determine the distance from point 0 to point 2. */
  79   double a = ((r0*r0) - (r1*r1) + (d*d)) / (2.0 * d) ;
  80
  81   /* Determine the coordinates of point 2. */
  82   Point p2 = X0 + D * (a/d);
  83
  84   /* Determine the distance from point 2 to either of the
  85    * intersection points.
  86    */
  87   double h = sqrt((r0*r0) - (a*a));
  88
  89   /* Now determine the offsets of the intersection points from
  90    * point 2.
  91    */
  92   Point r = (h/d)*rot90(D);
  93
  94   /* Determine the absolute intersection points. */
  95   p0 = p2 + r;
  96   p1 = p2 - r;
  97
  98   return 2;
  99 }
 100
 101 };
 102
 103
 104 #ifdef TEST
 105
 106 void run_test(double x0, double y0, double r0,
 107               double x1, double y1, double r1)
 108 {
 109   double x3, y3, x3_prime, y3_prime;
 110
 111   printf("x0=%F, y0=%F, r0=%F, x1=%F, y1=%F, r1=%F :\n",
 112           x0, y0, r0, x1, y1, r1);
 113   Geom::Point p0, p1;
 114   Geom::circle_circle_intersection(Geom::Point(x0, y0), r0,
 115                                    Geom::Point(x1, y1), r1,
 116                                    p0, p1);
 117   printf("  x3=%F, y3=%F, x3_prime=%F, y3_prime=%F\n",
 118             p0[0], p0[1], p1[0], p1[1]);
 119 }
 120
 121 int main(void)
 122 {
 123   /* Add more! */
 124   run_test(-1.0, -1.0, 1.5, 1.0, 1.0, 2.0);
 125   run_test(1.0, -1.0, 1.5, -1.0, 1.0, 2.0);
 126   run_test(-1.0, 1.0, 1.5, 1.0, -1.0, 2.0);
 127   run_test(1.0, 1.0, 1.5, -1.0, -1.0, 2.0);
 128   exit(0);
 129 }
 130 #endif
 131
 132 /*
 133   Local Variables:
 134   mode:c++
 135   c-file-style:"stroustrup"
 136   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 137   indent-tabs-mode:nil
 138   fill-column:99
 139   End:
 140 */
 141 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :