Find X location using 3 known (X,Y) location using trilateration

Question

I post this question in stackoverflow here and was advised it was best suited for here.

I am trying to understand the maths behind trilateration, we have 3 access points $(\text{AP's: } 1,2,3)$ and we know the centre coordinates of theses $3$ (AP's). Lost device ($X$) is the location where all $3$ circle intersect.

example GRID $\Rightarrow x=30, y=30.$

Known Locations: $\text{AP}_1 = (5,5), \text{AP}_2 = (5,15), \text{AP}_3 = (20,10).$

Unknown Location: $X$

Lets say $X = (9,11)$

how do we work out the intersection of all $3$ circles by the maths.

your help is greatly appreciated.

Answer 1

Use the distance equation. If your unknown point is $(x,y)$, your known points are $(x_i, y_i)$ which are distances $r_i$ from your unknown point, then you get three equations:

$$(x-x_1)^2 + (y-y_1)^2 = r_{1}^2 \\ (x-x_2)^2 + (y-y_2)^2 = r_{2}^2 \\ (x-x_3)^2 + (y-y_3)^2 = r_{3}^2$$

We can expand out the squares in each one:

$$x^2 - 2x_1x + x_1^2 + y^2 - 2y_1y + y_1^2 = r_1^2 \\ x^2 - 2x_2x + x_2^2 + y^2 - 2y_2y + y_2^2 = r_2^2 \\ x^2 - 2x_3x + x_3^2 + y^2 - 2y_3y + y_3^2 = r_3^2$$

If we subtract the second equation from the first, we get

$$(-2x_1 + 2x_2)x + (-2y_1 + 2y_2)y = r_1^2 - r_2^2 - x_1^2 + x_2^2 - y_1^2 + y_2^2 .$$

Likewise, subtracting the third equation from the second,

$$(-2x_2 + 2x_3)x + (-2y_2 + 2y_3)y = r_2^2 - r_3^2 - x_2^2 + x_3^2 - y_2^2 + y_3^2 .$$

This is a system of two equations in two unknowns:

$$Ax + By = C \\ Dx + Ey = F$$

which has the solution:

$$x = \frac{CE-FB}{EA-BD} \\ y = \frac{CD-AF}{BD-AE}$$

Answer 2

I have a solution that works quite well. It involves finding the centroid which will help for scenarios where the circles don't intersect perfectly.

Suppose you have three receivers located at three known points $A(0,0)$, $B(0,1)$, $C(1,0)$.

And suppose the the distance from each receiver is known; therefore a circle can be drawn around each receiver with a radius as follows:

[picture at the end]

$a^2 = (x-0)^2 +(y-0)^2$; (red circle)

$b^2 = (x-0)^2 +(y-1)^2$; (blue circle)

$c^2 = (x-1)^2 + (y-0)^2$; (green circle)

• this problem can be understood as drawing lines between the two points at which each circle intersects. If these three lines are drawn, then they will all intersect at one point.

circle A and circle B intersect when c^2 = a^2. Note that the 'y' term will cancel out and only leave an 'x' value as follows, which draws a line between them:

$x = (1-c^2+a^2)/2$;

circles A and B intersect when $a^2 = b^2$ which results in:

$$y = (1-b^2+a^2)/2$$

circles B and C intersect when $b^2=c^2$, and let $b^2-c^2 = z$:

$$x = (z+2y)/2$$

This will execute trilateration well even if the circles don't intersect perfectly.

Try it out on a website like www.desmos.com, as I did in the picture attached, and play with the values of a,b,c to see if you make the model better!

This can be further improved..... any sugggestions????

Answer 3

I'm investigating the same problem, with an added twist.

I've got information from 3 cell towers about the exact time when they received a signal, down to the nanosecond. But I don't know when the message was sent. So my problem is to look for 3 intersecting circles, that have a common unknown offset added to their radius.

At light speed, every nanosecond allows a radio wave to advance 0.0003 kilometers. I'm approximating the map of Holland, where all this is happening, as a flat rectangle where every degree longitude counts for 66 kilometers, while a degree latitude equals 105 kilometers.

I've got these cell tower coordinates, with the time of signal reception:

1. 51.949505 4.545394 Time+46942ns
2. 51.942551 4.497042 Time+51510ns
3. 51.972046 4.595404 Time+58837ns

The online graphing with desmos.com was an awesome find ! Thanks MatMc. It allows me to quickly draw this situation as : https://www.desmos.com/calculator/gsrvhwvt6o As (x,y) coordinates, I used the lat/long degrees, which makes it easy to plug any results into Google Maps. The drawback is that this makes units of both axis different in size, so every real-life circle on the map gets drawn on the mathematical grid as an ellipse.

Now what really bothers me, is the appearance of 2 perfect intersections, upon picking the proper time offsets. I got a razor-sharp location fix for both d=-12.950967 and d=-12.172546 . Earlier on, I drew some quick circles by hand, and I concluded that the northernmost intersection was the location. A triangulation van was dispatched, and thankfully they found the signal at that location. Now I realize that I just got lucky. I could just as well have bumped into the southernmost intersection, by choosing a different common offset, and then the guys would have found nothing there.