CODEWITHSUNDEEP
computational-geometrygraph-algorithm
Mario
Mario

Reputation: 529

Reconstruct 3d points from point spacing

I have a set of e.g. 8 points. I know all distances between each points. Is there an algorithm to reconstruct the 3d coordinates of those points.

Upvotes: 4

Views: 328

Answers (3)

Mario
Mario

Reputation: 529

An other possibility is the metric Multidimensionale Skalierung.

Upvotes: 0

Nuclearman
Nuclearman

Reputation: 5304

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.

Upvotes: 5

Ante
Ante

Reputation: 5448

Let assume that points are in a general position. That no 3 points are on a same line, and no 4 points are on a same plane. It isn't a restriction, just to make algorithm simpler without checks for a special cases.

Intersection, if exists, of four spheres (in a general position) is a single point. It can be seen since intersection of two spheres is a circle, intersection of three spheres are 2 points, and if center of forth sphere isn't on a plane with centers of other 3 spheres, that sphere can pass only through one of intersection points.

So, if distances are valid, than shape can be created by incremental adding points to it.

Position on first 4 points defines orientation. E.g. first point set in origin, second point set on +X on given distance to first, third point set in XY plane in +Y direction on intersection of circles, and forth point set in +Z direction on intersection of 3 spheres.

Additional points can be positioned by intersection of 4 spheres with centers in first 4 points and radii given by distances to them.

Upvotes: 2

Related Questions