Formeln zur Berechnung der Geo-Nähe

Brauche ich zur Umsetzung einer Geo-Umkreissuche in meiner Anwendung, aber ich bin sehr verwirrt in Bezug auf die richtige Formel zu verwenden. Nach einigen Recherchen im Web und in StackOverflow fand ich, dass die Lösungen sind:

  1. Verwenden Sie die Haversine Formel
  2. Verwenden Sie die Great-Circle-Distance-Formel
  3. Verwenden Räumliche Suchmaschinen - in der Datenbank

Option #3 ist nicht wirklich eine option für mich ATM. Jetzt bin ich ein wenig verwirrt, da ich immer dachte, dass der Great-Circle-Distance-Formel und Haversine Formel wurden Synonym aber anscheinend war ich falsch?

Haversine Formel http://i46.tinypic.com/30shbn6.png

Oben im Bild war genommen von der atemberaubenden Geo (Nähe) - Suche mit MySQL Papier, und nutzt die folgenden Funktionen:

ASIN, SQRT, POWER, SIN, PI, COS

Habe ich auch gesehen, die Abweichungen von der gleiche Formel (Sphärische Gesetz der Cosinus)wie diese:

(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))))

Verwendet, die folgenden Funktionen:

ACOS, COS, RADIANS, SIN

Ich bin kein Mathe-Experte, aber sind diese Formeln das gleiche? Ich habe über einige mehr Variationen und Formeln (wie die Sphärische Gesetz der Cosinus und die Vincenty ist Formeln - das scheint die Genaueste) und das macht mich noch mehr verwirrt...

Brauche ich, um wählen Sie ein gutes Allzweck-Formel zur Umsetzung in PHP /MySQL. Kann jemand mir erklären die Unterschiede zwischen den Formeln, die ich oben erwähnte?

  • Welches ist das am schnellsten zu berechnen?
  • Die eine liefert die genauesten Ergebnisse?
  • Welche ist die beste in Bezug auf Geschwindigkeit /Genauigkeit der Ergebnisse?

Ich Schätze Ihre Einsicht auf diese Fragen.

Basierend auf theonlytheory Antwort getestet habe ich die folgenden Great-Circle-Distance-Formeln:

  • Vincenty-Formel
  • Haversine Formel
  • Sphärische Gesetz der Cosinus

Den Vincenty-Formel tot ist langsam, aber es ist ziemlich genau (bis 0,5 mm).

Den Haversine Formel ist wesentlich schneller als die Vincenty-Formel, ich war in der Lage zu laufen 1 million Berechnungen in etwa 6 Sekunden, was ziemlich viel ist akzeptabel für meine Bedürfnisse.

Den Sphärische Gesetz der Cosinus-Formel offenbart werden fast doppelt so schnell als die Haversine Formel, und die Präzision Unterschied ist neglectfulness für die meisten Einsatzszenarien.

Hier sind einige test-Standorte:

  • Google HQ (37.422045-122.084347)
  • San Francisco, CA (37.77493-122.419416)
  • Eiffelturm, Frankreich (48.85822.294407)
  • Opera House, Sydney (-33.856553151.214696)

Google-HQ - San Francisco, CA:

  • Vincenty-Formel: 49 087.066 meters
  • Haversine-Formel: 49 103.006 meters
  • Sphärische Gesetz des Cosinus: 49 103.006 meters

Google-HQ - Eiffel Tower, Frankreich:

  • Vincenty-Formel: 8 989 724.399 meters
  • Haversine-Formel: 8 967 042.917 meters
  • Sphärische Gesetz des Cosinus: 8 967 042.917 meters

Google-HQ - Opera House, Sydney:

  • Vincenty-Formel: 11 939 773.640 meters
  • Haversine-Formel: 11 952 717.240 meters
  • Sphärische Gesetz des Cosinus: 11 952 717.240 meters

Wie Sie sehen können gibt es keinen spürbaren Unterschied zwischen der Haversine-Formel und das Sphärische Gesetz des Cosinus, aber beide haben Entfernung offsets so hoch wie der 22 Kilometer im Vergleich zu der Vincenty-Formel, da es verwendet eine längliche Annäherung an die Erde statt einer sphärischen.

InformationsquelleAutor der Frage Alix Axel | 2010-01-19

  1. 34

    Das Gesetz der Cosinus-und der Haversine Formel geben identische Ergebnisse, vorausgesetzt, die Maschine mit unendlicher Genauigkeit. Die Haversine Formel ist robuster floating point Fehler. Allerdings sind die heutigen Maschinen haben die doppelte Genauigkeit von 15 signifikanten zahlen, und das Gesetz der Cosinus kann nur gut funktionieren für Sie. Diese beiden Formeln setzen sphärischen Erde, in der Erwägung, dass Vicenty die iterative Lösung (möglichst genaue) geht von einer ellipsoidischen Erde (in Wirklichkeit ist die Erde nicht auch ein ellipsoid - es ist ein geoid). Einige Referenzen:
    http://www.movable-type.co.uk/scripts/gis-faq-5.1.html

    Es wird noch besser: beachten Sie die Breite, die verwendet werden, in das Gesetz der Cosinus sowie die Haversine ist die geozentrische Breite, die sich von den geodätischen Breitengrad. Für eine Kugel, diese beiden sind die gleichen.

    Welches ist am schnellsten zu berechnen?

    In der Reihenfolge vom schnellsten zum langsamsten sind: Gesetz der Cosinus (5 trig. Anrufe) -> haversine (beinhaltet sqrt) -> Vicenty (zu lösen haben, diese iterativ in einer for-Schleife)

    Welche ist die Genaueste?

    Vicenty.

    Welche am besten ist, wenn die Geschwindigkeit und Genauigkeit sind beide in Betracht gezogen?

    Wenn Ihr problem mit der domain ist so, dass für die Entfernungen, die Sie versuchen, zu berechnen, die Erde kann als Wohnung, dann kannst du (ich bin nicht zu geben, details) eine Formel der form x = kx * Unterschied in der Länge, y = ky * Unterschied in der Breite. Dann Entfernung = sqrt(dxdx + dydy). Wenn Ihr problem mit der domain ist so, dass es gelöst werden kann mit der Entfernung quadratisch, dann werden Sie nicht haben, zu nehmen, sqrt, und diese Formel wird so schnell wie Sie möglicherweise erhalten. Es hat den zusätzlichen Vorteil, dass Sie berechnen können, die Vektor Abstand - x ist der Abstand in Ost-Richtung und y-Abstand in nördlicher Richtung.
    Ansonsten Experimentieren Sie mit den 3 und wählen Sie, was am besten funktioniert in Ihrer situation.

    InformationsquelleAutor der Antwort morpheus

  2. 11

    Du willst also:

    • Sortieren von Datensätzen durch die Entfernung von p0
    • wählen Sie nur die Datensätze, deren Abstand von p0 ist weniger als r

    Der trick ist, dass Sie nicht genau, müssen zur Berechnung der großkreisentfernung! Sie können tun, mit alle Funktion von ein paar der Punkte, die einen realen Wert streng wächst mit dem großen Kreis, der Abstand zwischen den Punkten. Es gibt viele solcher Funktionen, und einige sind viel schneller zu berechnen als die verschiedenen Formeln für die exakte großkreisentfernung. Eine solche Funktion ist der euklidische Abstand in 3D. Umwandlung von Längen-und Breitengrad, zu einem 3D-Punkt auf der Kugel nicht um inverse trigonometrische Funktionen.

    Sobald Sie die x -, Y -, Z -, können Sie erkennen, dass Sie nicht wirklich brauchen, die Distanz von p0 zu Ihrem Punkt, denn man kann auch den Abstand von der Tangente Ebene an p0. Dass die Entfernung auch streng wächst mit der großkreisentfernung, und berechnet sich aus X,Y,Z als lineare Kombination - nicht einmal eine Wurzel benötigt wird. Sie müssen nur precompute die Koeffizienten und die cutoff-Distanz entspricht, die gewünschte great circle distance.

    InformationsquelleAutor der Antwort BASTA

Schreibe einen Kommentar