At 09:32 23/05/2002, Gerald K. Dobiasovsky wrote:
From: "Morgan L. Owens" Sent: Wednesday, May 22, 2002 3:28 PM
I think I'm outclassed. I mean, here's me still tinkering in two dimensions... Next thing to do would be to parameterise things a bit...
Having tinkered some, I've now got a parameterised version. p1-p4 are the centres of four circles. The inversion group is then illustrated. What made this tricky is my insistence that the radii of the circles be as "natural" as possible; for any (finite) distribution of points (at least two) in the plane there are (uncountably) many ways of assigning radii to circles centred on those points such that none can be enlarged without it overlapping some other. This is the case even with a mere two points: one can be huge and the other tiny, or one can be tiny and the other huge, but the most "natural" choice would be that they're equal-sized. Ditto for n points equally spaced around a circle; if I were to have three points forming the vertices of an equilateral triangle the natural solution would be three mutually tangent circles of equal size, not one huge circle with two tiny nubs. The solution is fairly robust, based on my half-baked test procedures - the result is independent of which order points are specified, and there don't seem to be any nasty discontinuities where a circle suddenly jumps in size when its position is tweaked slightly. This should make it ripe for animation. So, after a quick rendition of the happy Job's Done Shuffle: 4movable{ ; For any set of four points in the plane, there are an infinite number ; of solutions to the problem of mutually tangent circles centred on those ; points. For the sake of definiteness, some more or less arbitrary methods ; have to be applied. First, we find the distances between each pair of ; points. d21=d12=cabs(p1-p2) d31=d13=cabs(p1-p3) d41=d14=cabs(p1-p4) d32=d23=cabs(p2-p3) d42=d24=cabs(p2-p4) d43=d34=cabs(p3-p4) ; The radius of each circle is _at least_ half the distance between its centre ; and the centre of the nearest other circle. r1=d12 r2=d21 r3=d31 r4=d41 r1=(d13<r1)*d13+(d13>=r1)*r1 r2=(d23<r2)*d23+(d23>=r2)*r2 r3=(d32<r3)*d32+(d32>=r3)*r3 r4=(d42<r4)*d42+(d42>=r4)*r4 r1=(d14<r1)*d14+(d14>=r1)*r1 r2=(d24<r2)*d24+(d24>=r2)*r2 r3=(d34<r3)*d34+(d34>=r3)*r3 r4=(d43<r4)*d43+(d43>=r4)*r4 ;Yeah, I said "half", didn't I? r1=r1/2 r2=r2/2 r3=r3/2 r4=r4/2 ; We subtract these radii from our distances, leaving only some possible "excess" d21=d12=d12-r1-r2 d31=d13=d13-r1-r3 d41=d14=d14-r1-r4 d32=d23=d23-r2-r3 d42=d24=d24-r2-r4 d43=d34=d34-r3-r4 ; At this point the two nearest circles are already tangent to each other. The ; others, however, may still have some distance remaining between themselves ; and the others. This remaining distance is what I referred to above as the ; "excess". For two circles that are tangent, this excess is zero. ; ; If both of the remaining circles are free to grow (a circle is "free to ; grow" when it is not tangent to any other circle), we want both to be as ; large as possible - we don't want, for example, one to be so large that the ; other is unable to grow any further at all. The most sensible solution is ; for each to take half of the excess that lies between them; unless of course ; that would cause one to overlap either of the first two circles, in which ; case the growth is limited by the excess lying between it and the fixed ; circle. ; We note which circles can still grow (i.e. nonzero excess between it and all ; others) g1=(d12*d13*d14>0) g2=(d21*d23*d24>0) g3=(d31*d32*d34>0) g4=(d41*d42*d43>0) if(g1) ma=1,da1=0,da2=d12,da3=d13,da4=d14 elseif(g2) ma=2,da1=d21,da2=0,da3=d23,da4=d24 elseif(g3) ma=3,da1=d31,da2=d32,da3=0,da4=d34 elseif(g4) ma=4,da1=d41,da2=d42,da3=d43,da4=0 else ma=0 endif if(g1 && ma!=1) mb=1,db1=0,db2=d12,db3=db3,db4=d14 elseif(g2 && ma!=2) mb=2,db1=d21,db2=0,db3=d23,db4=d24 elseif(g3 && ma!=3) mb=3,db1=d31,db2=d32,db3=0,db4=d34 elseif(g4 && ma!=4) mb=4,db1=d41,db2=d42,db3=d43,db4=0 else mb=0 endif ; ma and mb are the only two (if any) circles that can still grow. if(ma!=0) ; At least one circle can still grow. if(mb==0) ; and it's the only one, so we grow it as big as it will go. if(ma==1) d=da2 d=(da3<d)*da3+(da3>=d)*d d=(da4<d)*da4+(da4>=d)*d r1=r1+d elseif(ma==2) d=da1 d=(da3<d)*da3+(da3>=d)*d d=(da4<d)*da4+(da4>=d)*d r2=r2+d elseif(ma==3) d=da1 d=(da2<d)*da2+(da2>=d)*d d=(da4<d)*da4+(da4>=d)*d r3=r3+d elseif(ma==4) d=da1 d=(da2<d)*da2+(da2>=d)*d d=(da3<d)*da3+(da3>=d)*d r4=r4+d endif else ; Both can grow, so we grow them both as much as they can go. if((ma==1 && mb==2)||(ma==2 && mb==1)) dab=d12 elseif((ma==1 && mb==3)||(ma==3 && mb==1)) dab=d13 elseif((ma==1 && mb==4)||(ma==4 && mb==1)) dab=d14 elseif((ma==2 && mb==3)||(ma==3 && mb==2)) dab=d23 elseif((ma==2 && mb==4)||(ma==4 && mb==2)) dab=d24 elseif((ma==3 && mb==4)||(ma==4 && mb==3)) dab=d34 endif da=dab/2 if(ma!=1) da=(da1<da)*da1+(da1>=da)*da endif if(ma!=2) da=(da2<da)*da2+(da2>=da)*da endif if(ma!=3) da=(da3<da)*da3+(da3>=da)*da endif if(ma!=4) da=(da4<da)*da4+(da4>=da)*da endif db=dab/2 if(mb!=1) db=(db1<db)*db1+(db1>=db)*db endif if(mb!=2) db=(db2<db)*db2+(db2>=db)*db endif if(mb!=3) db=(db3<db)*db3+(db3>=db)*db endif if(mb!=4) db=(db4<db)*db4+(db4>=db)*db endif if(ma==1) r1=r1+da elseif(ma==2) r2=r2+da elseif(ma==3) r3=r3+da elseif(ma==4) r4=r4+da endif if(mb==1) r1=r1+db elseif(mb==2) r2=r2+db elseif(mb==3) r3=r3+db elseif(mb==4) r4=r4+db endif endif endif rr1=sqr(r1) rr2=sqr(r2) rr3=sqr(r3) rr4=sqr(r4) z=pixel: inside=0 if(|z-p1|<rr1) z=r1*conj(r1/(z-p1))+p1 inside=1 elseif(|z-p2|<rr2) z=r2*conj(r2/(z-p2))+p2 inside=1 elseif(|z-p3|<rr3) z=r3*conj(r3/(z-p3))+p3 inside=1 elseif(|z-p4|<rr4) z=r4*conj(r4/(z-p4))+p4 inside=1 endif inside} Morgan L. Owens "Dance all around the World with me."