下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 地图矢量数据拓扑关系生成算法

地图矢量数据拓扑关系生成算法.pdf

地图矢量数据拓扑关系生成算法

hzliuqi1988
2013-08-01 0人阅读 举报 0 0 暂无简介

简介:本文档为《地图矢量数据拓扑关系生成算法pdf》,可适用于高等教育领域

第28卷 第4期2012年7月地理与地理信息科学Geography and Geo-Information ScienceVol.28 No.4July 2012  收稿日期:2012-01-07 修订日期:2012-03-12  基金项目:国家自然科学基金项目(41071297)  作者简介:徐立(1985-)男博士研究生主要研究领域是空间数据模型和数字制图技术。E-mail:xuli_1985@yeah.net地图矢量数据拓扑关系生成算法徐 立1孙 群1杨 帅2徐 振3(1.信息工程大学测绘学院河南郑州4500522.北京大学地球与空间科学学院北京1008713.66240部队北京100042)摘要:拓扑关系的建立是地图矢量数据管理和更新的重要内容。在综合多种典型拓扑算法优点的基础上详细描述了拓扑关系生成算法的主要过程并在线要素互相交断链、结点匹配和特殊情况处理等方面对算法进行了改进。最后以1∶25万济宁市地形图数据进行了实验结果表明该算法在效率方面优于传统算法。关键词:拓扑元素拓扑关系线要素互相交断链结点匹配多边形追踪中图分类号:P283  文献标识码:A  文章编号:1672-0504(2012)04-0018-04  地图图形数据的拓扑关系是对地图矢量数据进行空间查询、分析和质量检查等操作的基础[1]。拓扑关系生成算法主要包括3方面的内容:线要素互相交断链、结点与弧段间关系的建立、弧段与多边形间关系的建立。在处理大量数据的情况下传统算法在线要素互相交断链过程中效率会明显降低在建立结点与弧段间关系的过程中传统算法往往无法科学地匹配不同精度的结点另外由于地图矢量数据较复杂在建立弧段与多边形间关系的过程中有时会出现一些特殊情况传统算法并没有合理地处理这些特殊情况。针对以上不足结合现有地图矢量数据的特点本文对传统的地图矢量关系生成算法做出了相应的改进。1 拓扑元素的分类及地理意义拓扑元素与空间要素并不是一一对应的关系。按照拓扑学原理地图要素中的拓扑元素主要有3种基本类型:结点、弧段和面域[2]。(1)结点。两条或两条以上弧段的连接点称为结点一条闭合弧段的首尾接点或一条悬挂链的端点也可称为结点[3]。结点可以有实际地理意义如道路中的交叉口、桥梁和界碑等也可以无实际地理意义如湖泊边线上的结点。(2)弧段。两结点间的有向线段称为弧段[3]。弧段一般都具有实际意义如道路、管线和面状河流湖泊的边线等但在某些特殊情况下也可能没有实际意义如面状要素的强制闭合线。在弧段的定义中弧段是带有方向性的但其对应的空间要素可能并没有方向性如一般的公路(单车道公路除外)没有方向性。方向对于用来构建面域的弧段是有作用的图1中湖泊a的边线是顺时针方向岛屿b的边线是逆时针方向在计算湖泊面积时岛屿b的面积会出现负值。图1 弧段的方向性Fig.1 Directions of the arcs(3)面域。面域是指由一条或若干条弧段构成的闭合多边形[3]每个面域都有一个内点(面域内的任意一点承载面域的属性信息)与之相对应。绝大多数面域具有实际意义如面状河流与湖泊、行政区和面状居民地等。依据以上不同拓扑元素的地理意义可以在拓扑数据预处理时自动筛选需要参加拓扑的元素。2 算法的主要步骤目前一般采用自动方式生成地图数据拓扑关系首先对需要参加拓扑的数据进行预处理再根据左转算法(通过判断邻接弧间的内角)和基于图的理论确定拓扑关系[4]。拓扑关系处理流程如图2所示。在地图矢量数据中只是部分要素层的部分要素需要参加拓扑以1∶25万地形图的居民地层为例只有由面属性决定的边线、图边强制闭合线、图幅内强制闭合线和街区边线需要参加拓扑[5]。因此在拓扑关系构建前需要建立一个拓扑控制表依据该表对初始数据进行筛选以确定需要参加拓扑的要素。每个参加拓扑的要素层必须包含相应的拓扑控制表每个参加拓扑的要素必须包含编码信息和精度等级信息。每种要素(以编码区分)都有一个精度等级如省道比一般的县道等级高在进行结点匹配时若省道相关的结点与附近县道相关的结点在空间位置上发生冲突则以省道相关的结点坐标为准。图2 拓扑算法处理流程Fig.2 The process of the topological algorithm2.1 线要素互相交断链在采集地图数据时为节省时间可能将几条相连的弧段作为一条线要素输入这样可能导致弧段之间相交。这种情况是不允许的因为在弧段的定义中规定:弧段之间除了结点外不能有其它的公共点[6]。因此需要对参加拓扑的线要素进行互相交断链处理。2.1.1 线要素格网索引的建立 一幅地图矢量数据中线要素数量最多若对所有参加拓扑的线要素两两求交势必降低算法效率。从全局角度考虑大部分情况下线要素并不相交这时可以将地图区域分为M×N个矩形子区域。由于有可能出现相交点落在线段延长线上且交点在线段某端点附近的特殊情况这时两条线段实际上可能相交但两条线段却又处于相邻的两个网格区域则无法对两条线段进行相交处理所以必须对网格进行适当的外扩处理所生成的网格宽度w和高度h公式如下:w=(Xmax-Xmin)N+2 Dh=(Ymax-Ymin)M+2 D其中:Xmax、Xmin、Ymax、Ymin为图幅的外接范围D为结点匹配误差2D为网格扩充的长度。2.1.2 线要素间的互相交断链 线要素格网索引建立完毕后针对每个格网中的线要素进行互相交断链处理算法如下:设网格线要素链表为Link任意线要素为Lin为Link包含的线要素个数从链表Link中取出第一个线要素并设置为当前要素L将线要素L依次与后面的线要素Li(1<i≤ni为整数)求交。(1)判断L是否已求交或是否有效若已求交或无效则转入步骤3判断L的ID是否与Li的ID相同若相同则转入步骤3判断L和Li的外接矩形是否相交若不相交则转入步骤3。(2)将L标记为已求交并依次取出Li中包含的线段求出它们与L的交点。若其中一条线段Li与L产生交点将Li标记为已求交如图3所示:L与Li中的线段AB相交产生交点P1、P2、P3。对于其它特殊情况还需另行处理:如图4中交点P1刚好与折线L的端点重合此时生成3个线要素根据交点对应于Li中的线段号将交点重新排序为:P1、P2、P3。  (3)在Link中取出当前线要素的后一个线要素若不为空将该要素设为当前要素L转入步骤2反之转入步骤4。(4)建立新链表Link2重新遍历链表Link若线要素有效则将要素加入链表Link2据此生成的新链表Link2即为线要素互相交断链结果。2.2 结点与弧段间关系的建立线要素进行互相交断链处理生成的数据是孤立的弧段和结点必须进一步通过结点匹配的方法建立结点与弧段之间的关联关系同时也为弧段与多边形间关系的建立奠定了数据基础。2.2.1 点要素格网索引的建立 建立结点与弧段间关系之前除了要读入参加拓扑的结点要素(有实页91第第4期   徐 立等:地图矢量数据拓扑关系生成算法际意义的点状要素)还需加入弧段的首、末结点[7]。这里将结点分为两种类型:有实际地理意义的结点要素没有实际地理意义且属于某一弧段的结点。类似于线要素的自相交断链算法为了提高算法效率必须对结点要素建立网格索引此过程中只需判断结点是否落入特定的网格即可。另外每个网格区域必须往外扩张2D(D为结点匹配容差)大小的范围以防止相邻网格间出现结点漏匹配的情况。2.2.2 结点匹配 结点匹配主要有两个作用:一是将距离在阈值D范围内的结点合并为一个点当所有结点的精度等级相同时可将其平均位置设为新结点的位置否则将等级最高的结点的位置设为平均位置二是生成弧段与结点之间的拓扑关系。由于每个索引网格采用的算法都一样所以下述结点匹配算法主要是针对单个索引网格主要步骤如下:(1)对网格内所有的结点排序。首先在x方向上对结点排序然后在y方向上对结点排序则点位相近的结点排至一起这时只需对排序后的结点进行一次循环操作便可找出位置相同或相近的结点从而减少了比较次数。另外对x和y两个方向的结点进行排序可以避免结点间仅在某一方向距离很小而带来的干扰。(2)排序后结点的处理。1)从排序后的链表中取出第一个结点并设为当前结点。2)依次取出后面的结点与当前结点进行比较若后面结点不为空且两点间的距离小于等于匹配限差D则将两结点作为一组若两点间的距离大于匹配限差D则计算点组中的结点数结点数大于1则转入步骤3反之转入步骤5。3)找出点组中所有结点的关联弧段将其中的关联结点(首结点或末结点)设为新结点P(XY)并将这些弧段设为新结点的关联弧段。4)将点组中具有实际意义的结点坐标设为(XY)删除点组中没有实际意义的结点。5)取出下一个未比较的结点若该结点不为空则将该结点设为当前结点转入步骤2否则结点与弧段的拓扑关系初步建立完毕转入步骤6。6)依次遍历每个结点将伪结点删除。在地图矢量数据中若1个二链结点所关联的两条弧段属性完全相同那该结点为伪结点即所关联的两条弧段可以合并成一条弧段若1个二链结点所关联的两条弧段属性部分相同则该结点不是伪结点。例如有一个结点A在A处只连接沥青路L1和水泥路L2因L1和L2道路性质不同不能合并成一条道路结点A则不是伪结点。伪结点的处理主要分为3步:将两条关联弧段合并为一条弧段若结点有实际地理意义则将结点修改为一般地理点要素否则删除该结点删除原来的弧段。2.3 弧段与多边形间关系的建立弧段与多边形关系的建立也称为面域构建该过程是拓扑关系生成算法的最后阶段其主要作用是根据结点与弧段的关联关系、多边形与面域点的包含关系和多边形之间的包含关系生成简单多边形实体和复合多边形实体(如含有多个岛屿的湖泊)。算法主要分为多边形追踪和面域点与多边形关系的确定两个过程前者是根据结点与弧段间的关联关系构建多边形后者是在前者的基础上确定面域点与多边形的对应关系。2.3.1 多边形追踪 多边形追踪算法的基本思路是:首先以数据中任意一条弧段为初始弧段以初始弧段的首结点或末结点为初始结点找出初始结点的所有关联弧段然后以关联弧段中方向角最小的弧段为后续弧段并将后续弧段的另一端点作为后续结点再以上述方法进行循环追踪直至满足追踪条件则停止本次追踪。对于大多数图形而言每个多边形都可根据上述思想构建但必须考虑以下两种特殊情况(图5):若以图5a所示方向进行多边形`追踪在结点A处可能存在一条闭合弧段b(单独构成一个多边形)本次追踪可能在A点提前结束此时需要重新回到A点删除弧段b以弧段c为后续弧段继续向下追踪。以图5b所示方向进行多边形追踪在结点A处下一个弧段是c但是c以后的弧段都不能构成多边形如果继续向下追踪则会提前结束追踪。此时追踪的顺序为:先追踪到弧段d发现没有后续弧段则退回至结点B追踪到弧段e再次退回至结点B然后继续退回至结点A直至构成一个多边形。图5 多边形追踪特殊情况Fig.5 The exceptive instances of polygon tracking2.3.2 面域点与多边形对应关系的确定 面域点与多边形之间可能存在多对多的关系即一个面域点可能落入多个多边形内一个多边形可能包含多个面域点所以必须确定面域点实际与哪个多边形对应以保证面域点与多边形之间的一对一关系具体过程不再赘述。页02第地理与地理信息科学               第28卷3 实验分析本文以1∶25万济宁市地形图的交通层和居民地层为实验数据采用逐步增加拓扑要素的方法比较了传统拓扑关系生成算法和本文拓扑关系生成算法在执行效率上的差异结果如表1、表2所示。表1 交通层拓扑生成实验Table 1 Topological data generation for traffic layer实验编号总弧段个数传统算法耗时本文算法耗时1 200 85 632 386 112 863 945 613 4964 1 204 726 5865 1 766 1 237 1 0216 2 294 1 823 1 4617 2 999 2 320 1 9488 3 058 2 423 2 0399 3 723 3 459 2 94610 4 204 4 346 3 722注:时间单位是CPU时间片占用频数表2同。表2 居民地层拓扑生成实验Table 2 Topological data generation for habitation layer实验编号总面域个数传统算法耗时本文算法耗时1 209 39 322 258 57 543 419 195 1734 461 224 1945 516 275 2366 755 566 4877 824 658 5738 846 692 6059 910 784 69010 1 021 793 702  表1中交通层数据主要用来生成道路拓扑网算法的耗时与参加拓扑的弧段总数呈正相关因此实验主要对比两种算法建立结点与弧段间关系的效率。可以看出当弧段总数较小时两种算法的时间相差不大但随着弧段总数的增加两种算法的时间差越来越大说明在大数据量情况下本文算法能够明显减少拓扑关系生成的时间。表2中由于不需要对居民地数据进行线要素互相交断链处理算法的耗时与参加拓扑的面域总数呈正相关因此实验主要对比两种算法追踪多边形的效率。可以看出随着面域总数的增加两种算法的时间差不断增大但当面域总数增至一定数量时两者的时间差比较稳定但本文算法的效率一直优于传统算法。4 结论拓扑关系生成算法主要包括线要素互相交断链、结点匹配和多边形追踪等子算法。本文对以下方面进行了改进:1)利用要素编码控制表的形式筛选参加拓扑的要素并对每类要素设置精度等级使结点匹配时的点坐标拟合更科学2)根据属性信息对伪结点进行自动处理对结点和弧段建立网格索引提高了算法的运行效率3)对算法中出现的多种特殊情况进行了处理提高了算法的稳定性。参考文献:[1] 华一新吴升赵军喜.地理信息系统原理与技术[M].北京:解放军出版社2001.30.[2] 谢露蓉.地图图形数据拓扑关系的建立[J].测绘科学19993(2):36-41.[3] 赵国成.基于Microstation的扫描矢量化软件的研制[D].信息工程大学2004.53-54.[4] 陈春张树文徐佳芬.GIS中多边形图拓扑信息生成的数学基础[J].测绘学报19963(4):266-271.[5] 刘海砚.数字地图制图原理与技术[M].北京:解放军出版社2006.62.[6] 程双伟.GIS中拓扑关系的建立与更新[D].信息工程大学2002.16.[7] 李丽丽.基于拓扑关系的导航电子地图增量更新关键技术研究[D].吉林大学2009.30-31.Topological Algorithm for Map Vector DataXU Li 1SUN Qun1YANG Shuai 2XU Zhen3(1.Institute of Surveying and MappingInformation Engineering UniversityZhengzhou 4500522.School of Earth and Space SciencesPeking UniversityBeijing 1008713.66240TroopsBeijing 100042China)Abstract:The establishment of topological relationship is essential to map vector data management and updating.Based on theadvantages of multiple topological algorithm being integratedthe main process of topological was introduced detailedly.The to-pological algorithm was modified at the aspects of line feature intersectingnode matching and area building.Finallyan experi-ment was tried on the 1∶250 000scale topographical map data for Jining.It indicated that the efficiency of topological algorithmcould be improved compared to the traditional algorithm.Key words:topological elementtopological relationshipline feature intersectingnode matchingpolygon tracking页12第第4期   徐 立等:地图矢量数据拓扑关系生成算法

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/4

地图矢量数据拓扑关系生成算法

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利