Algorytm upraszczania linii z wykorzystaniem interpolacji

• Autorzy: Kozioł K.

Warianty tytułu

EN

A line simplification algorithm using interpolation

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

generalizacja kartograficzna; algorytmy upraszczania; statystyka; interpolacja wielomianowa; MRDB

EN

cartographic generalisation; simplification algorithms; statistics; polynomial interpolation; MRDB

• Wydawca: Polskie Towarzystwo Informacji Przestrzennej
• Czasopismo: Roczniki Geomatyki
• Rocznik: 2013
• Tom: T. 11, z. 3(60)
• Strony: 45--59
• Opis fizyczny: Bibliogr. 22 poz., rys., tab., wykr.

Twórcy

autor

Kozioł K.

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

Bibliografia

• 1.Brassel K.E., Weibel R. 1988. A Review and Framework of Automated Map Generalization. Int. Journal of Geographical Information Systems, 2(3): 229-244.
• 2.Chrobak T., 2000, Numerical Method for Generalizing the Linear Elements of Large-Scale Maps, Based on the Example of Rivers, Cartographica, Vol. 37.
• 3.Chrobak T., 2010, The role of least image dimensions in generalization of object in spatial databases, Geodesy and Cartography, Polish Committee for Scientific Research,
• 4.de Boor, C., 1978, A Practical Guide to Splines, Springer-Verlag
• 5.Douglas D., Peuker T. 1973. Algorithms for the reduction of the number of points required to represent a digitised line or its caricature, The Canadian Cartographer, Vol 10: 112-122.
• 6.Kozioł, K., 2011. Porównanie wybranych algorytmów upraszczania linii na przykładzie reprezentatywnego obszaru testowego. Roczniki Geomatyki t. 9 z. 1: 49-57, PTIP, Warszawa.
• 7.Lang T., 1969. Rules for robot draughtsmen, Geographical Magazine, Vol 42 50-51.
• 8.Li, Z., 1993. Some observations on the issue of line generalisation. Cartographic Journal, 30 (1): 68-71.
• 9.Li Z, 2007. Algorithmic Foundation of Multi-scale Spatial Representation. CRC Press (Taylor & Francis Group). (ISBN: 0849390729). 280pp.
• 10.McMaster, R. B., 1986. A statistical analysis of mathematical measures for line simplification, American Cartographer, 13:103-116.
• 11.McMaster R. B., 1991. Conceptual frameworks for geographical knowledge. Chapter 1.2 In Buttenfield, B. P. and McMaster R B., Map Generalization: Making Rules for Knowledge Representation. London Longman.
• 12.McMaster R. B., Monmonier M. S., 1989. A Conceptual Framework for Quantitative and Qualitative Raster-Mode Generalization, Proceedings GIS/LIS '89, Orlando, Florida, 2: 390-403.
• 13.McMaster R. B., Shea K.S. 1992. Generalization in digital cartography. Publication supported by the A.A.G., Washington, D C. 134 pp.
• 14.Müller J-C., 1991. Generalization of spatial databases. In D.J Maguire Goodchild M.F. Rhind D.W. (eds), Geographic information systems. London: Longman: 457-75.
• 15.Perkal J., 1966. An attempt at objective generalization. Discussioi Paper No. 10. Ann Arbor, Mich: Michigan Inter-Universit Community of Mathematical Geographers.
• 16.Piątkowski F., 1969. Kartografia – Redagowanie map i reprodukcja kartograficzna, PWN Warszawa.
• 17.Saliszczew K.A., 1998. Kartografia ogólna, Wydawnictwo Naukowe PWN, Warszawa.
• 18.Shea K. S., McMaster R. B., 1989. Cartographic generalization in a digital environment: When and how to generalize. Proceedings Auto-Carto 9, Ninth International Symposium on Computer-Assisted Cartography, Baltimore, Maryland, March 1989: 56-67.
• 19.Sydow E., 1866. Drei Kartenklippen. Geographisches Jahrebuch 1866.
• 20.Visvalingam M., Whyatt J. D., 1993. Line Generalisation by Repeated Elimination of Points. Cartographic Journal, vol. 30, no. 1: 46-51.
• 21.Wang Z., 1996. Manual versus Automated Line Generalization. Proceedings of GIS/LIS ‘96, Denver, Colorado: 94=106.
• 22.Wang Z., Müller J-C., 1998. Line Generalization based on Analysis of Shape Characteristics. Cartography and Geographical Information Systems, 25 (1): 3 - 15.