Algorytmy danych geoprzestrzennych

Relacje przestrzenne

Krzysztof Dyba

Relacja przestrzenna

Relacja przestrzenna określa sposób w jaki obiekty są ze sobą powiązane pod względem lokalizacji, odległości i interakcji w przestrzeni. Relacje te opisują wzajemne zależności pomiędzy obiektami.

Rodzaje relacji przestrzennych

  • Topologiczne – opisują zależności pomiędzy obiektami, np. przyleganie do siebie dwóch działek katastralnych
  • Odległościowe – opisują odległość między obiektami, np. odległość między dwoma miastami czy lokalizacja najbliższego szpitala
  • Wzorce i rozkład przestrzenny – opisują rozmieszczenie obiektów w przestrzeni (tj. czy są skupione, równomiernie rozłożone lub rozproszone losowo), np. rozmieszczenie szkół w mieście

Zastosowania

  • Zapytania przestrzenne – wybieranie obiektów na podstawie ich relacji przestrzennej z innymi obiektami, np. wybierz wszystkie budynki, które znajdują się w strefie 1 km od centrum miasta
  • Analiza przestrzenna – modelowanie zjawisk w kontekście geograficznym, np. wyznaczenie obszaru, który dotknięty jest przez negatywny czynnik (mapa zanieczyszczeń)
  • Połączenia przestrzenne tabel – obiekty dopasowywane są na podstawie określonej relacji topologicznej, a nie klucza (ID) w tabeli

Predykaty

Predykat (predicate) to:

  • wyrażenie opisujące pewne właściwości lub relacje
  • funkcja orzekająca o spełnieniu jakiegoś warunku (sprawdza go i zwraca prawdę bądź fałsz)


Przykład: Funkcja sprawdzająca czy liczba jest parzysta.

Predykaty przestrzenne

Predykaty przestrzenne (geometryczne) to wyrażenia logiczne lub warunki opisujące relacje topologiczną między obiektami w przestrzeni.

Przykłady:

  • Obiekt A przechodzi przez obiekt B
  • Obiekt A jest całkowicie zawarty w obiekcie B
  • Obiekt A całkowicie zawiera obiekt B
  • Obiekty A i B nie przecinają się ani nie są styczne

Predykaty przestrzenne

  • Zawiera (Contains)
  • Przechodzi (Crosses)
  • Pokrywa (Covers)
  • Pokryty przez (Coveredby)
  • Rozłączny (Disjoint)
  • Równy (Equals)
  • Przecina (Intersects)
  • Nakłada (Overlaps)
  • Dotyka (Touches)
  • Wewnątrz (Within)

Zawiera

Jedna geometria całkowicie zawiera w sobie inną geometrię.

                          P1 zawiera P2: PRAWDA
                          P2 zawiera P1: FAŁSZ

Przykład: Powiat zawierający miasto.

Przechodzi

Dwie geometrie mają częściowo wspólne punkty (nie wszystkie). Zwykle dotyczy przecięcia linii i poligonu lub dwóch linii.

            L1 przechodzi przez P1: PRAWDA
            P1 przechodzi przez L1: PRAWDA

Przykład: Droga przebiegająca częściowo przez las i miasto.

Pokrywa

Jedna geometria całkowicie obejmuje drugą, ale nie oznacza to, że są identyczne (geometria pokrywająca drugą może być większa).

              P1 pokrywa P2: PRAWDA
              P2 pokrywa P1: FAŁSZ

Przykład: Powiat pokrywający miasto.

Pokryty przez

Jedna geometria znajduje się całkowicie wewnątrz innej geometrii, ale większa geometria może wykraczać poza nią.

              P1 jest pokryty przez P2: FAŁSZ
              P2 jest pokryty przez P1: PRAWDA

Przykład: Miasto pokryte jest przez powiat.

Rozłączny

Dwie geometrie nie mają ze sobą żadnego wspólnego punktu (nie przecinają się i nie stykają, tj. są rozdzielone).

              P1 jest rozłączny od P2: PRAWDA
              P2 jest rozłączny od P1: PRAWDA

Przykład: Dwa budynki w różnych częściach miasta.

Równy

Dwie geometrie są dokładnie takie same (mają identyczne kształt i położenie).

              P1 jest równy P2: PRAWDA
              P2 jest równy P1: PRAWDA

Przykład: Budynek zajmujący całą powierzchnię działki katastralnej.

Przecina

Dwie geometrie mają co najmniej jeden punkt wspólny.

                  P1 przecina P2: PRAWDA
                  P2 przecina P1: PRAWDA

Przykład: Droga przecinająca linię kolejową (przejazd kolejowy).

Nakłada

Dwie geometrie dzielą części swojego wnętrza, ale nie całość (częściowo się nakładają).

            P1 nakłada się z P2: PRAWDA
            P2 nakłada się z P1: PRAWDA

Przykład: Obszar parku narodowego pokrywający się częściowo z obszarem lasu.

Dotyka

Dwie geometrie mają wspólną granicę, ale nie pokrywają się (stykają się tylko na krawędzi).

                    P1 dotyka P2: PRAWDA
                    P2 dotyka P1: PRAWDA

Przykład: Dwie sąsiadujące ze sobą działki katastralne.

Wewnątrz

Jedna geometria jest całkowicie zawarta w innej geometrii.

                    P1 jest wewnątrz P2: FAŁSZ
                    P2 jest wewnątrz P1: PRAWDA

Przykład: Miasto znajdujące się w powiecie.

Implementacje

Predykaty przestrzenne są implementowane w różnym oprogramowaniu geoinformacyjnym, w tym:

Model DE-9IM

Model DE-9IM

Model DE-9IM (Dimensionally Extended 9 Intersection Model) to model topologiczny stosowany w systemach informacji geograficznej do opisu relacji przestrzennych między dwoma obiektami geometrycznymi, takimi jak punkty, linie i poligony.

Jest fundamentalnym konceptem w topologii przestrzennej.

Założenia

Model DE-9IM testuje przecięcia między wnętrzem, granicą i zewnętrzem dwóch geometrii definiowanych w następujący sposób:

  • wnętrze (Interior) – główna część obiektu (rdzeń)
  • granica (Boundary) – krawędź obiektu
  • zewnętrze (Exterior) – przestrzeń poza obiektem

Uwaga! W przypadku linii, granicą jest punkt początkowy oraz końcowy linii. Natomiast punkt w ogóle nie posiada granic.

Założenia

Model określa wymiar każdego możliwego przecięcia między tymi częściami w postaci macierzy 3 x 3, w której każda komórka reprezentuje przecięcie dwóch obiektów (A i B).

I(B) B(B) E(B)
I(A) I/I I/B I/E
B(A) B/I B/B B/E
E(A) E/I E/B E/E

Założenia

Komórki macierzy mogą przyjmować następujące wartości:

  • F – przecięcie jest puste (fałsz, brak przecięcia)
  • T – przecięcie nie jest puste (prawda)
  • * – wymiar przecięcia nie ma znaczenia

W przypadku wystąpienia przecięcia można uszczegółowić typ zwróconej geometrii:

  • 0 – przecięcie jest punktem (0-wymiarowe)
  • 1 – przecięcie jest linią (1-wymiarowe)
  • 2 – przecięcie jest poligonem (2-wymiarowe)

Założenia

Wynik jest zakodowany jako 9-znakowy łańcuch tekstu, gdzie każdy znak odpowiada komórce w macierzy, czytany od lewej do prawej, od góry do dołu. Na przykład:

  • FF2FF1212
  • T*F**FFF* (Equals)
  • FF*FF**** (Disjoint)

Przykład

https://postgis.net/workshops/postgis-intro/de9im.html

Predykat a model DE-9IM

Predykat przestrzenny:

  • sprawdza czy zachodzi dana relacja
  • zwraca wartość logiczną
  • jest prosty w interpretacji

Model DE-9IM:

  • szczegółowa analiza topologiczna
  • zwraca macierz 9-komórkową
  • jest bardziej złożony i trudniejszy w interpretacji