Generalisation and Multiple Representation

Trajectories and line generalisation

6204.3 - Shape-Adaptive Geometric Simplification of Heterogeneous Line Datasets

Thursday, July 6
11:10 AM - 11:30 AM
Location: Virginia B

Line generalization is one of the essential data processing operations in GIS and cartography. Many point reduction, line simplification and generalization algorithms have been developed for this purpose so far. Weibel (1996) noted that many algorithms developed for line generalization neglect significant constraints which are well established in cartographic practice. As a consequence, results can be used for minimal simplification. Among the constraints Weibel identified preservation of original line character (Gestalt), that requires the preservation of the intrinsic character expressing the generating process of a feature represented by a cartographic line.

Buttenfield (1987) was one of the first who emphasized the necessity of analyzing the line shape for parameterizing generalization algorithms. Plazanet et al. (1995) developed the methodology of line segmentation into fragments with different shape characteristics. Mustiere (2005) developed the local and adaptive approach to road generalization, in which different algorithms may be successively applied to each part of a road. Park et al. (2011) developed a hybrid line simplification approach for cartographic generalization. Their methodology for segmenting and simplifying linear features is based on the quantitative shape characteristics.

These studies were concerned with homogeneous line datasets which contain one type of features: buildings, roads etc. The developed segmentation approaches were based on quantitative characteristics and handle the continuous variations in line morphology, but do not handle the variations in line character which is a qualitative characteristic.

At the same time there are heterogeneous line datasets in which lines of different character may coexist. One example is administrative borders. These lines may follow parallel and meridian directions in one part, being arranged in a clearly perceived orthogonal pattern. In other parts they may be long and straight without orthogonality, but still visually schematic, following some selected azimuth. And, finally, they may coincide with rivers and mountain ridges, being naturally smooth and non-schematic.

We developed an approach and generalization model for geometric simplification of lines consisting of three characters: non-schematic, irregular schematic and orthogonal. Our approach consists generally of the three steps: preprocessing, processing and postprocessing.

Preprocessing stage involves operations such as filtering, segmentation and squaring. Filtering is a point-reduction with small tolerance and is performed to remove excessively digitized points from the line. Segmentation allows subdivision of the line into the fragments of different character. All lines are considered to be constructed by edges and vertices. We use the minimal edge length S and angle tolerance A (difference from 90 degrees) to extract the orthogonal segments. The minimal edge length D is used to extract the schematic segments. All the remaining segments are considered to be non-schematic. Squaring is applied to orthogonal segments to make almost right angles be just right.

Processing involves iterative geometric simplification of the segments, in which every segment is simplified with the dedicated algorithm, then excessively small segments are appropriately merged with neighbors and simplification is performed again. Experimental work shows that Li-Openshaw produces smooth shapes and works well for simplification of non-schematic segments. Douglas-Peucker algorithm effectively keeps and emphasises the sharp and edgy nature of schematic parts of the line. Orthogonal segments are simplified with the customized approach.

Postprocessing is similar to preprocessing but is optionally performed on the simplified geometry and is dedicated to regularize the result.

The performance of the developed approach is tested on rayons borders in Russian Komi and Arkhangelsk regions and counties in US’ Montana and Oregon States. Results show that our model effectively segments the line dataset into the homogenuous parts, while the application of the appropriate algorithm allows keeping their characters.

Timofey Samsonov

Leading Researcher
Lomonosov Moscow State University, Faculty of Geography, Department of Cartography and Geoinformatics

Timofey Samsonov is a leading researcher at the Department of Cartography and Geoinformatics, Faculty of Geography, Lomonosov Moscow State University, Moscow, Russia. Timofey holds a PhD in Cartography (2010) from Lomonosov MSU. His interests include generalization of spatial data, multiscale mapping, terrain mapping and analysis, spatial analysis and automation in cartography. Timofey is active in two ICA Commissions: ICA Commission on Generalisation and Multiple Representation and ICA Commission on Mountain Cartography.


Send Email for Timofey Samsonov

Olga Yakimova

Associate Professor
Demidov Yaroslavl State University, Faculty of Mathematics

Olga Yakimova is an associate professor at Department of Computer Security and Mathematical Methods of Information Processing, Faculty of Mathematics, Demidov Yaroslavl State University, Yaroslavl, Russia. She holds a PhD in Mathematics, her interests in addition to pure mathematics, numerical methods and programming include the applications of mathematical approaches in cartography.


Send Email for Olga Yakimova

Dirk Burghardt

Prof. Dipl.-Phys. Dr.-Ing. habil.
TU Dresden, Institut of Cartography

Dirk Burghardt is a full professor in the Cartographic Institute at Dresden University of Technology since 2009. From 1998-2001 he worked as a software engineer and product manager in a map production company in Switzerland. Between 2002 and 2008 he was lecturer in the GIS Division at the University of Zurich (CH). Prof. Burghardt is the chair of the ICA Commission on Generalisation and Multiple Representation of the International Cartographic Association since 2011. His main research interests include automated generalisation and map production, geographic information retrieval, interactive cartographic presentations, geovisual analytics and cartographic communication.


Send Email for Dirk Burghardt


6204.3 - Shape-Adaptive Geometric Simplification of Heterogeneous Line Datasets

Attendees who have favorited this

Please enter your access key

The asset you are trying to access is locked. Please enter your access key to unlock.

Send Email for Shape-Adaptive Geometric Simplification of Heterogeneous Line Datasets