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>
47 namespace Geom{
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;
58 /* Determine the straight-line distance between the centers. */
59 double d = L2(D);
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 }
73 /* 'point 2' is the point where the line through the circle
74 * intersection points crosses the line between the circle
75 * centers.
76 */
78 /* Determine the distance from point 0 to point 2. */
79 double a = ((r0*r0) - (r1*r1) + (d*d)) / (2.0 * d) ;
81 /* Determine the coordinates of point 2. */
82 Point p2 = X0 + D * (a/d);
84 /* Determine the distance from point 2 to either of the
85 * intersection points.
86 */
87 double h = sqrt((r0*r0) - (a*a));
89 /* Now determine the offsets of the intersection points from
90 * point 2.
91 */
92 Point r = (h/d)*rot90(D);
94 /* Determine the absolute intersection points. */
95 p0 = p2 + r;
96 p1 = p2 - r;
98 return 2;
99 }
101 };
104 #ifdef TEST
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;
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 }
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
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:encoding=utf-8:textwidth=99 :