Welcher SRS soll für globale Entfernungsabfragen verwendet werden?

8

Ich habe eine Datenbank mit vielen Punkten in WGS84. Jetzt erstelle ich einen Cache, der NN ausführt und mithilfe eines KDtree in Bereichsabfragen zeigt. Der Punkt ist, dass der Suchradius in Metern angegeben wird und dass lat / lon kein netter SRS für diese geometrischen Abfragen ist.

Ich suche ein geometrisches SRS, das auf die ganze Welt anwendbar ist und Entfernungen bewahrt. Fehler von ein paar Zehntel Metern interessieren mich nicht.

coordinate-system distance nearest-neighbor RickyA
quelle
Warum konvertieren Sie nicht alle Punkte in 3D-xyz-Koordinaten (geozentrisch) und bauen darauf Ihren KD-Baum auf? Obwohl Entfernungen nicht beibehalten werden, können Entfernungen auf der Kugel für Abfragezwecke leicht in Entfernungen in 3D konvertiert werden. Tatsächlich ist es so einfach, Lat-Lon mit einem Ellipsoidmodell in XYZ umzuwandeln, dass Sie überhaupt keine Genauigkeit opfern müssen, aber selbst wenn Sie ein sphärisches Modell verwenden, sollten alle Abstände (im schlimmsten Fall) auf etwa 0,3% genau sein ).
whuber

Antworten:

2

Ich habe nach "Spherical Spatial Index" gegoogelt. Es gibt eine Reihe möglicher Methoden, bei denen die Kugel dreieckig zerlegt oder voronoi gekachelt wird. Eine Methode, die leicht zu implementieren ist, besteht darin, Ihre Daten in 3D zu betrachten, wie im Abschnitt "3D-Begrenzungsrahmen" hier:

http://lin-ear-th-inking.blogspot.co.uk/2007/09/geodetic-data-in-postgis-spherical.html

Dann brauchen Sie einen räumlichen 3D-Index, dann können Sie schnell alle Punkte innerhalb Ihrer 1 km finden. Dies wäre ein 3D- Suchradius von 1 km , der sich geringfügig von einem Radius von 1 km entlang der Erdoberfläche unterscheidet. Bei kleinen Suchradien wäre er jedoch effektiv identisch (rechnen Sie nach, um die Korrektur zu berechnen).

Wenn Sie absolute Präzision wünschen, verwenden Sie dies als ersten Schritt und berechnen Sie dann die Entfernungen über einen Großkreis, um die weiter entfernten zu entfernen (die Entfernung entlang einer Kugel ist immer größer als die Entfernung durch eine Kugel).

Spacedman
quelle
Hey, das ist eine Idee! Ich könnte mich in meinem KDTree in eine andere Dimension quetschen und damit arbeiten.
Muss aber noch
4

Bei SRS / Map-Projektionen ist dies immer ein Kompromiss. Es gibt wirklich keinen, der zu allen Orten der Welt passt. Könnte auch annehmen, dass die Erde eine Kugel ist.

Anstatt nach einem SRS zu suchen, der für die ganze Welt geeignet ist, sollten Sie besser nach Algorithmen zur Entfernungsberechnung suchen . Ein Beispiel ist der Great Circle Distance, der auf sphärischer Trigonometrie basiert. Es werden jedoch folgende Annahmen getroffen:

  • 1 Bogenminute entspricht 1 Seemeile
  • 1 Seemeile ist 1,852 km.

Die Formel lautet:

D = 1.852 * 60 * ARCOS ( SIN(L1) * SIN(L2) + COS(L1) * COS(L2) * COS(DG)

Wo:

L1  =   latitude at the first point (degrees)
L2  =   latitude at the second point (degrees)
G1  =   longitude at the first point (degrees)
G2  =   longitude at the second point (degrees)
DG  =   longitude of the second point minus longitude of the first point (degrees)
DL  =   latitude of the second point minus latitude of the first point (degrees)
D   =   computed distance (km)

Möglicherweise möchten Sie es jedoch zuerst mit Ihren Daten testen und die Ergebnisse anzeigen. Übrigens, verwenden Sie eine räumliche Datenbank wie PostGIS?

RK
quelle
Nun, das ist der Punkt. Postgis ist mir nicht schnell genug. Was ich jetzt mache, ist, alle Punkte in Redis zu setzen und einen KDtree-Index darüber zu erstellen. ABER der KDtree ist eine geometrische Lösung. Wenn ich ihm eine Frage wie "Alle Punkte in einem Radius von 1k geben" stelle, wird der Abstand geometrisch überschritten. Ich kann dort keinen Haversine machen. Ich muss es vorher in einen ungefähr äquidistanten SRS umwandeln. Aber welcher?
RickyA
Meine Antwort wurde mit der Formel aktualisiert. Das ist das Problem, es gibt kein projiziertes (geometrisches) SRS / CRS, das auf die ganze Welt anwendbar ist.
RK
Und die besten ca.? Die Pole interessieren mich nicht wirklich, nur die Pinguine dort, aber etwas, das geometrisch besser funktioniert als WGS84?
RickyA
Postgis unterstützt die sphärische Ebene, wenn der Geografietyp anstelle der Geometrie verwendet wird. postgis.refractions.net/docs/…
Nickves
1
@nickves ja das habe ich gesehen, aber postgis ist mir wirklich nicht schnell genug. Ich benötige weniger als 2 ms Latenz und sollte 1000 Anfragen pro Sekunde verarbeiten können. Ich könnte aber Postgis Lösungen
rückentwickeln