0

对于游戏，我需要计算地图上的项目是否在玩家的范围内。地图就是地球。我正在使用 Haversine 公式来计算玩家和每个项目之间的距离。然而，我做了一些分析，发现所有这些 sin/cos 计算都太慢了，无法进行平滑的游戏。

是否有其他方法可以检查地球上的两个点可能在 x 米的范围内？该方法不需要精确，但它必须快速并在距离 <= x 时返回 true。如果距离 > x，它也可能返回真（但不应该总是返回真）。

我的测试代码（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;
4

1 回答 1

0

在曲率可以忽略不计的短距离情况下，您可以使用线性近似并取点之间的欧几里得距离。

对于曲率很重要的长距离测量，一种快速而肮脏的方法可能涉及提前计算球体（即地球）上各点之间的弧长，以获得不同的弧长。例如，您将创建一个数组/查找表，从 φ₀、φ₁ 和 Δλ (|λ₀-λ₁|) 的量化值中找到关于纵（垂直）轴的半球的近似值，因为距离是相同的对于相等和相反的纵向差异。您可以通过增加数组的大小来提高准确性。如果您的内存预算不紧张，您可以尝试将其设置得非常大。

使用特定的数据结构或校正公式可能会提高近似值的准确性，但我不确定。

然后你可以比较物品和玩家之间的范围和距离。

于 2016-08-25T07:52:23.997 回答