# Trilateration algorithm for n amount of points

I need to find algorithm that can calculate centroid A (aka gravity center, geometric center, center of mass) from the figure where circles T1,T2,T3,T4,T5,..,Tn intersect AND length of line R from centroid to farthest corner of mentioned figure

Following information is given:

• T1 Latitude = 56.999883 Longitude = 24.144473 Radius = 943
• T2 Latitude = 57.005352 Longitude = 24.151168 Radius = 857
• T3 Latitude = 57.005352 Longitude = 24.163356 Radius = 714
• T4 Latitude = 56.999042 Longitude = 24.168506 Radius = 714
• T5 Latitude = 56.994226 Longitude = 24.15709 Radius = 771

Result should look like this: A Latitude = XX.XXXXXXX Longitude = XX.XXXXXXX Radius = XX As you probably already figured out, I am working on software that can find device location by closest Wifi Access Points or Mobile Base stations, as number of access points or base stations might change, I need an algorithm that can adapt to uncertain amount of points.

There are some similar questions here and here, but none of them exactly answers to my question.

• what language are you working in? – WolfOdrade Nov 8 '12 at 23:35
• Mostly PHP, little bit of JavaScript. I guess I had to mention this before but I am a web developer and to understand Whuber's answer I will have to find a mathematician. – Kārlis Baumanis Nov 8 '12 at 23:54
• Are the radii derived from relative signal strengths? – Kirk Kuykendall Nov 9 '12 at 2:25
• Yes! Actually Radiuses are in dBm – Kārlis Baumanis Nov 9 '12 at 8:32
• @Reddox, partly - I managed to calculate it with php_exec() using mathematica on serverside. – Kārlis Baumanis Mar 24 '14 at 9:27

The radius measurements surely are subject to some error. I would expect the amount of error to be proportional to the radii themselves. Let us assume the measurements are otherwise unbiased. A reasonable solution then uses weighted nonlinear least squares fitting, with weights inversely proportional to the squared radii.

This is standard stuff available in (among other things) Python, `R`, Mathematica, and many full-featured statistical packages, so I will just illustrate it. Here are some data obtained by measuring the distances, with relative error of 10%, to five random access points surrounding the device location: Mathematica needs just one line of code and no measurable CPU time to compute the fit:

``````fit = NonlinearModelFit[data, Norm[{x, y} - {x0, y0}], {x0, y0}, {x, y}, Weights -> 1/observations^2]
``````

### Edit--

For large radii, more accurate (spherical or ellipsoidal) solutions can be found merely by replacing the Euclidean distance `Norm[{x, y} - {x0, y0}]` by a function to compute the spherical or ellipsoidal distance. In Mathematica this could be done, e.g., via

``````fit = NonlinearModelFit[data, GeoDistance[{x, y}, {x0, y0}], {x0, y0}, {x, y},
Weights -> 1/observations^2]
``````

### --end of edit

One advantage of using a statistical technique like this is that it can produce confidence intervals for the parameters (which are the coordinates of the device) and even a simultaneous confidence ellipse for the device location.

``````ellipsoid = fit["ParameterConfidenceRegion", ConfidenceLevel -> 0.95];
fit["ParameterConfidenceIntervalTable", ConfidenceLevel -> 0.95]
`````` It is instructive to plot the data and the solution:

``````Graphics[{Opacity[0.2], EdgeForm[Opacity[0.75]], White, Disk[Most[#], Last[#]] & /@ data,
Opacity, Red, ellipsoid,
PointSize[0.0125], Blue, Point[source], Red, Point[solution],
PointSize[0.0083], White, Point @ points},
Background -> Black, ImageSize -> 600]
`````` • The white dots are the (known) access point locations.

• The large blue dot is the true device location.

• The gray circles represent the measured radii. Ideally, they would all intersect at the true device location--but obviously they do not, due to measurement error.

• The large red dot is the estimated device location.

• The red ellipse demarcates a 95% confidence region for the device location.

The shape of the ellipse in this case is of interest: the locational uncertainty is greatest along a NW-SE line. Here, the distances to three access points (to the NE and SW) barely change and there is a trade-off in errors between the distances to the two other access points (to the north and southeast).

(A more accurate confidence region can be obtained in some systems as a contour of a likelihood function; this ellipse is just a second-order approximation to such a contour.)

When the radii are measured without error, all the circles will have at least one point of mutual intersection and--if that point is unique--it will be the unique solution.

This method works with two or more access points. Three or more are needed to obtain confidence intervals. When only two are available, it finds one of the points of intersection (if they exist); otherwise, it selects an appropriate location between the two access points.

• Well done Bill! – user681 Nov 8 '12 at 20:51
• @Reddox In principle, yes: any turing-complete language can do literally any computation. But PHP would be way down anybody's list of choices as a target language. Even the PHP manual admits as much: "PHP is probably not the very best language to create a desktop application with a graphical user interface, but if you know PHP very well, and would like to use some advanced PHP features in your client-side applications you can also use PHP-GTK to write such programs." – whuber Oct 29 '13 at 13:35
• @Reddox Thank you for the link. I see how it provides geometry calculations. In this circumstance those aren't really needed: the only such calculation is an application of the Pythagorean theorem to obtain distances as root sums of squares (the call to `Norm` in my code). All the work is involved in the weighted nonlinear least squares fitting, but I don't believe the GEOS library provides that capability. Possibly GEOS could be of some help when accurate ellipsoidal distances are needed. – whuber Nov 13 '13 at 14:25
• If I'm reading this correctly, @BenR, it seems you are weighting the data in proportion to the squared radii rather than inversely proportional to them. What happens when you divide by `square(data)` instead of multiplying by it? – whuber Feb 12 '14 at 17:08
• – whuber Feb 12 '14 at 17:20

In this case, every circle intersects all the other circles and so we can determine the intersection points this way:

First determine all n*(n-1) intersection points. Call the set of these intersection point I. Take a list of points T which contains the innermost points. Then for each point p in I, check if p is inside every circle. If p is inside every circle, then this is point on the innermost intersection. Add such a point to the list T.

Now you have the desired intersection coordinates. I can think of at least two ways to predict the location:

1. Just calculate the centroid (use distance as weight?) of the polygon formed by T and centroid is the desired location.
2. Calculate the minimum circle that contains every point of T. Then the center of this circle is the desired location. Calculating R should be straightforward after this.

Another note: first convert signal strength to distance using free space path model (or variations). My take is: you have any training dataset, you should try to find path loss exponent using some learning technique instead of using n=2 or n=2.2 as fixed value.

• what is T...the "innermost points" - if I have 5 nodes..how many "innermost points" should I be checking for? – ewizard Mar 3 '18 at 2:42