地理信息系统中地图标注问题的研究与实现
摘要
地理信息系统（Geographical Information System， 简称GIS）作为集计算机科学、地理学、测绘、环境科学、空间科学、地质学、信息科学和管理科学等于一体的多学科结合的新兴边缘学科，正在以前所未有的速度飞速发展起来，并在城市地下管网的管理系统、城市综合管理系统、港口管理系统、金融管理分析系统、生态环境管理分析系统、人口管理系统等行业有着广泛的应用。随着地理信息系统的广泛应用，地图的标注问题作为GIS的一个基本的地图显示问题也越来越受到人们的重视，因为无论应用在哪个具体的行业，地图的显示质量都直接影响着软件的质量。
地理信息系统的标注可以分为三类：点特征的标注（例如城市或者山峰）、线特征的标注（例如河流或者道路）以及区域特征的标注（例如海洋或者国家）。对于点标注来说，简单地讲就是要求标注文字位于被标注点附近，并且标注之间不发生重叠，标注与地理特征符号之间也不发生重叠。对于线特征和区域特征标注，除了要求标注之间不发生重叠以外，还要求标注文字沿着地理特征的形状分散排列，对于区域特征，还要求标注内容位于区域以内，并尽量位于区域多边形内部中间位置的一条折线上。
针对不同标注问题的要求，本文分别讨论了三种标注的解决方法。
点标注问题（Point- Feature Label placement , PFLP）已经被证明是NP难的，因此已有的标注算法或者具有指数级别的运算时间复杂度,或者算法本身是不完全的。已有的点标注算法有穷
尽搜索算法、贪心算法、离散梯度下降算法、交叠向量的近似梯度算法、随机搜索算法以及启发算法等。穷尽搜索算法由于运算时间会随着输入点的数目的增加而急剧增加，是不适合于实际应用的；离散梯度下降算法、交叠向量算法在运算时间上有了很大的改善，但是算法容易陷入局部最小值而得不到最终的解；目前标注质量最高的是模拟退火算法（随机搜索算法的一种），但是模拟退火算法时间消耗很大；基于规则的启发式算法运算速度快，易于实现，适用于对时间要求较严格的应用。
对于线标注来说，问题本身相对比较简单，对标注文字位置的要求相比较而言也不如点标注那么严格，但它作为点特征标注和区域特征标注之间的桥梁，标注的好坏也不可忽略。利用二次开发组件MapObjects所提供的函数，就可以实现标注文字沿着线特征进行标注。如果进一步要求标注的美观性以及对区域标注的实用性，就可以根据已知线特征的坐标以及标注文字的数目将标注文字较分散地标注在线特征的附近。
对于区域特征，由标注要求以及区域的特性，可知如果将标注文字标注在区域多边形的骨架上，则标注文字就可以满足要求。因此作者首先总结了已有骨架算法——骨架的定义最初是由Blum所提出的，多年来不断有人对其进行研究，但是目前所发表的骨架化算法大多应用于图像处理领域，可以识别图像形状，重建模型，少有算法是针对图形多边形的。作者在总结比较了以前的算法的基础上，提出了基于三角形重心的平面多边形近似骨架化算法。该算法对输入n个顶点的多边形，可以在O(n)时间内计算求得多边形骨架。
在研究期间，作者还参加了基于GIS的朝阳区财政局纳税管理
系统GIS部分的设计实现，并独立完成了系统中基本地图操作模块、显示并控制地图图层的属性模块，以及根据所选地图属性对地图进行着色以及地图标注模块的实现。当时由于时间和知识有限，没有将标注算法应用于软件的开发。后来作者将上面所提到的三种改进标注的算法加以实现并加入系统的标注模块中，获得了令人满意的标注效果。
GIS (Geographical Information System ) is a new rising brim subject which is the combination of the computer science , grography , mapping , environment science , space science , geology , information science and manage science . GIS is developing at a very fast speed , and it is widely used in more and more field , such as the management system of city underground pipe-net , integrative management of the city , management of the port , finance management and analysis system , the management and analysis system of the environment , and the population management system . As the widely used of GIS , some basic problems in map display become more and more important and people pay more and more attention to them ,such as label placement , for in no matter what field , the quality of the map display can affect the quality of the software directly.
In GIS , three different label-placement tasks are usually identified : labeling of point features (such as cities or mountain peaks ) , line features (such as rivers or roads) , and area features (such as oceas or countries). For the point features labeling ,the text labels must be placed near the labeled feature on maps while avoiding overlaps with cartographic symbols and other labels .For the line features and area features , in spite the avoiding
overlaps , the label words should be placed along the features and there should be some distance between each words . If the features are area features , label words should be placed inside the area and along a line in the middle of the polygon the whole way.
In this paper , the three label-placement tasks are discussed separately .
The point-feature Label Placement (PFLP) has been proved to be NP-hard , so the published algorithms are either have exponential time complaxity or are incomplete . The existing algorithms for PFLP includes the exhaustive search , the greedy algorithms , the discrete gradient descent algorithms , the algorithms of approximating the gradient with overlap vectors , the stochastic search algorithms , the heuristic method and so on .The exhaustive methods are impractical for the running time of the methods will increase rapidly as the number of the input number increases . The discrete gradient algorithms and the algorithms of approximating the gradient with overlap vectors improve greatly in time complexity ,but the algorithms tend to stuck in local minima without getting the final result .The simulated anneling for PFLP(a kind of stochastic gradient-descent method) has the best labeling quality , but the time complexity is high .The Heuristic method based on rules has a comparatively high speed , and is easy to
implement ,the Heuristic method is used where the running time is strictly confined .
For the line features labeling, the problem is comparatively easier,and is less strict in confining the label placement then PFLP .But it can not be ignored for it is the bridge between the other labeling problem . We could place the label words along the line features by using the functions provided in MapObjects. If added aesthetic feeling is demanded ,the label words can be placed along the line features with some distance between every two words according to coordinates of the line features if the step length is given .
For the area features label , from the requirement of the label placement and the characteristic of the area features, the requirement could be satisfide by placing the label words on the skeletons of the area polygons .The published algorithms are summarized in this paper . The definition of skeleton was given by Blum , many researches about skeleton were done sine then .But the existing algorithms by now are mostly used handling image—recognizing the shape of image , reconstruct the model ,seldom are for graphic polygon. On the basis of summarization and compare former algorithms ,the approximate skeleton method for 2-D polygons based on center of gravity is put forward .The algorithms runs in time
O(n),where n is the total number of vertices in the polyg
地理信息系统的标注可以分为三类：点特征的标注（例如城市或者山峰）、线特征的标注（例如河流或者道路）以及区域特征的标注（例如海洋或者国家）。对于点标注来说，简单地讲就是要求标注文字位于被标注点附近，并且标注之间不发生重叠，标注与地理特征符号之间也不发生重叠。对于线特征和区域特征标注，除了要求标注之间不发生重叠以外，还要求标注文字沿着地理特征的形状分散排列，对于区域特征，还要求标注内容位于区域以内，并尽量位于区域多边形内部中间位置的一条折线上。
针对不同标注问题的要求，本文分别讨论了三种标注的解决方法。
点标注问题（Point- Feature Label placement , PFLP）已经被证明是NP难的，因此已有的标注算法或者具有指数级别的运算时间复杂度,或者算法本身是不完全的。已有的点标注算法有穷
尽搜索算法、贪心算法、离散梯度下降算法、交叠向量的近似梯度算法、随机搜索算法以及启发算法等。穷尽搜索算法由于运算时间会随着输入点的数目的增加而急剧增加，是不适合于实际应用的；离散梯度下降算法、交叠向量算法在运算时间上有了很大的改善，但是算法容易陷入局部最小值而得不到最终的解；目前标注质量最高的是模拟退火算法（随机搜索算法的一种），但是模拟退火算法时间消耗很大；基于规则的启发式算法运算速度快，易于实现，适用于对时间要求较严格的应用。
对于线标注来说，问题本身相对比较简单，对标注文字位置的要求相比较而言也不如点标注那么严格，但它作为点特征标注和区域特征标注之间的桥梁，标注的好坏也不可忽略。利用二次开发组件MapObjects所提供的函数，就可以实现标注文字沿着线特征进行标注。如果进一步要求标注的美观性以及对区域标注的实用性，就可以根据已知线特征的坐标以及标注文字的数目将标注文字较分散地标注在线特征的附近。
对于区域特征，由标注要求以及区域的特性，可知如果将标注文字标注在区域多边形的骨架上，则标注文字就可以满足要求。因此作者首先总结了已有骨架算法——骨架的定义最初是由Blum所提出的，多年来不断有人对其进行研究，但是目前所发表的骨架化算法大多应用于图像处理领域，可以识别图像形状，重建模型，少有算法是针对图形多边形的。作者在总结比较了以前的算法的基础上，提出了基于三角形重心的平面多边形近似骨架化算法。该算法对输入n个顶点的多边形，可以在O(n)时间内计算求得多边形骨架。
在研究期间，作者还参加了基于GIS的朝阳区财政局纳税管理
系统GIS部分的设计实现，并独立完成了系统中基本地图操作模块、显示并控制地图图层的属性模块，以及根据所选地图属性对地图进行着色以及地图标注模块的实现。当时由于时间和知识有限，没有将标注算法应用于软件的开发。后来作者将上面所提到的三种改进标注的算法加以实现并加入系统的标注模块中，获得了令人满意的标注效果。
GIS (Geographical Information System ) is a new rising brim subject which is the combination of the computer science , grography , mapping , environment science , space science , geology , information science and manage science . GIS is developing at a very fast speed , and it is widely used in more and more field , such as the management system of city underground pipe-net , integrative management of the city , management of the port , finance management and analysis system , the management and analysis system of the environment , and the population management system . As the widely used of GIS , some basic problems in map display become more and more important and people pay more and more attention to them ,such as label placement , for in no matter what field , the quality of the map display can affect the quality of the software directly.
In GIS , three different label-placement tasks are usually identified : labeling of point features (such as cities or mountain peaks ) , line features (such as rivers or roads) , and area features (such as oceas or countries). For the point features labeling ,the text labels must be placed near the labeled feature on maps while avoiding overlaps with cartographic symbols and other labels .For the line features and area features , in spite the avoiding
overlaps , the label words should be placed along the features and there should be some distance between each words . If the features are area features , label words should be placed inside the area and along a line in the middle of the polygon the whole way.
In this paper , the three label-placement tasks are discussed separately .
The point-feature Label Placement (PFLP) has been proved to be NP-hard , so the published algorithms are either have exponential time complaxity or are incomplete . The existing algorithms for PFLP includes the exhaustive search , the greedy algorithms , the discrete gradient descent algorithms , the algorithms of approximating the gradient with overlap vectors , the stochastic search algorithms , the heuristic method and so on .The exhaustive methods are impractical for the running time of the methods will increase rapidly as the number of the input number increases . The discrete gradient algorithms and the algorithms of approximating the gradient with overlap vectors improve greatly in time complexity ,but the algorithms tend to stuck in local minima without getting the final result .The simulated anneling for PFLP(a kind of stochastic gradient-descent method) has the best labeling quality , but the time complexity is high .The Heuristic method based on rules has a comparatively high speed , and is easy to
implement ,the Heuristic method is used where the running time is strictly confined .
For the line features labeling, the problem is comparatively easier,and is less strict in confining the label placement then PFLP .But it can not be ignored for it is the bridge between the other labeling problem . We could place the label words along the line features by using the functions provided in MapObjects. If added aesthetic feeling is demanded ,the label words can be placed along the line features with some distance between every two words according to coordinates of the line features if the step length is given .
For the area features label , from the requirement of the label placement and the characteristic of the area features, the requirement could be satisfide by placing the label words on the skeletons of the area polygons .The published algorithms are summarized in this paper . The definition of skeleton was given by Blum , many researches about skeleton were done sine then .But the existing algorithms by now are mostly used handling image—recognizing the shape of image , reconstruct the model ,seldom are for graphic polygon. On the basis of summarization and compare former algorithms ,the approximate skeleton method for 2-D polygons based on center of gravity is put forward .The algorithms runs in time
O(n),where n is the total number of vertices in the polyg
引文
[1]http://www.hbcpdi.com.cn/intranet/%D1%A7%CA%F5%BD%BB%C1%F7/xueshu002.htm
[2]于秀兰 陈滢 饶芳艳等，WebGIS中地图点状要素标注算法设计，遥感信息，2002 no.3
[3]Jon Christensen , Joe Marks , An Empirical Study of Altorighms for Point-Feature Label Placement
[4][美]Michael N . DeMers，地理信息系统基本原理，电子工业出版社，第66页~第88页
[5]Frank Wagner , Alexander Wolff , A Combinatorial Framework for Map Labeling , 1998
[6]Blum H . A Transformation for Extracting New Deseripton of Shape , Model for the Perception of Speech and Visual Forms , Wathen - Dunn. W . Ed . Cambridge.MA:MIT Press , 1967
[7]车武军，杨勋年，汪国昭，动态骨架算法，软件学报，Vol .14 ,No.4，2003
[8]R.Ogniewicz and M.Ilg , Voronoi Skeletons : Theory and Applications ,
[9] Lee TC , Kashyap RL . Building Skeleton Models Via 3-D Medial Surface/Axis Thinning Algorithms . CVGIP:Graphical Models and Image Processing , 1994 , 56(6) : 462~478
[10] Lobregt S , Verbeek PW , Broen FCA . Three-Dimensional Skeletonization : Principle and Algorithm . IEEE
Transactions on Pattern Analysis and Machine Intelligence , 1980 , 2(1) : 75~77
[11]李小俊，张逸新，基于边界点偏置的VORONOI骨架算法的研究，计算机应用，2002年第22卷第10期
[12]周培德，确定任意多边形中轴的算法，北京理工大学学报，Vol . 20 No . 6 Dec , 2000
[13]杨义军等，复杂带状图像的快速三角剖分与骨架化算法，计算机辅助设计与图形学学报，2003年10月，第15卷第10期
[14]Martin Held,FIST Fast Industrial-Strength Triangulation of Polygons , Algorithmica 30(4): 563-596, 2001
[15]刘光，地理信息系统二次开发教程——组件篇，清华大学出版社，第1页-第24页
[2]于秀兰 陈滢 饶芳艳等，WebGIS中地图点状要素标注算法设计，遥感信息，2002 no.3
[3]Jon Christensen , Joe Marks , An Empirical Study of Altorighms for Point-Feature Label Placement
[4][美]Michael N . DeMers，地理信息系统基本原理，电子工业出版社，第66页~第88页
[5]Frank Wagner , Alexander Wolff , A Combinatorial Framework for Map Labeling , 1998
[6]Blum H . A Transformation for Extracting New Deseripton of Shape , Model for the Perception of Speech and Visual Forms , Wathen - Dunn. W . Ed . Cambridge.MA:MIT Press , 1967
[7]车武军，杨勋年，汪国昭，动态骨架算法，软件学报，Vol .14 ,No.4，2003
[8]R.Ogniewicz and M.Ilg , Voronoi Skeletons : Theory and Applications ,
[9] Lee TC , Kashyap RL . Building Skeleton Models Via 3-D Medial Surface/Axis Thinning Algorithms . CVGIP:Graphical Models and Image Processing , 1994 , 56(6) : 462~478
[10] Lobregt S , Verbeek PW , Broen FCA . Three-Dimensional Skeletonization : Principle and Algorithm . IEEE
Transactions on Pattern Analysis and Machine Intelligence , 1980 , 2(1) : 75~77
[11]李小俊，张逸新，基于边界点偏置的VORONOI骨架算法的研究，计算机应用，2002年第22卷第10期
[12]周培德，确定任意多边形中轴的算法，北京理工大学学报，Vol . 20 No . 6 Dec , 2000
[13]杨义军等，复杂带状图像的快速三角剖分与骨架化算法，计算机辅助设计与图形学学报，2003年10月，第15卷第10期
[14]Martin Held,FIST Fast Industrial-Strength Triangulation of Polygons , Algorithmica 30(4): 563-596, 2001
[15]刘光，地理信息系统二次开发教程——组件篇，清华大学出版社，第1页-第24页