论文部分内容阅读
地理信息系统(Geographical Information System, 简称GIS)作为集计算机科学、地理学、测绘、环境科学、空间科学、地质学、信息科学和管理科学等于一体的多学科结合的新兴边缘学科,正在以前所未有的速度飞速发展起来,并在城市地下管网的管理系统、城市综合管理系统、港口管理系统、金融管理分析系统、生态环境管理分析系统、人口管理系统等行业有着广泛的应用。随着地理信息系统的广泛应用,地图的标注问题作为GIS的一个基本的地图显示问题也越来越受到人们的重视,因为无论应用在哪个具体的行业,地图的显示质量都直接影响着软件的质量。地理信息系统的标注可以分为三类:点特征的标注(例如城市或者山峰)、线特征的标注(例如河流或者道路)以及区域特征的标注(例如海洋或者国家)。对于点标注来说,简单地讲就是要求标注文字位于被标注点附近,并且标注之间不发生重叠,标注与地理特征符号之间也不发生重叠。对于线特征和区域特征标注,除了要求标注之间不发生重叠以外,还要求标注文字沿着地理特征的形状分散排列,对于区域特征,还要求标注内容位于区域以内,并尽量位于区域多边形内部中间位置的一条折线上。针对不同标注问题的要求,本文分别讨论了三种标注的解决方法。点标注问题(Point- Feature Label placement , PFLP)已经被证明是NP难的,因此已有的标注算法或者具有指数级别的运算时间复杂度,或者算法本身是不完全的。已有的点标注算法有穷<WP=63>尽搜索算法、贪心算法、离散梯度下降算法、交叠向量的近似梯度算法、随机搜索算法以及启发算法等。穷尽搜索算法由于运算时间会随着输入点的数目的增加而急剧增加,是不适合于实际应用的;离散梯度下降算法、交叠向量算法在运算时间上有了很大的改善,但是算法容易陷入局部最小值而得不到最终的解;目前标注质量最高的是模拟退火算法(随机搜索算法的一种),但是模拟退火算法时间消耗很大;基于规则的启发式算法运算速度快,易于实现,适用于对时间要求较严格的应用。对于线标注来说,问题本身相对比较简单,对标注文字位置的要求相比较而言也不如点标注那么严格,但它作为点特征标注和区域特征标注之间的桥梁,标注的好坏也不可忽略。利用二次开发组件MapObjects所提供的函数,就可以实现标注文字沿着线特征进行标注。如果进一步要求标注的美观性以及对区域标注的实用性,就可以根据已知线特征的坐标以及标注文字的数目将标注文字较分散地标注在线特征的附近。对于区域特征,由标注要求以及区域的特性,可知如果将标注文字标注在区域多边形的骨架上,则标注文字就可以满足要求。因此作者首先总结了已有骨架算法——骨架的定义最初是由Blum所提出的,多年来不断有人对其进行研究,但是目前所发表的骨架化算法大多应用于图像处理领域,可以识别图像形状,重建模型,少有算法是针对图形多边形的。作者在总结比较了以前的算法的基础上,提出了基于三角形重心的平面多边形近似骨架化算法。该算法对输入n个顶点的多边形,可以在O(n)时间内计算求得多边形骨架。在研究期间,作者还参加了基于GIS的朝阳区财政局纳税管理<WP=64>系统GIS部分的设计实现,并独立完成了系统中基本地图操作模块、显示并控制地图图层的属性模块,以及根据所选地图属性对地图进行着色以及地图标注模块的实现。当时由于时间和知识有限,没有将标注算法应用于软件的开发。后来作者将上面所提到的三种改进标注的算法加以实现并加入系统的标注模块中,获得了令人满意的标注效果。