A line simplification algorithm using interpolation

Krystian Kozioł
AGH University of Science and Technology in Krakow
Faculty of Mining Surveying and Environmental Engineering
Department of Geomatics
Poland

Abstract

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.

Keywords:

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

Full Text:

PDF (Polish)

References

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.