calculate points coordinates on plane from their distances matrix

Question

Given a list of points on a plane is simple to generate a distances list between each pair of points.

Pseudo Code:

distances = []
for each point_a in points at index_a
  for each point_b in points at index_b having index_b > index_a
    dist = sqrt(abs(point_a.x-point_b.x)^2 + abs(point_a.y-point_b.y)^2)
    push [index_a, index_b, dist] in distances

Now, having distances is it possible to calculate back the coordinates of points?
Obviously relative coordinates, with any translation/rotation/symmetry.
With an approximation too, if it could simplify computation.
It would be even ok if the generated points wouldn't represent the originals points, the important thing is that the distances list fits them.
....
edit: Pseudo Code appreciated !!

Answer 1

Yes, generally speaking you can do this, up to rigid motions and reflections. Take $n+1$ points (assuming your space is $\mathbb{R}^n$) and assemble a simplex (triangle, tetrahedron, etc) from them. The simplex is unique up to isometry: you can see this by comparing the number of degrees of freedom $(n+1)n$ to the number of length constraints, and the dimension of the orthogonal group $O(n)$ and translation group.

Now that you have your simplex, add all of the other points: each point's position is overdetermined given the positions of the points in the simplex.

---

If you are on the plane, the points are $p_i$ and the distance between points $i$ and $j$ is $d_{ij}$:

1. Put the point $p_1$ anywhere you like.
2. Draw the circle of radius $d_{12}$ centered at $p_1$.
3. Put the point $p_2$ anywhere on that circle.
4. Draw the circle of radius $d_{13}$ centered at $p_1$, and the circle of radius $d_{23}$ centered at $p_2$. If your distances came from some (unknown) layout of the points in the plane, these two circle must intersect in at least one point. Pick one point of intersection and put $p_3$ there.

You now have your simplex. Follow the next step for every remaining point $p_i$:

5. Draw the circle of radius $d_{1i}$ centered at $p_1$ and $d_{2i}$ centered at $p_2$. These two circles will intersect in at least one point (typically two). To decide which to pick for $p_i$, draw the circle of radius $d_{3i}$ centered at $p_3$; it will pass through one of the intersection points. Pick that one.