PostGIS najbliższe punkty za pomocą ST_Distance, kNN

23

Muszę uzyskać dla każdego elementu na jednym stole najbliższy punkt innego stołu. Pierwszy stół zawiera znaki drogowe, a drugi Hol wejściowy miasta. Chodzi o to, że nie mogę użyć funkcji ST_ClosestPoint i muszę użyć funkcji ST_Distance i uzyskać rekord min (ST_distance), ale utknąłem przy tworzeniu zapytania.

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

Muszę uzyskać identyfikator najbliższego wejścia_hall każdego traffic_sign.

Moje zapytanie do tej pory:

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

Dzięki temu uzyskuję odległość od każdego znaku ruchu do każdego wejścia. Ale jak mogę uzyskać tylko minimalny dystans?

Pozdrowienia,

Egidi
źródło
Jaka wersja PostgreSQL?
Jakub Kania,

Odpowiedzi:

41

Jesteś prawie na miejscu. Jest mała sztuczka polegająca na użyciu odrębnego operatora Postgres , który zwróci pierwsze dopasowanie każdej kombinacji - gdy zamawiasz przez ST_Distance, skutecznie zwróci najbliższy punkt z każdego senalu do każdego portu.

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");

Jeśli wiesz, że minimalna odległość w każdym przypadku nie jest większa niż pewna ilość x (i masz indeks przestrzenny na swoich stołach), możesz to przyspieszyć, umieszczając WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", distance)np. Jeśli wiadomo, że wszystkie minimalne odległości są nie więcej niż 10 km, a następnie:

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");

Oczywiście należy to zachować ostrożnie, ponieważ jeśli minimalna odległość jest większa, po prostu nie dostaniesz rzędu dla tej kombinacji senalu i portu.

Uwaga: Kolejność według kolejności musi być zgodna z odrębnością na zamówienie, co ma sens, ponieważ odrębność polega na przyjęciu pierwszej odrębnej grupy na podstawie pewnego uporządkowania.

Zakłada się, że masz indeks przestrzenny na obu tabelach.

EDYCJA 1 . Istnieje jeszcze inna opcja, która polega na użyciu operatorów <-> i <#> Postgresa (odpowiednio obliczenia odległości między punktami środkowymi i ograniczającymi), które efektywniej wykorzystują indeks przestrzenny i nie wymagają hakowania ST_DW trakcie hackowania, aby uniknąć n ^ 2 porównania. Jest dobry artykuł na blogu wyjaśniający, jak działają. Należy zauważyć, że te dwa operatory działają w klauzuli ORDER BY.

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

EDYCJA 2 . Ponieważ na to pytanie poświęcono wiele uwagi, a k-najbliżsi sąsiedzi (kNN) są na ogół trudnym problemem (pod względem czasu działania algorytmu) w GIS, warto nieco rozszerzyć pierwotny zakres tego pytania.

Standardowym sposobem znajdowania x najbliższych sąsiadów jednego obiektu jest użycie ŁĄCZENIA BOCZNEGO (koncepcyjnie podobne do znaku dla każdej pętli). Pożyczając bezwstydnie od odpowiedzi dbaston , zrobiłbyś coś takiego:

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

Tak więc, jeśli chcesz znaleźć najbliższe 10 portów, uporządkowane według odległości, po prostu musisz zmienić klauzulę LIMIT w bocznym zapytaniu podrzędnym. Jest to o wiele trudniejsze do uniknięcia bez ŁĄCZNIKÓW PÓŹNIEJSZYCH i wymaga użycia logiki typu ARRAY. Chociaż to podejście działa dobrze, można je znacznie przyspieszyć, jeśli wiesz, że musisz szukać tylko na określoną odległość. W tym przypadku możesz użyć ST_DWithin (signs.geom, ports.geom, 1000) w podzapytaniu, co ze względu na sposób indeksowania działa z operatorem <-> - jedna z geometrii powinna być stała, a nie odniesienie do kolumny - może być znacznie szybsze. Na przykład, aby uzyskać 3 najbliższe porty w promieniu 10 km, możesz napisać coś takiego:

 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;

Jak zawsze użycie będzie się różnić w zależności od dystrybucji danych i zapytań, więc EXPLAIN jest twoim najlepszym przyjacielem.

Wreszcie, istnieje niewielka gotcha, jeśli używasz LEWEJ zamiast KRZYŻ DOŁĄCZ PÓŹNIEJ, ponieważ musisz dodać PRAWDA po aliasie zapytań bocznych, np.

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
źródło
Należy zauważyć, że nie będzie to dobrze działać w przypadku dużych ilości danych.
Jakub Kania,
@JakubKania. Zależy to od tego, czy możesz użyć ST_DW ramach, czy nie. Ale tak, punkt wzięty. Niestety, operator <-> / <#> wymaga, aby jedna z geometrii była stała, prawda?
John Powell,
@ JohnPowellakaBarça jest szansa, że ​​wiesz, gdzie obecnie znajduje się ten blog? - czy podobne wyjaśnienie operatorów <-> i <#>? Dzięki!!
DPSSpatial
@DPSSpatial, to denerwujące. Nie wiem, ale jest to i to , które porozmawiać trochę o tym podejściu. Drugi, wykorzystujący również połączenia boczne, co jest kolejnym interesującym ulepszeniem.
John Powell,
@DPSSpatial. To wszystko jest trochę śliskie w przypadku <->, <#> i bocznych połączeń. Zrobiłem to z bardzo dużymi zestawami danych, a wydajność była okropna, bez użycia ST_DWithin, czego wszystkiego należy unikać. W końcu knn jest skomplikowanym problemem, więc użycie może się różnić. Powodzenia :-)
John Powell,
13

Można to zrobić za pomocą LATERAL JOINPostgreSQL 9.3+:

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
źródło
10

Podejście z łączeniem krzyżowym nie używa indeksów i wymaga dużo pamięci. Więc zasadniczo masz dwie możliwości. Przed wersją 9.3 użyłeś skorelowanego podzapytania. 9.3+ możesz użyć LATERAL JOIN.

KNN GIST z bocznym zwrotem akcji Wkrótce w bazie danych w pobliżu

(dokładne zapytania wkrótce)

Jakub Kania
źródło
1
Fajne zastosowanie łączenia bocznego. Nie widziałem tego wcześniej w tym kontekście.
John Powell,
1
@ JohnBarça To jeden z najlepszych kontekstów, jakie widziałem. Podejrzewam również, że byłoby to pomocne, gdy naprawdę trzeba użyć, ST_DISTANCE()aby znaleźć najbliższy wielokąt, a sprzężenie krzyżowe powoduje, że na serwerze brakuje pamięci. Najbliższe zapytanie wielokąta jest nadal nierozwiązane AFAIK.
Jakub Kania
2

@John Barça

ORDER BY jest błędny!

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

Dobrze

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

w przeciwnym razie nie zwróci najbliższego, tylko który ma mały identyfikator portu

strech
źródło
1
Prawidłowy wygląda tak (użyłem punktów i linii):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, rozumiem cię teraz. Prawdopodobnie lepiej jest zastosować podejście LATERAL JOIN, jak w odpowiedzi @ dbaston, która wyjaśnia, co jest porównywane z tym, co pod względem bliskości. Nie używam już powyższego podejścia.
John Powell,