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.
R
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
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))
R
1. Jakie są różnice między tymi dwoma blokami kodu?
2. Alternatywne podejście w R?
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:
X_min
).X_maks
).Y_min
).Y_maks
).SpatExtent: 7.067, 91.287, 7.527, 89.509 (xmin, xmax, ymin, ymax)
Powierzchnia: 6904 m^2
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ę.
Powierzchnia: 6856 m^2
Powierzchnia: 6910 m^2
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:
n - liczba punktów wejściowych
h - liczba punktów na otoczce
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.
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 rzeczywisty
Punkt na powierzchni
Centroid nie gwarantuje, że będzie znajdował się wewnątrz geometrii.
Lokalizacja centroidów rzeczywistych i punktów na powierzchni nie jest identyczna.
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:
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)\).
Dwa podstawowe zastosowania to:
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:
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.
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
współczynnik * (wierzchołek - centroid) + centroid
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 poziome: (2a - x, y), gdzie a to linia wertykalna
Odbicie pionowe: (x, 2b - y), gdzie b to linia horyzontalna
θ = -θ * pi / 180
x' = (x - x0) * cos(θ) - (y - y0) * sin(θ) + x0
y' = (x - x0) * sin(θ) + (y - y0) * cos(θ) + y0