View Question
 Question
 Subject: Geometry - shperes collision Category: Computers > Algorithms Asked by: jonathontrimble-ga List Price: \$75.00 Posted: 14 Mar 2006 02:27 PST Expires: 30 Mar 2006 03:45 PST Question ID: 707081
 ```I have three points (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) and I know the distance from each point to another point d1, d2 and d3 respectively. I want to know the equation(s) that let me calculate the (x,y,z) coordinate of the third point. I need to be able to calculate this in a computer program so the answer needs to be practical in that I want to simply supply the coordniates not solve the equations. I suspect (but don't know) that this can be solved by matrices and involves the collision point of three spheres. I'd also like to know how to expand this to include a fourth and a fifth sphere into the equation. thanks``` Request for Question Clarification by hedgie-ga on 29 Mar 2006 01:45 PST ```Hello jonathon When you say: "I need to be able to calculate this .. on a PC .." do you expect the answer to provide the code, or just the equations? The equations can be solved on ordinary computer, using standard libraries, but to write such program does requires programming skills. The last coment by ansel have some elements which are correct; However the equations cannot be linearised. Three spheres will in general intersect in two points (so you will have two solutions for given d1 d2 d3) if the spheres are close enough. Four and more spheres, in general case, will not intersect, so there will be no solution. General case means for most positions. An example of two speres 'just touching' is not a general case, it is 'special case' and the two spheres will define one point; One way to have N>3 spheres would be to discuss special cases. Another way one can understand phrase "expand this .. to N spheres" would be a LSQ solution - solution where d.i distances are aproximate, and one looks for best fit to overdetermined situation: http://en.wikipedia.org/wiki/Least_squares Is that what you mean? So, are you still interested in the problem? and is correct set of equation a sufficient answer? Hedgie```
 There is no answer at this time.

 ```I'm not quite sure what you are asking. You go back and forth between points and spheres. You also mention a collision point. A sphere implies a non-zero radius. If two spheres collide, the collision point would be different than the center point of either of the two spheres. If I look at only the first paragraph and assume you are only talking about points, are you saying given the location of two points and the three distances between those two points and a third point of unknown location, what is the location of the third point? You also mention a fourth and fifth sphere. How do they fit in? Please clarify.```
 ```I think I finally figured out what you are talking about in the first paragraph. You have three points P1(x1,y1,z1) P2(x2,y2,z2) P3(x3,y3,z3) There is one additional point Q in an unknown location. The distance from P1 to Q is d1 The distance from P2 to Q is d2 The distance from P3 to Q is d3 What are the coordinates of Q? And this has nothing to do with spheres. Is this understanding correct? If so, there is in general, no unique solution. In 3 space, it takes four non-coplanar points to locate something uniquely. For any three points, there will always exist a plane that contains all of them. The fourth point Q, will usually not be in the plane. If that is the case, then when you find one possible location of Q above the plane, there is another possible location of Q the same distance below the plane. As far as the spheres are concerned and the collision point of the spheres, I still am not sure what you are referring to.```
 ```Ansel, great restatement of the problem. I would understand that the spheres are the 3d sweep of d1, d2, d3 from their relative points (but I was also confused about this before your restatement). There was a similar question some time ago, but I cannot find it.```
 ```Myoarin, I think you are right about the spheres. The intersection of the spheres is the solution. For a unique solution you need four non-coplanar points. P1(x1,y1,z1) P2(x2,y2,z2) P3(x3,y3,z3) P4(x4,y4,z4) There is one additional point Q in an unknown location. The distance from P1 to Q is d1 The distance from P2 to Q is d2 The distance from P3 to Q is d3 The distance from P4 to Q is d4 What are the coordinates of Q? First set up the equations for the spheres of intersection: S1, S2, S3, S4 S1: (x-x1)^2+(y-y1)^2+(z-z1)^2 = (d1)^2 S2: (x-x2)^2+(y-y2)^2+(z-z2)^2 = (d2)^2 S3: (x-x3)^2+(y-y3)^2+(z-z3)^2 = (d3)^2 S4: (x-x4)^2+(y-y4)^2+(z-z4)^2 = (d4)^2 If you combine them correctly you can make all the squared terms drop out. Examples are: S1+S2-S3-S4 S1-S2+S3-S4 S1-S2-S3+S4 This will leave you with three equations and three unknowns. All of the equations will be linear. The solution to this is straight forward and will give the coordinates of your point Q.```