ESSENTIAL OPERATIONS AND ALGORITHMS FOR GEOMETRIC TRANSFORMATIONS IN DIGITAL MAP GENERALIZATION

Z.L. Li

Hong Kong Polytechnic University, Dept. of Land Surveying and Geo-Informatics, Hong Kong

lszlli@polyu.edu.hk

 

A national mapping agency may have maps at scales from 1:1,000 to 1:1,000,000 scale and even smaller. One critical issue faced by national mapping agencies is to update maps at so many scales frequently. The ideal approach is to update maps at the largest scale frequently and to derive maps at smaller scale on demand only. This can be achieved by digital map generalization.

 

As a map contains (geo)metric information (related to position, size and shape), thematic information (related to the types and importance of features) and relational information (about spatial relationship between neighbouring features), there must be three types of transformations involved in digital map generalization, geometric, thematic and relational.

 

The geometric transformations are achieved by some operations. The issues related to geometric transformations are

         What operations are essential?

         What operations are currently available? and

         What algorithms are available for each of these essential operations?

 

In classic textbook, only very few operations are identified, e.g. classification, induction, simplification and symbolization by Robinson et al (1984) and aggregation, combination, simplification, displacement and selective omission by Keates (1989). However, some of these concepts are far too vague. More recently, a list of 12 operations have been identified by McMaster and Shaea (1992), i.e. aggregation, amalgamation, classification, collapse, displacement, enhancement, exaggeration, merge, refinement, simplification, smoothing and typification. However, these operations are still general too general to be computerized. Indeed, it may mean different things by the operation. For example, typification is often referred to the re-arrangement of buildings (e.g. from 5 rows x 4 columns to 3x2) but is also applicable to individual roads (e.g. from 4 bends to 2 bends) and road network (elimination of minor roads and retention of important road). Therefore, a systematic classification needs to be carried out.

 

This project aims to make such a classification of generalization operations. Various criteria could be used for such a classification. However, in this text, emphasis is on the implementation of algorithms and thus classification is made based on the dimension of geometric elements. After such a classification, a list of 32 operations is identified and algorithms appropriate to each of these operations are searched. New proposals are made if no suitable algorithms are currently available.