Point Feature Label Placement Research Based On Simulated-Annealing Algorithm

Automatic map label placement plays an important role in the automation of cartography. This problem is also active and difficult issue in cartography and GIS field. As a descriptive tool representing a large space with a small one, the map has the problem of feature space competition. On one hand, a dense map has little space for labels; on the other hand, the labels must be placed without conflicting each other or overlapping with other features. The label placement should obey to the visibility and aesthetic rules for map. Research shows that the complexity of finding the optimum label placement is a NP-hard problem.This thesis concentrates on the issue of point feature label placement (PFLP), giving a systematic and overall research on PFLP, and covering the aspects about labeling rules, labeling model, labeling algorithm, quality evaluation and experiment. Finally, a whole solution for PFLP is presented. It includes the main contents as follows:1. The Review of Map Labeling KnowledgeWe give a systematic review and summarization of the exiting labeling knowledge, which includes label function, classification, element, labeling rule and quality evaluation.2. The Global Optimization Theory and Simulated Annealing AlgorithmPFLP is regarded as a combination optimization problem for space competition.Guided by this, an optimal algorithm------Simulated Annealing Algorithm is used to findthe global optimum solution for label placement.3. The Construction of Labeling Expression Model and its OperationBy the summarization of PFLP, a six-element model is provided, which includes un-labeled feature, label property, label position, labeling rule, quality evaluation functionand labeling algorithm. And the labeling process is divided into three key parts------candidate position generation, position evaluation and position selection.4. The Research of Labeling Evaluation ModelBy analysis of the main aspects for labeling quality, an accessible labeling quality evaluation model is set up. And based on the model, the quality evaluation function is deduced.5. The Use of Voronoi DiagramWe decide whether the label should be "pre-labeled" or how to divide the labels into relative groups by the freedom of each label, which is calculated by means of Voronoi diagram.