Algorytm upraszczania linii z wykorzystaniem interpolacji

W publikacji autor przedstawia nowy algorytm upraszczania, dokonujący zamiany łamanej pierwotnej na krzywą poprzez proces interpolacji. W wyniku działania algorytmu punkty na krzywej rozmieszczane są zależnie od skali mapy tworząc łamaną uogólnioną. Dodatkowo w rozmieszczaniu uwzględnia się: punkty ekstremalne krzywej zgodne z normą rozpoznawalności rysunku oraz punkty charakterystyczne. Nowy algorytm porównano z najczęściej stosowanymi algorytmami upraszczania: Douglasa - Peukera, Visvalinghama i Whyatta, Wanga oraz Chrobaka. W porównaniach badano: liczbę wierzchołków łamanych po uproszczeniu, strzałki jako najkrótsze odległości od wierzchołków usuniętych łamanej pierwotnej do boków łamanej uproszczonej oraz różnicę pomiędzy długością łamanej pierwotnej z długościami po uproszczeniu łamanych. Porównanie wykazało, że wyniki nowego algorytmu cechują się: najmniejszą liczbą usuwanych wierzchołków, najkrótszymi strzałkami, najmniejszą różnicą długości pierwotnej do długości uproszczonych, najmniejszymi średnimi błędami strzałek łamanej po upraszczaniu oraz największymi rozstępami skali pierwotnej do uogólnianej. Cechy nowego algorytmu zwiększają procent automatyzacji procesu upraszczania, a zwiększenie rozstępu skal ma szczególne znaczenie w Wielorozdzielczych/ Wieloreprezentacyjnych Bazach Danych.

The paper presents a new line simplification algorithm for converting the original polyline into a curve. The arrangement of points on the curve depends on the scale of the map. The critical points of the curve, according to the recognisability norm were also taken into consideration. The proposed algorithm is compared to the most widely used simplification algorithms. As it has been proven in the comparison, the results of the new algorithm show the smallest number of deleted vertices, the shortest bows, and the smallest difference between the lengths of the original polygonal curve and the simplified curve. Those features increase the automation of the simplification process.