**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.