Algorytmy danych geoprzestrzennych

Operacje geometryczne

Krzysztof Dyba

Operacje geometryczne

Operacje geometryczne to zbiór technik stosowanych do przetwarzania i analizowania danych wektorowych.

Umożliwiają one wykonywanie różnych zadań, takich jak tworzenie, modyfikowanie, łączenie, uproszczenie czy transformacje geometrii obiektów wektorowych.

Generowanie punktów

n = 100
zakres = c(xmin = 0, xmax = 100, ymin = 0, ymax = 100)
x_wsp = runif(n, zakres["xmin"], zakres["xmax"])
y_wsp = runif(n, zakres["ymin"], zakres["ymax"])
mat = matrix(c(x_wsp, y_wsp), ncol = 2)

Python

import random
n = 100
zakres = {"xmin": 0, "xmax": 100, "ymin": 0, "ymax": 100}
x_wsp = []
y_wsp = []
for _ in range(n):
  x_wsp.append(random.uniform(zakres["xmin"], zakres["xmax"]))
  y_wsp.append(random.uniform(zakres["ymin"], zakres["ymax"]))
mat = list(zip(x_wsp, y_wsp))

Generowanie punktów w poligonach

Wygenerowanie punktu w zasięgu poligonu
Sprawdzenie czy punkt znajduje się w poligonie

n = 10
licznik = 1
lista = list()

while (licznik <= n) {
  x = runif(1, zakres["xmin"], zakres["xmax"])
  y = runif(1, zakres["ymin"], zakres["ymax"])
  pt = vect(cbind(x, y))
  warunek = relate(pt, poly, relation = "within")
  if (isTRUE(warunek)) {
    lista = append(lista, pt)
    licznik = licznik + 1
  }
}

Generowanie punktów w poligonach

Tworzenie geometrii

Well-known text (WKT)

POLYGON ((40 30, 60 30, 50 55, 40 30))
LINESTRING (50 30, 50 15)
MULTIPOINT ((45 43), (55 43), (42 34), (58 34))

Generowanie siatki

n = 10
mat = matrix(rep(NA, times = 2 * n^2),
             ncol = 2)
iter = 1

for (x in seq(1, 100, by = 10)) {
  for (y in seq(1, 100, by = 10)) {
    mat[iter, ] = c(x, y)
    iter = iter + 1
  }
}

Python

n = 10
lista = []
counter = 0

for x in range(1, 101, 10):
    for y in range(1, 101, 10):
        lista.append([x, y])
        counter += 1

1. Jakie są różnice między tymi dwoma blokami kodu?

2. Alternatywne podejście w R?

Generowanie siatki

Zakres przestrzenny

Zakres przestrzenny (minimalny prostokąt ograniczający, obwiednia) to prosta geometryczna reprezentacja zasięgu przestrzennego obiektów. Jest to najmniejszy prostokąt, który całkowicie pokrywa obiekty, a jego boki są równoległe do osi układu współrzędnych.

Zakres przestrzenny jest definiowany przez cztery wartości:

Minimalna długość geograficzna (X_min).
Maksymalna długość geograficzna (X_maks).
Minimalna szerokość geograficzna (Y_min).
Maksymalna szerokość geograficzna (Y_maks).

Zakres przestrzenny

SpatExtent: 7.067, 91.287, 7.527, 89.509 (xmin, xmax, ymin, ymax)
Powierzchnia: 6904 m^2

Obrócony prostokąt ograniczający

Obrócony prostokąt ograniczający (minimal bounding rotated rectangle) to najmniejszy prostokąt, który całkowicie pokrywa obiekty, przy czym prostokąt może się obracać, aby osiągnąć minimalną powierzchnię.

Obrócony prostokąt ograniczający

Powierzchnia: 6856 m^2

Minimalne koło ograniczające

Powierzchnia: 6910 m^2

Otoczka wypukła

Otoczka wypukła to obiekt geometryczny, który reprezentuje najmniejszy wielokąt wypukły. Można to porównać do rozciągania gumy wokół gwoździ.

Przykładowe algorytmy:

Gift Wrapping (Jarvis March): \(O(nh)\)
Graham’s Scan: \(O(n \log n)\)
QuickHull: \(O(n \log n)\)
Monotone Chain (Andrew’s Algorithm): \(O(n \log n)\)
Chan’s Algorithm: \(O(n \log h)\)

n - liczba punktów wejściowych
h - liczba punktów na otoczce

Otoczka wypukła

Algorytm Jarvisa

Znajdź najbardziej wysunięty punkt na lewo (punkt o najmniejszej współrzędnej X).
Znajdź następny punkt otoczki, który tworzy najmniejszy kąt przeciwnie do ruchu wskazówek zegara.
Po znalezieniu kolejnego punktu, ustaw go jako bieżący i powtórz krok 2.
Kontynuuj ten proces, aż wrócisz do punktu początkowego.

Animacja (Wikipedia)

Bufor

Bufor to strefa lub obszar utworzony wokół obiektu przestrzennego w określonej odległości. Zazwyczaj używany jest do reprezentowania obszaru wpływu lub bliskości wokół obiektu.

Bufor

Łączenie geometrii

Centroid

Centroid to geometryczny środek obiektu przestrzennego. Inaczej mówiąc, jest to pojedynczy punkt, który reprezentuje średnią arytmetyczną wyliczoną ze współrzędnych wszystkich wierzchołków.

W przypadku obiektu punktowego, centroid jest po prostu lokalizacją samego punktu.

Centroid

Centroid rzeczywisty

Punkt na powierzchni

Centroid nie gwarantuje, że będzie znajdował się wewnątrz geometrii.

Centroid

Lokalizacja centroidów rzeczywistych i punktów na powierzchni nie jest identyczna.

Uproszczenie geometrii

Algorytm Douglasa Peuckera

Algorytm Douglasa Peuckera jest jedną z najczęściej stosowanych metod upraszczania geometrii. Działa poprzez rekurencyjne usuwanie punktów, które znajdują się w określonej odległości od linii łączącej dwa punkty.

Kroki:

Zacznij od połączenia pierwszego i ostatniego wierzchołka w linii prostej.
Znajdź wierzchołek położony prostopadle najdalej od tej linii.
Jeśli odległość tego wierzchołka jest większa niż zdefiniowana odległość (tolerancja), to zostaje on zachowany.
Jeśli odległość jest mniejsza niż tolerancja, to wierzchołek zostaje usunięty.
Powtarzaj, dopóki wszystkie wierzchołki nie przekroczą progu tolerancji.

Animacja (Wikipedia)

Diagram Woronoja

Diagram Woronoja jest to podział płaszczyzny na regiony na podstawie odległości do określonego zestawu punktów. Każdy region, zwany komórką Woronoja lub wielokątem Thiessena, składa się ze wszystkich punktów, które są bliżej określonego punktu początkowego niż jakiegokolwiek innego punktu początkowego.

Do ich wygenerowania najczęściej stosuje się algorytm Fortune’a o złożoności \(O(n \log n)\).

Diagram Woronoja

Animacja (Wikipedia)

Diagram Woronoja

Dwa podstawowe zastosowania to:

Interpolacja przestrzenna, np. szacowanie opadów na podstawie pomiarów ze stacji meteorologicznych poprzez zdefiniowanie najbliższych obszarów wokół stacji.
Wyznaczanie obszarów, np. określenie obszaru działalności konkretnej remizy strażackiej.

Triangulacja Delone

Triangulacja Delone jest to metoda tworzenia sieci trójkątów z zestawu punktów w taki sposób, że żaden punkt nie znajduje się wewnątrz okręgu żadnego trójkąta, dzięki czemu trójkąty są jak najbardziej regularne.

Algorytmy:

Dziel i zwyciężaj (Divide and conquer) – dzielenie punktów na mniejsze podzbiory, triangulacja każdego podzbioru, a następnie scalanie.
Przyrostowe (Incremental) – dodawanie punktów jeden po drugim i aktualizowanie triangulacji w celu zachowania własności Delone.
Odwracania (Flip) – rozpoczęcie od dowolnej triangulacji, a następnie “odwracanie” krawędzi w celu spełnienia warunku Delone.

Triangulacja Delone

Związek z diagramem Woronoja

Krawędzie triangulacji Delone odpowiadają wspólnej granicy pomiędzy dwiema komórkami Woronoja. Natomiast, wierzchołki diagramu Woronoja leżą w środkach okręgów opisanych trójkątów Delone.

Ta dualność jest fundamentalną relacją i sprawia, że te dwie struktury są ściśle ze sobą powiązane.

Transformacje geometryczne

Przesunięcie
Przeskalowanie
Transpozycja
Odbicie
Obrócenie

Przesunięcie

                          x  y                   x  y
                    [1,] 40 30             [1,] 50 35
                    [2,] 60 30             [2,] 70 35
                    [3,] 50 40    ---->    [3,] 60 45
                    [4,] 40 30             [4,] 50 35

Przeskalowanie

                  współczynnik * (wierzchołek - centroid) + centroid

Transpozycja

                              x  y                   x  y
                        [1,] 40 30             [1,] 30 40
                        [2,] 60 30             [2,] 30 60
                        [3,] 50 40    ---->    [3,] 40 50
                        [4,] 40 30             [4,] 30 40

Odbicie

            Odbicie poziome: (2a - x, y), gdzie a to linia wertykalna
            Odbicie pionowe: (x, 2b - y), gdzie b to linia horyzontalna

Obrócenie

                  θ  = -θ * pi / 180
                  x' = (x - x0) * cos(θ) - (y - y0) * sin(θ) + x0
                  y' = (x - x0) * sin(θ) + (y - y0) * cos(θ) + y0

Inne operacje

Statystyki geometrii, np. długość, obwód, powierzchnia, liczba wierzchołków
Walidacja i naprawa geometrii
Usuwanie zduplikowanych wierzchołków
Uzupełnienie dziur w poligonach
Reprojekcje
…