基于分类的GIS地图符号快速标注算法-.doc

基于分类的GIS地图符号快速标注算法*摘 要：对地理特征进行标注是gis的重要功能，地图标注可以提高地图的可理解性，因而地图标注一直是制图和gis的研究热点。随着地理信息的指数增长，海量数据快速符号化成为了地图信息有效传输亟待解决的问题。本文提出了一种基于分类的地图符号快速标注算法，将全局的环境要素变换成分组标注序列，将标注过程分解为等价分组标注过程。试验分析结果表明，与常规方法相比，有效提高了地图的标注速度。该算法为海量数据快速符号化的研究提供了基础，为大数据量地图信息有效传输的实现提供了支撑。关键词：分类；gis；快速标注算法 fast labeling algorithm based on the classification of gis map symbolsli zhen-xing, shao feng-jing, sun ren-cheng, li shu-jing,wu shun-yao( qingdao university information engineering college, qingdao 266071, china)【abstract】the important function of gis is to label the geography feature, which can improve the intelligibility of the map.consequently, the map labeling problem has been a fundamental question for gis. with the exponential growth of geographic information, huge amounts of data fast symbol problem need to be solved for effective transfer of map information. this paper presents a rapid arithmetic, based on category. the algorithm stated in this paper transfers geography element to grouped sequence labeling, and disassembles the labeling process into equivalent group mark process. the test results show that, compared with conventional methods, to effectively improve the speed of the map marked. the algorithm for the huge amounts of data fast symbolic provides the foundation provided support for the effective transmission of large amount of data map information.【key words】classification; gis; fast labeling algorithm地理信息系统(gis) 是计算机技术在地图学领域发展而形成的一门新兴技术。随着gis的广泛应用，地图信息的传输模式已由纸质形式逐渐演变为电子形式。用户可根据需要在地图中进行地理分析、信息检索、目标定位、地理模型计算，进而做出决策支持1。随着地理信息的不断积累，地图符号数量庞大且绘制过程复杂，已严重制约了地图信息的有效传输。地图符号绘制速度决定了地图的显示速度2，如何对海量数据快速符号化、减少时间延迟成为亟待解决的问题。地图标注问题是地理信息系统中重要研究问题之一，离散计算几何研究领域学者已进行了深入探索3。刘灿由等4采用格网索引与双缓存并行调度技术解决海量数据的快速调度显示问题；yang等5利用基于三角形剖分的多分辨率模型的矢量数据简化网络传输的算法；m.bertolotto6等构建了一种多比例尺数据和渐进传输的概念模型，以解决拓扑结构变化的问题，该方法能较好的实现矢量数量的简化和传输；王同合等2采用基于符号库的gis地图符号快速绘制算法提高矢量地图的显示速度；针对渔业资源分布图绘制，于杰等7提出了渔业资源分布图批处理算法，以实现对海量渔获数据自动批处理制图；针对超大数据量矢量电子地图显示的问题，陈刚8提出了对数据进行分区建索引和分层显示的方法。然而，上述研究工作在处理大量标注时需要频繁的交互修改，严重影响了地图制图的速度。本文从标注类别特性角度出发，提出了一种基于分类的gis地图符号快速标注算法，对提高海量数据符号化速度具有重要意义。 1 相关定义为便于后续的表述，本文对快速标注算法所涉及的相关概念和前提作如下定义：1）环境要素信息e是地图绘制的信息载体，为自动制图或查询时标注信息的集合。环境要素的结构模型可以表示为如下的元组形式：e=ec,eo,ep,eh,et式中，ec指该环境要素的类别分量；eo为符号类别分量；ep为标识环境要素的坐标分量，包括经度、纬度、高度；eh表示该要素的属性分量；et表示环境要素的时间分量。以上5个元组分量构成了完整的标注信息，其中，ec,eo,ep,eh分量取值不能为空，et分量并非必须项，取值可以为空。2）地理要素类别ec=ci,1in其中，n为标注涉及的地理要素类别维数；ci的类别集合ri=rij,1in；1imi其中,mi为ri的类别维数，rij为具体要素在ci维上的分布情况。3）符号类别eo=olk,1in；1im其中，s为符号类别维数，m为oi维的符号类别总数，oij表示某个符号。4）坐标ep=pi,1in其中，n为环境要素的坐标维数；pi=plo,pla,ph，plo,pla,ph分别为标注涉及的经度、纬度和高度信息。5）属性值h=hi,1it其中，t为环境要素涉及属性的维数，hi为第i维的属性值。 2 快速标注算法快速标注算法的实质是将全局的环境要素标注序列按照类别特性等价变换为分组标注序列的过程。标注过程是多种要素展示的过程，具有类别特性，可以从性质、用途、形状、尺度、色彩等5个方面考虑标注分类9，gis展示时可根据分类指标对要素进行分类。同时，根据符号的几何特征对地图符号进行分类。通过对要素与符号的分类完成全局环境要素的分组，使标注过程分解为等价分组标注过程。 2.1 要素类别划分要素分类主要为了解决两个问题，一是地图显示中的自动制图综合问题，另一个是查询问题10。对地图的绘制可转化为对要素层所属的类别的分组绘制。要素分类对解决数字地图显示中的制图综合和查询、符号样式设置及针对不同需求的灵活查询问题，提供了很好的思路。针对要素对象的特殊性，按照某种分类规则在逻辑上将要素细分成不同类型的子层。参照定义ec=ci,1in与ri=rij,1in；1imi，在制图或者查询过程中，根据其特点和分类指标对专题要素进行分类绘制。以海洋监测应用为例，监测数据包含赤潮、海冰、浒苔、海浪等多维数据，每个维包含相应子类数据。ci代表赤潮、海冰、浒苔、海浪等多维数据，ri代表i维度下的子类数据集合，rij代表子类数据下分类集合或具体分类。 2.2 地图符号划分根据符号的几何特征，地图符号主要分为点状符号、线状符号和面状符号11。根据地理信息系统对现实的抽象，可将特定应用数据分为点、线、面12。针对特定应用，对每一类地图符号建立对应符号，设置不同的符号显示控制样式。绘图时按照符号编号，地理要素相关的位置、大小、颜色等参数就能完成地图符号的绘制。符号库采用二叉树结构，组织结构图1所示。将符号分为点、线、面文件分别存储在地图符号库。节点代表某类标注类型，子节点代表3种类型的符号是根节点下的，而每个符号项是某个符号类型节点下的子节点，叶节点代表某个具体符号13。 2.3 算法执行流程本文将全局的环境要素标注过程解析为等价分组标注序列，绘图时各组并发执行。在绘制过程中每组对应的符号资源不再修改，降低了绘制算法的系统资源开销。将标注过程频繁的交互修改按照实际分组情况降低了频率，有效提高了算法效率。算法的输入条件为环境要素e=ec,eo,ep,eh,et，e的标注条件为q=eceoep。其特点为要素类别ec及符号类别eo维数较少，以此为主要划分条件，可以进一步分解为q=eceo，产生rij,okt分组序列。执行流程如图2所示。首先获取环境要素e，对类别及标注进行分类，然后进入相应的分组序列rij,okt，通过分组同步执行与直接读取符号库的方法，提高地图符号绘制速度。 3 试验结果及对比分析大数据量地图标注算法的性能在于标注过程的分组方案。本文算法在确定分组序列后利用相应绘制方法执行分组序列，即可得到最终的绘制结果。试验电脑cpu为inter? core? 2 duo e4500 2.20ghz， 2g内存，操作系统为windows server2003 sp2，web服务器为iis6.0。开发语言为c#与，并采用c#的性能分析功能命名空间system. diagnostics准确地测量执行时间，不计刷新、叠加等过程运行时间。试验分为a、b两组，a组实验采用本算法并通过多线程编程完成分组序列的并发执行，b组实验没有采用本算法。地图底图采用arcgis server9.3平台的usa_data示例数据，标注数据为模拟数据，假设为2类要素数据，符号类别为1.2.3三种形式且地理坐标随机生成。a组试验通过本算法可得到6组分组序列rij,okt，分别获得统计时间并取每组最大值作为运行时间。对1000，5000，25000，50000，100000， 200000，1000000个标注数据进行4次重复试验，获取运行时间平均值。试验分组及运行时间统计如表1所示，时间单位为毫秒(ms)。从以上统计数据得出时间对比分析图，见图3所示，a组试验所花费时间明显少于b组试验。在标注分组相对均匀的情况下，采用本算法后随着标注量的增加，能够显著的提高地图绘制效率。图3 时间对比表1 试验统计运行时间/msa1组a2组a3组a4组a5组a6组a时间b时间1000191369281821958718 50004181797255190108365493 2500083989044631411774918295563 5000025274108172816103094882966781203.67 10000041687385922124156551038962861481.42556.75 20000092169598451273924233673342812723.25404.67 100000030243424643013694483529920561386071709731210 4 结束语从地图符号绘制过程及实验对比分析可以看出，本文方法由于采用分类处理和分组序列同步绘制，并且在绘制过程中直接读取符号，降低了系统资源开销，提高了符号绘制速度，从而大大提高了海量数据快速符号化问题速度。该算法已在渤海海洋环境信息集成及动态管理技术示范应用渤海海洋异构数据集成快速访问提取及智能分析技术项目中成功应用，取得了良好效果。参考文献1 朱正国. 电子地图中标注算法的研究及应用d. 成都：西华大学,2009.2 王同合,岳春生,赵夫来等. 基于模板的嵌入式gis地图符号快速绘制算法j. 测绘科学技术学报,2009,26(5): 330-332.3 bernard chazelle et al. application challenges to computational geometry: cg impact task force report r. technical report,tr-521-96,princeton university. april 1996.4 刘灿由,崔铁军,郭黎等. 电子地图多尺度快速表达的关键技术研究j. 地理信息世界,2009,(03): 70-74.5 yang b s, purves r, weibel r. efficient transmission of vector data over the internet j. international journal of geographical information science, 2007, 21(2): 215-237.6 bertolotto m, egenhofer mj. progressive transmission of vector map data over the world wide web j. geoinformatica, 2001, 5(4): 345-373.7 于杰,李永振,黄洪辉等. 渔业资源分布图批处理算法arcgis二次开发的实现j. 海岸工程,2008, 27(2): 52-57.8 陈刚. 超大数据量矢量电子地图显示的方法研究及实践j. 测绘通报,2000,(2): 15-17.9 郑贵洲,吴信才. mapgis图层在地图数据处理和管理中的作用