Automated map generalization with multiple operators: a simulated annealing approach

Abstract

This paper explores the use of the stochastic optimization technique of simulated annealing for map generalization. An algorithm is presented that performs operations of displacement, size exaggeration, deletion and size reduction of multiple map objects in order to resolve graphic conflict resulting from map scale reduction. It adopts a trial position approach in which each of n discrete polygonal objects is assigned k candidate trial positions that represent the original, displaced, size exaggerated, deleted and size reduced states of the object. This gives rise to a possible kⁿ distinct map configurations; the expectation is that some of these configurations will contain reduced levels of graphic conflict. Finding the configuration with least conflict by means of an exhaustive search is, however, not practical for realistic values of n and k. We show that evaluation of a subset of the configurations, using simulated annealing, can result in effective resolution of graphic conflict.

Acknowledgments

Nathan Thomas is funded by EPSRC CASE Studentship 00802722, which is carried out in collaboration with the Ordnance Survey. The authors express thanks to the Institut Géographique National and the Ordnance Survey for permission to use their data in parts of the work presented.