Resolving Graphic Conflict In Scale Reduced Maps: A Simulated Annealing Approach

Abstract

This thesis explores the use of the stochastic optimisation technique of simulated annealing for cartographic map generalisation. The technique performs operations of displacement, deletion, reduction and enlargement of multiple map objects in order to resolve graphic conflict resulting from a reduction in map scale. A trial position approach is adopted in which each of n discrete polygonal objects is assigned k candidate trial positions that represent the original, displaced, reduced and enlarged states of the object. This gives rise to a possible kⁿ distinct map configurations; the expectation is that some of the configurations will contain reduced levels of conflict. Finding the configuration with least conflict by means of an exhaustive search is, however, not practical for realistic values of n and k. However, the thesis shows through an evaluation of a subset of the configurations, using simulated annealing, can result in an effective resolution of graphic conflict in real time.

Furthermore the thesis explores various methods of improving upon the existing simulated annealing work. Firstly, two techniques were developed that aid in improving execution times using a data partitioning and a two-stage annealing strategy. Secondly, an investigation was carried out which explores the application of high-order feature alignment and the use of a continuous search space. Moreover the thesis explores the use of incorporating additional feature classes into the existing SA framework.

A thorough evaluation has been carried out which demonstrate the usefulness of each approach. The research has achieved five key improvements over the original SA technique: a reduction in execution times; a greater support for generalisation operators; presented a solution to maintaining high-order feature alignment; provided a greater support for additional feature classes; and, a refinement to the search space resulting in an improved graphic display output.

Although the thesis demonstrates the potential of simulated annealing as a means of reducing graphic conflict in scale-reduced maps, there still exists an enormous scope for further work. Additional techniques need to be devised to reduce execution times further for use with on-the-fly generalisation tasks. Other areas for future work include the incorporation of more sophisticated operators and an investigation to determine if SA can be adapted to resolve graphic conflict between linear features.

Date of Award	May 2004
Original language	English
Supervisor	Mark Ware (Supervisor), David Kidner (Supervisor) & Andrew Ware (Supervisor)