Wie finde ich effizient den nächstgelegenen Punkt über der Datenlinie?

10

Ich habe eine PostgreSQL 9.1-Tabelle mit Hunderttausenden von PostGIS-PUNKTEN. Für jede dieser Punkte möchte ich den nächstgelegenen Punkt in einer anderen Tabelle von PUNKTEN finden. Die Punkte in der zweiten Tabelle stellen ein Raster auf der ganzen Welt dar, daher weiß ich, dass es immer eine Übereinstimmung innerhalb von 1 Grad geben wird. Dies ist die Abfrage, die ich bisher verwende und die GIST-Indizes verwendet. Sie ist also relativ schnell (insgesamt ca. 30 Sekunden).

SELECT DISTINCT ON (p.id)
    p.id, ST_AsText(p.pos)
    , ST_AsText(first_value(g.location) OVER (PARTITION BY p.id ORDER BY ST_Distance(p.pos, g.location::geography)))
FROM point p
JOIN grid g ON ST_DWithin(p.pos::geometry, g.location, 1)

Das einzige Problem ist die Datumsgrenze. Die Gitterpunkte haben nur 180 Breitengrad, nicht -180. Bei Verwendung der Geometrieversion von ST_Distance werden keine Punkte auf der anderen Seite der Datenlinie zurückgegeben. Z.B. Wenn p.pos POINT(-179.88056 -16.68833)der nächste Gitterpunkt ist, wird er möglicherweise zurückgegeben POINT(180 -16.25), die obige Abfrage gibt ihn jedoch nicht zurück. Was ist der beste Weg, um dies zu beheben?

Ich möchte nicht wirklich zwei Koordinaten für einen einzelnen Gitterpunkt haben (-180 und +180). Ich habe versucht, meine eigene Funktion hinzuzufügen, die nach diesem speziellen Fall sucht, aber dann wird die Abfrage nicht innerhalb von 5 Minuten zurückgegeben, wahrscheinlich weil sie den Index nicht mehr verwenden kann. Ich habe auch versucht, die geografische Version von ST_DWithin zu verwenden, und diese Abfrage wurde auch nach 5 Minuten nicht zurückgegeben.

postgis nearest-neighbor EM0
quelle
Gute Frage (und kluger Hack in Ihrer Antwort!). Man muss sich jedoch fragen: Wenn die Software -180 = 180 für den Längengrad nicht erkennen kann, gibt sie wahrscheinlich vor, dass es sich um projizierte Koordinaten handelt, und verwendet euklidische Algorithmen, um die nächstgelegenen Punkte zu finden, was zu Fehlern führen wird (subtile Nähe) der Äquator, riesig in der Nähe der Pole und der + -180 Meridiane). Ich weiß nicht, ob dies zu erheblichen Problemen in Ihrer Anwendung führt, aber in vielen anderen Fällen wird dies der Fall sein, und diese Umgehung wird die Fehler nicht beheben.
whuber
Guter Punkt, aber in diesem Fall führt die Clientanwendung keine anderen "engsten" Berechnungen durch - sie erhält nur einige Daten, die dem von meiner Abfrage zurückgegebenen Rasterpunkt zugeordnet sind.
EM0

Antworten:

6

OK, ich habe endlich einen Weg gefunden, es zu hacken, der nicht nur das Problem mit der Datenlinie umgeht, sondern auch schneller ist.

CREATE OR REPLACE FUNCTION nearest_grid_point(point geography(Point))
RETURNS integer
AS $BODY$
    SELECT pointid
    FROM
    (
            -- The normal case
        SELECT pointid, location
        FROM grid
        WHERE ST_DWithin($1::geometry, location, 1)

        UNION ALL

            -- The dateline hack
        SELECT pointid, location
        FROM grid
        WHERE (ST_X($1::geometry) < -178.75 AND longitude = 180)
    ) sub
    ORDER BY ST_Distance($1, location::geography)
    LIMIT 1;
$BODY$ LANGUAGE SQL STABLE;

SELECT p.id, ST_AsText(p.pos), g.pointid, ST_AsText(g.location)
FROM point p
JOIN grid g ON nearest_grid_point(p.pos) = g.pointid

Ich war sehr überrascht zu sehen, dass diese Funktion, die für jede Zeile aufgerufen wird, schneller als die ursprüngliche Fensterfunktion ist, aber - mehr als zehnmal schneller. PostgreSQL-Performance ist wirklich eine schwarze Kunst!

EM0
quelle