利用双重索引快速构建道路网络连通拓扑.pdf

《利用双重索引快速构建道路网络连通拓扑.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第15卷第4期地球信息科学学报V01．15．NO．42013年8月JOURNALOFGEO一1NFORMATIONSCIENCEAug．，2013利用双重索引快速构建道路网络连通拓扑撤志恒，芮小平，宋现锋，刘真余，王静(中国科学院大学资源与环境学院，北京100049)摘要：路网拓扑关系的生成是进行最优路径规划的基础。本文针对ISOGDF4．0模型对道路连通拓扑的定义，结合最优路径规划对道路网络连通拓扑的要求，提出一种使用R．tree空间索引和B．tree索引双重索引方式快速生成道路连通拓扑的算法。连通拓扑快速构建算法包括新道路生成和网络拓扑

2、提取两部分，新道路生成过程中，首先，自上而下地打断道路形成直线段集并求交点，然后，自下而上地重构直线段集以生成新道路。在打断道路求交点过程中，对道路建立R—tree空间索引，显著提高了几何要素的查找速度。在网络拓扑提取过程中对序列化数据建立B．tree索引，使得其查找速度大大加快。通过对双重索引算法的时间复杂度分析与验证表明，本文提出的拓扑生成算法具有较高的执行效率。关键词：道路网；连通拓扑；双重索引；R—tree；B．tree；有效算法DoI：10．3724／SPJ．1047．20】3．004981引言素使用点和边表示，道路的交汇表示为零

3、维的点，道路抽象表示为一维的线，道路的长度、通行能力、最优路径规划是交通地理信息系统的研究热车道数等特性作为属性存储，这种道路表达模型是点，其核心是最短路径算法⋯，其实质是寻找道路网本文提出算法的基础。络中两点之间的“最短路径”(即以一种或多种指标国内外学者对道路的多边形拓扑构建算法研计量的耗费最小的路径)【2]。执行最优路径规划的究较多，主要研究拓扑的完备性。多边形作为完前提是道路网络已经建立正确的拓扑，因此，构建备拓扑结构中的基本单元，在空间查询、分析方面道路网络拓扑是实现最优路径算法的关键。有重要作用。但在进行路径规划时，主要使用道路

4、国际标准化组织(InternationalStandardization连通拓扑信息，即边与结点之间的拓扑关系，而不Organization，ISO)制定的导航地理数据概念模型是多边形拓扑提供的信息，故高效快速地构建道路国际标准草案(ISOGDF4．0)中，对道路网络拓扑关的连通拓扑即可满足大部分最优路径规划的需要。系给出了明确的定义]。GDF4．0根据不同的应用目前，对连通拓扑的研究集中在构建算法上，需求，定义了道路网基本表达单元(结点、边与面)何超英在构建导航数据库时主要采用连通拓扑，并之间3种不同的拓扑关系，即道路网完全拓扑、连通补充

5、部分完全拓扑，其他研究者在构建道路网络拓扑和非显式拓扑。完全拓扑使用面表示多边形拓扑时多采用类似连通拓扑的结构[5,9-131。这些研究要素，明确定义道路网中所有点线面基本表达单元多是从构建算法出发，并没有考虑算法的执行效率之间的拓扑关系；连通拓扑使用结点和边表示零维问题，也没有提出针对连通拓扑构建过程的加速技对象(结点)和一维对象(边)，明确定义结点和边的术。针对算法执行效率的改进问题，孙棣华提出三拓扑关系，不定义面和边之间的拓扑关系；非显式类典型的道路的相交模型，然后对实际的道路相交拓扑不定义基本表达单元之问的拓扑关系，空间要情况进行类

6、型划分，统计类别信息作为处理道路交素间的拓扑关系只能通过坐标值计算得到。根点的辅助信息，以此来提高处理速度1。使用有关据GDF4．0对连通拓扑的定义，道路网络中所有要交点类型的辅助信息可以简化求交点算法的复杂收稿日期：2013—01—21；修回日期：20130315．基金项目：国家科技支撑计划项目课题(2012BAC25B01)。作者简介：撖志恒(1988一)，男，河南平顶山人，硕士生，研究方向为地理信息科学应用。E—mail：ronald．han7@gmail．tom通讯作者：芮小平(1975一)，男，江苏苏州人，博士，副教授，研究方向为

7、地理信息科学理论与应用。E—mail：ruixp@yahoo．com．cn4期撖志恒等：利用双重索引快速构建道路网络连通拓扑499度，但计算道路网中交点与典型相交模型的相似性时间复杂度为O(1og(Ⅳ))。B．tree可以高效完成一又会增加时间开销。陆守一提出使用外包矩形判维空间查询，但并不适合线段或多边形这类二维或断道路相交的可能性，再对道路进行求交u。外包多维数据的查询，R—tree索引更适合多维数据的查矩形相交判断能降低求交点运算的次数，但并没有询，它是B—tree在高维空间的扩展，也是一种多叉平减少一条道路的外包矩形与其他道路外包矩

8、形的衡树，其查询效率为O(1og(Ⅳ))。比较次数。徐立对道路建立格网索引加速连通拓R—tree索引通过设计虚拟矩形目标，将空间目扑构建”。对道路建立空间索引加速相交判断是标包含