computational-geometry - 从点间距重建 3d 点

Question

我有一组例如 8 点。我知道每个点之间的所有距离。是否有一种算法可以重建这些点的 3d 坐标。

Answer 1

What you are try to do is called Trilateration. It might be wise to do a bit of research before you proceed, as it's tricky to get right. However, I'll start you off with the following.

The following should work, as long as you have the actual 3D distances. Problems may come up if you don't.

1. Take a point, p1, and assign it to be the origin, (0,0,0).
2. Take another point, p2, and place it at (distance(p1,p2),0,0)
3. Take another point, p3, and place it on the (x,y,0) plane based on it's distance from p1 and p2.
4. Take another point, p4, and place in 3D space, based on it's distance from p1, p2, p3.
5. Repeat step 4 until no points remain.

The first 3 steps are enough to orient and fix the coordinates.

Solving steps 3 and 4 can be done by making use of planar triangles, that form easily due to how the points are centered.

Answer 2

假设点处于一般位置。没有3个点在同一条线上，也没有4个点在同一平面上。这不是限制，只是为了使算法更简单而不检查特殊情况。

四个球体（在一般位置）的交点（如果存在）是一个点。可以看出，由于两个球体的交点是一个圆，三个球体的交点是2个点，如果第四个球体的中心不在与其他3个球体中心的平面上，则该球体只能通过其中一个交点.

因此，如果距离有效，则可以通过向其增量添加点来创建形状。

前 4 个点的位置定义了方向。例如，第一个点设置在原点，第二个点设置在到第一个距离的 +X 上，第三个点设置在 XY 平面上的 +Y 方向上的圆相交处，第四个点设置在 +Z 方向上的三个球体的相交处。

可以通过将 4 个球体与前 4 个点的中心相交来定位附加点，半径由到它们的距离给出。

Answer 3

另一种可能性是度量Multidimensionale Skalierung。