-
摘要: 为解决现有地理信息系统无法完成城市轨道交通三维缓冲区构建的难题, 采用八叉树作为构建三维缓冲区的基础数据结构, 用线性八叉树编码储存轨道交通实体的空间结构信息, 将交通三维缓冲区分析转化为八叉树节点的空间分析。研究了八叉树节点的空间关系, 得出了一种线性八叉树邻域分析的新算法, 即0-1互换算法。运用0-1互换算法找出轨道交通的边界节点, 确定边界节点的边界方向, 由边界节点构建交通三维缓冲区, 形成了一套由线性八叉树构建城市轨道交通三维缓冲区的新方法。运用0-1互换算法对直线隧道、曲线隧道、直线高架桥、曲线高架桥等轨道交通实体模型进行边界节点提取, 并与传统算法和经典肖氏算法进行了比较。选择连拱隧道、单拱隧道和高架桥3种结构, 分别进行了三维缓冲区构建, 统计了3种结构分割的八叉树节点数量, 并与采用传统栅格结构进行三维缓冲区分析的栅格节点数量进行对比。分析结果表明: 与传统算法和经典肖氏算法相比, 0-1互换算法在对直线隧道、曲线隧道、直线高架桥、曲线高架桥4种轨道交通实体模型的边界节点提取中耗时最少, 分别为5、7、10、18ms, 将算法的时间复杂度由二次阶减少为一次阶; 基于线性八叉树的交通三维缓冲区构建方法, 对连拱隧道、单拱隧道与高架桥进行三维缓冲区构建时, 其存储空间分别为栅格结构的7.26%、3.64%、3.72%。可见, 基于线性八叉树结构的交通三维缓冲区构建方法能显著降低分析节点数量, 提高交通三维缓冲区的构建效率。Abstract: In order to solve the problem that the existing GIS buffer algorithm can not create the3 Dbuffer zone of urban rail transit, octree was adopted as a fundamental data structure for creating the 3Dbuffer zone.The 3Dsolid information of urban rail transit was stored by using linear octree encoding, and the analysis of 3Dbuffer zone was transferred into the spatial analysis of octree nodes.The topology of octree nodes was analyzed, and a new algorithm, i.e.0-1 swapalgorithm, was proposed for linear octree neighborhood analysis.The boundary nodes of rail transit were identified by using the 0-1 swap algorithm, and the directions of boundary nodes were determined.The 3Dbuffer zone of rail transit was created by using boundary nodes.A new3 Dbuffer zone creation method of urban rail transit was formed based on linear octree.The boundary nodes of straight tunnel, curved tunnel, straight viaduct and curved viaduct were created by using the 0-1swap algorithm, and the result was compared with that of conventional algorithm and classical Xiao' s algorithm.The 3Dbuffer zones of double-arch tunnel, single-arch tunnel and viaduct were created by using the proposed method, and the number of octree nodes extracted from the different structures was counted and compared with the number of raster nodes of traditional structure.Analysis result indicates that compared with the conventional algorithm and the classical Xiao' s algorithm, the elapsed times of boundary nodes creation for straight tunnel, curved tunnel, straight viaduct and curved viaduct are minimum by using the 0-1swap algorithm, and the values are 5, 7, 10, 18 ms respectively.The time complexity reduces from second order to first order by using the 0-1swap algorithm.For the 3Dbuffer creation method based on linear octree, the memory spaces of octree data structures are 7.26%, 3.64% and 3.72% of the spaces of raster structures when the 3Dbuffer zones of twin-arch tunnel, singelarch tunnel and viaduct are created.Therefore, the 3D buffer zone creation method greatly reduces the number of analysis nodes, and improves the efficiency of creating the 3Dbuffer zone.
-
图 9 连拱隧道三维缓冲区生成过程
Figure 9. Generation process of 3D buffer zone for double-arch tunnel
表 1 提取时间比较
Table 1. Comparison of extraction times
表 2 节点数量比较
Table 2. Comparison of node numbers
-
[1] 左小清. 面向交通网络的三维GIS数据模型与可视化[D]. 武汉: 武汉大学, 2004.ZUO Xiao-qing. 3D GIS data model and visualization in transportation network[D]. Wuhan: Wuhan University, 2004. (in Chinese). [2] 涂圣文, 苏州. 基于GIS和遗传粒子群的公路智能选线方法[J]. 长安大学学报: 自然科学版, 2010, 30(4): 39-45. doi: 10.3969/j.issn.1671-8879.2010.04.008TU Sheng-wen, SU Zhou. Intelligent route selection of highway alignments based on GIS and hybrid genetic algorithm and particle swarm optimization[J]. Journal of Chang' an University: Natural Science Editon, 2010, 30(4): 39-45. (in Chinese). doi: 10.3969/j.issn.1671-8879.2010.04.008 [3] RIENZO F D, ORESTE P, PELIZZA S. 3DGIS supporting underground urbanisation in the city of Turin(Italy)[J]. Geotechnical and Geological Engineering, 2009, 27(4): 539-547. doi: 10.1007/s10706-009-9255-2 [4] SCIANNA A. Building 3DGIS data models using open source software[J]. Applied Geomatics, 2013, 5(2): 119-132. doi: 10.1007/s12518-013-0099-3 [5] 毋河海. 关于GIS缓冲区的建立问题[J]. 武汉测绘科技大学学报, 1997, 22(4): 358-366. doi: 10.3321/j.issn:1671-8860.1997.04.013WU He-hai. Problem of buffer zone construction in GIS[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1997, 22(4): 358-366. (in Chinese). doi: 10.3321/j.issn:1671-8860.1997.04.013 [6] 彭认灿, 陈轶, 刘国辉, 等. MapInfo系统线(面)目标缓冲区构建模型存在的问题及其改进方法[J]. 武汉大学学报: 信息科学版, 2007, 32(8): 719-722. https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200708017.htmPENG Ren-can, CHEN Yi, LIU Guo-hui, et al. Problem and improving method for MapInfo line(area)buffer construction model[J]. Geomatics and Information Science of Wuhan University, 2007, 32(8): 719-722. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200708017.htm [7] BHATIA S, VIRA V, CHOKSI D, et al. An algorithm for generating geometric buffers for vector feature layers[J]. Geo-spatial Information Science, 2013, 16(2): 130-138. doi: 10.1080/10095020.2012.747643 [8] GOMBOŠI M, ŽALIK B. Point-in-polygon tests for geometric buffers[J]. Computers and Geosciences, 2005, 31(10): 1201-1212. doi: 10.1016/j.cageo.2005.03.009 [9] 李科, 杜琳. 基于膨胀算法的缓冲区分析的设计与实现[J]. 测绘学院学报, 2005, 22(3): 229-231. doi: 10.3969/j.issn.1673-6338.2005.03.023LI Ke, DU Lin. An algorithm of buffer zones based on algorithm of dialation[J]. Journal of Institute of Surveying and Mapping, 2005, 22(3): 229-231. (in Chinese). doi: 10.3969/j.issn.1673-6338.2005.03.023 [10] 王结臣, 沈定涛, 陈焱明. 基于栅格距离法的缓冲区生成与实现[J]. 科技通报, 2009, 25(5): 556-561. https://www.cnki.com.cn/Article/CJFDTOTAL-KJTB200905005.htmWANG Jie-chen, SHEN Ding-tao, CHEN Yan-ming. Algorithm of raster-based distance computing on buffer generation and its implementation[J]. Bulletin of Science and Technology, 2009, 25(5): 556-561. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-KJTB200905005.htm [11] 卢新明, 王红娟. 基于高效布尔运算的三维矢量缓冲区算法[J]. 中国矿业大学学报, 2012, 41(3): 481-487. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGKD201203024.htmLU Xin-ming, WANG Hong-juan. An algorithm for 3Dvector buffer based on efficient Boolean operation[J]. Journal of China University of Mining and Technology, 2012, 41(3): 481-487. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGKD201203024.htm [12] 范俊甫, 马廷, 周成虎, 等. 几何部件缓冲区域合并的Buffer算法及其并行优化方法[J]. 测绘学报, 2014, 43(9): 969-975. https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201409015.htmFAN Jun-fu, MA Ting, ZHOU Cheng-hu, et al. Research on a buffer algorithm based on region-merging of buffered geometry components and its parallel optimization[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(9): 969-975. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB201409015.htm [13] 李芳玉, 潘懋, 朱雷. 三维缓冲体生成栅格算法研究[J]. 计算机辅助设计与图形学学报, 2005, 17(9): 1928-1932. doi: 10.3321/j.issn:1003-9775.2005.09.006LI Fang-yu, PAN Mao, ZHU Lei. Research on the algorithm for3Draster buffer-generation[J]. Journal of Computer-Aided Design and Computer Graphics, 2005, 17(9): 1928-1932. (in Chinese). doi: 10.3321/j.issn:1003-9775.2005.09.006 [14] 李芳玉. 基于栅格的三维GIS缓冲体分析研究[J]. 计算机工程, 2007, 33(21): 6-8. doi: 10.3969/j.issn.1000-3428.2007.21.003LI Fang-yu. Research on raster-based buffer analysis in 3D GIS[J]. Computer Engineering, 2007, 33(21): 6-8. (in Chinese). doi: 10.3969/j.issn.1000-3428.2007.21.003 [15] 邱华. 三维体数据生成及三维缓冲区分析[D]. 长沙: 中南大学, 2011.QIU Hua. Three-dimensional volume data generation and three-dimensional buffer analysis[D]. Changsha: Central South University, 2011. (in Chinese). [16] 王结臣, 沈定涛, 崔璨. 缓冲区生成的游程刷叠置算法[J]. 武汉大学学报: 信息科学版, 2010, 35(9): 1121-1124. https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201009032.htmWANG Jie-chen, SHEN Ding-tao, CUI Can. RLE-B algorithm for buffer generation[J]. Geomatics and Information Science of Wuhan University, 2010, 35(9): 1121-1124. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH201009032.htm [17] JUAN-ARINYO R, SOLÉJ. Constructing face octrees from voxel-based volume representations[J]. Computer-Aided Design, 1995, 27(10): 783-791. doi: 10.1016/0010-4485(94)00032-9 [18] SHI Wen-zhong. Development of a hybrid model for threedimensional GIS[J]. Geo-spatial Information Science, 2000, 3(2): 6-12. doi: 10.1007/BF02826617 [19] YODER R, BLONIARZ P. A practical algorithm for computing neighbors in quadtrees, octrees, and hyperoctrees[C]∥IEEE. Proceedings of the 2006International Conference on Modeling, Simulation, and Visualization Methods. New York: IEEE, 2006: 249-255. [20] 黄淼, 张海朝, 李超. 基于八叉树空间分割的k近邻搜索算法[J]. 计算机应用, 2008, 28(8): 2046-2048, 2051. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY200808043.htmHUANG Miao, ZHANG Hai-chao, LI Chao. Algorithm for finding k-nearest neighbors based on octree segmentation in space[J]. Computer Applications, 2008, 28(8): 2046-2048, 2051. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY200808043.htm [21] HORNUNG A, WURM K M, BENNEWITZ M, et al. OctoMap: an efficient probabilistic 3D mapping framework based on octrees[J]. Autonomous Robots, 2013, 34(3): 189-206. doi: 10.1007/s10514-012-9321-0 [22] MURMAN S M. Compact upwind schemes on adaptive octrees[J]. Journal of Computational Physics, 2010, 229(4): 1167-1180. [23] SAMET H. Neighbor finding in images represented by octrees[J]. Computer Vision, Graphics, and Image Processing, 1989, 46(3): 367-386. [24] SCHRACK G. Finding neighbors of equal size in linear quadtrees and octrees in constant time[J]. CVGIP: Image Understanding, 1992, 55(3): 221-230. [25] 肖乐斌, 龚建华, 谢传节. 线性四叉树和线性八叉树邻域寻找的一种新算法[J]. 测绘学报, 1998, 27(3): 195-203. https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB803.001.htmXIAO Le-bin, GONG Jian-hua, XIE Chuan-jie. A new algorithm for searching neighbors in the linear quadtree and octree[J]. Acta Geodaetica et Cartographica Sinica, 1998, 27(3): 195-203. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-CHXB803.001.htm -
下载:
点击查看大图
图(11) / 表(2)
计量
- 文章访问数: 836
- HTML全文浏览量: 216
- PDF下载量: 944
- 被引次数: 0
