Algorytm upraszczania linii z wykorzystaniem interpolacji

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

Streszczenie

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.

Słowa kluczowe:

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

Pełny tekst:

PDF

Bibliografia

Brassel K.E., Weibel R., 1988: A Review and Framework of Automated Map Generalization. Int. Journal of Geographical Information Systems, 2(3): 229-244.

Chrobak T., 2000: Numerical Method for Generalizing the Linear Elements of Large-Scale Maps, Based on the Example of Rivers, Cartographica, Vol. 37.

Chrobak T., 2010: The role of least image dimensions in generalization of object in spatial databases, Geodesy and Cartography, Polish Committee for Scientific Research.

de Boor, C., 1978: A Practical Guide to Splines, Springer-Verlag.

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.

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.

Lang T., 1969: Rules for robot draughtsmen, Geographical Magazine, Vol 42 50-51.

Li, Z., 1993: Some observations on the issue of line generalisation. Cartographic Journal, 30 (1): 68-71.

Li Z, 2007: Algorithmic Foundation of Multi-scale Spatial Representation. CRC Press (Taylor & Francis Group). ISBN: 0849390729. 280 pp.

McMaster, R.B., 1986: A statistical analysis of mathematical measures for line simplification, American Cartographer, 13:103-116.

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.

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.

McMaster R.B., Shea K.S., 1992: Generalization in digital cartography. Publication supported by the A.A.G., Washington, DC. 134 pp.

Müller J-C., 1991: Generalization of spatial databases. [In] Maguire D.J, Goodchild M.F., Rhind D.W. (eds), Geographic information systems. London: Longman: 457-75.

Perkal J., 1966: An attempt at objective generalization. Discussioi Paper No. 10. Ann Arbor, Mich: Michigan Inter-Universit Community of Mathematical Geographers.

Piątkowski F., 1969: Kartografia – Redagowanie map i reprodukcja kartograficzna, PWN Warszawa.

Saliszczew K.A., 1998: Kartografia ogólna, Wydawnictwo Naukowe PWN, Warszawa.

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.

Sydow E., 1866: Drei Kartenklippen. Geographisches Jahrebuch 1866.

Visvalingam M., Whyatt J.D., 1993: Line Generalisation by Repeated Elimination of Points. Cartographic Journal, vol. 30, no. 1: 46-51.

Wang Z., 1996: Manual versus Automated Line Generalization. Proceedings of GIS/LIS‘96, Denver, Colorado: 94-106.

Wang Z., Müller J-C., 1998: Line Generalization based on Analysis of Shape Characteristics. Cartography and Geographical Information Systems, 25 (1): 3-15.