10.25 LAB: Triangulation

Triangulation is the process of locating an unknown point given two known points and distances from those known points.

Consider two points (x₁,y₁) and (x₂,y₂).

Let (x,y) be an unknown point whose distances to points 1 and 2 d₁ and d₂, respectively, are known. The Pythagorean theorem allows us to express x and y (the coordinates of the unknown point) in terms of (x₁,y₁), (x₂,y₂), d₁, and d₂:

d12=(xx1)^2+(yy1)^2, and

d22=(xx2)^2+(yy2)^2.

Inverting these two formulae to make them explicit in x and y is really a lot of fun, but it takes a while. Here is the final result:

x=1/2(1+b^2)[2[x1b(ay1)][4(b(ay1)x1)24(1+b2)(x12d12+(y1a)2)]12], and

y=a+bx

where a=d12d22[(x12+y12)(x22+y22)]2(y2y1), and

b=x2x1y2y1

Note that the two possible values for x, x₊, and x_- arise from the positive and negative sense of the square root, and the value of y derives from its particular x. So because of the power of 2 in the Pythagorean theorem, we find that there are two possible points, (x₊, y₊) and (x_-, y_-), that are each d₁ from (x₁, y₁) and d₂ from (x₂, y₂). "Triangulation" refers to the fact that we need a third known point to decide which of (x₊, y₊) and (x_-, y_-) is our sought-after point. So long as that third point (x₃, y₃), is closer to (x₊, y₊) than it is to (x_-, y_-) (or vice versa), we can choose the final unknown point to be the one that is closer to (x₃, y₃).

These formulae can be expressed as functions.

import numpy as np def a( d1, d2, x1, y1, x2, y2 ): numerator=d1**2-d2**2 - ((x1**2+y1**2)-(x2**2+y2**2)) denominator=2*(y2-y1) return numerator/denominator def b( x1, y1, x2, y2 ): return -(x2-x1)/(y2-y1) def solve_xy( x1, y1, x2, y2, d1, d2 ): bb=b(x1,y1,x2,y2) aa=a(d1,d2,x1,y1,x2,y2) rad=4*(bb*(aa-y1)-x1)**2 - 4*(1+bb**2)*(x1**2-d1**2+(y1-aa)**2) pre=2*(x1-bb*(aa-y1)) den=2*(1+bb**2) xp=(pre+np.sqrt(rad))/den xm=(pre-np.sqrt(rad))/den yp=aa+xp*bb ym=aa+xm*bb return xm,ym,xp,yp 

Consider that point 1 is a distance of 4.1 (arbitrary units) from the unknown point with (x₁, y₁) coordinates of (-2.4,1.8) and that point 2 is a distance of 3.8 from the unknown point with (x₂, y₂) coordinates of (-1.9,-1.9).

1. Use the functions above to determine two potential sets of coordinates (x_p, y_p) or (x_m, y_m) for the unknown point.

To check this calculation, use a point-to-point distance calculation (for which Pythagoras gets credit) to determine if the same given distance can be calculated using the original known coordinates and the (x_p, y_p) or (x_m, y_m) coordinates.

2. Define a function called pythagoras that takes as arguments the coordinates of two points (e.g., for a and b, (xa, ya, xb, yb)) and returns the distance between the two points.

3. Use pythagoras to determine if the calculated distances of point 1 from (x_p, y_p) and (x_m, y_m) are equivalent. Do the same for point 2.

Now, to properly call this "triangulation" to locate a single point, we need a third point as a reference. We need not specify the distance from the unknown point to this third; we merely choose the resulting point that is closer to this third reference point.

3. Write a function called triangulate that takes as arguments the potential coordinates of the unknown point (x_p, y_p) and (x_m, y_m) followed by the coordinates of the reference point (x₃, y₃) and returns the coordinates of the point closest to the third point.

The point closest to the reference point will be taken to be the unknown location.