Thread Subject: How can I increase this solve syntax ?

tic;
solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+(y20-4.0166)^2+(znn-1)^2=(1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20','y20','znn');
toc
Elapsed time is 0.117134 seconds.

the elapsed time is to high, because this solving is in the for loop for millions counters.

PL help me that how can I increase the speed ?

On 5/22/2011 9:38 PM, mahdi roozbhani wrote:
> tic;
> solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+
> (y20-4.0166)^2+(znn-1)^2=(1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20',
> 'y20','znn');
> toc
> Elapsed time is 0.117134 seconds.
>
> the elapsed time is to high, because this solving is in the for loop for millions counters.
>
> PL help me that how can I increase the speed ?

Is the above timing from the first try? First time you call solve it is slow
(cach effect), second time should be faster.

This is what I get on my PC (second try)

EDU>> tic;
solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+(y20-4.0166)^2+(znn-1)^2=
(1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20','y20','znn');
toc
Elapsed time is 0.060639 seconds.

On the same PC, this is what I get using Mathematica

-----------------------------
{time,result}=Timing[Solve[{(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2== (1+1)^2,(x20-4.7476)^2+
(y20-4.0166)^2+(znn-1)^2== (1+1)^2,(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2==(1+1)^2},{x20,y20,znn}]];

time
---------------------------
Out[17]= 0.016000000000000014


--Nasser

In every loop the numbers are changed, so every solving is supposed as a first time. this equations are for tangenting one sphere to other 3 spheres with different radious.

I am thankful, if u can find a way for my problem.
------------------------------------------------------------------------------------------------------------------
"Nasser M. Abbasi" <nma@12000.org> wrote in message <ircpv6$8tf$4@speranza.aioe.org>...
> On 5/22/2011 9:38 PM, mahdi roozbhani wrote:
> > tic;
> > solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+
> > (y20-4.0166)^2+(znn-1)^2=(1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20',
> > 'y20','znn');
> > toc
> > Elapsed time is 0.117134 seconds.
> >
> > the elapsed time is to high, because this solving is in the for loop for millions counters.
> >
> > PL help me that how can I increase the speed ?
>
> Is the above timing from the first try? First time you call solve it is slow
> (cach effect), second time should be faster.
>
> This is what I get on my PC (second try)
>
> EDU>> tic;
> solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+(y20-4.0166)^2+(znn-1)^2=
> (1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20','y20','znn');
> toc
> Elapsed time is 0.060639 seconds.
>
> On the same PC, this is what I get using Mathematica
>
> -----------------------------
> {time,result}=Timing[Solve[{(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2== (1+1)^2,(x20-4.7476)^2+
> (y20-4.0166)^2+(znn-1)^2== (1+1)^2,(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2==(1+1)^2},{x20,y20,znn}]];
>
> time
> ---------------------------
> Out[17]= 0.016000000000000014
>
>
> --Nasser

On 5/22/2011 10:16 PM, mahdi roozbhani wrote:
> In every loop the numbers are changed, so every solving is supposed as a first time.
> this equations are for tangenting one sphere to other 3 spheres with different radious.
>
> I am thankful, if u can find a way for my problem.

Please do not top post.

If you are running it in a loop, then timing is not due to first time calling solve,
since clearly solve will have been called the first time in the loop. That bit
of delay at the first time will average out.

I meant solve seems to be slow the very first time it is used, after you start
Matlab, that is, due to loading sysm engine and such.

I do not know how to speed symbolic solve. May be get faster PC if the performance
is not ok for you, or try adding RAM if your Ram is low, or try
numerical approach to your problem, or contact Mathworks and tell them to speed
up solve in the next version. Not sure what else to suggest.

hth,
--Nasser

> ------------------------------------------------------------------------------------------------------------------
> "Nasser M. Abbasi"<nma@12000.org> wrote in message<ircpv6$8tf$4@speranza.aioe.org>...
>> On 5/22/2011 9:38 PM, mahdi roozbhani wrote:
>>> tic;
>>> solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+
>>> (y20-4.0166)^2+(znn-1)^2=(1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20',
>>> 'y20','znn');
>>> toc
>>> Elapsed time is 0.117134 seconds.
>>>
>>> the elapsed time is to high, because this solving is in the for loop for millions counters.
>>>
>>> PL help me that how can I increase the speed ?
>>
>> Is the above timing from the first try? First time you call solve it is slow
>> (cach effect), second time should be faster.
>>
>> This is what I get on my PC (second try)
>>
>> EDU>> tic;
>> solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+(y20-4.0166)^2+(znn-1)^2=
>> (1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20','y20','znn');
>> toc
>> Elapsed time is 0.060639 seconds.
>>
>> On the same PC, this is what I get using Mathematica
>>
>> -----------------------------
>> {time,result}=Timing[Solve[{(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2== (1+1)^2,(x20-4.7476)^2+
>> (y20-4.0166)^2+(znn-1)^2== (1+1)^2,(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2==(1+1)^2},{x20,y20,znn}]];
>>
>> time
>> ---------------------------
>> Out[17]= 0.016000000000000014
>>
>>
>> --Nasser

TX friend.
----------------------------------------------------------------------------------------------------------
"Nasser M. Abbasi" <nma@12000.org> wrote in message <ircr7r$b4u$2@speranza.aioe.org>...
> On 5/22/2011 10:16 PM, mahdi roozbhani wrote:
> > In every loop the numbers are changed, so every solving is supposed as a first time.
> > this equations are for tangenting one sphere to other 3 spheres with different radious.
> >
> > I am thankful, if u can find a way for my problem.
>
> Please do not top post.
>
> If you are running it in a loop, then timing is not due to first time calling solve,
> since clearly solve will have been called the first time in the loop. That bit
> of delay at the first time will average out.
>
> I meant solve seems to be slow the very first time it is used, after you start
> Matlab, that is, due to loading sysm engine and such.
>
> I do not know how to speed symbolic solve. May be get faster PC if the performance
> is not ok for you, or try adding RAM if your Ram is low, or try
> numerical approach to your problem, or contact Mathworks and tell them to speed
> up solve in the next version. Not sure what else to suggest.
>
> hth,
> --Nasser
>
> > ------------------------------------------------------------------------------------------------------------------
> > "Nasser M. Abbasi"<nma@12000.org> wrote in message<ircpv6$8tf$4@speranza.aioe.org>...
> >> On 5/22/2011 9:38 PM, mahdi roozbhani wrote:
> >>> tic;
> >>> solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+
> >>> (y20-4.0166)^2+(znn-1)^2=(1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20',
> >>> 'y20','znn');
> >>> toc
> >>> Elapsed time is 0.117134 seconds.
> >>>
> >>> the elapsed time is to high, because this solving is in the for loop for millions counters.
> >>>
> >>> PL help me that how can I increase the speed ?
> >>
> >> Is the above timing from the first try? First time you call solve it is slow
> >> (cach effect), second time should be faster.
> >>
> >> This is what I get on my PC (second try)
> >>
> >> EDU>> tic;
> >> solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+(y20-4.0166)^2+(znn-1)^2=
> >> (1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20','y20','znn');
> >> toc
> >> Elapsed time is 0.060639 seconds.
> >>
> >> On the same PC, this is what I get using Mathematica
> >>
> >> -----------------------------
> >> {time,result}=Timing[Solve[{(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2== (1+1)^2,(x20-4.7476)^2+
> >> (y20-4.0166)^2+(znn-1)^2== (1+1)^2,(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2==(1+1)^2},{x20,y20,znn}]];
> >>
> >> time
> >> ---------------------------
> >> Out[17]= 0.016000000000000014
> >>
> >>
> >> --Nasser

"mahdi roozbhani" <m.m.roozbahani@gmail.com> wrote in message <ircqik$itv$1@newscl01ah.mathworks.com>...
> In every loop the numbers are changed, so every solving is supposed as a first time. this equations are for tangenting one sphere to other 3 spheres with different radious.
> ......
> > On 5/22/2011 9:38 PM, mahdi roozbhani wrote:
> > > solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+
> > > (y20-4.0166)^2+(znn-1)^2=(1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20',
> > > 'y20','znn');
- - - - - - - - - - -
  If you are solving the same type of intersecting sphere problem repeatedly with differences only in the radii and centers, I am very surprised you are using 'solve' for this purpose.

  There is an efficient procedure which matlab can easily carry out for finding the solution(s) to this problem using specific formulas which I am certain is far, far faster than anything that could be achieved by 'solve'. The first step is finding the intersection between three planes, two of them orthogonal to lines connecting centers, and the third plane containing the three centers. Matlab is specifically designed to rapidly solve the problem of intersection of three planes. The second step is to locate a point, actually two points in opposite directions, along the line of intersection of the first two planes which are the correct distance from that first intersection point, again something that would be accomplished very quickly.

  In your second post you described the problem as "tangenting one sphere to other 3 spheres with different radious", which if I interpret your words correctly is not the same problem as the sphere intersection problem but one that can be solved in an equally efficient manner.

  About the only purpose I can see for using 'solve' would be to use it just once with generalized symbols for the centers and radii, and thereafter to implement the resulting formulas with direct numerical, rather than symbolic, calculations. I do have serious doubts that the formulas 'solve' would come up with would constitute the most efficient algorithm for doing this, however.

Roger Stafford

Mr Roger:
Be honest, I did not understand completely your solution, if u can describe for me more.I would be so thankful.
for better explanation of my problem;
I have three spheres with different radios and we have the coordinates of these three spheres(it should be mentioned that there is no limitation that the three spheres are tangented to each other or not previously). Now I wanna calculate the coordinate of fourth sphere which is tangented to theses three spheres.
TX friend.
----------------------------------------------------------------------------------------------------------------------
"Roger Stafford" wrote in message <ird26c$7kk$1@newscl01ah.mathworks.com>...
> "mahdi roozbhani" <m.m.roozbahani@gmail.com> wrote in message <ircqik$itv$1@newscl01ah.mathworks.com>...
> > In every loop the numbers are changed, so every solving is supposed as a first time. this equations are for tangenting one sphere to other 3 spheres with different radious.
> > ......
> > > On 5/22/2011 9:38 PM, mahdi roozbhani wrote:
> > > > solve('(x20-6.5563)^2+(y20-6.3529)^2+(znn-1)^2=(1+1)^2','(x20-4.7476)^2+
> > > > (y20-4.0166)^2+(znn-1)^2=(1+1)^2','(x20-8.1058)^2+(y20-4.017)^2+(znn-1)^2=(1+1)^2','x20',
> > > > 'y20','znn');
> - - - - - - - - - - -
> If you are solving the same type of intersecting sphere problem repeatedly with differences only in the radii and centers, I am very surprised you are using 'solve' for this purpose.
>
> There is an efficient procedure which matlab can easily carry out for finding the solution(s) to this problem using specific formulas which I am certain is far, far faster than anything that could be achieved by 'solve'. The first step is finding the intersection between three planes, two of them orthogonal to lines connecting centers, and the third plane containing the three centers. Matlab is specifically designed to rapidly solve the problem of intersection of three planes. The second step is to locate a point, actually two points in opposite directions, along the line of intersection of the first two planes which are the correct distance from that first intersection point, again something that would be accomplished very quickly.
>
> In your second post you described the problem as "tangenting one sphere to other 3 spheres with different radious", which if I interpret your words correctly is not the same problem as the sphere intersection problem but one that can be solved in an equally efficient manner.
>
> About the only purpose I can see for using 'solve' would be to use it just once with generalized symbols for the centers and radii, and thereafter to implement the resulting formulas with direct numerical, rather than symbolic, calculations. I do have serious doubts that the formulas 'solve' would come up with would constitute the most efficient algorithm for doing this, however.
>
> Roger Stafford

"mahdi roozbhani" <m.m.roozbahani@gmail.com> wrote in message <irddv8$606$1@newscl01ah.mathworks.com>...
> Mr Roger:
> Be honest, I did not understand completely your solution, if u can describe for me more.I would be so thankful.
> for better explanation of my problem;
> I have three spheres with different radios and we have the coordinates of these three spheres(it should be mentioned that there is no limitation that the three spheres are tangented to each other or not previously). Now I wanna calculate the coordinate of fourth sphere which is tangented to theses three spheres.
> TX friend.
- - - - - - - - - - -
  Hello Mahdi. The following code assumes that c1, c2, and c3 are each three-element vectors containing the center coordinates of three spheres and that scalars r1, r2, and r3 are their respective radii. The scalar r0 is the desired radius of a fourth sphere that is to be externally tangent to each of the three spheres. Vectors of the two possible centers of this fourth sphere, c0 and c00, are computed. These will lie on symmetrically opposite sides of the plane containing the three centers.

 c21 = c2-c1;
 c31 = c3-c1;
 r10 = r1+r0;
 t1 = cross(c21,c31);
 t2 = dot(t1,t1);
 t3 = ((r10^2-(r2+r0)^2+dot(c21,c21))*cross(c31,t1) - ...
       (r10^2-(r3+r0)^2+dot(c31,c31))*cross(c21,t1))/(2*t2);
 t4 = r10^2-dot(t3,t3);
 t3 = c1+t3;
 if t4 >= 0
  t1 = sqrt(t4/t2)*t1;
  c0 = t3+t1;
  c00 = t3-t1;
 else
  fprintf('No solution possible!\n')
 end

  That these solutions are correct can be verified by testing that the distance between centers c0 and c1 is r0+r1, and similarly for c2 and c3, as well as like tests using c00.

  I am sure you will find that the time consumed in a single pass through this code will be very much less than the 0.117134 seconds you quoted using 'solve'. Moreover, this code can easily be modified (vectorized) to handle arrays containing many combinations of centers and radii, so as to avoid for-looping.

  I have not given an explanation here of the reasoning behind the above operations. Such an explanation would follow along the lines I have previously described, but if you feel the need to have some more detailed explanation of the individual steps above, please let me know.

Roger Stafford

Great...(I'm not allowed to continue about appreciation)
if you can clarify t1 t2 t3 and t4 in geometry manner,I will make sense the way.
You told that I can promote this solution,take for example, tangenting one sphere on four spheres or tangentiong one sphere on two spheres. How can I apply theses type of tangenting in your code?



  
------------------------------------------------------------------------------------------------------------------------
"Roger Stafford" wrote in message <ire9pq$4so$1@newscl01ah.mathworks.com>...
> "mahdi roozbhani" <m.m.roozbahani@gmail.com> wrote in message <irddv8$606$1@newscl01ah.mathworks.com>...
> > Mr Roger:
> > Be honest, I did not understand completely your solution, if u can describe for me more.I would be so thankful.
> > for better explanation of my problem;
> > I have three spheres with different radios and we have the coordinates of these three spheres(it should be mentioned that there is no limitation that the three spheres are tangented to each other or not previously). Now I wanna calculate the coordinate of fourth sphere which is tangented to theses three spheres.
> > TX friend.
> - - - - - - - - - - -
> Hello Mahdi. The following code assumes that c1, c2, and c3 are each three-element vectors containing the center coordinates of three spheres and that scalars r1, r2, and r3 are their respective radii. The scalar r0 is the desired radius of a fourth sphere that is to be externally tangent to each of the three spheres. Vectors of the two possible centers of this fourth sphere, c0 and c00, are computed. These will lie on symmetrically opposite sides of the plane containing the three centers.
>
> c21 = c2-c1;
> c31 = c3-c1;
> r10 = r1+r0;
> t1 = cross(c21,c31);
> t2 = dot(t1,t1);
> t3 = ((r10^2-(r2+r0)^2+dot(c21,c21))*cross(c31,t1) - ...
> (r10^2-(r3+r0)^2+dot(c31,c31))*cross(c21,t1))/(2*t2);
> t4 = r10^2-dot(t3,t3);
> t3 = c1+t3;
> if t4 >= 0
> t1 = sqrt(t4/t2)*t1;
> c0 = t3+t1;
> c00 = t3-t1;
> else
> fprintf('No solution possible!\n')
> end
>
> That these solutions are correct can be verified by testing that the distance between centers c0 and c1 is r0+r1, and similarly for c2 and c3, as well as like tests using c00.
>
> I am sure you will find that the time consumed in a single pass through this code will be very much less than the 0.117134 seconds you quoted using 'solve'. Moreover, this code can easily be modified (vectorized) to handle arrays containing many combinations of centers and radii, so as to avoid for-looping.
>
> I have not given an explanation here of the reasoning behind the above operations. Such an explanation would follow along the lines I have previously described, but if you feel the need to have some more detailed explanation of the individual steps above, please let me know.
>
> Roger Stafford

On 5/23/2011 8:25 PM, mahdi roozbhani wrote:
> Great...(I'm not allowed to continue about appreciation)
> if you can clarify t1 t2 t3 and t4 in geometry manner,I will make sense the way.
> You told that I can promote this solution,take for example, tangenting one
> sphere on four spheres or tangentiong one sphere on two spheres. How can I apply
>theses type of tangenting in your code?
>

do not top post.

>
>
>
> ------------------------------------------------------------------------------------------------------------------------
> "Roger Stafford" wrote in message<ire9pq$4so$1@newscl01ah.mathworks.com>...
>> "mahdi roozbhani"<m.m.roozbahani@gmail.com> wrote in message<irddv8$606$1@newscl01ah.mathworks.com>...
>>> Mr Roger:
>>> Be honest, I did not understand completely your solution, if u can describe for me

"mahdi roozbhani" <m.m.roozbahani@gmail.com> wrote in message <irf8eg$pii$1@newscl01ah.mathworks.com>...
> Great...(I'm not allowed to continue about appreciation)
> if you can clarify t1 t2 t3 and t4 in geometry manner,I will make sense the way.
> You told that I can promote this solution,take for example, tangenting one sphere on four spheres or tangentiong one sphere on two spheres. How can I apply theses type of tangenting in your code?
- - - - - - - - - -
  As to your question about the four (mysterious) 't' variables, first, c21 and c31 are vectors pointing from centers c1 to c2 and c1 to c3. Their cross product t1 is a vector orthogonal to each of these and thus is orthogonal to the plane containing all three centers. Scalar t2 is the square of its magnitude.

  As I mentioned earlier, the first phase of the computation finds the intersection between three planes. One plane contains the unknown fourth center c0 and is orthogonal to the vector c21, and the second plane contains c0 and is orthogonal to c31. The third plane contains all three centers. The vector t3 is defined as that vector which points from center c1 to this three-plane intersection point, and is found from the solution to three simultaneous linear equations as explained below, given by the indicated expression for t3.

  Since it lies entirely in the plane of the three centers, the vector t3 must necessarily be orthogonal to the line segment between the above three-plane intersection point and c0, so the square of this segment length is equal to (r1+r0)^2 minus the square of the length of t3, which gives scalar t4. However, if t4 turns out to be a negative quantity, that means there can be no solution - the three spheres are too far apart for the fourth sphere to be tangent to all three simultaneously. Otherwise, by dividing vector t1 by the square root of t2 which normalizes it, and multiplying by the square root of t4, we get a rescaled vector t1 which extends exactly from the above three-plane intersection point to c0 itself.

  Finally by adding c1 to t3 we get a new value for t3 which makes it a vector extending from the origin to the three-plane intersection. By adding and also subtracting the above rescaled t1 to this new t3, we get the two possible solutions for c0 which in the code have been called c0 and c00.

  The above three simultaneous linear equations can be obtained as follows. Temporarily shift the coordinate origin to the center point c1, so that the three centers are now located at [0,0,0], c21, and c31, and call the coordinates of these latter two c21 = [a,b,c] and c31 = [d,e,f]. Also call R1 = r1+r0, R2 = r2+r0, and R3 = r3+r0. Designate the unknown, (shifted) coordinates of c0-c1 as [x,y,z]. Then we have the three equations to be satisfied by x, y, and z:

  x^2 + y^2 + z^2 = R1^2
 (x-a)^2 + (y-b)^2 + (z-c)^2 = R2^2
 (x-d)^2 + (y-e)^2 + (z-f)^2 = R3^2

By subtracting the first equation from the other two, transposing known terms to the right, and dividing by -2 we arrive at the two equations

 a*x + b*y + c*z = (R1^2-R2^2+a^2+b^2+c^2)/2 = (R1^2-R2^2+dot(c21,c21))/2
 d*x + e*y + f*z = (R1^2-R3^2+d^2+e^2+f^2)/2 = (R1^2-R3^2+dot(c31,c31))/2

Each of these two equations taken separately defines a plane which contains the desired center at c0-c1 and is orthogonal to the vectors c21 = [a,b,c] and c31 = [d,e,f], respectively. Taken together they define a line of intersection which runs through c0-c1 and is orthogonal to the plane of the three centers. We now add as a third equation the equation of the three centers:

 dot(cross(c21,c31),[x,y,z]) =
 (b*f-c*e)*x + (c*d-a*f)*y + (a*e-b*d)*z = 0

(which forces [x,y,z] away from c0-c1 and down onto the three centers' plane.) Taking all three linear equations together gives us the desired point of intersection of the three planes, and t3 = [x,y,z] will be its solution. It can be checked using either Cramer's rule or by vector analysis methods (or even by using 'solve') that the expression given in the code for t3 is indeed the unique solution for these three equations.

  As to your second question regarding solving this problem for more or less than three other spheres - with four spheres instead it is an overdetermined problem and in general has no solution, and with two or fewer spheres an underdetermined problem and in general has infinitely many solutions. Therefore the solution I have given only applies to the case of three other spheres.

  It should be noted here that besides the case when t4 is negative, another case when the code I have given would fail occurs when the three centers are colinear, which would in general have infinitely many solutions. This would be indicated by having a zero value for t1 = cross(c21,c31) and would produce a NaN or infinity in the division by t2 while computing t3.

Roger Stafford

"Roger Stafford" wrote in message <irh11m$33p$1@newscl01ah.mathworks.com>...
> "mahdi roozbhani" <m.m.roozbahani@gmail.com> wrote in message <irf8eg$pii$1@newscl01ah.mathworks.com>...
> > Great...(I'm not allowed to continue about appreciation)
> > if you can clarify t1 t2 t3 and t4 in geometry manner,I will make sense the way.
> > You told that I can promote this solution,take for example, tangenting one sphere on four spheres or tangentiong one sphere on two spheres. How can I apply theses type of tangenting in your code?
> - - - - - - - - - -
> As to your question about the four (mysterious) 't' variables, first, c21 and c31 are vectors pointing from centers c1 to c2 and c1 to c3. Their cross product t1 is a vector orthogonal to each of these and thus is orthogonal to the plane containing all three centers. Scalar t2 is the square of its magnitude.
>
> As I mentioned earlier, the first phase of the computation finds the intersection between three planes. One plane contains the unknown fourth center c0 and is orthogonal to the vector c21, and the second plane contains c0 and is orthogonal to c31. The third plane contains all three centers. The vector t3 is defined as that vector which points from center c1 to this three-plane intersection point, and is found from the solution to three simultaneous linear equations as explained below, given by the indicated expression for t3.
>
> Since it lies entirely in the plane of the three centers, the vector t3 must necessarily be orthogonal to the line segment between the above three-plane intersection point and c0, so the square of this segment length is equal to (r1+r0)^2 minus the square of the length of t3, which gives scalar t4. However, if t4 turns out to be a negative quantity, that means there can be no solution - the three spheres are too far apart for the fourth sphere to be tangent to all three simultaneously. Otherwise, by dividing vector t1 by the square root of t2 which normalizes it, and multiplying by the square root of t4, we get a rescaled vector t1 which extends exactly from the above three-plane intersection point to c0 itself.
>
> Finally by adding c1 to t3 we get a new value for t3 which makes it a vector extending from the origin to the three-plane intersection. By adding and also subtracting the above rescaled t1 to this new t3, we get the two possible solutions for c0 which in the code have been called c0 and c00.
>
> The above three simultaneous linear equations can be obtained as follows. Temporarily shift the coordinate origin to the center point c1, so that the three centers are now located at [0,0,0], c21, and c31, and call the coordinates of these latter two c21 = [a,b,c] and c31 = [d,e,f]. Also call R1 = r1+r0, R2 = r2+r0, and R3 = r3+r0. Designate the unknown, (shifted) coordinates of c0-c1 as [x,y,z]. Then we have the three equations to be satisfied by x, y, and z:
>
> x^2 + y^2 + z^2 = R1^2
> (x-a)^2 + (y-b)^2 + (z-c)^2 = R2^2
> (x-d)^2 + (y-e)^2 + (z-f)^2 = R3^2
>
> By subtracting the first equation from the other two, transposing known terms to the right, and dividing by -2 we arrive at the two equations
>
> a*x + b*y + c*z = (R1^2-R2^2+a^2+b^2+c^2)/2 = (R1^2-R2^2+dot(c21,c21))/2
> d*x + e*y + f*z = (R1^2-R3^2+d^2+e^2+f^2)/2 = (R1^2-R3^2+dot(c31,c31))/2
>
> Each of these two equations taken separately defines a plane which contains the desired center at c0-c1 and is orthogonal to the vectors c21 = [a,b,c] and c31 = [d,e,f], respectively. Taken together they define a line of intersection which runs through c0-c1 and is orthogonal to the plane of the three centers. We now add as a third equation the equation of the three centers:
>
> dot(cross(c21,c31),[x,y,z]) =
> (b*f-c*e)*x + (c*d-a*f)*y + (a*e-b*d)*z = 0
>
> (which forces [x,y,z] away from c0-c1 and down onto the three centers' plane.) Taking all three linear equations together gives us the desired point of intersection of the three planes, and t3 = [x,y,z] will be its solution. It can be checked using either Cramer's rule or by vector analysis methods (or even by using 'solve') that the expression given in the code for t3 is indeed the unique solution for these three equations.
>
> As to your second question regarding solving this problem for more or less than three other spheres - with four spheres instead it is an overdetermined problem and in general has no solution, and with two or fewer spheres an underdetermined problem and in general has infinitely many solutions. Therefore the solution I have given only applies to the case of three other spheres.
>
> It should be noted here that besides the case when t4 is negative, another case when the code I have given would fail occurs when the three centers are colinear, which would in general have infinitely many solutions. This would be indicated by having a zero value for t1 = cross(c21,c31) and would produce a NaN or infinity in the division by t2 while computing t3.
>
> Roger Stafford

Hi,

These might be of some interest to OP
http://www.diku.dk/hjemmesider/ansatte/rfonseca/implementations/apollonius3d.pdf

http://home.bway.net/lewis/lewbrid.pdf (problem 4 /pg 13 deals with his 2nd question)

Regards,
Florin

"Florin Neacsu" wrote in message <irh71j$kqo$1@newscl01ah.mathworks.com>...
> Hi,
>
> These might be of some interest to OP
> http://www.diku.dk/hjemmesider/ansatte/rfonseca/implementations/apollonius3d.pdf
>
> http://home.bway.net/lewis/lewbrid.pdf (problem 4 /pg 13 deals with his 2nd question)
>
> Regards,
> Florin
- - - - - - - - -
  Hello Florin. If Mahdi permits the radius r0 of the moveable sphere to vary suitably, then it could become possible to adjust r0 in such a way that the sphere is externally tangent to each of a set of four given spheres, though not with the method I have presented as it stands. (It should be noted that not all arrangements of four given spheres would permit such a solution.)

  I believe I see a way in which the method could be modified to solve that problem, though. It can be shown that the path followed by c0 and c00 as r0 varies would trace out one entire branch of a certain planar 3D hyperbola whose parameters could presumably be expressed explicitly. Doing the same thing with a different set of three out of the four spheres would produce a second hyperbola. If the four spheres are so situated that a solution is possible, these hyperbolas must intersect somewhere and do so with the same value of r0, and that should be something that is subject to direct computation using the two hyperbolas' parameters.

  In the report at "http://home.bway.net/lewis/lewbrid.pdf" which you referred to I believe it is problem 3 that pertains to Mahdi's question. In it they speak of an answer to this problem having 18366 terms. That suggests to me that they are using a very difficult approach to the problem. I can't imagine the above two hyperbolas and their intersection involving anything remotely approaching such complexity. Do you think I am being overconfident?

Roger Stafford

"Roger Stafford" wrote in message <irhjpo$mjo$1@newscl01ah.mathworks.com>...
> "Florin Neacsu" wrote in message <irh71j$kqo$1@newscl01ah.mathworks.com>...
> > Hi,
> >
> > These might be of some interest to OP
> > http://www.diku.dk/hjemmesider/ansatte/rfonseca/implementations/apollonius3d.pdf
> >
> > http://home.bway.net/lewis/lewbrid.pdf (problem 4 /pg 13 deals with his 2nd question)
> >
> > Regards,
> > Florin
> - - - - - - - - -
> Hello Florin. If Mahdi permits the radius r0 of the moveable sphere to vary suitably, then it could become possible to adjust r0 in such a way that the sphere is externally tangent to each of a set of four given spheres, though not with the method I have presented as it stands. (It should be noted that not all arrangements of four given spheres would permit such a solution.)
>
> I believe I see a way in which the method could be modified to solve that problem, though. It can be shown that the path followed by c0 and c00 as r0 varies would trace out one entire branch of a certain planar 3D hyperbola whose parameters could presumably be expressed explicitly. Doing the same thing with a different set of three out of the four spheres would produce a second hyperbola. If the four spheres are so situated that a solution is possible, these hyperbolas must intersect somewhere and do so with the same value of r0, and that should be something that is subject to direct computation using the two hyperbolas' parameters.
>
> In the report at "http://home.bway.net/lewis/lewbrid.pdf" which you referred to I believe it is problem 3 that pertains to Mahdi's question. In it they speak of an answer to this problem having 18366 terms. That suggests to me that they are using a very difficult approach to the problem. I can't imagine the above two hyperbolas and their intersection involving anything remotely approaching such complexity. Do you think I am being overconfident?
>
> Roger Stafford

Hello,

They are using the method called "Dixon-KSY" (it's the first time I see this nomenclature) which they briefly describe and refer the reader to another paper. They do mention that is a fully blown equation without making any simplifications, hence the large number of terms. I fail to understand how they came up with that number though.
Your idea of hyperbola's branches makes sense to me, but when I start writing it down I have a problem with the fact that the sphere could be tangent externally or internally (which means two different branches of the hyperbola (right?)). It is late in the day and I am sloppy. I will give it some more thought and get back to you.

Regards,
Florin

> "Florin Neacsu" wrote in message <irh71j$kqo$1@newscl01ah.mathworks.com>...
> > http://www.diku.dk/hjemmesider/ansatte/rfonseca/implementations/apollonius3d.pdf
- - - - - - - - - - - -
  Florin, I have just read your other reference to "apollonius3d.pdf" by Rasmus Fonseca dated just ten days ago. That looks like a good way to solve that problem. The 18366 terms in the other paper are undoubtedly the result of putting an automatic solver like matlab's 'solve' to work trying to get an algebraic solution without any intelligent input from humans. I believe we humans still have a significant role to play in the world of mathematical analysis, computers notwithstanding.

Roger Stafford

------------------------------------------------------------------------------------------------------------------------
Hi Florin and Roger:
I read all your posts completely and precisely.One of my question was about
tangenting one sphere to 4 spheres,while the radios of the fifth is predetermined.
This solution can be solved easily by applying appollonius problem for 3D confirming
to shared link by Florin.

a11xs + a12ys + a13zs + a14rs = b1
a21xs + a22ys + a23zs + a24rs = b2
a31xs + a32ys + a33zs + a34rs = b3
where
ai1 = 2xi+1 - 2x1
ai2 = 2yi+1 - 2y1
ai3 = 2zi+1 - 2z1
ai4 = 2s1r1 - 2si+1*ri+1
bi = (x^2 i+1 + y^2 i+1 + z^2 i+1)- (x^2 1 + y^21 + z^21) + r^21 -r^2 i+1
it should be mentioned that we knows that there is possibilty for being tangented with 4 spheres.

Mr Roger (questions)
1)why must vector t3 necessarily be orthogonal to the line segment between the
above three-plane intersection point and c0 ?

2)How does this equation force the[x y z]to be away from c0-c1 and down onto the
three centers'plane?
 dot(cross(c21,c31),[x,y,z]) =
 (b*f-c*e)*x + (c*d-a*f)*y + (a*e-b*d)*z = 0

3)is there any special name for your way or any article which I can refer that ?

regards
Mahdi
-----------------------------------------------------------------------------------

"mahdi roozbhani" <m.m.roozbahani@gmail.com> wrote in message <iri0eo$n9o$1@newscl01ah.mathworks.com>...
> Hi Florin and Roger:
> I read all your posts completely and precisely.One of my question was about
> tangenting one sphere to 4 spheres,while the radios of the fifth is predetermined.
> This solution can be solved easily by applying appollonius problem for 3D confirming
> to shared link by Florin.
>
> a11xs + a12ys + a13zs + a14rs = b1
> a21xs + a22ys + a23zs + a24rs = b2
> a31xs + a32ys + a33zs + a34rs = b3
> where
> ai1 = 2xi+1 - 2x1
> ai2 = 2yi+1 - 2y1
> ai3 = 2zi+1 - 2z1
> ai4 = 2s1r1 - 2si+1*ri+1
> bi = (x^2 i+1 + y^2 i+1 + z^2 i+1)- (x^2 1 + y^21 + z^21) + r^21 -r^2 i+1
> it should be mentioned that we knows that there is possibilty for being tangented with 4 spheres.
>
> Mr Roger (questions)
> 1)why must vector t3 necessarily be orthogonal to the line segment between the
> above three-plane intersection point and c0 ?
>
> 2)How does this equation force the[x y z]to be away from c0-c1 and down onto the
> three centers'plane?
> dot(cross(c21,c31),[x,y,z]) =
> (b*f-c*e)*x + (c*d-a*f)*y + (a*e-b*d)*z = 0
>
> 3)is there any special name for your way or any article which I can refer that ?
>
> regards
> Mahdi
- - - - - - - - -
  Mahdi, I think you misunderstood the point of Rasmus Fonseca's paper. In equations (9), (10), and (11) he has three linear equations in four unknowns, one of them being, rs, the radius of the fifth sphere which is to be tangent to the four others. From these equations he can determine the three coordinates of its center as a linear function of rs, and at that point any value of rs would give a solution to those three particular equations.

  However he has yet to satisfy the original equation (1). On page 4 he states "By plugging equations 17, 18 and 19 into equation 1 ...". When he does this at that last step, this yields a quadratic equation that rs must satisfy in equation (29). In other words, rs is not at all arbitrary if equation (1) is to be true. It must be just the right value. Therefore you cannot predetermine the radius of that fifth sphere. It must be left adjustable.

  In answer to your three questions:

1) Of those original three planes, the first two planes were orthogonal to c21 and c31, respectively, and these both lie within the third plane. As a consequence both planes are orthogonal to that third plane and the same must hold true of their line of intersection. Since t3 lies entirely in the third plane, this makes it orthogonal to that intersection line.

2) To require that

 dot(cross(c21,c31),[x,y,z]) = dot(cross(c21,c31),t3) = 0

implies that since the base of vector t3 lies in the three centers' plane then so does its other end. Remember, at that point I was only trying to find the intersection point of the three planes, not the center c0. The center c0 was only instrumental in determining the placement of the two planes.

3) No, this particular algorithm is of my own devising but I am sure it is not original. Its basic idea must have been reinvented many times.

Roger Stafford

Roger:
You are right about rs. rs is for verifying that the sphere(fifth) is eligible for tangenting or not.
and my other question is that ?
In your opinion, is it possible to apply the procedure of 3D appollonius problem for tangenting one sphere on 3 spheres ?
--------------------------------------------------------------------------------------------------------------------
-
"Roger Stafford" wrote in message <iriat0$hul$1@newscl01ah.mathworks.com>...
> "mahdi roozbhani" <m.m.roozbahani@gmail.com> wrote in message <iri0eo$n9o$1@newscl01ah.mathworks.com>...
> > Hi Florin and Roger:
> > I read all your posts completely and precisely.One of my question was about
> > tangenting one sphere to 4 spheres,while the radios of the fifth is predetermined.
> > This solution can be solved easily by applying appollonius problem for 3D confirming
> > to shared link by Florin.
> >
> > a11xs + a12ys + a13zs + a14rs = b1
> > a21xs + a22ys + a23zs + a24rs = b2
> > a31xs + a32ys + a33zs + a34rs = b3
> > where
> > ai1 = 2xi+1 - 2x1
> > ai2 = 2yi+1 - 2y1
> > ai3 = 2zi+1 - 2z1
> > ai4 = 2s1r1 - 2si+1*ri+1
> > bi = (x^2 i+1 + y^2 i+1 + z^2 i+1)- (x^2 1 + y^21 + z^21) + r^21 -r^2 i+1
> > it should be mentioned that we knows that there is possibilty for being tangented with 4 spheres.
> >
> > Mr Roger (questions)
> > 1)why must vector t3 necessarily be orthogonal to the line segment between the
> > above three-plane intersection point and c0 ?
> >
> > 2)How does this equation force the[x y z]to be away from c0-c1 and down onto the
> > three centers'plane?
> > dot(cross(c21,c31),[x,y,z]) =
> > (b*f-c*e)*x + (c*d-a*f)*y + (a*e-b*d)*z = 0
> >
> > 3)is there any special name for your way or any article which I can refer that ?
> >
> > regards
> > Mahdi
> - - - - - - - - -
> Mahdi, I think you misunderstood the point of Rasmus Fonseca's paper. In equations (9), (10), and (11) he has three linear equations in four unknowns, one of them being, rs, the radius of the fifth sphere which is to be tangent to the four others. From these equations he can determine the three coordinates of its center as a linear function of rs, and at that point any value of rs would give a solution to those three particular equations.
>
> However he has yet to satisfy the original equation (1). On page 4 he states "By plugging equations 17, 18 and 19 into equation 1 ...". When he does this at that last step, this yields a quadratic equation that rs must satisfy in equation (29). In other words, rs is not at all arbitrary if equation (1) is to be true. It must be just the right value. Therefore you cannot predetermine the radius of that fifth sphere. It must be left adjustable.
>
> In answer to your three questions:
>
> 1) Of those original three planes, the first two planes were orthogonal to c21 and c31, respectively, and these both lie within the third plane. As a consequence both planes are orthogonal to that third plane and the same must hold true of their line of intersection. Since t3 lies entirely in the third plane, this makes it orthogonal to that intersection line.
>
> 2) To require that
>
> dot(cross(c21,c31),[x,y,z]) = dot(cross(c21,c31),t3) = 0
>
> implies that since the base of vector t3 lies in the three centers' plane then so does its other end. Remember, at that point I was only trying to find the intersection point of the three planes, not the center c0. The center c0 was only instrumental in determining the placement of the two planes.
>
> 3) No, this particular algorithm is of my own devising but I am sure it is not original. Its basic idea must have been reinvented many times.
>
> Roger Stafford