If I have three spheres that intersect, how can I find the two points at
which they intersect?

Was there a 'geometry of the sphere' web page posted once here?

Post a reply to this message

As I think about it the five possible cases are:
    no intersection
    1 pt
    2 pts
    a circle
    a sphere

For my application at hand, I am interested in the 2 pt scenario, if that
makes the answer easier for anyone to find, thanks.

________________
Greg M. Johnson
No intentional use of own fonts whatsoever.


"Greg M. Johnson" wrote:

> If I have three spheres that intersect, how can I find the two points at
> which they intersect?
>
> Was there a 'geometry of the sphere' web page posted once here?

Post a reply to this message

"Greg M. Johnson" wrote:
> 
> As I think about it the five possible cases are:
>     no intersection
>     1 pt
>     2 pts
>     a circle
>     a sphere
> 
> For my application at hand, I am interested in the 2 pt scenario, if that
> makes the answer easier for anyone to find, thanks.
> 

I'm not so sure, it has been some time, since i did that kind of math stuff, but
the general equation of a sphere is:

 ( x - xm )^2 + ( y - ym )^2 + ( z - zm )^2 - r^2 = 0

with <xm, ym, zm> the center of the sphere and r the radius.  

Make it 3 different spheres and all equations being zero -> you should get the
result.

(I'm not totally sure about this, so feel free to correct me if there is a
mistake)

BTW, i suspect this does not solve your problem, because it's not a numerical
method, but maybe it helps somehow.

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
Homepage: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

Christoph Hormann wrote:
> 
> "Greg M. Johnson" wrote:
> >
> > As I think about it the five possible cases are:
> >     no intersection
> >     1 pt
> >     2 pts
> >     a circle
> >     a sphere
> >
> > For my application at hand, I am interested in the 2 pt scenario, if that
> > makes the answer easier for anyone to find, thanks.
> >
> 
> I'm not so sure, it has been some time, since i did that kind of math stuff, but
> the general equation of a sphere is:
> 
>  ( x - xm )^2 + ( y - ym )^2 + ( z - zm )^2 - r^2 = 0
> 
> with <xm, ym, zm> the center of the sphere and r the radius.
> 
> Make it 3 different spheres and all equations being zero -> you should get the
> result.
> 
> (I'm not totally sure about this, so feel free to correct me if there is a
> mistake)
> 
> BTW, i suspect this does not solve your problem, because it's not a numerical
> method, but maybe it helps somehow.
> 
> Christoph
> 
> --
> Christoph Hormann <chr### [at] gmxde>
> Homepage: http://www.schunter.etc.tu-bs.de/~chris/

You're on the right track.

You need three equations in three unknowns: ( In VERY general terms!)

a(x1)^2 + b(y1)^2 + c(z1)^2 = 0
d(x2)^2 + e(y2)^2 + f(z2)^2 = 0
g(x3)^2 + h(y3)^2 + i(z3)^2 = 0

You now simultainously solve the three equations. If they are liniarly
independent the there will be 2 uneque salutions, the points of
intersection. Now there is a gotch in this. I know how to do this with
liniar equations, BUT, I don't know if it can be donw like this with
quadratic equations. Probubly have to look in an advanced math textbook.
I don'e recall second or higher order equations being covered in my
liniar algebera course.

Ken Matassa

Post a reply to this message

Using this technique I came up with HUGELY complicated equations for one (???) point.
I haven't put this into pov yet, but I fear that my the values of the variables in my
equations will boild down to:

(0-0)/(0-0)
.

Ken Matassa wrote:

> Christoph Hormann wrote:
> >
> > "Greg M. Johnson" wrote:
> > >
> > > As I think about it the five possible cases are:
> > >     no intersection
> > >     1 pt
> > >     2 pts
> > >     a circle
> > >     a sphere
> > >
> > > For my application at hand, I am interested in the 2 pt scenario, if that
> > > makes the answer easier for anyone to find, thanks.
> > >
> >
> > I'm not so sure, it has been some time, since i did that kind of math stuff, but
> > the general equation of a sphere is:
> >
> >  ( x - xm )^2 + ( y - ym )^2 + ( z - zm )^2 - r^2 = 0
> >
> > with <xm, ym, zm> the center of the sphere and r the radius.
> >
> > Make it 3 different spheres and all equations being zero -> you should get the
> > result.
> >
> > (I'm not totally sure about this, so feel free to correct me if there is a
> > mistake)
> >
> > BTW, i suspect this does not solve your problem, because it's not a numerical
> > method, but maybe it helps somehow.
> >
> > Christoph
> >
> > --
> > Christoph Hormann <chr### [at] gmxde>
> > Homepage: http://www.schunter.etc.tu-bs.de/~chris/
>
> You're on the right track.
>
> You need three equations in three unknowns: ( In VERY general terms!)
>
> a(x1)^2 + b(y1)^2 + c(z1)^2 = 0
> d(x2)^2 + e(y2)^2 + f(z2)^2 = 0
> g(x3)^2 + h(y3)^2 + i(z3)^2 = 0
>
> You now simultainously solve the three equations. If they are liniarly
> independent the there will be 2 uneque salutions, the points of
> intersection. Now there is a gotch in this. I know how to do this with
> liniar equations, BUT, I don't know if it can be donw like this with
> quadratic equations. Probubly have to look in an advanced math textbook.
> I don'e recall second or higher order equations being covered in my
> liniar algebera course.
>
> Ken Matassa

Post a reply to this message

For the three spheres you get the 3 functions:

I:   ( x - x0 )^2 + ( y - y0 )^2 + ( z - z0 )^2 - r0 ^2
II:  ( x - x1 )^2 + ( y - y1 )^2 + ( z - z1 )^2 - r1 ^2
III: ( x - x2 )^2 + ( y - y2 )^2 + ( z - z2 )^2 - r2 ^2

with <xn,yn,zn> as the middle points and rn the radii

When you set I == II and I == III and simplify this you get two
equations of the following form:

A*x+B*y+C*z==D

(with A,B,C,D as constants)

These are the equations for the planes in which the cutting circles lie
in. Now you just need to calcualte the cutting line of these two planes.
And finally cut one of your inital sphere with this line... then you get
your desired points.

I didn't care about the specal cases here (0/1/infitely many points)
because you said you were only interested in the 2 points-case.

I don't know if there is a more easy way but it should work this way.
You can also get a general formula from this.

Hope this helps
- Micha

Post a reply to this message

On Thu, 19 Oct 2000 20:57:21 -0700, Ken Matassa <kma### [at] pacbellnet>
wrote:

>I don'e recall second or higher order equations being covered in my
>liniar algebera course.

That's why it's called _linear_ algebra :)


Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] usanet
TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message

I tried exactly this approach and got multiple divide by zero messages.

#declare x1=0;
#declare y1=0;
#declare z1=0;
#declare r1=1.3;          //really this sphere plus radius to touch it!

#declare x2=2;
#declare y2=0;
#declare z2=0;
#declare r2=1.3;

#declare x3=0.5;
#declare y3=0;
#declare z3=.5;
#declare r3=1.3;

#declare a32=-2*x3+2*x2;
#declare b32=-2*y3+2*y2;
#declare c32=-2*z3+2*z2;
#declare d32=r3^2-r2^2+x3^2-x2^2+y3^2-y2^2+z3^2-z2^2 ;

#declare a31=-2*x3+2*x1;
#declare b31=-2*y3+2*y1;
#declare c31=-2*z3+2*z1;
#declare d31=r3^2-r1^2+x3^2-x1^2+y3^2-y1^2+z3^2-z1^2 ;

#declare a21=-2*x2+2*x1;
#declare b21=-2*y2+2*y1;
#declare c21=-2*z2+2*z1;
#declare d21=r2^2-r1^2+x2^2-x1^2+y2^2-y1^2+z2^2-z1^2 ;

#declare
z4=((d21*a31-d31*a21)/(a21*b31-b21*a21)+(d32*a21=d21*a32)/(a21*b32-a32*b21))

                /

((c21*a32-c32*a21)/(a21*b32-a32*b21)+(a21*c32-c21*a31)/(a21*b31-b21*a31));

#declare
y4=z4*(c21*a32-c32*a21)/(a21*b32-a32*b21)+(d21*a32-d32*a21)/(a21*b32-a32*b21);

#declare x4=-y4*b21/a21-z4*c21/a21-d21/a21;




Micha Riser wrote:

> For the three spheres you get the 3 functions:
>
> I:   ( x - x0 )^2 + ( y - y0 )^2 + ( z - z0 )^2 - r0 ^2
> II:  ( x - x1 )^2 + ( y - y1 )^2 + ( z - z1 )^2 - r1 ^2
> III: ( x - x2 )^2 + ( y - y2 )^2 + ( z - z2 )^2 - r2 ^2
>
> with <xn,yn,zn> as the middle points and rn the radii
>
> When you set I == II and I == III and simplify this you get two
> equations of the following form:
>
> A*x+B*y+C*z==D
>
> (with A,B,C,D as constants)
>
> These are the equations for the planes in which the cutting circles lie
> in. Now you just need to calcualte the cutting line of these two planes.
> And finally cut one of your inital sphere with this line... then you get
> your desired points.
>
> I didn't care about the specal cases here (0/1/infitely many points)
> because you said you were only interested in the 2 points-case.
>
> I don't know if there is a more easy way but it should work this way.
> You can also get a general formula from this.
>
> Hope this helps
> - Micha

Post a reply to this message

Greg M.Johnson wrote:
> ...
> #declare
>
z4=((d21*a31-d31*a21)/(a21*b31-b21*a21)+(d32*a21=d21*a32)/(a21*b32-a32*b21))
>
>                 /
>
> ((c21*a32-c32*a21)/(a21*b32-a32*b21)+(a21*c32-c21*a31)/(a21*b31-b21*a31));
> ...

I think I've spotted some errors here.

Try to do the following changes to the above formula:

(d32*a21 = d21*a32)  = = = > (a21*d32 - d21*a32)

(a21*b31-b21*a21)  = = = > (a21*b31-b21*a31)

(a21*c32-c21*a31)  = = = > (a21*c31-c21*a31)


The first expression was written as a logical one: (something = otherthing)
In the other two the indexes were in error.

I'm on a journey to north Norway now, so I don't have
any more time to check the rest of your code.


Regards,

Tor Olav Kristensen

Post a reply to this message

Greg M. Johnson wrote:
> 
> If I have three spheres that intersect, how can I find the two points
> at which they intersect?

This macro will return one of the two intersection points you want, or
bomb out with an error if the spheres do not intersect in the way you
want; if you don't want it to bomb, then you can change it to do
something else.

I tested it and it seems to work.  There may be a simpler algorithm.

// START OF MACRO CODE

#macro IntersectThreeSpheres(pA,rA,pB,rB,pC,rC,fW)
// pX = center of sphere X
// rX = radius of sphere X
// fW= flag controlling which of two possible values to use
//     >0 if you want the upper one, <0 if the lower

#local vB=pB-pA;
#local vC=pC-pA;
#local vF=pC-pB;

#local vN=vcross(vC,vB);

#if(vlength(vN)=0) #error "Centers of circles lie on one line.\n" #end

#local vN=vnormalize(vN);

#local dAB=vlength(vB);
#local dAC=vlength(vC);
#local dBC=vlength(vF);

#if(dAB>rA+rB | rA>dAB+rB | rB>rA+dAB)
  #error "First and second spheres do not intersect.\n"
#end

#if(dAC>rA+rC | rA>dAC+rC | rC>rA+dAC)
  #error "First and third spheres do not intersect.\n"
#end

#if(dBC>rB+rC | rB>dBC+rC | rC>rB+dBC)
  #error "Second and third spheres do not intersect.\n"
#end

#local dKAB=(rA*rA-rB*rB+dAB*dAB)/2/dAB;
#local dKAC=(rA*rA-rC*rC+dAC*dAC)/2/dAC;
#local vB=vnormalize(vB);
#local vC=vnormalize(vC);

#local sD=vdot(vN,vcross(vB,vC));

#local sN=vdot(vN,pA);
#local sB=vdot(vB,pA)+dKAB;
#local sC=vdot(vC,pA)+dKAC;

#local pM=<vdot(<sN,vN.y,vN.z>,vcross(<sB,vB.y,vB.z>,<sC,vC.y,vC.z>))/sD,
           vdot(<vN.x,sN,vN.z>,vcross(<vB.x,sB,vB.z>,<vC.x,sC,vC.z>))/sD,
           vdot(<vN.x,vN.y,sN>,vcross(<vB.x,vB.y,sB>,<vC.x,vC.y,sC>))/sD>;

#debug concat("<",str(pM.x,0,3),",",str(pM.y,0,3),",",str(pM.z,0,3),">\n")

#local sD=vlength(pA-pM);
#local sD=rA*rA-sD*sD;
#if(sD<0) #error "Not the kind of intersection you're after.\n" #end
#local sD=sqrt(sD);

( (fW>0)?(pM+vN*sD):(pM-vN*sD) )

#end

//END OF MACRO CODE

Hope this helps,
John
(posted and e-mailed)
-- 
ICQ: 46085459

Post a reply to this message