Optymalizacja obliczeń najbliższego sąsiada za pomocą PostGIS

Używam PostGIS do obliczania najbliższych sąsiadów wielokątów. Chcę obliczyć minimalną odległość od każdego wielokąta do najbliższego wielokąta.

Do tej pory mam wielką pomoc od Mike'a Toews' odpowiedzi (które cytuję ze zmianą moll) tutaj:

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

Następnie obliczyłem minimum:

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

Jednak moim wyzwaniem jest obliczenie tego dla dużej liczby wielokątów (1 000 000). Ponieważ powyższe obliczenia porównują każdy wielokąt z każdym innym wielokątem, zastanawiałem się, jak mogę poprawić obliczenia, aby nie musiałem wykonywać obliczeń 10 ^ 12.

Jedną z moich myśli było buforowanie każdego wielokąta, a następnie obliczenie najbliższych sąsiadów wszystkich wartości w buforze dla tego wielokąta i zapisanie minimum. Nie jestem pewien, czy jest to najlepsze podejście, czy też jest funkcja w PostGIS, z której powinienem korzystać.

EDYCJA: Korzystając z jednej z sugestii Nicklas, eksperymentuję z 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

Zwraca tabelę identyfikacyjną każdego wielokąta i informację, czy znajduje się w pewnej odległości, czy nie. Czy można zbudować IF/ELSEinstrukcję typu za pomocą SQL? (Przeczytałem o użyciu CASEwarunku) Czy powinienem spróbować dołączyć tabelę, którą tworzę, do oryginalnej tabeli, a następnie ponownie uruchomić zapytanie przy użyciu ST_Distance?

Na stronie BostonGIS znajduje się duża sekcja „Najbliższy sąsiad” .

EDYTOWAĆ:

Co powiesz na

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)

W odniesieniu do instrukcji CASE :

SELECT a,
   CASE WHEN a=1 THEN 'one'
        WHEN a=2 THEN 'two'
        ELSE 'other'
   END
FROM test;

Halo

Istnieją pewne rzeczy, które należy rozważyć, aby przyspieszyć ruch, a niektóre rzeczy mogą być możliwe w przyszłości.

Po pierwsze , wspomniałeś, że rozważasz użycie bufora do znalezienia wielokątów w pewnym minimalnym zakresie, aby uniknąć obliczenia wszystkich kombinacji.

Jak omówiono w innym linku z Bostonu gis, właściwym sposobem na to w PostGIS jest użycie ST_Dwithin . ST_Dwithin używa indeksu, aby znaleźć sąsiadów w określonym zakresie.

Zależy to oczywiście od zestawu danych, czy wystarczy użyć stałej wartości dla st_DWithin dla wszystkich wielokątów, czy też trzeba zrobić coś takiego, jak dyskutuje podmrok i wildintellect.

Drugą rzeczą jest użycie PostGIS 1.5+ tutaj. Wynika to z faktu, że obliczenia wielokątów wieloboków są znacznie szybsze od 1,5, jeśli ich obwiednia nie przecinają się. Możesz przeczytać więcej na ten temat tutaj. .

Trzecią rzeczą, o której należy wspomnieć, jest przyszłość.

W PostgreSQL 9.1 będzie coś o nazwie knn-gist. Jest to indeks, który nie tylko może odpowiedzieć tak lub nie, ale także zwrócić wynik uporządkowany bezpośrednio z indeksu. Możesz o tym przeczytać tutaj .

Ale po stronie PostGIS nadal będzie dużo pracy, zanim knn gist pomoże w takich sprawach. Jest na to bilet .

pozdrowienia

Nicklas

Następujące strony związane z pracą mistrzów Nathana Kerra dają dobry wgląd w tę bezpośrednią kwestię. Mój współpracownik wypróbował metodę Bostongi tu i tutaj , ale miał pewne problemy z prawidłowym działaniem.

Innym podejściem do myślenia podobnym do bufora jest zrobienie prostokąta rozwijającego się / kurczącego. Zasadniczo przekaż 1, aby wykonać obwiednię (jest to prosta jednostka + x do pola początkowego wielokąta) przeciąć, które Twoim zdaniem złapie przynajmniej jedno przecięcie. Dla danych, które uzyskały przecięcie, wykonaj zapytanie podrzędne, które sprawdza te dopasowania dla najbliższego. Dla danych, które nie pasują, rozwiń ramkę graniczną i powtórz.

Jest to z pewnością problem z programowaniem rekurencyjnym i może być lepiej wykonany w Pythonie z Shapely niż 100% bezpośrednio w Postgis.