0
$\begingroup$

The problem I stand in front of is that I need to determine the coordinates of some nodes. The information I have in hand is the distance from all nodes to all nodes. That is every node has a vector with its distance to all other nodes and from that I want to determine the coordinate for all nodes. What needs to be had in mind is that the distances are measured and thus will have some error.

The question is what is the best way to solve this problem.

My thoughts so far is to choose one point as $(0,0,0)$ and another points as $(d_{10},0,0)$, where $d_{10}$ is the distance between node $0$ and node $1$.

Then describe the relations between the distanced and coordinates for all nodes to all nodes. Here the equation from node $0$ to node $1$

$$f(\bar{x})_{1,0} = \sqrt{(x_1-x_0)^2+(y_1-y_0)^2+(z_1-z_0)^2} - d_{10} =0$$

I will then do that for all nodes and run them through a non-linear optimization, where the objective is to

$$\text{min}~ \sum{f(\bar{x})_{i, i-1}}$$

Is this a good way to go or are there any other solutions that would be better?

An interesting add on is how does the problem change when not all nodes has the distance from each other.

$\endgroup$

2 Answers 2

0
$\begingroup$

If I properly understand, you have $n$ points of unknown cooredinates $(x_i,y_i,z_i)$ and you know all the distances $$d_{ij}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2}$$ This makes $\frac{n(n-1)}2$ equations for $3(n-1)$ variables since, as you decided (good idea, for sure) to fix one of the points at the origin. So, in principle, as soon as $n \geq 6$, there could be a solution.

For sure, as you wrote, the most natural function to minimize would be $$\Phi=\sum_{i=1}^{n-1} \sum_{j=i+1}^n\left(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2}-d_{ij} \right)^2$$

Personally, I think that I should first try to minimize (at least in a first step) $$\Psi=\sum_{i=1}^{n-1} \sum_{j=i+1}^n\left({(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2}-d^2_{ij} \right)^2$$ which is more than likely better conditioned than $\Phi$.

In principle, this could work if some distances are missing as long as the total number of distances is $\geq 3(n-1)$.

$\endgroup$
2
  • $\begingroup$ Yes, you have understood it correctly. I have played around a bit with minimizing the Psi function you proposed. And it look like it will do the trick. How did you come to the number of distances >= 3(n-1)? $\endgroup$
    – Erik
    Commented Jul 19, 2019 at 12:15
  • $\begingroup$ @Erik. Good to know ! May I confess that I worked this problem quite a lot. Concerning the minimum number of distances : you have 3 coordinates per point but to one point are assigned the coordinates to whatever you want. Then ... $\endgroup$ Commented Jul 19, 2019 at 17:34
0
$\begingroup$

Considering the objective function as

$$ \sum_i\sum_j \left((x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2-d^2_{ij}\right)^2 $$

the script below (in MATHEMATICA) shows the initial set of random points in red and the solution obtained after the minimization in blue. There are two anchored points. The first and the last. Those points are given as restrictions.

n = 5;
pts = RandomReal[{-10, 10}, {n, 3}];
DD = Table[(pts[[i]] - pts[[j]]).(pts[[i]] - pts[[j]]), {i, 1, n}, {j, 1, n}];
For[i = 1; s = 0, i <= n, i++,
  For[j = i, j <= n, j++, If[i != j, s += ((Subscript[x, i] - Subscript[x, j])^2 + (Subscript[y, i] - Subscript[y, j])^2 + (Subscript[z, i] - Subscript[z, j])^2 -DD[[i, j]])^2]
  ]
]
vars = Variables[s];
pts1 = pts[[1]];
ptsn = pts[[n]];
const1 = Thread[{Subscript[x, 1], Subscript[y, 1],Subscript[z, 1]} == pts1];
const2 = Thread[{Subscript[x, n], Subscript[y, n],Subscript[z, n]} == ptsn];
constrs = Join[const1, const2];
sol = Minimize[Join[{s}, constrs], vars];
Print["Minimization error = ", sol[[1]]]
ptsol = Table[{Subscript[x, k], Subscript[y, k], Subscript[z, k]} /.sol[[2]], {k, 1, n}]
t1 = Table[Graphics3D[{Red, PointSize[0.02], Point[pts[[k]]]}], {k, 1, n}];
e1 = Table[Graphics3D[{Red, Line[{pts[[i]], pts[[j]]}]}], {i, 1, n}, {j, 1,  n}];
t2 = Table[Graphics3D[{Blue, PointSize[0.02], Point[ptsol[[k]]]}], {k, 1, n}];
e2 = Table[Graphics3D[{Blue, Line[{ptsol[[i]], ptsol[[j]]}]}], {i, 1, n}, {j, 1, n}];
Show[e1, e2, t1, t2]

Follows a series of examples.

n = 3

enter image description here n = 4

enter image description here

n = 5

enter image description here

n = 15

enter image description here

NOTE

This problem has many symmetries so unexpected solutions are allowed. More anchor points can be considered in order to reduce the possible solutions.

$\endgroup$
2
  • $\begingroup$ Thanks for the simulations. To avoid some symmetries i will fix one node on 0,0,0 and another in d,0,0. Though it is till possible that one get the nodes "upside down" when optimizing. $\endgroup$
    – Erik
    Commented Jul 19, 2019 at 12:18
  • $\begingroup$ @Erik Now the script can consider anchored points as restrictions in the minimization process. Even so there are a lot of possible solutions that can be reduced introducing more anchored points. $\endgroup$
    – Cesareo
    Commented Jul 19, 2019 at 13:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .