Build 3d model from distances between points

Question

Let's say we've got some points and we only know the distance each point and its closest neighbors. How can we calculate 3d coordinates for each of those points, so that the distances between them are matching?

• We'd like to program this solution, so geometry with pen and compass won't work
• The distances between the points may slightly vary due to measuring inaccuracy
• We may ask the user to place the first few points in special ways, so the model becomes explicit

In the real-world terms, we have multiple devices that can calculate the distance to each other. Based on these distances we want to build a 3d model of the devices.

Example:

Let's say we've got four devices. We can only let devices measure the distance to other devices. So we've got the following values:
- Device A can calculate: $|\overline{AB}|$ $|\overline{AC}|$ $|\overline{AD}|$
- Device B can calculate: $|\overline{BA}|$ $|\overline{BC}|$ $|\overline{BD}|$
- Device C can calculate: $|\overline{CA}|$ $|\overline{CB}|$ $|\overline{CD}|$
- Device D can calculate: $|\overline{DA}|$ $|\overline{DB}|$ $|\overline{DD}|$

Based on those values, we want to calculate the locations of the devices in space. One possible result could look like the following:
- A(0 0 0) (let's define the location of this device as absolute zero)
- B(0 1 1)
- C(2 1 2)
- D(4 2 4)

Answer 1

Let's say we've got some points and we only know the distance each point and its closest neighbors.

Only the closest neighbors, or all pairwise distances?

How can we calculate 3d coordinates for each of those points, so that the distances between them are matching?

As lhf commented to the question, this is a distance geometry problem. Also see Euclidean distance matrix. Software solutions already exist, but this is a topic in ongoing research.

One important detail to realize that distances alone are not enough to determine the chirality of a chiral point set. Consider, for example, the distances between atoms in alanine, a common amino acid. It has two isomers, L-alanine and D-alanine, that have the exact same atoms and interatomic distances, but have different biochemistry. (L-alanine is common in protein synthesis, D-alanine has been found in some bacterial cell walls.) Or, as an another example, consider three points at sea level on Earth, and a fourth non-coplanar point in the middle: it is impossible to tell whether the fourth point is above or below sea level, only its distance to the plane formed by the three other points.

As a simpler example, consider four points in the shape of an L, with three in a straight line, and one off to the side. The pairwise distances define the radius and position along the axis of the off point, but not its direction. To be able to determine their geometry, the locations of the off point and one of the other points must be fixed first. (In a five-point V, you'd have to fix three points, with at least one from each limb, and so on.)

So, it is not always possible to reconstruct the original point set using their pairwise distances alone. Sometimes you end up with two or more possible configurations, and sometimes an infinite number of configurations (due to axial or spherical symmetry, for example), that can only be "fixed" by initially fixing the position of certain specific points, depending on the point set.

Answer 2

I would propose splitting into smaller groups of points.

For example $3$ points in $2D$ we can calculate relative coordinates.

Then we can replace these three by one point, for example midpoint and coupled with rigid transformation which can be expressed with linear transformation.

Here is an example with optimizing for such an translation+rotation or translation+reflection operator if we choose 4 points instead of 3 in each "block".