Porównanie wybranych algorytmów upraszczania linii na przykładzie reprezentatywnego obszaru testowego

• Autorzy: Kozioł K.

Warianty tytułu

EN

Comparison of selected simplification algorithms on the example of a representative test area

• Języki publikacji: PL

Abstrakty

PL

Norma rozpoznawalności wprowadzona do procesu upraszczania powoduje jednoznaczność otrzymanych wyników procesu upraszczania. Zastosowanie normy jest możliwe dla innych algorytmów, lecz należy je przekształcić w zależności od parametrów wymaganych przez poszczególne algorytmy. AIgorytm Chrobaka wykazał się najmniejszymi zmianami w zakresie liczby wierzchołów usuniętych z krzywej, czego efektem jest prawidłowe odzwierciedlenie rzeczywistości geograficznej. Wybrane do porównania algorytmy (Douglasa-Peuckera, Langa, Reumanna- Witkama) cechuje jedna wspólna wada jaką jest jedynie odrzucanie wierzchołków krzywej pierwotnej. Autor podaje propozycję aby określać te algorytmy mianem algorytmów "odrzucania". Pojawienie się konfliktów jest nie do uniknięcia, jednakże liczba tych konfliktów jest jedną z miar jakości przeprowadzonego procesu upraszczania. AIgorytm Chrobaka można stosować bez ograniczeń ilościowych dla danych źródłowych i powinien on stać się jednym z algorytmów stosowanych w narzędziach GIS, jako alternatywny w stosunku do zaprezentowanych algorytmów. AIgorytm Chrobaka jest algorytmem globalnym (analiza całej krzywej),jednakże jego wynik zachowuje lokalne ekstrema krzywej, dzięki czemu przebieg krzywej wynikowej jest adekwatny do faktów geograficznych.

EN

The operator of simplification is one of the most widely used in cartography, and now there are many algorithms performing this process automatically. In 1999, Chrobak developed his own algorithm based on the value of drawing recognition with the use of elementary triangle for testing curve. This algorithm does not provide the possibility of introducing any value of tolerances (linear or angular), but only the value of the target scale. In this paper, the author made attempt to compare Chrobak's algorithm and other algorithms functioning in GIS. The results are not so surprising but very interesting from the point of view of rendering geographical facts in different scales. When comparing the number of vertices, remaining after simplification of various algorithms with the result of Chrobak;s algorithm, the obtained results differed even four times. The three algorithms compared should be called rejection algorithms, because they do not fulfill the basic condition that is .similarity. in relation to the initial curve.

Słowa kluczowe

PL

generalizacja; upraszczanie; norma rozpoznawalności rysunku; algorytm Langa; algorytm Douglasa-Peuckera; algorytm Reumanna-Witkama; metoda Chrobaka

EN

generalization; simplification; standard of drawing recognition; Lang algorithm; Douglas-Peucker algorithm; Reumann-Witkam algorithm; Chrobak's method

• Wydawca: Polskie Towarzystwo Informacji Przestrzennej
• Czasopismo: Roczniki Geomatyki
• Rocznik: 2011
• Tom: T. 9, z. 1
• Strony: 49--57
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Kozioł K.

• Katedra Geomatyki, Wydział Geodezji Górniczej i Inżynierii Środowiska Akademia Górniczo-Hutnicza w Krakowie,

Bibliografia

• 1. Chrobak T., 1999: Badanie przydatności trójkąta elementarnego w komputerowej generalizacji kartograficznej, UWND AGH Kraków.
• 2. Chrobak T., Kozioł K., Szostak M., Zukowska M., 2007: Podstawy cyfrowej generalizacji kartograficznej, UWND AGH Kraków.
• 3. Chrobak T., 2009: Przydatnos6 osnowy kartograficznej i metody obiektywnego upraszczania obiekt6w do aktualizacji danych w TBD, Geoamtics and Environmental Engineering, Vol. 3, No. 111, 81-90, UWND AGH Kraków.
• 4. Chrobak T., 2010: The role of least image dimensions in generalization of object in spatial databases, Geodesy and Cartography, Polish Committee for Scientific Research (w druku).
• 5. Douglas D.H., Peucker T.K., 1973: Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature, The Canadian Cartographer, Vol. 10, No. 2, 112-22.
• 6. Lang T., 1969: Rules for the Robot Draughtsmen, The Geographical Magazine, 42(1), 50-51.
• 7. Reumann K., Witkam A.K.P., 1974: Optimizing curve segmentation in computer graphics, Proceedings. International Computing Symposium, North-Holland Publishing Company, Amsterdam, 52-78.
• 8. Saliszczew K.A., 1998: Kartografia ogólna, Wydawnictwo naukowe PWN, Warszawa.