Быстрое приближение, если точка на земле находится в радиусе действия

Question

Для игры мне нужно рассчитать, находятся ли предметы на карте в зоне действия игрока. Карта - это земля. Я использую формулу Хаверсайна для расчета расстояния между игроком и каждым предметом. Тем не менее, я провел некоторое профилирование и обнаружил, что все эти вычисления sin / cos слишком медленные, чтобы учесть небольшой игровой процесс.

Есть ли какой-то другой способ проверки двух точек на земле, который может быть в диапазоне х метров? Метод не должен быть точным, но он должен быть быстрым и возвращать true, если расстояние <= x. Он также может возвращать true, если расстояние> x (но не всегда должно возвращать true).

Мой тестовый код (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;

Answer 1

В случае коротких расстояний, когда кривизна незначительна, вы можете использовать линейное приближение и взять евклидово расстояние между точками.

Быстрый и грязный подход к измерениям на больших расстояниях, где вопросы кривизны могут включать предварительный расчет длин дуг между точками на сфероиде (то есть земле) для различных длин дуг заранее. Например, вы должны создать массив (ы)/ справочную таблицу, чтобы найти приближенные из квантованных значений φ₀, φ₁ и Δλ (|λ₀-λ₁|) для полушария относительно продольной (вертикальной) оси, поскольку расстояния одинаковы для равных и противоположных продольных разностей. Вы можете повысить точность, увеличив размер массива (ов). Если у вас недостаточно памяти, попробуйте сделать его очень большим.

Повышение точности аппроксимации может быть возможно с использованием конкретных структур данных или формул коррекции, но я не уверен.

Затем вы можете сравнить расстояние и расстояние между предметом и игроком.