hallett@mrsvr.UUCP (Jeff Hallett) (08/09/89)
I have an interesting geometry problem. Given three circles, I need
to be able to find a circle tangent to all three. I realize that,
as specified, there are upto 6 possible solutions, but there is
always one. I place no constraints such as circumscription or
disjoint unions, but would like the solution to find all possible
tangential circles to the given three and provide some mechanism to
choose one from the set.
Any help would be appreciated. I've worked on this a long time and
it is not really a simple geometry problem.
Thanks much.
--
Jeffrey A. Hallett, PET Software Engineering
GE Medical Systems, W641, PO Box 414
Milwaukee, WI 53201
(414) 548-5173 : EMAIL - hallett@postron.gemed.ge.combeshers@cs.cs.columbia.edu (Clifford Beshers) (08/09/89)
In article <859@mrsvr.UUCP> hallett@mrsvr.UUCP (Jeff Hallett) writes:
I have an interesting geometry problem. Given three circles, I need
to be able to find a circle tangent to all three. I realize that,
as specified, there are upto 6 possible solutions, but there is
always one.
Do you mean, for any 3 circles a, b and c there exists a circle d
that is tangent to each of a, b and c? What about the case where
a, b and c share the same center, but each has a radius different
from the other. I can't visualize a circle d tangent to all three.
--
-----------------------------------------------
Cliff Beshers
Columbia University Computer Science Department
beshers@cs.columbia.edutj@XN.LL.MIT.EDU (Thomas E. Jones) (08/09/89)
With the help of Macsyma, I worked out the equations a few months ago.
Here's the program. The few equations should be figurable from this.
It works fairly well. Any suggestions?
------- CUT HERE --------
#include<stdio.h>
#include<math.h>
/* Find Radius and center of a circle that goes through
* 3 points (x1,y1) (x2,y2) (x3,y3)
* Copyright 1988, Thomas E. Jones MIT Lincoln Laboratory tj@xn.ll.mit.edu
* May be freely distributed and used for any purpose.
*/
double PI;
double circ_x(x1,y1,x2,y2,x3,y3)
double x1,y1,x2,y2,x3,y3;
{ double y32,y22,y12,x12,x32,x22,num,den;
y32=y3*y3;
y22=y2*y2;
y12=y1*y1;
x12=x1*x1;
x32=x3*x3;
x22=x2*x2;
num= -( (y2-y1)*y32 + (-y22+y12-x22+x12)*y3 + y1*y22 +
(-y12+x32-x12)*y2+(x22-x32)*y1);
den= 2*((x2-x1)*y3 + (x1-x3)*y2 + (x3-x2)*y1);
if (den==0.0){
return(9999.0);
}
else
return(num/den);
}
double circ_y(x1,y1,x2,y2,x)
double x1,y1,x2,y2,x;
{ double result,num,den;
if((y2==y1))
result=9999.0;
else
result=((x1-x2)*x/(y2-y1)+(y1+y2)/2+(x2-x1)*(x1+x2)/(2*(y2-y1)));
return(result);
}
double angle(x,y)
double x,y;
{ double pi;
pi=3.14159265;
if (x==0){
if (y>=0)
return(pi/2.0);
else
return(3.0*pi/2.0);
}
else {
if (x>=0){
if(y>=0)
return(atan(y/x));
else
return(2*pi+atan(y/x));
}
else {
if(y>=0)
return(pi+atan(y/x));
else
return(pi+atan(y/x));
}
}
}
int circle_conv(x1,y1,x2,y2,x3,y3,x,y,sa,ea,r)
int x1,y1,x2,y2,x3,y3,*x,*y,*r;
double *sa,*ea;
{
double fx1,fy1,fx2,fy2,fx3,fy3,fx,fy,fr;
fx1=x1*1.0;
fy1=y1*1.0;
fx2=x2*1.0;
fy2=y2*1.0;
fx3=x3*1.0;
fy3=y3*1.0;
fx=circ_x(fx1,fy1,fx2,fy2,fx3,fy3);
fy=circ_y(fx1,fy1,fx2,fy2,fx);
fr=sqrt((fx1- fx)*(fx1- fx)+(fy1- fy)*(fy1- fy));
*x=fx;
*y=fy;
*r=fr;
*sa=angle(fx3-fx,fy3-fy);
*ea=angle(fx1-fx,fy1-fy);
if ((fx==9999.0)||(fy==9999.0))
return(0);
else
return(1);
}
/*
main(){
int i,x1,y1,x2,y2,x3,y3,x,y,r;
double sa,ea;
for(i=1;i<=10;i++){
printf("enter x and y\n");
scanf("%lf %lf",&sa,&ea);
printf("%f %f angle=%f\n",sa,ea,angle(sa,ea)*180.0/3.14159);
}
PI=M_PI;
printf("Enter x1,y1,x2,y2,x3,y3\n");
scanf("%d,%d,%d,%d,%d,%d",&x1,&y1,&x2,&y2,&x3,&y3);
circle_conv(x1,y1,x2,y2,x3,y3,&x,&y,&sa,&ea,&r);
printf("center X is %d\n",x);
printf("center Y is %d\n",y);
printf("radius = %d\n",r);
printf("start angle = %f degrees\n",sa*180.0/PI);
printf("end angle = %f degrees\n",ea*180.0/PI);
}
------ END OF PROGRAM -----
--
tj@xn.ll.mit.edu or tj@ll-xn.arpa (one of these should work)
Thomas E. Jones, home (617) 279-0767 work (617) 981-5093jbm@eos.UUCP (Jeffrey Mulligan) (08/09/89)
beshers@cs.cs.columbia.edu (Clifford Beshers) writes: >In article <859@mrsvr.UUCP> hallett@mrsvr.UUCP (Jeff Hallett) writes: > I have an interesting geometry problem. Given three circles, I need > to be able to find a circle tangent to all three. I realize that, > as specified, there are upto 6 possible solutions, but there is > always one. >Do you mean, for any 3 circles a, b and c there exists a circle d >that is tangent to each of a, b and c? What about the case where >a, b and c share the same center, but each has a radius different >from the other. I can't visualize a circle d tangent to all three. Good counterexample. If you accept the following lemma, I think it is obvious that there is no solution for the case of 3 concentric circles: Lemma: If circle A is tangent to circle B at point T, the the points of A excluding T must lie either entirely inside, or entirely outside, of circle B. -- Jeff Mulligan (jbm@aurora.arc.nasa.gov) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-6290
nagle@well.UUCP (John Nagle) (08/09/89)
In classical geometry, this is called the Problem of Appolonius.
There is a compass-and-straightedge solution to this problem, not that
many people care any more.
AutoCAD has a solution to this problem built into it. The solution
used in AutoCAD was new, and had good numerical stability without special
casing. It was developed by Autodesk's staff topologist, and, as far as I
know, has not been published.
John Naglejdchrist@watcgl.waterloo.edu (Dan Christensen) (08/10/89)
In article <4630@eos.UUCP> jbm@eos.UUCP (Jeffrey Mulligan) writes: > >Good counterexample. If you accept the following lemma, >I think it is obvious that there is no solution for the case >of 3 concentric circles: > >Lemma: If circle A is tangent to circle B at point T, the the >points of A excluding T must lie either entirely inside, or entirely >outside, of circle B. I think you have to add the restriction that A and B are distinct circles for this to be true. ---- Dan Christensen, Computer Graphics Lab, jdchrist@watcgl.uwaterloo.ca University of Waterloo, Waterloo, Ont. jdchrist@watcgl.waterloo.edu
schiller@adobe.com (Steve Schiller) (08/12/89)
Actually, in the general case there are eight circles tangent to three given circles. (As people have pointed out there are degenerate cases with less solutions.) The reference I used to solve this problem was a book published around 1900 on conics. Conics seemed to be a hot topic around then. Anyway, I suggest you go to the largest library near you and try to find your own tome on conics. Then you have to translate the mathematical concepts into numerically stable code. It was several years ago when I wrote this code and unfortunately I don't really remember how I did it - or I would tell you, but it was a fairly complicated piece of code. Steve Schiller
hallett@shoreland.uucp (Jeff Hallett x4-6328) (08/18/89)
In article <BESHERS.89Aug8163857@cs.cs.columbia.edu> beshers@cs.cs.columbia.edu (Clifford Beshers) writes: >In article <859@mrsvr.UUCP> hallett@mrsvr.UUCP (Jeff Hallett) writes: > > > I have an interesting geometry problem. Given three circles, I need > to be able to find a circle tangent to all three. I realize that, > as specified, there are upto 6 possible solutions, but there is > always one. > >Do you mean, for any 3 circles a, b and c there exists a circle d >that is tangent to each of a, b and c? What about the case where >a, b and c share the same center, but each has a radius different >from the other. I can't visualize a circle d tangent to all three. Gee, I'm so grateful for this solution. Ok, so perhaps I was too hasty in stating that there is always a solution. I admit that I made the assumption that there was some portion in each circle which was disjoint from the other two. I thereby amend the problem. Rather than critquing the problem, how about a solution which either finds the tangential circles or determines that there is no such circle? Apologies if this sounds needlessly harsh, but I find this type of posting very insulting. It does not help me in my predicament in the least and only makes me feel worse for being unable to solve it in the first place. Thanks in advance. -- Jeffrey A. Hallett, PET Software Engineering GE Medical Systems, W641, PO Box 414 Milwaukee, WI 53201 (414) 548-5173 : EMAIL - hallett@postron.gemed.ge.com
hallett@shoreland.uucp (Jeff Hallett x4-6328) (08/18/89)
In article <13068@well.UUCP> nagle@well.UUCP (John Nagle) writes: > > In classical geometry, this is called the Problem of Appolonius. >There is a compass-and-straightedge solution to this problem, not that >many people care any more. I most certainly care - that is why I posted in the first place. If you could post it, I would appreciate it. > > AutoCAD has a solution to this problem built into it. The solution >used in AutoCAD was new, and had good numerical stability without special >casing. It was developed by Autodesk's staff topologist, and, as far as I >know, has not been published. > How is it invoked? Thanks. -- Jeffrey A. Hallett, PET Software Engineering GE Medical Systems, W641, PO Box 414 Milwaukee, WI 53201 (414) 548-5173 : EMAIL - hallett@postron.gemed.ge.com
cme@cloud9.Stratus.COM (Carl Ellison) (08/18/89)
In article <890@mrsvr.UUCP>, hallett@shoreland.uucp (Jeff Hallett x4-6328) writes: > In article <BESHERS.89Aug8163857@cs.cs.columbia.edu> beshers@cs.cs.columbia.edu (Clifford Beshers) writes: > >In article <859@mrsvr.UUCP> hallett@mrsvr.UUCP (Jeff Hallett) writes: > > >I realize that, > > >as specified, there are upto 6 possible solutions, but there is > > >always one. > >What about the case where > >a, b and c share the same center, but each has a radius different > >from the other. > Ok, so perhaps I was too > hasty in stating that there is always a solution. > [ . . . ] > Rather than critquing the problem, how about a solution which either > finds the tangential circles or determines that there is no such > circle? > [ . . . ] > Apologies if this sounds needlessly harsh, but I find this type of > posting very insulting. It does not help me in my predicament in the > least and only makes me feel worse for being unable to solve it in the > first place. What do you think this newsgroup is, anyway? ...a private, free pool of expertise to solve your work problems for you? I've got a suggestion. Why don't you solve the problem yourself and post your solution? Meanwhile, the practice of providing a counter-example is in the best tradition of mathematics and probably the most helpful thing someone could have done. I believe that you owe a thank-you to Clifford Beshers for doing that. I'm sure he had no intention of insulting you. He's doing what any good mathematician does -- shoot down an improper statement and do it with an economy of words. On the other hand, your attitude about his posting and about the network in general does invite a personal attack. I would suggest that you reconsider both. --Carl Ellison UUCP:: cme@cloud9.Stratus.COM SNail:: Stratus Computer; 55 Fairbanks Blvd.; Marlborough MA 01752 Disclaimer:: (of course)
rokicki@polya.Stanford.EDU (Tomas G. Rokicki) (08/19/89)
This particular puzzle (given three circles, find all circles tangental
to these three) was given as a programming puzzle at the 1987 ACM National
Programming contest. A correct solution to this puzzle by Bob Alverson
of the Stanford team helped Stanford take the title that year. As a
member of the team, I vaguely recall the solution; it was quite clever.
It's also not excruciatingly difficult, simply requiring a few insights.
I encourage everyone to try and find an analytical solution before
reading the spoiler which follows.
Given x_i, y_i, and r_i, 1 <= i <= 3. Find all x, y, and r, such that
the circle described by the latter triple is tangent to all three
specified circles.
If two circles are tangent, then they can either be `interior'
circles, where the larger wholly includes the smaller, or they can
be `exterior' circles, where the only point shared by the circles
is the tangent point.
If C_i (the i'th circle, described by x_i, y_i, r_i) is `interior'
tangent to C (our result circle), then the distance between the
centers must be equal to the difference in the radii of the circles.
(x-x_i)^2 + (y-y_i)^2 = (r-r_i)^2 (1)
If the circles are `exterior' tangent, then the distance must be
equal to the sum of the radii of the circles:
(x-x_i)^2 + (y-y_i)^2 = (r+r_i)^2 (2)
The only difference between these equations is the sign of r_i.
For the remainder of the solution, we solve for interior tangents.
For all solutions, this algorithm should be iterated over both
positive and negative r_i's, for all i. (Since there are three,
we would call it eight times.
If we expand (1), we have
x^2 - 2xx_i + x_i^2 + y^2 - 2yy_i + y_i^2 = r^2 - 2rr_i + r_i^2 (3)
This gives us three equations and three unknowns, but there are some
nasty square terms. Let's introduce another variable, k, such that
x^2 + y^2 - r^2 = k (4)
Now, we can rewrite the above equation as
k - 2xx_i + x_i^2 - 2yy_i + y_i^2 = 2rr_i + r_i^2 (5)
which is nice and linear (the x_i, etc. are constants.) Writing this
as a system of equations, we have
/ 2x_1 2y_1 2r_1 \ / x \ / x_1^2 + y_1^2 - r_1^2 \ / k \
| 2x_1 2y_1 2r_1 | | y | = | x_2^2 + y_2^2 - r_2^2 | + | k | (6)
\ 2x_1 2y_1 2r_1 / \ r / \ x_3^3 + y_3^3 - r_3^3 / \ k /
If the first square matrix is nonsingular, we can easily solve this
system for x, y, and r, in terms of k. Our solution is of the form
x = a_x + b_x k
y = a_y + b_y k (7)
r = a_r + b_r k
where all of the a_i and b_i are numbers dependent only on c_i, so
they can be directly evaluated.
Our only remaining task is to evaluate k. Taking our definition of
k from (4), we have
x^2 + y^2 - r^2 = k (8)
or
(a_x + b_x k)^2 + (a_y + b_y k)^2 - (a_r + b_r k)^2 = k (9)
which is an easily solved quadratic equation for k. If the quadratic
equation has no solutions, there are no solutions for this set of
interior/exterior assignments. Otherwise, we solve for the (up to)
two possible values of k. We reject any solutions which would make
r negative (they will be found by symmetry with another set of
interior/exterior assignments, only with r correctly positive.)
And this gives us x, y, and r, easily.
If the quadratic equation has a `0' term for k^2, then it
is a simple linear equation for k with one solution.
There remain only singularities. Specifically, if the original
input matrix is singular, this solution will fail, even though
there may be solutions. However, it is easy to show (and left as
an exercise) that if there is a solution, a constant may be added
to all input x_i's, y_i's, or r_i's to make the matrix nonsingular.
This constant must then be subtracted (in the case of x_i's or y_i's)
or added (in the case of r_i's) to the resulting x, y, or r,
respectively, to find the real solution.
Writing this up as a numerically stable algorithm must be done
carefully, but is not terribly difficult. It just looks a lot
uglier than it really is.
-tommccaugh@s.cs.uiuc.edu (08/20/89)
This note seems to be a flame...whether its predecessor was or not, this is an inappropriate forum for registering such discontent: perhaps mailing to the individual in question instead would suffice the needs of the writer without consuming network resources intended for the sharing of information.
mccaugh@s.cs.uiuc.edu (08/20/89)
It just occured to me that what I wrote could be construed as a flame: with sincere apologies to the net, I was just trying to "keep the record straight".
hallett@shoreland.uucp (Jeff Hallett x4-6328) (08/22/89)
In article <11391@polya.Stanford.EDU> rokicki@polya.Stanford.EDU (Tomas G. Rokicki) writes: >This particular puzzle (given three circles, find all circles tangental >to these three) was given as a programming puzzle at the 1987 ACM National >Programming contest. A correct solution to this puzzle by Bob Alverson >of the Stanford team helped Stanford take the title that year. As a >member of the team, I vaguely recall the solution; it was quite clever. >It's also not excruciatingly difficult, simply requiring a few insights. > >I encourage everyone to try and find an analytical solution before >reading the spoiler which follows. Thank you very much Tom. Your description has shown me the one idea that I was missing in my solution. I appreciate your time. I am forced now to comment on a previous posting...the person asked if I thought this was a private pool from which I may extract to solve my personal work problems. The answer is no, but rather a pool from which anyone may draw when they have difficulty without fear of ridicule. There is a tremendous amount of expertise on the Net, as demonstrated by Tom, that, without the Net, would never be distributed to the masses. It is my feeling that if someone is going to be on the net, they should be there with the mindset that, if they can pass on info to help another, they should and that if they need help, they can ask. No matter how good someone is, there may come a time when some small thing escapes them - having a forum like this is a tremendous benefit for getting objective commentary and insight. As far as counterexamples go, they are worthwhile when they lead to a solution of the original problem. I think that this is the crucial part missing from the previous poster's tirade. Just demonstrating counterexamples, without any other useful information, is demeaning to someone who may already feel sheepish about asking publicly in the first place. Thanks for all the help. -- Jeffrey A. Hallett, PET Software Engineering GE Medical Systems, W641, PO Box 414 Milwaukee, WI 53201 (414) 548-5173 : EMAIL - hallett@positron.gemed.ge.com
tuna@athena.mit.edu (Kirk 'UhOh' Johnson) (08/23/89)
In article <902@mrsvr.UUCP> hallett@shoreland.UUCP (Jeff Hallett x4-6328) writes: > >As far as counterexamples go, they are worthwhile when they lead to a >solution of the original problem. I think that this is the crucial >part missing from the previous poster's tirade. Just demonstrating >counterexamples, without any other useful information, is demeaning to >someone who may already feel sheepish about asking publicly in the >first place. > i'm sorry, but i completely disagree. i saw both your original posting and the followup which you think was demeaning. by presenting a counterexample, the author of that followup could well have been trying to ensure that they were visualizing the same problem you were or something like that. in any case, i seriously doubt anybody was trying to belittle you. kirk
turk@Apple.COM (Ken "Turk" Turkowski) (08/23/89)
I haven't worked this out, but perhaps the solution would be simpler if solved through the use of conformal mapping in the complex plane, where circles and lines are the same. Specifically, find the conformal mapping that takes one of the circles into a line, find the pencil of circles that are tangent to the two remaining circles, then find the one circle in this pencil that is tangent to the line. Then, apply the inverse conformal mapping and, voila, you have the desired circle. -- Ken Turkowski @ Apple Computer, Inc., Cupertino, CA Internet: turk@apple.com Applelink: TURKOWSKI1 UUCP: sun!apple!turk
jbm@eos.UUCP (Jeffrey Mulligan) (08/24/89)
OK, how about this: First consider the case of just two tangent circles: circle X with radius r, and circle A with radius a. Let d be the distance between the centers. There are 3 cases: 1. A is inside of X: r = d + a 2. X is inside of A: r = a - d 3. A and X are externally tangent: r = d - a Now we impose the condition that circle X must be tangent to a second circle B with radius b. We will rename the distance between the centers of X and A (previously "d") "da", and call the distance between the centers of X and B "db". Now we can write down the same 3 cases for B and X, and equate r's for A and B, for a total of nine cases: 1 (1,1) da + a = db + b da - db = b - a 2 (1,2) da + a = b - db da + db = b - a 3 (1,3) da + a = db - b da - db = -(a + b) 4 (2,1) a - da = db + b da + db = a - b 5 (2,2) a - da = b - db da - db = a - b 6 (2,3) a - da = db - b da + db = a + b 7 (3,1) da - a = db + b da - db = a + b 8 (3,2) da - a = b - db da + db = a + b 9 (3,3) da - a = db - b da - db = a - b We can group these cases: I 6,8 da + db = a + b ellipse II 2,4 da + db = | a - b | ellipse III 1,5,9 da - db = +- ( a - b ) hyperbola IV 3,7 da - db = +- ( a + b ) hyperbola These are all conics having foci at the centers of A and B. For any point on one of these curves, there is a corresponding r for which the circle centered at the chosen point with radius r will be tangent to A and B. Note that for the case of A and B concentric that da=db regardless of r, so there are no solutions to cases III and IV (well, unless a==b). Now if we add a third circle C, we get four more conic sections (defined bewteen A and C or B and C). Any intersections between the new four and the original four should correspond to valid solutions. It is left as an exercise to the reader to show that the max. number of solutions is 9 or whatever it is. -- Jeff Mulligan (jbm@aurora.arc.nasa.gov) NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035 (415) 694-6290
cme@cloud9.Stratus.COM (Carl Ellison) (08/24/89)
In article <902@mrsvr.UUCP>, hallett@shoreland.uucp (Jeff Hallett x4-6328) writes: > [ . . . ] [this newsgroup as] a pool from > which anyone may draw when they have difficulty without fear of > ridicule. > [ . . . ] > Just demonstrating > counterexamples, without any other useful information, is demeaning to > someone who may already feel sheepish about asking publicly in the > first place. If you (or any other reader) is already feeling sheepish or inferior or otherwise insecure about his or her mathematical ability, this message may not help, but this is an important point to me so let me make it again. In mathematics, between mathematicians, providing a counterexample which totally disproves or demolishes someone else's most cherished belief is a normal action -- an opportunity to be siezed if it ever presents itself. Mathematicians do sieze that opportunity. The counterexample is presented dryly or with relish but never with any salesman-like words trying to smooth ruffled feelings or egos. A good mathematician is oblivious to the concept of egos which need soothing. This is *not* a personal attack. This does not drive mathematicians or computer scientists apart. This is behavior between friends. When this happens, the recipient mathematician is thankful. It is only because I like you that I would bother to type in a counterexample shooting down your claim or type this message reminding you that you're not under attack. So, please, don't react as if someone were attacking you. We love you. Finally, there is no reason to post other useful information. Coming up with the counterexample and posting it is already a great gift. It deserves your heartfelt thanks. --Carl Ellison UUCP:: cme@cloud9.Stratus.COM SNail:: Stratus Computer; 55 Fairbanks Blvd.; Marlborough MA 01752 Disclaimer:: (of course)