2

After a week of searching and experimenting it's clear that I'm stuck. I've got 4 known points [A,B,C,D] in space and their respective distances to an unknown point X. My mathematics knowledge is basic at best so had frustrating times trying to understand some of the 3d maths out there so can anyone explain the algorithm needed with a step-by-step example in c++ the way to find that point X? Thanks.

E.g: Point A {-39, 24.9062, -0.65625}, point B {-13.5, 25.2812, -4} and point C {-11.5625, 43.8125, 11.625 }. Distances AX = 21.5116, BX = 43.8125, and CX = 11.625.

As people have pointed out there is the solution of working out the X point intersection with spheres but as I said my maths is not really that good so a working example would be appreciated.

I reckon another possible solution would be to first find out the distance between the base of the plane where the ABC triangle lies on and point X. This distance would essentially be the height of the tretrahedron ABCX makes. Then from there use trigonometry to work out the elevation angles of the AX, BX and CX vertices to work out the m of the y = mx + b lines. Again this is where my maths skills fizzle out.

Indicating the Matlab/Mathematica example is all well and good but as it uses its own library of math function and assumes good working knowledge of the math craft to solve the problem it just simply doesn't help me I'm afraid. I'm looking for a step-by-step solution for this exact problem in C++ (or C).

Nowhere I've looked (including SO) has anyone explained comprehensively the solution to this 3-dimensional problem from absolute start to absolute finish. Not everyone is good at maths that's why I would prefer a working example so i can go through and get a better grasp.

Regardless thank you all for the various links and suggestions both past and future.

Keyboard embossed forhead
  • 93
  • 2
  • 12
  • http://stackoverflow.com/questions/19254562/determine-the-position-of-a-point-in-3d-space-given-the-distance-to-n-points-wit – HEKTO Mar 09 '15 at 20:13
  • http://math.stackexchange.com/questions/472548/finding-position-of-a-point-in-cartesian-coordinate-by-knowing-its-distance-from – HEKTO Mar 09 '15 at 20:14
  • I've seen those previously but thanks suggesting the links in any case. Sadly my implementation needs to be in C++ (or C if it comes to that) and as for the linear algebra that deals with a plane not 3D space so again a no go. – Keyboard embossed forhead Mar 09 '15 at 21:14
  • what about this http://stackoverflow.com/q/25850564/2521214 just cast sphere from each point with radius equal to distance to X. find the common intersection between all sphere pair combinations or between all of them at once. – Spektre Mar 10 '15 at 07:38
  • 1
    @CodieCodeMonkey - the OP explicitly said that the question you claimed as the exact duplicate didn't help him/her. It makes sense cause he/she wanted C++ not Matlab – HEKTO Mar 10 '15 at 14:20

2 Answers2

0

The problem you are asking about is called Trilateration. Basically, you can select three anchor points and use the forth one to remove ambiguity. This Wiki article tries to simplify calculations assuming that these three points lie in the z = 0 plane.

A general case will need much more complex calculations, so you need to map your three anchor points to the case, discussed in this article, then to find a solution, then to map them back using inverse transformation.

You can easily find C++ code for that problem using the search string "trilateration C++".

HEKTO
  • 3,876
  • 2
  • 24
  • 45
0

First write the equation of three spheres centered on three known points and with known radii.

(X-Xi)² + (Y-Yi)² + (Z-Zi)² = Ri²

Subtracting the first from the other two, the terms X², Y² and Z² disappear, leaving two plane equations, that define a straight line.

Find two distinct points P0 and P1 along this line (for instance using Line of intersection between two planes), and form the parametric equation of the line

P = P0 + t (P1 - P0).

Plugging this into the equation of the first sphere yields a quadratic equation that should give you two solutions in t.

[(P0 - C0) + t (P1 - P0)]² = (P0 - C0)² - 2 (P0 - C0).(P1 - P0) t + (P1 - P0)²t² = R0²

Compute the two P, then use the fourth point to keep the solution that best matches the distance to it.

Community
  • 1
  • 1
  • A follow up question, what if we have more than 4 distances from known points? like 50? How to calculate the solution? – FantasticAI Oct 31 '21 at 19:13