Automated cartographic generalization with a triangulated spatial model
This thesis describes a doctoral project which has addressed some of the problems of automatically performing cartographic generalization in a holistic manner, that is, processing the map features in the context of the whole map rather than individual features in isolation. The approach is based on two key ideas: firstly, that the map surface can be represented by a structure based on simplicial complexes which provides useful relationships for topology and proximity and facilitates many of the fundamental generalization operations. Secondly, that the epistemological structures needed for generalization can be represented by a hierarchy of "context" frames, each of which encapsulate the knowledge required to recognize, generalize and resolve a cartographic situation. A data structure that uses simplicial complexes to represent map objects has been designed and implemented. Each object is described by a set of two-dimensional simplices (triangles) that are maintained in the form of a constrained Delaunay triangulation. This structure gives a fully connected two-dimensional plenum that stores important spatial relationships such as "enclosed", "adjacent" and "between" explicitly. This simplicial data structure (SDS), as it is called, can be used directly to perform several types of operations necessary for automatic generalization, for example, automatic overlap detection, displacement, merging, enlargement, simplification of building outlines and skeletonization. Algorithms for many of these operators have been implemented while others are proposed. Pseudo-code and descriptions are used to document many of these operators, results are given and discussed. A frame-based architecture is proposed which provides a framework for the representation and application of knowledge for generalization. The project was funded by an EPSRC CASE studentship in collaboration with the Ordnance Survey.
Networked Digital Library of Theses and Dissertations