Trilateration

From Wikipedia, the free encyclopedia

Standing at B, you want to know your location relative to the reference points P1, P2, and P3 on a 2D plane. Measuring r1 narrows your position down to a circle. Next, measuring r2 narrows it down to two points, A and B. A third measurement, r3, gives your coordinates at B. A fourth measurement could also be made to reduce error.

Trilateration is a method of determining the relative positions of objects using the geometry of triangles in a similar fashion as triangulation. Unlike triangulation, which uses angle measurements (together with at least one known distance) to calculate the subject's location, trilateration uses the known locations of two or more reference points, and the measured distance between the subject and each reference point. To accurately and uniquely determine the relative location of a point on a 2D plane using trilateration alone, generally at least 3 reference points are needed.

[edit] Derivation

A mathematical derivation for the solution of a three-dimensional trilateration problem can be found by taking the formulae for three spheres and setting them equal to each other. To do this, we must apply three constraints to the centers of these spheres; all three must be on the z=0 plane, one must be on the origin, and one other must be on the x-axis. It is, however, possible to translate any set of three points to comply with these constraints, find the solution point, and then reverse the translation to find the solution point in the original coordinate system.

Starting with three spheres,

$r_1^2=x^2+y^2+z^2$ ,

$r_2^2=(x-d)^2+y^2+z^2,$

and

$r_3^2=(x-i)^2+(y-j)^2+z^2$ ,

we subtract the second from the first and solve for x:

$x=\frac{r_1^2-r_2^2+d^2}{2d}$ .

Substituting this back into the formula for the first sphere produces the formula for a circle, the solution to the intersection of the first two spheres:

$y^2+z^2=r_1^2-\frac{(r_1^2-r_2^2+d^2)^2}{4d^2}$ .

Setting this formula equal to the formula for the third sphere finds:

$y=\frac{r_1^2-r_3^2-x^2+(x-i)^2+j^2}{2j}=\frac{r_1^2-r_3^2+i^2+j^2}{2j}-\frac{i}{j}x$ .

Now that we have the x- and y-coordinates of the solution point, we can simply rearrange the formula for the first sphere to find the z-coordinate:

$z=\sqrt{r_1^2-x^2-y^2}$

Now we have the solution to all three points x, y and z. Because z is expressed as a square root, it is possible for there to be zero, one or two solutions to the problem.

This last part can be visualized as taking the circle found from intersecting the first and second sphere and intersecting that with the third sphere. If that circle falls entirely outside of the sphere, z is equal to the square root of a negative number: no real solution exists. If that circle touches the sphere on exactly one point, z is equal to zero. If that circle touches the surface of the sphere at two points, then z is equal to plus or minus the square root of a positive number.

In the case of no solution, a not uncommon one when using noisy data, the nearest solution is zero. One should be careful, though, to do a sanity check and assume zero only when the error is appropriately small.

In the case of two solutions, some technique must be used to disambiguate between the two. This can be done mathematically, by using a fourth sphere with its center not being located on the same plane as the centers of the other three, and determining which point lies closest to the surface of this sphere. Or it can be done logically—for example, GPS receivers assume that the point that lies inside the orbit of the satellites is the correct one when faced with this ambiguity, because it is generally safe to assume that the user is never in space, outside the satellites' orbits.

[edit] Error model

When measurement error is introduced into the picture, things become a little more complicated. If we know that the distance from P to a reference point lies in a range (a closed interval) [r₁, r₂], then we know that P lies in a circular band between the circles of those two radii. If we know a range for another point, we can take the intersection, which will be either one or two areas bounded by circular arcs. A third point will usually narrow it down to a single area, but this area may still be of significant size; additional reference points can help shrink it further, but as the area shrinks more measurements quickly become less useful. In three dimensions, we are instead intersecting spherical shells with thickness, similar to bowling balls.

This new model emphasizes the importance of choosing three points that are in very different directions — if the points are relatively close together and all far from the point being located, it will take very precise measurement to find the point using trilateration.Polish