1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ they wont necessarily determine a unique point P. take a circle not contained in any of the three coordinate planes, the points at right angles relative to one another in the plane they lie in. then any point on the line through the circle's center along the normal to the plane will be equidistant to the four points. $\endgroup$ – David P Feb 28 '15 at 18:39
  • $\begingroup$ @DavidP Thanks. You are right, the requirements are not strong enough to cover all situations. The situation you described, however, can only occur whenever two points have two equal coordinates. In my imagination experiment, I had imposed that requirement implictly without noting it down. I will edit my post there, thanks. As well, if I in the end have a small, finite number of potential points, that is acceptable as well; I am writing a computer program in which I can rule out certain points and states. $\endgroup$ – univise Feb 28 '15 at 19:08
  • $\begingroup$ They do not need to have equal coordinates. The circle with the four points can be rotated freely about its center without changing the distance to the points on the line $\endgroup$ – David P Feb 28 '15 at 19:19
  • $\begingroup$ @DavidP I misunderstood your comment there, I understand what you mean now. In that case, the four points my not be in one plain. In other words, it must not be possible to draw a 'real' four-sided figure with the four points as its corners ('real' here means not possible to be drawn in our world, thus it would have to be flat). Thank you for pointing that flaw out in my conception. $\endgroup$ – univise Feb 28 '15 at 19:30
1
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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


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


$\endgroup$
1
  • $\begingroup$ That is a great proposition - thank you, Joseph. I do wonder whether this will return the coordinates of exactly one point and not of several? Have you got a proof or explanation at hand that would show that? On a side, is there a reason to square the differences or would it suffice to take the absolute value? I would believe the absolute value should suffice. $\endgroup$ – univise Feb 28 '15 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.