Algorytmy danych geoprzestrzennych

Wprowadzenie

Krzysztof Dyba

Informacje o zajęciach

Wykłady

  • liczba godzin: 15
  • zaliczenie: test

Ćwiczenia

  • liczba godzin: 30
  • część praktyczna w PyQGIS
  • zaliczenie: projekt końcowy + aktywność na zajęciach




Kontakt:

Źródła wiedzy

Algorytm

Algorytm to zestaw precyzyjnie zdefiniowanych instrukcji krok po kroku służących do rozwiązania konkretnego problemu lub wykonania zadania w skończonym czasie.

Jest to jednoznaczna sekwencja operacji, która wykorzystuje dane wejściowe, przetwarza je zgodnie z określonymi zasadami i generuje dane wyjściowe.

Cechy algorytmu

  • Jednoznaczność – każdy krok algorytmu musi być precyzyjnie i jednoznacznie zdefiniowany bez miejsca na otwarte interpretacje.
  • Skończoność – algorytm musi zakończyć działanie po skończonej liczbie kroków, tj. nie może działać w nieskończoność.
  • Efektywność – każdy krok algorytmu musi być wykonywalny i osiągalny przy użyciu dostępnych zasobów.
  • Poprawność – algorytm powinien generować poprawne dane wyjściowe (dla poprawnych danych wejściowych).

Przykłady algorytmów

Przepis kuchenny to instrukcja w jaki sposób przygotować składniki (dane wejściowe), aby otrzymać potrawę (dane wyjściowe).

  • Algorytmy sortowania (np. bąbelkowe, pozycyjne)
  • Algorytmy wyszukiwania (np. liniowe, binarne)
  • Algorytmy szyfrowania (np. algorytm Huffmana)
  • Algorytmy uczenia maszynowego
  • i wiele innych

Schemat blokowy

flowchart TD
    A[Start] --> B{PUNKT DECYZYJNY}
    B -->|Tak| C[AKCJA 1]
    B -->|Nie| D[AKCJA 2]
    C --> E[Koniec]
    D --> E

Prostokąt reprezentuje etap procesu.

Romb reprezentuje punkt decyzyjny, który rozgałęzia przepływ na podstawie warunków TAK/NIE lub PRAWDA/FAŁSZ.

Schemat blokowy to wizualna reprezentacja procesu, która ilustruje sekwencję kroków, decyzji i działań podejmowanych w celu osiągnięcia określonego celu.

W przeciwieństwie do algorytmu, cechuje się uproszczoną formą, przez co jest łatwiejszy w odbiorze.

https://mermaid.js.org/

Przykład

Szukanie wartości maksymalnej w zbiorze

Przykład

Dane wejściowe: Lista liczb.

Dane wyjściowe: Największa liczba z listy.

Kroki:

  1. Ustaw pierwszą liczbę z listy jako największą.

  2. Dla każdej liczby na liście:

    Jeśli bieżąca liczba jest większa od największej, to ustaw ją na bieżącą.

  3. Zwróć największą liczbę.

Przykład – schemat blokowy

flowchart LR
    A[Start] --> B[Ustaw pierwszy element jako maks]
    B --> C[Dla każdego elementu z listy]
    C --> D{Czy bieżący element jest większy od maks?}
    D -- Tak --> E[Ustaw nowe maksimum]
    D -- Nie --> F[Sprawdź kolejny element]
    E --> F
    F --> G{Czy są kolejne elementy do sprawdzenia?}
    G -- Tak --> C
    G -- Nie --> H[Zwróć maks]
    H --> I[Koniec]


flowchart LR
    A[Start] --> B[Ustaw pierwszy element jako maks]
    B --> C[Dla każdego elementu z listy]
    C --> D{Czy bieżący element jest większy od maks?}
    D -- Tak --> E[Ustaw nowe maksimum]
    D -- Nie --> F[Sprawdź kolejny element]
    E --> F
    F --> G{Czy są kolejne elementy do sprawdzenia?}
    G -- Tak --> C
    G -- Nie --> H[Zwróć maks]
    H --> I[Koniec]

Przykład – pseudokod

Pseudokod – uproszczony sposób opisywania logiki algorytmu bez użycia ścisłej składni określonego języka programowania. Traktowany jest jako szkic kodu, zatem nie może zostać uruchomiony na komputerach.

ALGORYTM ZnajdzMaks(lista)
  maks = lista[1]
  FOR kazdego elementu IN lista:
    IF element > maks THEN
      maks = element
  RETURN maks

Przykład – implementacja

Python

liczby = [1, 5, 2, 8, 3, 9, 4, 7, 6]
maks = liczby[0]

for liczba in liczby:
  if liczba > maks:
    maks = liczba
print(maks)
#> 9

R

liczby = c(1, 5, 2, 8, 3, 9, 4, 7, 6)
maks = liczby[1]

for (liczba in liczby) {
  if (liczba > maks) {
    maks = liczba
  }
}
print(maks)
#> 9


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

Algorytm geoprzestrzenny

Algorytm geoprzestrzenny

Algorytm geoprzestrzenny to procedura obliczeniowa służąca do przetwarzania i analizowania danych geoprzestrzennych (tj. w kontekście przestrzennym).

Są one przede wszystkim wykorzystywane w systemach informacji geograficznej do między innymi:

  • analizy danych teledetekcyjnych,
  • monitorowania środowiska,
  • logistyki i nawigacji,
  • planowania przestrzennego.

Przykłady algorytmów geoprzestrzennych

  • Algorytmy indeksowania przestrzennego:
    • Drzewo czwórkowe (quadtree).
    • R-drzewo (R-tree).
  • Algorytmy interpolacji przestrzennej:
    • Odwrotne ważenie odległością (Inverse Distance Weighting).
    • Kriging.
  • Algorytmy analizy sieci:
    • Algorytm Dijkstry.
    • Algorytm A* (A-star search algorithm).
  • Algorytmy geometryczne:
    • Bufor.
    • Otoczka wypukła.

Przykłady zastosowań

  • Zapytania przestrzenne (np. znalezienie punktów na określonym obszarze).
  • Operacje geometryczne (np. stworzenie buforu obiektu liniowego).
  • Transformacja współrzędnych (np. konwersja pomiędzy układami współrzędnych).
  • Interpolacja przestrzenna (np. stworzenie ciągłej powierzchni z danych punktowych).
  • Optymalizacja trasy (np. znalezienie najszybszej trasy do celu).
  • Analizy ukształtowania terenu (np. obliczenie nachylenia terenu).
  • Inne??

Technologie – języki programowania

image/svg+xml

Asset 2

Technologie – oprogramowanie

image/svg+xml

QGIS

Saga GIS

Grass GIS

QGIS

328 algorytmów (narzędzi) w 26 kategoriach:

  • Kafle 3D
  • Kartografia
  • Bazy danych
  • Narzędzia plików
  • GPS
  • Interpolacja
  • Narzędzia warstw
  • Mesh
  • Narzędzia modelera
  • Analiza sieci
  • Wykresy
  • Przetwarzanie chmury punktów (3 moduły)
  • Przetwarzanie rastrów (4 moduły)
  • Przetwarzanie wektorów (8 modułów)

DOKUMENTACJA

Saga GIS

802 algorytmów (narzędzi) w 16 kategoriach:

  • Klimat i pogoda
  • Różne
  • Raster (grid)
  • Raster wielokanałowy (grid collection)
  • Przetwarzanie obrazów
  • Import/Eksport danych
  • Projekcje
  • Raportowanie
  • Wektor (shapes)
  • Symulacje
  • Analiza przestrzenna i geostatystyka
  • Nieregularna sieć trójkątów (TIN)
  • Dane tabelaryczne
  • Analiza terenu
  • Narzędzia (tool chains)
  • Wizualizacje

DOKUMENTACJA

Grass GIS

444 algorytmów (narzędzi) w 10 kategoriach:

  • Wizualizacja
  • Ogólne
  • Przetwarzanie rastrów
  • Przetwarzanie rastrów 3D
  • Przetwarzanie obrazów
  • Przetwarzanie wektorów
  • Bazy danych
  • Przetwarzanie czasowe
  • Kartografia
  • Różne

DOKUMENTACJA

Geointerfejs

Geointerfejs

Interfejsy definiują sposób, w jaki różne części systemu współdziałają ze sobą, umożliwiając im komunikację i wymianę informacji.

Geointerfejs odnosi się do interfejsu, który zapewnia dostęp do danych i usług geoprzestrzennych, umożliwiając interakcje pomiędzy różnymi systemami geoprzestrzennymi za pomocą interfejsu programowania aplikacji (API).

Otwarte interfejsy umożliwiają interoperacyjność między różnymi narzędziami, nawet jeśli są napisane w innych językach programowania lub używają odmiennych struktur do reprezentacji danych.

Interfejs wiersza poleceń

Interfejs wiersza poleceń (CLI) to oparty na tekście interfejs, który umożliwia użytkownikom interakcję z systemem lub oprogramowaniem poprzez wpisywanie poleceń w konsoli.

Wykorzystanie algorytmów programów GISowych jest możliwe poprzez powłokę systemową (np. bash czy PowerShell).

Geointerfejsy w R

flowchart TD
    A[R] --> B{{<a href='https://github.com/paleolimbot/geos'>geos</a>}}
    B --> C[GEOS]
    A --> D{{<a href='https://github.com/USDAForestService/gdalraster'>gdalraster</a>}}
    D --> E[GDAL]
    A --> F{{<a href='https://github.com/stevenpawley/Rsagacmd'>Rsagacmd</a>}}
    F --> G[Saga GIS]
    A --> H{{<a href='https://github.com/OSGeo/rgrass'>rgrass</a>}}
    H --> I[Grass GIS]
    A --> J{{<a href='https://github.com/r-spatial/qgisprocess'>qgisprocess</a>}}
    J --> K[QGIS]

Przykład

Wykorzystanie QGIS CLI za pośrednictwem pakietu qgisprocess w R:

library(qgisprocess)

qgis_search_algorithms("buffer")
#>    provider_title    group                algorithm          
#>  1 GDAL              Vector geoprocessing gdal:buffervectors
#>  2 GRASS             Vector (v.*)         grass7:v.buffer   
#>  3 QGIS (native c++) Vector geometry      native:buffer     

qgis_run_algorithm(
  "native:buffer",
  INPUT = "punkt.gpkg",
  OUTPUT = "bufor.gpkg",
  DISTANCE = 100
)
#> Geometry set for 1 feature 
#> Geometry type: POLYGON
#> Dimension:     XY
#> Bounding box:  xmin: 411648 ymin: 5084491 xmax: 411668 ymax: 5084511
#> Projected CRS: NAD83 / UTM zone 20N
#> POLYGON ((411668 5084501, 411668 5084498, 4...