Generalizer
Nazwa: Generalizer
Autor: Piotr Pociask
Wersja: 0.5
Repozytorium: QGIS Contributed Repository
Data aktualizacji: 15.03.2017

Wtyczka Generalizer służy do upraszczania, generalizacji i wygładzania linii. Narzędzie to stanowi przeniesienie większości możliwości jakie daje moduł v.generalize z GRASS GIS bezpośrednio do QGIS, dzięki czemu nie trzeba przeprowadzać konwersji warstw „do” i „z” mapsetów. Nowa warstwa może zostać zapisana na dysku w formacie ESRI Shapefile lub utworzona  w pamięci (tzw. memory layer, przy tworzeniu tej warstwy dodawany jest do nazwy przyrostek ‚_memory’). Dzięki drugiej opcji użytkownik może w prosty i szybki sposób sprawdzić czy parametry algorytmu odpowiadają jego oczekiwaniom.

Wtyczka posiada dwa tryby działania: normalny i wsadowy. W trybie normalnym należy wybrać z listy warstwę liniową, algorytm przekształcenia oraz ustawić jego parametry. Po kliknięciu OK zostanie utworzona nowa warstwa.

Generalizer – widok normalny

Tryb wsadowy (ang. batch mode) pozwala na jednoczesne przekształcenie wielu warstw i wybranie kilku algorytmów, które zostaną wykonane po kolei na każdej z wybranych warstw. Po kliknięciu przycisku ‚Add’ pojawią się komunikaty, dzięki którym można wybrać algorytm oraz ustawić jego parametry. Na każdej zaznaczonej warstwie będą wykonywane kolejne przekształcenia w ten sposób, że wynik pierwszej analizy stanowi wejście do drugiej analizy, wynik drugiej do trzeciej itd. Zachowując warstwy na dysku, poprzez wskazanie folderu do zapisu, do nazwy każdej utworzonej warstwy dodawany jest przyrostek ‚_new’.

Generalizer – tryb wsadowy


Opis algorytmów:

Generalizacja:

1. Remove small objects (usuń małe obiekty) 

Narzędzie pozwala usunąć linie krótsze od określonej wielkości. Algorytm jest często stosowany do usuwania artefaktów (np. linii o zerowej długości) powstających przy automatycznym generowaniu warstw liniowych takich jak izolinie.

threshold – określa minimalną długość linii.

Uproszczenie:

Algorytm Douglas-Peucker (źródło: wikimapia.org)

2. Douglas-Peucker Algorithm

W przeciwieństwie do innych algorytmów, metoda Douglas’a-Peucker’a bierze pod uwagę całą upraszczaną linię, a nie tylko jej wycinek. Dzięki temu efekty osiągane przy jej wykorzystaniu są bardzo dobre – linia wynikowa zachowuje ogólny charakter linii oryginalnej. Wszystkie punkty uproszczonej linii pokrywają się z punktami linii oryginalnej.

threshold – minimalna odległość punktu c od prostej a, jeśli b < threshold to punkt c jest pomijany przy tworzeniu linii wynikowej (oznaczenia z rysunku).

Przykład

3. Jenks Algorithm  

Algorytm Jenks’a polega na eliminacji punktu jeśli jego odległość od linii łączącej dwa sąsiednie punkty (poprzedni i kolejny na linii) jest mniejsza od wartości progowej (tolerancji).  Wszystkie punkty uproszczonej linii pokrywają się z punktami linii oryginalnej. Kolejne kroki działania algorytmu przedstawia poniższy obrazek:

Algorytm Jenks’a

 threshold – minimalna odległość punktu od linii łączącej sąsiednie punkty.

Przykład

4. Lang Algorithm 

W algorytmie Langa pierwszy punkt linii łączony jest odcinkiem z punktem znajdującym się o określoną liczbę „w przód” – domyślnie n=7. Następnie obliczane są wszystkie odległości od tego odcinka do węzłów znajdujących się pomiędzy wybranymi punktami. Jeśli któraś odległość jest większa od określonej tolerancji to procedura jest powtarzana dla odcinka między punktem pierwszym a n-1, aż do momentu, gdy wszystkie odległości między prostą a punktami pośrednimi będą mniejsze od tolerancji. Następnie cała procedura powtarzana jest dla odcinka od ostatniego punktu do leżącego n pozycji „w przód” w stosunku do niego.

Wizualizacja działania algorytmu Langa: http://www.geogra.uah.es/gisweb/1modulosespanyol/GeneralizacionLineas/LGmodule/LGLangVisualisation.htm

threshold – tolerancja odległości.

look ahead – określa liczbę punktów „w przód”.

Przykład

5. Reumann-Witkam Algorithm

Równolegle do odcinka łączącego dwa pierwsze punkty linii prowadzone są po obu jego stronach dwie proste. Następnie algorytm szuka kolejnego segmentu linii, który przecina jedną z tych prostych. Wszystkie punkty między pierwszym, a ostatnim przed miejscem przecięcia odcinka i prostej są usuwane z linii wynikowej. Następnie algorytm bada kolejny odcinek między pozostawionym punktem a jego następnym sąsiadem.

threshold – określa odległość prostych od badanego odcinka.

Przykład

6. Vertex Reduction (redukcja wierzchołków)

Prosta i szybka metoda upraszczania linii polegająca na usuwaniu sąsiednich węzłów, które znajdują się bliżej od zadanej odległości. [important]Ustawiając wartość threshold na minimalną wartość można usunąć z linii dublujące się wierzchołki[/important]

threshold – określa minimalną odległość pomiędzy dwoma punktami na tej samej linii.

Przykład

Wygładzenie:

7. Boyle’s Forward-Looking Algorithm  

Metoda „prostowania” linii. Polega na wyznaczaniu nowej pozycji na podstawie pozycji punktów poprzedzających dany węzeł oraz punktu znajdującego się dalej na linii, o liczbę pozycji określonych parametrem look ahead. Liczba węzłów (punktów) jest taka sama w linii oryginalnej i wygładzonej.

look ahead – pozycja następnego węzła względem obliczanego, który brany jest pod uwagę przy obliczaniu nowej pozycji. Im większa wartość tym linia jest prostsza.

Przykład

8. Chaiken’s Algorithm

W metodzie Chaiken’a wygładzanie linii polega na zaokrąglaniu kątów między sąsiednimi segmentami. Nowa linia nie ma wspólnych wierzchołków z  wygładzaną linią ale styka się z jej segmentami. Ma ona również większą liczbę punktów od wygładzanej linii uzależnioną od liczby iteracji.

Demonstracja działania algorytmu: http://www.multires.caltech.edu/teaching/demos/java/chaikin.htm

level – określa liczbę iteracji algorytmu.

weight – określa współczynnik ścięcia, im większy tym zaokrąglenia znajdują się bliżej węzłów linii.

Przykład

9. Hermite Spline Interpolation

Pomiędzy każdą parą punktów obliczany jest wzór wielomianowy określający krzywą Hermite’a. Na krzywej tworzone są nowe punkty oddalone od siebie o wartość parametru threshold. Z ich połączenia powstaje nowa, wygładzona linia. Przechodzi ona przez wszystkie wierzchołki oryginalnej linii.

[important]Nowa linia może posiadać bardzo dużą liczbę punktów w stosunku do pierwowzoru. Po jej utworzeniu warto zmniejszyć ich liczbę jednym z algorytmów generalizujących linie.[/important]

threshold – określa odległość między tworzonymi punktami.

thightness – współczynnik określający stopień wygięcia linii wynikowej.

Przykład

10. McMaster’s Distance-Weighting Algorithm

Algorytm określa nowe położenie punktu na podstawie średniej pozycji sąsiednich punktów, których liczbę określa look ahead. Parametr ten jest liczbą nieparzystą, a pod uwagę brane są n=(look_ahead-1)/2 punkty poprzednie i kolejne w stosunku do punktu obliczeniowego (środkowego).  Odległość punktu od punktu obliczeniowego jest brana pod uwagę. Im jest ona większa tym punkt ma mniejszy wpływ przy obliczaniu nowej pozycji.

slide – parametr funkcji interpolującej nową pozycję punktu, im wartość bliższa zera, tym linia wynikowa jest bardziej podobna do oryginału.

look ahead – liczba sąsiednich punktów służących do określenia nowej pozycji danego punktu na linii.

Przykład

11. McMaster’s Sliding Averaging Algorithm 

Algorytm określa nowe położenie punktu na podstawie średniej pozycji sąsiednich punktów, których liczbę określa look ahead. Parametr ten jest liczbą nieparzystą, pod uwagę brane są n=(look_ahead-1)/2 punkty poprzednie i kolejne w stosunku do punktu obliczeniowego. Parametr slide wykorzystywany jest w funkcji interpolującej pozycję punktu. Liczba punktów linii wejściowej i wyjściowej jest taka sama.

Wizualizacja działania algorytmu: http://www.geogra.uah.es/gisweb/1modulosespanyol/GeneralizacionLineas/LGmodule/LGMcMastersVisualisation.htm

slide – parametr funkcji interpolującej nową pozycję punktu, im wartość bliższa zera, tym linia wynikowa jest bardziej podobna do oryginału.

look ahead – liczba punktów służących do określenia nowej pozycji danego (środkowego) punktu na linii.

Przykład

12. Snakes Algorithm

Metoda ta polega na minimalizacji energii linii poprzez wygładzenie ostrych kątów. Jest to dosyć wolny algorytm wymagający (przy skomplikowanych liniach) dużej ilości pamięci, jednak wynik końcowy jest bardzo dobry.

alpha – ostrość (mniejsza wartość – linia ostrzejsza)

beta – krzywizna

Przykład