Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Triangulation using sphere intersects
Date: Thu, 29 Jan 2009 00:19:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 33
Message-ID: <glqslm$fjp$1@fred.mathworks.com>
References: <gg5tb3$ms3$1@fred.mathworks.com> <gg7ep2$dg$1@fred.mathworks.com> <gg7ibf$iq3$1@fred.mathworks.com> <glmpbp$cte$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1233188342 15993 172.30.248.35 (29 Jan 2009 00:19:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 29 Jan 2009 00:19:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:514603


"gregoire " <dfd@invalid.edu.sg> wrote in message <glmpbp$cte$1@fred.mathworks.com>...
> Im back on this personal project and let me first say Thank you very much for your advice Roger, it has been very helpful indeed.
> 
> It has occured to me that if I had 2 spheres which intersected I'd get a circle, and 3 spheres which intersected I could resolve this down to 2 points, however in coding this problem, I could just find all circle intersects between all pair of intersecting spheres, regardless if there are 2 or 3 intersecting spheres,  and then at a later time around, find intersects between these circles (where 3 spheres had intersected) in order to resolve this down to the 2 points?  As opposed to treating the case where 2 spheres or 3 sheres intersect, separately.  This is correct right?
> 
> Working on the above assumption, I have pretty much managed to calculate the centre, and the 2 orthogonal vectors, ie all the information I need to depict for all sphere pair-intersecting circles, in separate rows. So I now have thousands of these circles with the required information in separate rows, and am now having difficulty with a) using plot3 to plot these many many circles together in 3d space and b) attempting to find potential intersections betweens these circles so as to resolve further, some of these circles into just 2 points for increased accuracy, which arise when 3 or more spheres intersect.
> 
> Thank you

  Gregoire, I finally decided to stop being lazy and have worked out the matlab code for your problem 2.  Given three spheres, you want to find their two points of intersection (if they actually intersect.)  As you can see, it gives an answer without any iteration.  My claim is that the only time these calculations become subject to inaccuracy is when the problem is inherently ill-conditioned, as for example when the centers are nearly colinear, or when the two points of intersection are very close together.

  Let p1, p2, and p3 be three-element vectors giving the x,y,z coordinates of the spheres' three centers, and r1, r2, and r3 their respective radii.  Then do this:

 p21 = p2-p1;
 p31 = p3-p1;
 c = cross(p21,p31);
 c2 = sum(c.^2);
 u1 = cross(((sum(p21.^2)+r1^2-r2^2)*p31 - ...
             (sum(p31.^2)+r1^2-r3^2)*p21)/2,c)/c2;
 v = sqrt(r1^2-sum(u1.^2))*c/sqrt(c2);
 i1 = p1+u1+v;
 i2 = p1+u1-v;

The i1 and i2 will be vectors for the two points of intersection.  If there is any possibility of having radii such that no solution is possible (which can happen very easily) you should test that the first square root used in the calculation of v is real.  An impossible problem will make it imaginary.

  By way of explanation, the vector c is orthogonal to the plane of the three centers.  The vector u1 is the location of the three-plane intersection I mentioned earlier relative to the point p1, and can be obtained by solving the three linear equations in three unknowns I mentioned previously.  Vector v stretches from this plane-intersection point along the c direction to one of the three-sphere intersection points, while -v stretches to the other one.

  If the centers are nearly colinear, the cross product c is nearly zero and division by it becomes increasingly inaccurate as colinearity is approached.  That is inherent in the situation and no fault of the method.  When r1^2 and sum(u1.^2) are nearly equal the square root process becomes inaccurate, and again that is inherent in the geometry of the problem as the two intersection points approach each other.

  David, I disagree with your statement that there is a gain in accuracy from an iterative approach.  The very factors that lead to inaccuracy of the above code are the same ones that will cause inaccuracy in any iterative method.  Small errors in center locations or radii will lead to disproportionately larger errors in intersection positions in these cases for either type of method.

Roger Stafford