ПостГИС ближайшие пункты с ST_Distance, кНН

23

Мне нужно получить по каждому элементу на одной таблице ближайшую точку другой таблицы. Первая таблица содержит дорожные знаки, а вторая - входные залы города. Дело в том, что я не могу использовать функцию ST_ClosestPoint, и мне нужно использовать функцию ST_Distance и получить запись min (ST_distance), но я довольно застрял при построении запроса.

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

Мне нужно получить идентификатор ближайшего entrnce_hall каждого трафика_sign.

Мой запрос до сих пор:

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

При этом я получаю расстояние от каждого traffic_sign до каждого entry_hall. Но как я могу получить только минимальное расстояние?

С Уважением,

Egidi
источник
Какая версия PostgreSQL?
Якуб Кания

Ответы:

41

Вы почти там. Есть небольшая хитрость, которая заключается в использовании отдельного оператора Postgres , который будет возвращать первое совпадение каждой комбинации - так как вы упорядочиваете по ST_Distance, эффективно он будет возвращать ближайшую точку от каждого сенала к каждому порту.

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

Если вы знаете, что минимальное расстояние в каждом случае составляет не более некоторой величины x (и у вас есть пространственный индекс в ваших таблицах), вы можете ускорить это, поставив WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", distance), например, если все минимальные расстояния известны как не более 10км, тогда:

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

Очевидно, что это нужно использовать с осторожностью, так как, если минимальное расстояние больше, вы просто не получите строки для этой комбинации сенала и порта.

Примечание: порядок за порядком должен совпадать с отличным по порядку, что имеет смысл, так как отличным является выбор первой отличной группы на основе некоторого упорядочения.

Предполагается, что у вас есть пространственный индекс в обеих таблицах.

РЕДАКТИРОВАТЬ 1 . Есть еще одна опция, которая заключается в использовании операторов Postgres <-> и <#> (вычисления расстояния от центральной точки и ограничивающей рамки соответственно), которые более эффективно используют пространственный индекс и не требуют взлома ST_DWithin, чтобы избежать n ^ 2 сравнения. Есть хорошая статья в блоге, объясняющая, как они работают. Общее, на что следует обратить внимание, это то, что эти два оператора работают в предложении 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;

РЕДАКТИРОВАТЬ 2 . Поскольку этому вопросу уделяется много внимания, и k-ближайшие соседи (kNN), как правило, представляют собой сложную проблему (с точки зрения алгоритмического времени выполнения) в ГИС, представляется целесообразным несколько расширить исходную область этого вопроса.

Стандартный способ найти x ближайших соседей одного объекта - использовать LATERAL JOIN (концептуально аналогично a для каждого цикла). Заимствуя бесстыдно из ответа dbaston , вы бы сделали что-то вроде:

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

Итак, если вы хотите найти ближайшие 10 портов, упорядоченные по расстоянию, вам просто нужно изменить предложение LIMIT в боковом подзапросе. Это гораздо сложнее обойтись без LATERAL JOINS и включает в себя использование логики типа ARRAY. Хотя этот подход работает хорошо, его можно значительно ускорить, если вы знаете, что вам нужно искать только на определенном расстоянии. В этом случае вы можете использовать ST_DWithin (signs.geom, ports.geom, 1000) в подзапросе, который из-за способа индексации работает с оператором <-> - одна из геометрий должна быть константой, а не ссылка на столбец - может быть намного быстрее. Так, например, чтобы получить 3 ближайших порта, в пределах 10 км, вы могли бы написать что-то вроде следующего.

 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;

Как всегда, использование будет зависеть от вашего распределения данных и запросов, поэтому EXPLAIN - ваш лучший друг.

Наконец, есть небольшая ошибка, если вы используете LEFT вместо CROSS JOIN LATERAL в том смысле, что вы должны добавить ON TRUE после псевдонима боковых запросов, например,

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;
Джон Пауэлл
источник
Следует отметить, что это не будет хорошо работать с большими объемами данных.
Якуб Кания
@JakubKania. Это зависит от того, можете ли вы использовать ST_D с или нет. Но, да, точка взята. К сожалению, оператор Order by <-> / <#> требует, чтобы одна из геометрий была постоянной, нет?
Джон Пауэлл
@ JohnPowellakaBarça есть хоть какой-то шанс, что ты знаешь, где сейчас находится этот пост? - или аналогичное объяснение операторов <-> и <#>? Благодарность!!
DPSSpatial
@DPSSpatial, это раздражает. Я не знаю, но есть то и это, которые немного говорят об этом подходе. Второй - с использованием боковых соединений, что является еще одним интересным улучшением.
Джон Пауэлл
@DPSSpatial. Все это немного скользко, это <->, <#> и боковое соединение. Я сделал это с очень большими наборами данных, и производительность была ужасной, без использования ST_DWithin, которого все это должно было избежать. В конечном счете, knn - сложная проблема, поэтому использование может варьироваться. Удачи :-)
Джон Пауэлл
13

Это можно сделать с помощью 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
источник
10

Подход с перекрестным соединением не использует индексы и требует много памяти. Таким образом, у вас есть два варианта. До 9.3 вы использовали коррелированный подзапрос. 9.3+ вы можете использовать LATERAL JOIN.

KNN GIST с боковым поворотом Скоро появится в базе данных рядом с вами

(точные запросы, чтобы следовать скоро)

Якуб Кания
источник
1
Классное использование бокового соединения. Не видел этого раньше в этом контексте.
Джон Пауэлл
1
@ JohnBarça Это один из лучших контекстов, которые я видел. Я также подозреваю, что было бы полезно, когда вам действительно нужно ST_DISTANCE()найти ближайший полигон, а перекрестное соединение приводит к нехватке памяти на сервере. Ближайший запрос полигонов по-прежнему не решен AFAIK.
Якуб Кания
2

@ Джон Барса

ЗАКАЗАТЬ ПО неверно!

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

Правильно

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

в противном случае он вернет не ближайший, а только тот, у которого маленький идентификатор порта

растяжимую
источник
1
Правильный выглядит так (я использовал точки и линии):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
Хорошо, я понимаю тебя сейчас. На самом деле, вероятно, лучше использовать подход LATERAL JOIN, как в ответе @ dbaston, который проясняет, какая вещь сравнивается с другой с точки зрения близости. Я больше не использую подход выше.
Джон Пауэлл