Formules pour calculer la proximité géographique
j'ai besoin de mettre en place une recherche de proximité géo dans mon application mais je suis très confus en ce qui concerne la formule correcte à utiliser. Après quelques recherches dans le Web et dans StackOverflow j'ai trouvé que les solutions sont:
- utilisez la formule Haversine
-
utilisez la formule de grand cercle de Distance - utiliser un Spatial Moteur de recherche dans la base de données
L'Option #3 n'est vraiment pas une option pour moi ATM. Maintenant je suis un peu confus depuis que j'ai toujours pensé que la formule grand-cercle de Distance et formule Haversine étaient synonyme mais apparemment j'avais tort?
formule de Haversine http://i46.tinypic.com/30shbn6.png
la prise de vue ci-dessus a été prise de l'écran impressionnant géo (proximité) Recherche avec MySQL Papier, et utilise les fonctions suivantes:
ASIN, SQRT, POWER, SIN, PI, COS
j'ai également vu des variations de la même formule ( loi Sphérique des cosinus ) , comme celui-ci:
(3956 * ACOS(COS(RADIANS(o_lat)) * COS(RADIANS(d_lat)) * COS(RADIANS(d_lon) - RADIANS(o_lon)) + SIN(RADIANS(o_lat)) * SIN(RADIANS(d_lat))))
Qui utilise les fonctions suivantes:
ACOS, COS, RADIANS, SIN
Je ne suis pas un expert en mathématiques, mais ces formules sont-elles les mêmes? J'ai rencontré quelques plus de variations, et des formules (comme le loi Sphérique des cosinus et le Vincenty's formules "1519400920 - qui semble être le plus précis) et ça me rend encore plus confus...
I besoin de choisir une bonne formule d'usage général à mettre en œuvre dans PHP / MySQL. Quelqu'un peut-il m'expliquer les différences entre les formules que j'ai mentionné ci-dessus?
- lequel est le plus rapide à calculer?
- lequel fournit les résultats les plus précis?
- laquelle est la meilleure en termes de vitesse / précision des résultats?
je vous remercie de votre compréhension de ces questions.
basé sur theonlytheory réponse j'ai testé les formules de Distance Grand-Cercle suivantes:
- Formule De Vincenty
- Formule De Haversine
- loi Sphérique des cosinus
la formule de Vincenty est dead slow, cependant c'est assez précis (jusqu'à 0.5 mm) .
la formule de Haversine est beaucoup plus rapide que la formule de Vincenty, j'ai pu exécuter 1 million de calculs en environ 6 secondes ce qui est à peu près acceptable pour mes besoins.
Le Sphérique de la Loi des Cosinus Formule révélé presque deux fois plus vite , comme le Formule Haversine, et la différence de précision est négligente pour la plupart des cas d'utilisation.
voici quelques emplacements d'essai:
- Google HQ (
37.422045,-122.084347) - San Francisco, CA (
37.77493,-122.419416) - Tour Eiffel, France (
48.8582,2.294407) - Opéra De Sydney (
-33.856553,151.214696)
Google HQ-San Francisco, CA:
- Formule De Vincenty:
49 087.066 meters - Haversine Formule:
49 103.006 meters - loi Sphérique des cosinus:
49 103.006 meters
Google HQ-Tour Eiffel, France:
- Formule De Vincenty:
8 989 724.399 meters - Haversine Formule:
8 967 042.917 meters - loi Sphérique des cosinus:
8 967 042.917 meters
Google HQ-Opera House, Sydney:
- Vincenty Formule:
11 939 773.640 meters - Haversine Formule:
11 952 717.240 meters - loi Sphérique des cosinus:
11 952 717.240 meters
comme vous pouvez le voir, il ya aucune différence notable entre la formule Haversine et la loi sphérique de Cosines, mais les deux ont compensations de distance aussi élevé que 22 kilomètres par rapport à la formule Vincenty parce qu'il utilise un ellipsoïdale rapprochement de la terre à la place d'une sphérique.
2 réponses
la Loi de Cosines et la formule de Haversine donneront des résultats identiques en supposant une machine avec une précision infinie. La formule de Haversine est plus robuste aux erreurs de virgule flottante. Cependant, les machines d'aujourd'hui ont une double précision de l'ordre de 15 chiffres significatifs, et la loi de cosines peut fonctionner tout à fait bien pour vous. Ces deux formules supposent la Terre sphérique, tandis que la solution itérative de Vicenty (la plus précise) suppose la terre ellipsoïdale (en réalité la terre n'est même pas un ellipsoïde - c'est un géoïde). Quelques références: http://www.movable-type.co.uk/scripts/gis-faq-5.1.html
Il est de mieux en mieux: note de latitude pour être utilisé dans la loi des cosinus ainsi que la Haversine est la latitude géocentrique, qui est différente de la latitude géodésique. Pour une sphère, ces deux sont les mêmes.
Lequel est le plus rapide à calculer?
dans l'ordre du plus rapide au plus lent sont: la loi de cosines (5 trig. appels) - > haversine (implique sqrt) - > Vicenty (doivent résoudre ce itérativement dans une boucle)
Lequel est le plus précis?
Vicenty.
laquelle est la meilleure lorsque l'on tient compte à la fois de la vitesse et de la précision?
si votre domaine de problème est tel que pour les distances que vous essayez de calculer, la terre peut être considérée comme plate, alors vous pouvez travailler (Je ne vais pas donner de détails) une formule de la forme x = kx * différence de longitude, y = ky * différence de latitude. Puis distance = sqrt (DX dx + dy dy). Si votre problème de domaine est tel qu'il peut être résolu avec la distance au carré, alors vous n'aurez pas à prendre sqrt, et cette formule sera aussi rapide que vous obtenez éventuellement obtenir. Il a l'avantage supplémentaire que vous pouvez calculer le vecteur distance - x est la distance dans la direction de l'est, et y est la distance dans la direction du Nord. Autrement, expérimentez avec les 3 et choisissez ce qui fonctionne le mieux dans votre situation.
vous voulez Donc:
- trier les enregistrements selon la distance de p0
- sélectionner seulement les enregistrements dont la distance de p0 est inférieure à r
l'astuce est que vous n'avez pas exactement besoin de calculer la grande distance du cercle pour cela! Vous pouvez faire avec n'importe quelle" fonction 1519100920 "d'une paire de points à une valeur réelle qui se développe strictement avec le grand cercle distance entre les points . Il y a beaucoup de telles fonctions et certaines sont beaucoup plus rapides à calculer que les diverses formules pour la distance exacte grand cercle. Une de ces fonctions est la distance euclidienne en 3D. Convertir latitude et longitude à un point 3D sur la sphère n'implique pas de fonctions trigonométriques inverses.
une fois que vous avez x,Y,Z, Vous pouvez réaliser que vous n'avez pas réellement besoin de la distance de p0 à votre point, parce que vous pouvez aussi bien utiliser la distance du plan tangent à p0. Cette distance augmente aussi strictement avec la distance du grand cercle, et est calculée à partir de X,Y, Z comme une combinaison linéaire - même une racine carrée n'est pas nécessaire. Vous avez juste besoin de précalculer les coefficients et la distance limite qui correspond à la valeur souhaitée distance orthodromique.