Title: Perform trilateration in Python

[Finding the trilateration of three circles in Python]

This post explains how a Python program can use trilateration to locate a point that is known distances from three other points.

Trilateration is somewhat similar to triangulation, so the following two sections begin by explaining what triangulation and trilateration are.

Triangulation

In triangulation, you know the directions from two or more points toward an unknown location. You draw rays leaving the known points in their directions, and the place where those rays intersect gives you the unknown location.

For example, suppose you have a directional antenna. You go to point A in the picture on the right, and it tells you that the transmitter (point T) is in the direction of the red arrow. You then move to another point, this time B, and the antenna tells you that the transmitter is in the direction of the green arrow. The place where the red and green arrows intersect is the (approximate) location of the transmitter.

You can take more than two readings if you like. If you do, the new arrows may not all intersect at exactly the same point, but they should give you an area where the transmitter is likely to be.

This technique is called triangulation because you're using a triangle (defined by the points A, B, and C) to location one of the points.

Trilateration

In trilateration you use distances instead of angles to find an unknown location.

For example suppose you know that a target point T is some distance Ra away from point A. In that case you know that T lies on a circle with radius Ra centered at point A.

If you also know that the target is distance Rb away from point B, then it also lies on a circle with radius Rb centered at point B. Ideally those circles should intersect at one or two places. If they intersect at a single point, then the target should be at that point. If they intersect at two points, then the target lies at one of those points and you need a third measurement to figure out which.

If you have a third point and distance, then it defines a third circle. Ideally the three circles intersect at a single point, and that is where the target lies.

Unfortunately, the circles may not intersect at a single point. In that case they define a triangular area (where the sides of the triangle are actually arcs of the circles) and the target should be somewhere in that area.

This technique is called trilateration because it involves three lengths, in this example the segments AT, BT, and CT.

This is the technique Liam Neeson used in the movie Taken 2 to help his daughter locate him. Or sort of. I need to watch the movie again.

The Algorithm

To find the area where the target should be, find the points where each pair of circles intersects. Then for each pair of circles, find the point of intersection that is closest to the center of the third circle. That point of intersection is part of the triangle that defines the target area.

If you want a specific point near the target, you can average the triangles' vertex coordinates to find the triangle's centroid.

Python Code

The program uses the following simple Circle class to represent circles.

class Circle: def __init__(self, id, x, y, radius): self.id = id self.x = x self.y = y self.radius = radius

The following trilaterate function finds the triangle defined by three mutually intersecting circles.

def trilaterate(circle1, circle2, circle3): '''Perform the trilateration.''' # Find the points of intersection. p12 = find_trilateralization_corner(circle1, circle2, circle3) p23 = find_trilateralization_corner(circle2, circle3, circle1) p31 = find_trilateralization_corner(circle3, circle1, circle2) return (p12, p23, p31)

This code calls the find_trilateralization_corner function three times to find the triangle's corners. Of course that begs the question, "How does that function work?" Here's that function's code.

def find_trilateralization_corner(c1, c2, c3): ''' Find the intersections between circles c1 and c2. Return the point of intersection (POI) closest to the center of c3. ''' intersections = find_circle_circle_intersections( (c1.x, c1.y), c1.radius, (c2.x, c2.y), c2.radius) distances = [distance(point[0], point[1], c3.x, c3.y) for point in intersections] min_distance = min(distances) index = distances.index(min_distance) return intersections[index]

This code takes as parameters the two circles whose intersections it should find and the third circle that decides which point of intersection to use. It first uses the find_circle_circle_intersections function to find the place(s) where the first two circles intersect. (You can read about that function in my post Determine where two circles intersect in Python.)

Next, the code uses a list comprehension to find the distances from the points of intersection to the third circle's center. It uses min to get the minimum of those distances and then uses the distances list's index method to find the index of the closest point. The function finishes by returning the closest point, which the trilaterate function uses as one of the triangle's corners.

The last interesting piece of code is the following function that finds a triangle's centroid.

def find_triangle_centroid(p1, p2, p3): '''Return the triangle's centroid.''' return ( (p1[0] + p2[0] + p3[0]) / 3, (p1[1] + p2[1] + p3[1]) / 3 )

This function simply averages the coordinates of the triangle's vertices.

Conclusion

This method works in a "normal" situation, but there are several odd cases where it doesn't work well. For example, if the three circles do not all intersect each other, then you can't find three points of intersection to define the target area and the method does not produce a result. In that case you may be able to gradually increase the circles' radii until they do intersect and still get a meaningful target area.

[Trilateration doesn't work well if the circles' centers lie along a line] This algorithm also doesn't produce a good result if the triangles' centers lie roughly along a line, as shown in the picture on the right. In that case, the intersections define two areas where the target point may lie.

Download the example to experiment with it and to see additional details.