PostGIS nächstgelegene Punkte mit ST_Distance, kNN

23

Ich muss für jedes Element auf einer Tabelle den nächstgelegenen Punkt einer anderen Tabelle ermitteln. Der erste Tisch enthält Verkehrsschilder und der zweite die Eingangshallen der Stadt. Die Sache ist, dass ich die ST_ClosestPoint-Funktion nicht verwenden kann und die ST_Distance-Funktion verwenden und den min-Datensatz (ST_distance) abrufen muss, aber ich bin beim Erstellen der Abfrage ziemlich festgefahren.

CREATE TABLE traffic_signs
(
  id numeric(8,0) ),
  "GEOMETRY" geometry,
  CONSTRAINT traffic_signs_pkey PRIMARY KEY (id),
  CONSTRAINT traffic_signs_id_key UNIQUE (id)
)
WITH (
  OIDS=TRUE
);

CREATE TABLE entrance_halls
(
  id numeric(8,0) ),
  "GEOMETRY" geometry,
  CONSTRAINT entrance_halls_pkey PRIMARY KEY (id),
  CONSTRAINT entrance_halls_id_key UNIQUE (id)
)
WITH (
  OIDS=TRUE
);

Ich muss die ID der nächstgelegenen Eingangshalle jedes Verkehrszeichens erhalten.

Meine Anfrage bisher:

SELECT senal.id,port.id,ST_Distance(port."GEOMETRY",senal."GEOMETRY")  as dist
    FROM traffic_signs As senal, entrance_halls As port   
    ORDER BY senal.id,port.id,ST_Distance(port."GEOMETRY",senal."GEOMETRY")

Damit erhalte ich die Entfernung von jedem Verkehrszeichen zu jeder Eingangshalle. Aber wie kann ich nur die minimale Distanz bekommen?

Grüße,

Egidi
quelle
Welche Version von PostgreSQL?
Jakub Kania

Antworten:

41

Sie sind fast da. Es gibt einen kleinen Trick, der darin besteht, den eindeutigen Operator von Postgres zu verwenden , der das erste Match jeder Kombination zurückgibt. Wenn Sie mit ST_Distance bestellen, gibt er effektiv den nächstgelegenen Punkt von jedem Senal zu jedem Port zurück.

SELECT 
   DISTINCT ON (senal.id) senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY")  as dist
FROM traffic_signs As senal, entrance_halls As port   
ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Wenn Sie wissen, dass der Mindestabstand jeweils nicht mehr als einen Betrag x beträgt (und Sie einen räumlichen Index auf Ihren Tabellen haben), können Sie dies beschleunigen, indem Sie WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", distance)z. B. ein setzen, wenn alle Mindestabstände bekannt sind nicht mehr als 10km, dann:

SELECT 
   DISTINCT ON (senal.id) senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY")  as dist
FROM traffic_signs As senal, entrance_halls As port  
WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", 10000) 
ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Offensichtlich muss dies mit Vorsicht angewendet werden, da bei einem größeren Mindestabstand einfach keine Zeile für diese Kombination aus Senal und Port angezeigt wird.

Hinweis: Die Reihenfolge nach Reihenfolge muss mit der eindeutigen Reihenfolge übereinstimmen. Dies ist sinnvoll, da die erste eindeutige Gruppe basierend auf einer bestimmten Reihenfolge eindeutig ist.

Es wird davon ausgegangen, dass Sie für beide Tabellen einen räumlichen Index haben.

EDIT 1 . Es gibt eine weitere Option, nämlich die Verwendung der Postgres-Operatoren <-> und <#> (Mittelpunkt- bzw. Begrenzungsrahmen-Abstandsberechnungen), die den räumlichen Index effizienter nutzen und keinen ST_DWithin-Hack zur Vermeidung von n erfordern ^ 2 Vergleiche. Es gibt einen guten Blog-Artikel, der erklärt, wie sie funktionieren. Allgemein ist zu beachten, dass diese beiden Operatoren in der ORDER BY-Klausel arbeiten.

SELECT senal.id, 
  (SELECT port.id 
   FROM entrance_halls as port 
   ORDER BY senal.geom <#> port.geom LIMIT 1)
FROM  traffic_signs as senal;

BEARBEITEN 2 . Da diese Frage viel Beachtung gefunden hat und k-Nearest Neighbours (kNN) im Allgemeinen ein schwieriges Problem (in Bezug auf die algorithmische Laufzeit) in GIS darstellt, scheint es sinnvoll, den ursprünglichen Umfang dieser Frage etwas zu erweitern.

Die Standardmethode, um die x nächsten Nachbarn eines Objekts zu finden, ist die Verwendung eines LATERAL JOIN (konzeptionell a für jede Schleife ähnlich). Wenn Sie sich schamlos von dbastons Antwort leihen , würden Sie etwas tun wie:

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports
      ORDER BY signs.geom <-> ports.geom
     LIMIT 1
   ) AS closest_port

Wenn Sie also die nächsten 10 Ports nach Entfernung geordnet finden möchten, müssen Sie lediglich die LIMIT-Klausel in der seitlichen Unterabfrage ändern. Dies ist ohne LATERAL JOINS viel schwieriger und erfordert die Verwendung von ARRAY-Typ-Logik. Obwohl dieser Ansatz gut funktioniert, kann er enorm beschleunigt werden, wenn Sie wissen, dass Sie nur bis zu einer bestimmten Entfernung suchen müssen. In diesem Fall können Sie ST_DWithin (signs.geom, ports.geom, 1000) in der Unterabfrage verwenden. Aufgrund der Funktionsweise der Indizierung mit dem Operator <-> sollte eine der Geometrien eine Konstante sein und nicht ein Spaltenreferenz - kann viel schneller sein. Um beispielsweise die 3 nächstgelegenen Häfen innerhalb von 10 km zu finden, können Sie Folgendes schreiben.

 SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports
      WHERE ST_DWithin(ports.geom, signs.geom, 10000)
      ORDER BY ST_Distance(ports.geom, signs.geom)
     LIMIT 3
   ) AS closest_port;

Wie immer hängt die Verwendung von Ihrer Datenverteilung und Ihren Abfragen ab. EXPLAIN ist also Ihr bester Freund.

Schließlich gibt es ein kleines Problem, wenn Sie LEFT anstelle von CROSS JOIN LATERAL verwenden und nach dem Query- Alias ON TRUE hinzufügen müssen , z.

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
LEFT JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports          
      ORDER BY signs.geom <-> ports.geom
      LIMIT 1
   ) AS closest_port
   ON TRUE;
John Powell
quelle
Es ist zu beachten, dass dies bei großen Datenmengen nicht gut funktioniert.
Jakub Kania
@ JakubKania. Es hängt davon ab, ob Sie ST_DWithin verwenden können oder nicht. Aber ja, Punkt genommen. Leider erfordert der Operator Reihenfolge nach <-> / <#>, dass eine der Geometrien eine Konstante ist, nicht wahr?
John Powell
@ JohnPowellakaBarça Weißt du vielleicht, wo dieser Blog-Beitrag heutzutage lebt? - oder eine ähnliche Erklärung der Operatoren <-> und <#>? Vielen Dank!!
DPSSpatial
@DPSSpatial, das ist nervig. Ich nicht, aber es gibt dieses und jenes, das ein bisschen über diesen Ansatz spricht. Die zweite, die auch laterale Joins verwendet, ist eine weitere interessante Verbesserung.
John Powell
@DPSSpatial. Es ist alles ein bisschen rutschig dieses <->, <#> und laterale Join-Zeug. Ich habe dies mit sehr großen Datenmengen gemacht und die Leistung war schrecklich, ohne ST_DWithin zu verwenden, was all dies vermeiden soll. Letztendlich ist knn ein kompliziertes Problem, daher kann die Verwendung variieren. Viel Glück :-)
John Powell
13

Dies kann mit einem LATERAL JOINin PostgreSQL 9.3+ durchgeführt werden:

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
     id, 
     ST_Distance(ports.geom, signs.geom) as dist
     FROM ports
     ORDER BY signs.geom <-> ports.geom
   LIMIT 1) AS closest_port
dbaston
quelle
10

Der Ansatz mit Cross-Join verwendet keine Indizes und erfordert viel Speicher. Sie haben also grundsätzlich zwei Möglichkeiten. Vor Version 9.3 würden Sie eine korrelierte Unterabfrage verwenden. 9.3+ können Sie a verwenden LATERAL JOIN.

KNN GIST mit einem lateralen Twist Bald in einer Datenbank in Ihrer Nähe

(genaue Fragen folgen in Kürze)

Jakub Kania
quelle
1
Coole Verwendung einer seitlichen Verbindung. Hatte das in diesem Zusammenhang noch nie gesehen.
John Powell
1
@ JohnBarça Es ist einer der besten Zusammenhänge, die ich gesehen habe. Ich vermute auch, dass dies hilfreich ist, wenn Sie wirklich das ST_DISTANCE()nächste Polygon suchen müssen und der Server durch Cross-Joins nicht mehr genügend Arbeitsspeicher hat. Die nächste Polygonabfrage ist noch ungelöst.
Jakub Kania
2

@ John Barça

ORDER BY ist falsch!

ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Recht

senal.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY"),port.id;

Andernfalls wird nicht der nächste zurückgegeben, sondern nur der mit der kleinen Port-ID

Dehnung
quelle
1
Das richtige sieht so aus (ich habe Punkte und Linien verwendet):SELECT DISTINCT ON (points.id) points.id, lines.id, ST_Distance(lines.geom, points.geom) as dist FROM development.passed_entries As points, development."de_muc_rawSections_cleaned" As lines ORDER BY points.id, ST_Distance(lines.geom, points.geom),lines.id;
blackgis
1
OK, ich verstehe dich jetzt. Es ist tatsächlich wahrscheinlich besser, den Ansatz LATERAL JOIN zu verwenden, wie in @ dbastons Antwort, der verdeutlicht, welche Sache in Bezug auf die Nähe mit welcher anderen Sache verglichen wird. Ich benutze den obigen Ansatz nicht mehr.
John Powell