Fast Approximation if a point on earth is in range

Question

For a game I need to calculate if items on the map are in range of the player. The map is the earth. I'm using the Haversine formula to calculate the distance between the player and each item. However I did some profiling and found out that all those sin/cos calculations are too slow to allow for smoth gameplay.

Is there some other method to check of two points on earth could be withing a range of x metres? The method does not need to be exact, but it must be fast and return true if distance <= x. It may also return true if distance > x (but should not always return true).

My test code (LinqPad)

void Main()
{
    var lat = 53.553072;
    var lng = 9.993023;

    var lat0 = 53.553073;
    var lng0 = 9.993178;

    "Google Maps: 10.02m".Dump(); // 10.02m
    $"Euclid: {DistanceEuclid(lat, lng, lat0, lng0)}m".Dump(); // 10,2396639400397m
    $"Haversine: {DistanceHaversine(lat, lng, lat0, lng0)}m".Dump(); // 10,2396637520237m
}

const int R = 6371000;
const double PiBy180 = Math.PI / 180;
const double deglen = 111194.93;

double DistanceEuclid(double lat, double lng, double lat0, double lng0)
{
    var x = lat - lat0;
    var y = (lng - lng0)*Math.Cos(ToRadians(lat0));
    return deglen*Math.Sqrt(x*x + y*y);
}

public double DistanceHaversine(double lat, double lng, double lat0, double lng0)
{
    var lat1 = ToRadians(lat);
    var lat2 = ToRadians(lat0);
    var dLat = ToRadians(lat0 - lat);
    var dLng = ToRadians(lng0 - lng);
    var h = Math.Sin(dLat / 2) * Math.Sin(dLat / 2) + Math.Cos(lat1) * Math.Cos(lat2) * Math.Sin(dLng / 2) * Math.Sin(dLng / 2);
    var c = 2 * Math.Atan2(Math.Sqrt(h), Math.Sqrt(1 - h));
    return R * c;
}

double ToRadians(double degrees) => degrees * PiBy180;

@MikeEason your first link uses the Haversine formula, the other two are used to calculate the distance between points using x/y coordinates, but I have lat/lon. — wertzui
Such a simple distance formula is too slow? How many thousands of times are you calling it per frame? Maybe you should be implementing some space partitioning rather than bending over backwards to get a faster distance function. — Joren

Tarocco Tarocco · Accepted Answer · 2016-08-25T07:52:23

In the case of short distances where the curvature is negligible, you could use linear approximation and take the Euclidean distance between the points.

A quick and dirty approach for long distance measurements where curvature matters could involve pre-calculating arc lengths between points on the spheroid (i.e. earth) for distinct arc-lengths ahead of time. For instance, you would create an array(s)/lookup table to find approximate 𝘥 from quantized values of φ₀, φ₁ and Δλ (|λ₀-λ₁|) for a hemisphere about the longitudinal (vertical) axis, since the distances are the same for equal and opposite longitudinal differences. You can improve accuracy by increasing the size of the array(s). If your memory budget isn't tight, you can try making it very large.

Improving the accuracy of the approximation might be possible using specific data structures or correction formulas, but I'm not sure.

Then you can compare the range and the distance between the item and the player.

Fast Approximation if a point on earth is in range

1 Answers