Compute coordinates of a point in 3D-Euclidean Space

Question

My question concerns the computation of a point’s coordinates in three-dimensional Euclidean Space.

I have a point P in three-dimensional Euclidean Space whose coordinates are unknown. My goal is to compute its coordinates given the provided information: Given are four points named A, B, C, and D - whose coordinates are known – and their respective Euclidean Distances to point P named AP, BP, CP, and DP, respectively; no two given points are equal and neither does P equal any of those points. Furthermore, all four points are distributed over all three plains; for every coordinate (X, Y, and Z) it is possible to find two points who differ in the respective coordinate. Finally, it must not be possible to form a flat four-sided figure with the four points as corners (see also the comments down below).

I have already shown that it is possible to compute exactly one possible set of coordinates for point P: Imagine a sphere with the radius of AP and the point A in its centre. Now imagine a sphere around point B with the radius of BP. The two spheres create a circle where both of its edges meet; all points on this circle have a distance of AP to A and a distance of BP to B. Again, imagine a sphere at point C with a radius of CP. This sphere intersects with said circle at exactly two points. Finally, imagine a sphere around point D with radius DP. This sphere intersects exactly one of the said points; the intersected point is P.

I have derived an algorithm for the following special case of the problem. Let Ax, Ay, and Az be the X, Y, and Z coordinate of A, respectively. Furthermore, let: the coordinates of B be (Ax, Ay, Bz) with some value for Bz that is unequal to Az; the coordinates of C be (Ax, Cy, Az) with some value for Cy that is unequal to Ay; the coordinates of D be (Dx, Ay, Az) with some value for Dx that is unequal to Ax. In other words, if the situation was depicted using the coordinate axes, A would be on its origin, B on the Z-axis, C on the Y-axis, and D on the X-axis. It would then be possible to construct a triangle with the corners A, P and one of the given points, as all three of its sides are known. Then, with Heron's Theorem, it is possible to calculate the height of the triangle. There are more details to the algorithm but I will just save them as they would complicate the question.

Ultimately, I am seeking an algorithm for determining the coordinates of P. I appreciate any and all answers, even if they only suggest an idea for resolving my problem. If the answer proposes an algorithm for constructing a special case such as described above, this question would also be answered. It is not difficult to determine the coordinate of A’, B’, C’, and D’ which fulfil the imposed requirements of the special case, the problem I had was figuring out their distances to P.

Answer 1

This seems to be a common problem in navigation, as it corresponds to distance measurements of an object from different stations: Trilateration

The above article argues that three spheres will allow to pinpoint the location down to two candidates, thus a fourth sphere might settle the issue.

There is an interesting calculation, which uses a coordinate transform, to simplify the equations:

• all three centers lie in the plane $z=0$
• sphere one is at the origin $x=y=z=0$
• sphere two is on the $x$-axis $y=z=0$

I would study the problem for three spheres, which should give two candidates and then use the closest to the fourth sphere (if there is sucha point).

Answer 2

One possibility is to minimize the sum of the squared errors, i.e., find $(x,y,z)$ to minimize $$ f(x,y,z) =\\ \left(\sqrt{(x-x_1)^2+(y-y_1)^2+(z-z_1)^2}-{r_1}\right)^2 +\\ \left(\sqrt{(x-x_2)^2+(y-y_2)^2+(z-z_2)^2}-{r_2}\right)^2 +\\ \left(\sqrt{(x-x_3)^2+(y-y_3)^2+(z-z_3)^2}-{r_3}\right)^2 +\\ \left(\sqrt{(x-x_4)^2+(y-y_4)^2+(z-z_4)^2}-{r_4}\right)^2 $$ This could be computed, e.g., with Mathematica's NMinimize[] function.

To respond to the OP's question, squaring is preferable to absolute value for smoothness of the function, which is important for the accuracy of minimizing algorithms.

For example, setting

---

     

---

whose solution is clearly $(0,0,0)$, and then minimizing, results in

---

     

---

     

---