CAJ | 학술논문

　　路网拓扑关系的生成是进行最优路径规划的基础。本文针对ISO GDF4.0模型对道路连通拓扑的定义，结合最优路径规划对道路网络连通拓扑的要求，提出一种使用R-tree空间索引和B-tree索引双重索引方式快速生成道路连通拓扑的算法。连通拓扑快速构建算法包括新道路生成和网络拓扑提取两部分，新道路生成过程中，首先，自上而下地打断道路形成直线段集并求交点，然后，自下而上地重构直线段集以生成新道路。在打断道路求交点过程中，对道路建立R-tree空间索引，显著提高了几何要素的查找速度。在网络拓扑提取过程中对序列化数据建立B-tree索引，使得其查找速度大大加快。通过对双重索引算法的时间复杂度分析与验证表明，本文提出的拓扑生成算法具有较高的执行效率。
　　로망탁복관계적생성시진행최우로경규화적기출。본문침대ISO GDF4.0모형대도로련통탁복적정의，결합최우로경규화대도로망락련통탁복적요구，제출일충사용R-tree공간색인화B-tree색인쌍중색인방식쾌속생성도로련통탁복적산법。련통탁복쾌속구건산법포괄신도로생성화망락탁복제취량부분，신도로생성과정중，수선，자상이하지타단도로형성직선단집병구교점，연후，자하이상지중구직선단집이생성신도로。재타단도로구교점과정중，대도로건립R-tree공간색인，현저제고료궤하요소적사조속도。재망락탁복제취과정중대서렬화수거건립B-tree색인，사득기사조속도대대가쾌。통과대쌍중색인산법적시간복잡도분석여험증표명，본문제출적탁복생성산법구유교고적집행효솔。
A road network with topology is the basis for optimal path finding. According to the definition of con-nectivity topology by ISOGDF4.0 (Geographic Data File) model and the requirements of road network connec-tivity topology during the optimal path finding procedure, this paper presents an efficient algorithm to construct connectivity topology for road network using R-tree and B-tree indexes. The efficient algorithm contains two parts:the first part breaks the roads at intersections and generates anew road network;the second part constructs connectivity topology based on the new network. The procedure of building new road network breaks the roads into line segments and gets intersections at first, then reconstructs new roads with the line segments set and the intersections. During the procedure of getting intersections of any two line segments, the algorithm builds R-tree spatial index on the line segments to improve query operation efficiency significantly. What’s more, our algo-rithm also builds B-tree index on serialized data of the roads such as the identity codes while constructing con-nectivity topology to improve the query operation efficiency on serialized data. This paper also tests the time complexity of the algorithm using road networks with different scales. Experiment results show that our algo-rithm builds connectivity topology of large-scale road network in very short time. (For a road network that con-tains about 30 thousands line segments and 25 thousands points, the quick algorithm completes connectivity to-pology construction in no more than 3 seconds). The time cost of our algorithm increases slightly while the tradi-tional algorithm increases tremendously, to be exact, our algorithm’s time cost grows at the rate of O(v log(v)) while the traditional one grows with the speed of O(v2) , so we concluded that the quick algorithm has high effi-ciency and is valuable to practicable application.