Search code examples
algorithmtriangulation

Triangulation in 3D Space

Disclaimer: This is for class, however I'm fresh out of ideas and a nudge in the right direction would be much appreciated. Also, this needs to be implemented in raw C, so no fancy libraries can be used.

I have to write a search and rescue simulator for submarines, it has to find a probe that is randomly placed in 3D space in a grid from of the MAX_XYZ (100000). The only tools I'm given are a "ping" which will give the magnitude of the distance between a certain sub and the probe. The goal is to optimize the costs of this entire operation so a brute force attempt, like looking at every single coordinate, won't work. Hence I was thinking triangulation.

Now, it makes loads of sense to me, place three subs, each one of them uses their ping to get the distance between them and the probe. Since each sub have a known distance relative to one another, it's easy to build the base of a tetrahedron with them, and the results of the ping will point to a certain coordinate, the problem I'm having is how to figure out the elevation, or the height, of the tetrahedron.

So what I have as data is the following:

  1. Distances between subs (In vector format)
  2. Angles between each subs (very easy to compute)
  3. Distance between each sub and the probe (3 segments from the base to the peak)
  4. Angles inside each of the outer 3 surfaces of the tetrahedron.

I tried finding some sort of relationship with the vertices of the tetrahedron and the relative angles in each of them, however all I found had to deal with tetrahedrons built with equilateral triangles, which isn't much help. I have the impression this can be easily solved with trig but either I'm not seeing it or I need more coffee.

Any suggestions would be appreciated!

Solution

  • Since this is homework, I'll give a nudge.

    Generally this is the subject of Multilateration.

    Multilateration is a navigation technique based on the measurement of the difference in distance to two or more stations at known locations that broadcast signals at known times. Unlike measurements of absolute distance or angle, measuring the difference in distance results in an infinite number of locations that satisfy the measurement. When these possible locations are plotted, they form a hyperbolic curve. To locate the exact location along that curve, a second measurement is taken to a different pair of stations to produce a second curve, which intersects with the first. When the two are compared, a small number of possible locations are revealed, producing a "fix".

    The Wikipedia entry discusses the mathematics in detail.