Оптимизация расчета ближайшего соседа с помощью PostGIS

13

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

До сих пор мне очень помог ответ Майка Тьюса (который я цитирую с небольшим изменением) здесь:

SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_Distance(a.the_geom, b.the_geom) AS distance_between_a_and_b
FROM 
  public."TestArea" AS a, public."TestArea" AS b
WHERE
  a.hgt !=  b.hgt AND ST_Distance(a.the_geom, b.the_geom) < 400

Тогда я рассчитал минимум:

SELECT a_hgt, MIN(distance_between_a_and_b)
FROM public."lon_TestArea"
GROUP BY a_hgt

Однако моя задача состоит в том, чтобы рассчитать это для большого числа полигонов (1 000 000). Поскольку приведенный выше расчет сравнивает каждый многоугольник с любым другим многоугольником, я удивлялся, как можно улучшить вычисление, чтобы мне не приходилось выполнять 10 ^ 12 вычислений.

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


РЕДАКТИРОВАТЬ: Используя одно из предложений Никласа, я экспериментирую с ST_Dwithin():

CREATE TABLE mytable_withinRange AS SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_DWithin(a.the_geom, b.the_geom, 400)
FROM 
  public."lon_TestArea" AS a, public."lon_TestArea" AS b

введите описание изображения здесь

Это возвращает таблицу идентификатора каждого многоугольника, и находится ли он на определенном расстоянии или нет. Можно ли построить оператор IF/ELSEтипа с использованием SQL? (Я читал об использовании CASEусловия) Или я должен попытаться соединить таблицу, которую я создаю, с исходной таблицей, а затем снова выполнить запрос, используя ST_Distance?

djq
источник
взгляните на второй пример в бостонской ссылке в моем ответе. Вы должны использовать st_dwithin в части where запроса.
Никлас Авен

Ответы:

7

На странице BostonGIS есть большой раздел "Ближайший сосед" .


РЕДАКТИРОВАТЬ:

Как насчет

CREATE TABLE mytable_withinRange AS SELECT 
 a.hgt AS a_hgt,
 b.hgt AS b_hgt
FROM 
 public."lon_TestArea" AS a, public."lon_TestArea" AS b
WHERE 
 ST_DWithin(a.the_geom, b.the_geom, 400)

По поводу заявления CASE :

SELECT a,
   CASE WHEN a=1 THEN 'one'
        WHEN a=2 THEN 'two'
        ELSE 'other'
   END
FROM test;
Подземье
источник
Знаете ли вы, будет ли линия WHERE ST_DWithin(a.the_geom, b.the_geom, 400)препятствовать расстоянию больше, чем 400рассчитать или просто записать? Кроме того, можно ли использовать регистр для численных расчетов? например:CASE WHEN ST_DWithin(a.the_geom, b.the_geom, 400) == TRUE THEN ST_DWithin(a.the_geom, b.the_geom)
djq
1
@celenius Если расстояние больше 400 м, ничего в выбранной части не будет рассчитано. Я не понимаю, почему вы хотите поместить дело в смесь.
Никлас Авен
@ Никлас хорошо - я понимаю. Я думал, что это могло означать, что были сохранены только расстояния менее 400; это делает это намного проще, чем я. Благодарность!
djq
3

алло

Есть некоторые вещи, которые нужно учитывать, чтобы заставить вещи двигаться быстрее, и некоторые вещи, которые могут быть возможны в будущем.

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

Как уже говорилось в другой ссылке из Бостона, правильным способом сделать это в PostGIS является использование ST_Dwithin . ST_Dwithin использует индекс, чтобы найти соседей в определенном диапазоне.

Конечно, от набора данных зависит, достаточно ли просто использовать фиксированное значение st_DWithin для всех многоугольников или если вам нужно сделать что-то вроде обсуждаемого underdark и wildintellect.

Второе - использовать PostGIS 1.5+ здесь. Это потому, что вычисления от полигона к полигону намного быстрее, чем 1,5, если их ограничивающие рамки не пересекаются. Вы можете прочитать больше об этом здесь. ,

Третье, что следует упомянуть, это будущее.

В PostgreSQL 9.1 будет нечто, называемое knn-gist. Это индекс, который может не только ответить «да» или «нет», но и вернуть результат, упорядоченный непосредственно из индекса. Вы можете прочитать об этом здесь .

Но еще многое предстоит сделать на стороне PostGIS, прежде чем knn gist поможет в таких вещах. Для этого есть билет .

С уважением

Никлас

Никлас Авен
источник
Спасибо за предложения Никлас; так как мне было сложно запустить и запустить pgAdmin / PostGIS, я думаю, что сейчас я буду избегать использования 1.5. Похоже, ST_Dwithin () - это способ решить эту проблему.
DJQ
2
установка 1.5 не повлияет на отношения между postgresql и pgadmin. вы можете иметь более одной версии postgis на сервере базы данных, а затем загрузить одну из них в базу данных. так что вы можете иметь одну базу данных 1.4 и одну 1.5 на одном сервере базы данных.
Никлас Авен
1

Следующие страницы, связанные с магистерской работой Натана Керра, дают хорошее представление об этой прямой проблеме. Мой коллега пробовал метод Бостонги здесь и здесь , но у него были некоторые проблемы с его правильной работой.

Еще один подход к размышлению о том, что похоже на буфер, заключается в создании расширяющегося / сжимающегося прямоугольника. В основном, для прохождения 1 выполните ограничивающий прямоугольник (это прямые + x единицы для bbox вашего исходного многоугольника), который, по вашему мнению, поймает хотя бы одно пересечение. Для данных, которые получили пересечение, выполните подзапрос, который проверяет эти совпадения на ближайший. Если данные не совпадают, разверните ограничивающую рамку и повторите.

Очевидно, что это проблема рекурсивного программирования, и ее лучше было бы сделать на Python с Shapely, чем на 100% непосредственно в postgis.

wildintellect
источник