Ik moet een Geo-proximity-zoekopdracht in mijn applicatie implementeren, maar ik ben erg in de war over de juiste formule die ik moet gebruiken. Na wat zoekwerk op het web en in StackOverflow ontdekte ik dat de oplossingen zijn:
- Gebruik de Haversine-formule
Gebruik de Grote-cirkelafstandsformule- Gebruik een Spatial Search Enginein de database
Optie #3 is echt geen optie voor mij ATM. Nu ben ik een beetje in de war omdat ik altijd dacht dat de Grote-cirkelafstandsformuleen Haversine-formulewaren synoniemmaar blijkbaar had ik het mis?
De bovenstaande schermafbeelding is gemaakt van de geweldige Geo (proximity) Search met MySQL papier en gebruikt de volgende functies:
ASIN, SQRT, POWER, SIN, PI, COS
Ik heb ook variaties gezien van de dezelfde formule(Sferische Cosinuswet), zoals deze:
(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))))
Dat gebruikt de volgende functies:
ACOS, COS, RADIANS, SIN
Ik ben geen wiskunde-expert, maar zijn deze formules hetzelfde? Ik ben enkele meer variaties en formulestegengekomen (zoals de Sferische Cosinusweten de Vincenty’sformules– wat de meest nauwkeurig) en dat maakt me nog meer in de war…
Ik moet een goede formule voor algemene doeleinden kiezen om te implementeren in PHP / MySQL. Kan iemand mij de verschillen uitleggen tussen de formules die ik hierboven noemde?
- Welke is het snelst te berekenen?
- Welke geeft de meest nauwkeurige resultaten?
- Welke is de beste in termen van snelheid/nauwkeurigheid van de resultaten?
Ik waardeer uw inzicht in deze vragen.
Op basis van theonlytheoryheb ik de volgende Great-Circle getest Afstandsformules:
- Vincenty-formule
- Haversine-formule
- Sferische Cosinuswet
De Vincenty-formuleis erg traag, maar is behoorlijk nauwkeurig (tot 0,5 mm).
De Haversine-formuleis veel sneller dan de Vincenty-formule, ik kon 1 miljoen berekeningen uitvoeren in ongeveer 6 seconden, wat redelijk acceptabel is voor mijn behoeften.
De Sferische Wet van Cosinus Formulebleek bijna twee keer zo snelte zijn als de Haversine Formule, en het verschil in precisie is verwaarlozingvoor de meeste gebruiksgevallen.
Hier zijn enkele testlocaties:
- Google-hoofdkantoor(
37.422045,-122.084347) - San Francisco, CA(
37.77493,-122.419416) - Eiffeltoren, Frankrijk(
48.8582,2.294407) - Opera House, Sydney(
-33.856553,151.214696)
Google-hoofdkantoor – San Francisco, CA:
- Vincenty-formule:
49 087.066 meters - Haversine-formule:
49 103.006 meters - Sferische Cosinuswet:
49 103.006 meters
Google-hoofdkantoor – Eiffeltoren, Frankrijk:
- Vincenty-formule:
8 989 724.399 meters - Haversine-formule:
8 967 042.917 meters - Sferische Cosinuswet:
8 967 042.917 meters
Google-hoofdkantoor – Opera House, Sydney:
- Vincenty-formule:
11 939 773.640 meters - Haversine-formule:
11 952 717.240 meters - Sferische Cosinuswet:
11 952 717.240 meters
Zoals je kunt zien is er geen merkbaar verschiltussen de Haversine-formule en de sferische wet van cosinus, maar beide hebben afstandsverschuivingen tot wel 22 kilometervergeleken met de Vincenty-formule omdat het een ellipsoïde benadering van de aarde gebruikt in plaats van een bolvormige.
Antwoord 1, autoriteit 100%
De wet van cosinus en de formule van Haversine geven identieke resultaten uitgaande van een machine met oneindige precisie. De Haversine-formule is robuuster voor drijvende-kommafouten. De machines van vandaag hebben echter een dubbele nauwkeurigheid in de orde van 15 significante cijfers, en de cosinusregel kan prima voor u werken. Beide formules gaan uit van bolvormige aarde, terwijl Vicenty’s iteratieve oplossing (meest nauwkeurig) uitgaat van een ellipsoïde aarde (in werkelijkheid is de aarde niet eens een ellipsoïde – het is een geoïde). Enkele referenties:
http://www.movable-type.co.uk/scripts /gis-faq-5.1.html
Het wordt beter: let op de breedtegraad die moet worden gebruikt in de cosinusregel, evenals de Haversine is de geocentrische breedtegraad, die verschilt van de geodetische breedtegraad. Voor een bol zijn deze twee hetzelfde.
Welke is het snelst te berekenen?
In volgorde van snelst naar langzaamst zijn: cosinusregel (5 trig. calls) -> haversine (betreft sqrt) -> Vicenty (moet dit iteratief oplossen in een for-lus)
Welke is het meest nauwkeurig?
Vicentie.
Welke is het beste als zowel snelheid als nauwkeurigheid worden overwogen?
Als je probleemdomein zodanig is dat voor de afstanden die je probeert te berekenen, de aarde als plat kan worden beschouwd, dan kun je (ik ga geen details geven) een formule uitwerken van de vorm x = kx * verschil in lengtegraad, y = ky * verschil in breedtegraad. Dan afstand = sqrt(dxdx + dydy). Als je probleemdomein zo is dat het kan worden opgelost met het kwadraat van de afstand, dan hoef je geen sqrt te nemen, en deze formule zal zo snel mogelijk zijn. Het heeft als bijkomend voordeel dat je de vectorafstand kunt berekenen – x is afstand in oostelijke richting, en y is afstand in noordelijke richting.
Experimenteer anders met de 3 en kies wat het beste werkt in jouw situatie.
Antwoord 2, autoriteit 33%
Dus je wilt:
- records sorteren op afstand vanaf p0
- selecteer alleen records waarvan de afstand vanaf p0 kleiner is dan r
De truc is dat je daarvoor niet precies de grootcirkelafstand hoeft te berekenen! Je kunt met elkefunctie van een paar punten tot een echte waarde die strikt meegroeit met de grote cirkelafstand tussen de punten. Er zijn veel van dergelijke functies en sommige zijn veel sneller te berekenen dan de verschillende formules voor de exacte grootcirkelafstand. Een dergelijke functie is de Euclidische afstand in 3D. Het omzetten van breedte- en lengtegraad naar een 3D-punt op de bol vereist geen inverse trigonometrische functies.
Als je eenmaal x,Y,Z hebt, kun je je realiseren dat je de afstand van p0 tot je punt niet echt nodig hebt, omdat je net zo goed de afstand van het raakvlak bij p0 kunt gebruiken. Die afstand groeit ook strikt met de grootcirkelafstand en wordt berekend uit X,Y,Z als een lineaire combinatie – er is zelfs geen vierkantswortel nodig. U hoeft alleen de coëfficiënten en de afsnijafstand die overeenkomt met de gewenste grootcirkelafstand vooraf te berekenen.