【作者】 杜维；

【导师】 艾廷华；

【作者基本信息】 武汉大学 ， 地图制图学与地理信息工程， 2005， 硕士

【摘要】 地图注记配置的自动化是地图制图自动化的一个重要环节,也是地图制图和GIS研究领域的热点与难点问题。地图是用小空间(地图图面)描述大空间(制图实地范围)的表达工具。这种空间的急剧缩小引起了地图要素的强烈竞争,注记既要避免相互冲突和对地理要素的相互压盖,又要达到表达清晰、美观等制图规则要求。研究表明,寻找地图的最优注记是一个NP难度问题。 本文以点状居民地要素的注记自动配置为研究对象,对此问题进行了全面系统的分析,并深入研究了地名注记问题的规则、表达模型、质量评价模型、算法及编程实现等各个方面,并基于模拟退火算法提出了一套完整的解决方案。论文的主要内容包括: 1.注记知识的系统总结 对现有的地图注记基础知识进行了系统的总结和概括,其中包括地图注记的功能、分类、要素、配置规则以及评价准则等。 2.整体最优解理论及模拟退火算法的应用 研究了注记问题的整体最优解理论,将注记问题看成是空间竞争的组合优化问题,提出了使用模拟退火算法这种全局搜索方法来求取点状要素注记配置问题的整体最优解方案。 3.注记表达模型的建立及过程实施 提出了描述点状要素自动注记配置的6元组表达模型,即:待注记要素、注记属性、注记位置、注记规则、质量评价函数以及优化算法。并将注记配置过程划分为候选位置产生、位置评价、位置选择3个关键部分分别进行实施。 4.注记质量评价模型的建立 提出了一个顾及压盖、冲突、位置优先性、要素—注记关联性4方面的地图点状要素注记质量评价模型,对应的给出了PointOver、LabelOver、PosPref、PosAsso 4个评价子函数,并联合这些子函数建立了一个质量评价总函数。 5.Voronoi图的运用 利用Voronoi图可以反映空间事物邻近性的特性,对地图平面进行Voronoi多边形剖分,并计算每个Voronoi多边形对应注记的“自由度”,以决定是否对其进行“预注记”以及如何划分“注记相关组”。更多还原

【Abstract】 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.更多还原