Intersecting Circles

From: Martin 
Subject: intersection of two circles
Date: 2 Apr 1995 09:30:50 -0400

Hello Kings of Mathematics,

I read about your group in a journal for network computing. The magazine 
told that it's possible to get a solution of certain mathematical problems
from you.  I hope the problem is difficult enough for you!

The problem is, I do not think the problem is too difficult but for me.
So I have been happy to read about your box. What can I do? - I decided
to tell you the problem:

The Problem
===========

What is the solution to determine the intersection of two given circles
(which don't have the same center and do not only touch in one point)?

The formula of both circles are:

     (y-y01)^2 + (x-x01)^2 = R1^2                              (eq.1)
     (y-y02)^2 + (x-x02)^2 = R2^2                              (eq.2)

     where the center of both is M1: (x01 | y01)
                                 M2: (x02 | y02)

The two points of intersection are A: (x1 | y1) and
                                   B: (x2 | y2).

My Idea for a solution:
====================

In the first shot, I could not solve the two equations in the second power.
I blame myself, but I think it is very tricky.

Then I looked to the geometric circumstances, to get one linear equation
for substitution. I thought:
         __                                  ____
The line AB is devided by the rectangle line M1M2 in two halfs. The slope  
   ____
of M1M2 is m = y02-y01/x02-x01 and well known. So I get a third, linear
equation like
     y = - 1/m * x + b                                           (eq.3).

But there must be another, better idea to grip eq. 1/2! I never eliminate 
the square roots during my evaluations! Can you help me? I'm sorry, it is
a blame for me, but I would be happy to read your hints to me.

I am looking forward to your PM an say thank you!


Regards Martin

Dortmund, Germany

Date: 2 Apr 1995 16:50:57 -0400
From: Dr. Ken
Subject: Re: intersection of two circles

Hello there!

Well, you certainly shouldn't feel bad that you couldn't solve this
problem.  I don't think it's as easy as it looks.  Consider the fact 
that you could change the centers of the circles in such a way that 
the circles would intersect in no points, then one point, then two 
points, then one point, and then no points again.  So the formula for 
the points of intersection is going to be quite complex in order to 
account for that.  

I fed the equations into Mathematica, and it gave me this answer.  For
brevity of notation, I changed the equations to

  (x-a)^2 + (y-b)^2 == R
  
  (x-c)^2 + (y-d)^2 == r.

These are the two points:  

{{x -> (a^4 + a^2*b^2 - 2*a^3*c - b^2*c^2 + 2*a*c^3 - c^4 - 2*a^2*b*d + 
       2*b*c^2*d + a^2*d^2 - c^2*d^2 + a^2*r - 2*a*c*r + c^2*r - a^2*R + 
       2*a*c*R - c^2*R + b*((a - c)^2*
           (-a^4 - 2*a^2*b^2 - b^4 + 4*a^3*c + 4*a*b^2*c - 6*a^2*c^2 - 
             2*b^2*c^2 + 4*a*c^3 - c^4 + 4*a^2*b*d + 4*b^3*d - 
             8*a*b*c*d + 4*b*c^2*d - 2*a^2*d^2 - 6*b^2*d^2 + 4*a*c*d^2 - 
             2*c^2*d^2 + 4*b*d^3 - d^4 + 2*a^2*r + 2*b^2*r - 4*a*c*r + 
             2*c^2*r - 4*b*d*r + 2*d^2*r - r^2 + 2*a^2*R + 2*b^2*R - 
             4*a*c*R + 2*c^2*R - 4*b*d*R + 2*d^2*R + 2*r*R - R^2))^(1/2) - 
       d*((a - c)^2*(-a^4 - 2*a^2*b^2 - b^4 + 4*a^3*c + 4*a*b^2*c - 
             6*a^2*c^2 - 2*b^2*c^2 + 4*a*c^3 - c^4 + 4*a^2*b*d + 
             4*b^3*d - 8*a*b*c*d + 4*b*c^2*d - 2*a^2*d^2 - 6*b^2*d^2 + 
             4*a*c*d^2 - 2*c^2*d^2 + 4*b*d^3 - d^4 + 2*a^2*r + 2*b^2*r - 
             4*a*c*r + 2*c^2*r - 4*b*d*r + 2*d^2*r - r^2 + 2*a^2*R + 
             2*b^2*R - 4*a*c*R + 2*c^2*R - 4*b*d*R + 2*d^2*R + 2*r*R - R^2
             ))^(1/2))/(2*(a - c)*(a^2 + b^2 - 2*a*c + c^2 - 2*b*d + d^2)), 
   y -> (a^2*b + b^3 - 2*a*b*c + b*c^2 + a^2*d - b^2*d - 2*a*c*d + c^2*d - 
       b*d^2 + d^3 + b*r - d*r - b*R + d*R - 
       ((a - c)^2*(-a^4 - 2*a^2*b^2 - b^4 + 4*a^3*c + 4*a*b^2*c - 
            6*a^2*c^2 - 2*b^2*c^2 + 4*a*c^3 - c^4 + 4*a^2*b*d + 4*b^3*d - 
            8*a*b*c*d + 4*b*c^2*d - 2*a^2*d^2 - 6*b^2*d^2 + 4*a*c*d^2 - 
            2*c^2*d^2 + 4*b*d^3 - d^4 + 2*a^2*r + 2*b^2*r - 4*a*c*r + 
            2*c^2*r - 4*b*d*r + 2*d^2*r - r^2 + 2*a^2*R + 2*b^2*R - 
            4*a*c*R + 2*c^2*R - 4*b*d*R + 2*d^2*R + 2*r*R - R^2))^(1/2))/
     (2*(a^2 + b^2 - 2*a*c + c^2 - 2*b*d + d^2))}, 


  {x -> (a^4 + a^2*b^2 - 2*a^3*c - b^2*c^2 + 2*a*c^3 - c^4 - 2*a^2*b*d + 
       2*b*c^2*d + a^2*d^2 - c^2*d^2 + a^2*r - 2*a*c*r + c^2*r - a^2*R + 
       2*a*c*R - c^2*R - b*((a - c)^2*
           (-a^4 - 2*a^2*b^2 - b^4 + 4*a^3*c + 4*a*b^2*c - 6*a^2*c^2 - 
             2*b^2*c^2 + 4*a*c^3 - c^4 + 4*a^2*b*d + 4*b^3*d - 
             8*a*b*c*d + 4*b*c^2*d - 2*a^2*d^2 - 6*b^2*d^2 + 4*a*c*d^2 - 
             2*c^2*d^2 + 4*b*d^3 - d^4 + 2*a^2*r + 2*b^2*r - 4*a*c*r + 
             2*c^2*r - 4*b*d*r + 2*d^2*r - r^2 + 2*a^2*R + 2*b^2*R - 
             4*a*c*R + 2*c^2*R - 4*b*d*R + 2*d^2*R + 2*r*R - R^2))^(1/2) + 
       d*((a - c)^2*(-a^4 - 2*a^2*b^2 - b^4 + 4*a^3*c + 4*a*b^2*c - 
             6*a^2*c^2 - 2*b^2*c^2 + 4*a*c^3 - c^4 + 4*a^2*b*d + 4*b^3*d - 
             8*a*b*c*d + 4*b*c^2*d - 2*a^2*d^2 - 6*b^2*d^2 + 4*a*c*d^2 - 
             2*c^2*d^2 + 4*b*d^3 - d^4 + 2*a^2*r + 2*b^2*r - 4*a*c*r + 
             2*c^2*r - 4*b*d*r + 2*d^2*r - r^2 + 2*a^2*R + 2*b^2*R - 
             4*a*c*R + 2*c^2*R - 4*b*d*R + 2*d^2*R + 2*r*R - R^2))^(1/2))/
     (2*(a - c)*(a^2 + b^2 - 2*a*c + c^2 - 2*b*d + d^2)), 
   y -> (a^2*b + b^3 - 2*a*b*c + b*c^2 + a^2*d - b^2*d - 2*a*c*d + c^2*d - 
       b*d^2 + d^3 + b*r - d*r - b*R + d*R + 
       ((a - c)^2*(-a^4 - 2*a^2*b^2 - b^4 + 4*a^3*c + 4*a*b^2*c - 
            6*a^2*c^2 - 2*b^2*c^2 + 4*a*c^3 - c^4 + 4*a^2*b*d + 4*b^3*d - 
            8*a*b*c*d + 4*b*c^2*d - 2*a^2*d^2 - 6*b^2*d^2 + 4*a*c*d^2 - 
            2*c^2*d^2 + 4*b*d^3 - d^4 + 2*a^2*r + 2*b^2*r - 4*a*c*r + 
            2*c^2*r - 4*b*d*r + 2*d^2*r - r^2 + 2*a^2*R + 2*b^2*R - 
            4*a*c*R + 2*c^2*R - 4*b*d*R + 2*d^2*R + 2*r*R - R^2))^(1/2))/
     (2*(a^2 + b^2 - 2*a*c + c^2 - 2*b*d + d^2))}}


The computer couldn't simplify this any further.  I'm not sure whether 
this will be useful to you, but I thought I'd give it to you anyway.  Let 
us know if you don't understand the syntax of the formula.  Thanks!

-Ken "Dr." Math
    

Date: 04/24/2003 at 18:33:29
From: Cesar
Subject: Intersecting Circles (again)

Dear Dr Math:

I tried feeding these equations into Visual Basic and then 
verified the results using AutoCAD.  I get close values but 
they're not accurate enough (e.g., 4.6356 instead of 4.9243).

Is there another way to solve this problem?

Date: 04/25/2003 at 10:45:08
From: Doctor George
Subject: Re: Intersecting Circles (again)

Hi Cesar,

I would recommend a vector approach to finding the intersection 
points of two circles.

First, let C1 and C2 be the centers of the circles with radii r1 and 
r2, and let d be the distance between C1 and C2.

Now let V1 be the unit vector from C1 to C2, and let V2 be the unit 
vector perpendicular to V1.

Also let V3 be the vector from C1 to one of the intersection points.

Finally, let A be the angle between V1 and V3.

From the law of cosines we know that

        r2^2 = r1^2 + d^2 - 2*r1*d*cos(A)

With this equation we can solve for 'A'.

The intersection points will be

        C1 + [r1*cos(A)]*V1 + [r1*sin(A)]*V2

        C1 + [r1*cos(A)]*V1 - [r1*sin(A)]*V2

Does this make sense to you? Writing your program this way should 
make it much easier to debug.

A separate thread in our archive, 

   Intersections of Circles
   http://mathforum.org/library/drmath/view/51836.html   

shows an equivalent solution expressed algebraically, instead of 
with vectors. 

-Doctor George, The Math Forum
  http://mathforum.org/dr.math/