Introduction

For my previous post, where I find the signal strength of WiFi spots, I also needed an algorithm to actually locate the spot. I decided to use triangulation, which is commonly used in wireless communications to locate devices based on signal strength from known positions.

As my system uses GPS, I had to consider the Earth’s curvature. Calculating the geographic midpoint on a sphere isn’t trivial, but GeoMidpoint provides a great explanation (Method A).

Method Overview

Convert every geographic coordinate into a 3D Cartesian coordinate. Then apply weights, compute a weighted average, and convert back to geographic coordinates using atan2 and Pythagorean calculations.

Detailed Method

  1. Convert lat/lon to X, Y, Z:

    x = cos(lat) * cos(lon)
y = cos(lat) * sin(lon)
z = sin(lat)

  2. Set the weight: If not supplied, default to 1.

  3. Sum total weight: wht_total = w1 + w2 + ... + wn

  4. Compute weighted average:

    x_avg = (x1*w1 + x2*w2 + ... + xn*wn) / wht_total
y_avg = (y1*w1 + y2*w2 + ... + yn*wn) / wht_total
z_avg = (z1*w1 + z2*w2 + ... + zn*wn) / wht_total

  5. Convert back to lat/lon:

    lon = atan2(y_avg, x_avg)
lat = atan2(z_avg, sqrt(x_avg² + y_avg²))

Code (C#)

Coordinate Classes

class GeoCoordinate
{
    public double Longitude { get; set; }
    public double Latitude { get; set; }

    public GeoCoordinate() { Longitude = 0; Latitude = 0; }
    public GeoCoordinate(double lat, double lon) { Longitude = lon; Latitude = lat; }
}

class GeoCoordinate_Weighted : GeoCoordinate
{
    public double Weight { get; set; } = 1;
    public GeoCoordinate_Weighted(double lat, double lon, double weight)
    {
        Longitude = lon;
        Latitude = lat;
        Weight = weight;
    }
}

class Coordinate3D
{
    public double X, Y, Z;
    public Coordinate3D() { X = Y = Z = 0; }
    public Coordinate3D(double x, double y, double z) { X = x; Y = y; Z = z; }
}

Weighted Midpoint Calculation

static GeoCoordinate CalculateCentre(List<GeoCoordinate_Weighted> input)
{
    double totalWeight = 0;
    Coordinate3D sum = new Coordinate3D();

    foreach (var point in input)
    {
        double latRad = Rad(point.Latitude);
        double lonRad = Rad(point.Longitude);

        sum.X += Math.Cos(latRad) * Math.Cos(lonRad) * point.Weight;
        sum.Y += Math.Cos(latRad) * Math.Sin(lonRad) * point.Weight;
        sum.Z += Math.Sin(latRad) * point.Weight;

        totalWeight += point.Weight;
    }

    sum.X /= totalWeight;
    sum.Y /= totalWeight;
    sum.Z /= totalWeight;

    double lon = Deg(Math.Atan2(sum.Y, sum.X));
    double lat = Deg(Math.Atan2(sum.Z, Math.Sqrt(sum.X * sum.X + sum.Y * sum.Y)));

    return new GeoCoordinate(lat, lon);
}

static double Deg(double rad) => rad * 180 / Math.PI;
static double Rad(double deg) => deg * Math.PI / 180;

Test Case

Example 1:

var list = new List<GeoCoordinate_Weighted>
{
    new GeoCoordinate_Weighted(20, 10, 10),
    new GeoCoordinate_Weighted(0, 0, 1),
    new GeoCoordinate_Weighted(-20, -10, 1)
};
var centre = CalculateCentre(list);
Console.WriteLine($"Latitude: {centre.Latitude}, Longitude: {centre.Longitude}");

Matches GeoMidPoint output:

  • Latitude: 15.26935
  • Longitude: 7.48369

Example 2: 10 random global coordinates also match GeoMidPoint’s output.

Conclusion

The weighted midpoint algorithm works as expected. My application accurately matches GeoMidPoint’s output. Great for future triangulation-based location work!