Approximation rapide si un point sur la terre est dans la plage

Question

Pour un jeu, j'ai besoin de calculer si les objets sur la carte sont à portée du joueur. La carte est la terre. J'utilise la formule de Haversine pour calculer la distance entre le joueur et chaque objet. Cependant, j'ai fait quelques profils et découvert que tous ces calculs sin/cos sont trop lents pour permettre un gameplay smoth. Y a-t-il une autre méthode pour vérifier que deux points sur terre pourraient avoir une portée de x mètres? La méthode n'a pas besoin d'être exacte, mais elle doit être rapide et renvoyer vrai si la distance < = x. Il peut aussi renvoyer true si distance> x (mais ne devrait pas toujours retourner vrai).

Mon code de test (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

Dans le cas de courtes distances où la courbure est négligeable, vous pouvez utiliser l'approximation linéaire et prendre la distance euclidienne entre les points. Une approche rapide et encrassée pour les mesures à longue distance où la courbure est importante pourrait impliquer de pré-calculer des longueurs d'arc entre des points sur le sphéroïde (c'est-à-dire la terre) pour des longueurs d'arc distinctes à l'avance. Par exemple, vous créez un tableau (s)/table de recherche pour trouver approximatif des valeurs quantifiées de φ₀, φ₁ et Δλ (| λ₀-λ₁ |) pour un hémisphère autour de l'axe longitudinal (vertical), puisque les distances sont les mêmes pour les différences longitudinales égales et opposées. Vous pouvez améliorer la précision en augmentant la taille du ou des tableaux. Si votre budget de mémoire n'est pas serré, vous pouvez essayer de le rendre très grand.

Améliorer la précision de l'approximation pourrait être possible en utilisant des structures de données spécifiques ou des formules de correction, mais je ne suis pas sûr.

Ensuite, vous pouvez comparer la portée et la distance entre l'élément et le lecteur.