An Algorithm for Constructing Road Network Using Block Polygon Topology

CAI Xianhua; LIU Kaili; HU Zhuoliang; ZHANG Yuan

doi:10.13203/j.whugis20190348

Volume 46 Issue 8

Aug. 2021

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2021 > 46(8): 1170-1177. > DOI: 10.13203/j.whugis20190348

CAI Xianhua, LIU Kaili, HU Zhuoliang, ZHANG Yuan. An Algorithm for Constructing Road Network Using Block Polygon Topology[J]. Geomatics and Information Science of Wuhan University, 2021, 46(8): 1170-1177. DOI: 10.13203/j.whugis20190348

Citation:

PDF (5899 KB)

An Algorithm for Constructing Road Network Using Block Polygon Topology

1.
School of Transportation, Southeast University, Nanjing 211189, China

Funds:

The National Natural Science Foundation of China 41571375

The National Natural Science Foundation of China 51638004

More Information

Author Bio:
CAI Xianhua, PhD, professor, specializes in the geography information system for transportation application and development, spatial information visualization technology, computer aided cartography.E-mail: cai.x.h@seu.edu.cn
Received Date: December 26, 2019
Published Date: August 04, 2021

Graphical Abstract

Abstract

Abstract

Objectives Road network is the basis of various road traffic analysis and visualization. It is difficult to extract road centerlines automatically in analyzing the internal of complex polygonal road surface and difficult road surface segmentation.An algorithm of constructing road network is proposed to distinguish road sections and intersections, which can simplify data preprocessing based on the topological relationship among blocks.
Methods Firstly, through performing logical negation operation on road surface, complex polygons with holes are converted into independent and simple block polygons. Secondly, neighbor points among them are calculated, and neighboring blocks of each block can be obtained using the neighbor analysis. Consequently, the topological relationship among common road sections or common intersections is determined, and road sections and intersections are discriminated. Then, it is obtained that two common blocks on both sides of each section and all blocks which around each intersection, so the geometric positions of centerlines of road sections are calculated by means of applying the unit circle rolling tracking algorithm. Finally, according to the type of intersection, the positions of intersection associated with road sections are determined to complete the construction of the road network digital model.The algorithm is verified by developing experimental software which uses urban road surface data in a city topographic map with scale of 1∶1 000 as experimental data.
Results The experimental result shows that the topological relationship of the final road traffic network is accurate and the matching relationship among blocks is correct. The positions of road centerlines are accurate and every line shape is smooth. There are no excess centerlines or missing centerlines. The proposed method works well in dense and sparse neighborhoods. Compared with traditional algorithms, the algorithm for constructing road network by using street topology relationship doesn't need to perform manual segmentation or road surface edge line encryption. It simplifies complex graphics by negating the road surface and obtains road sections information according to topological relationship among polygons. The road centerlines are calculated by using unit circle rolling algorithm, so the geometric characteristic of the road centerlines and the accuracy of the topological relationship can be guaranteed. The experimental result shows that the method construct a road network with complete topology, accurate location and smooth shape.
Conclusions In the process of constructing the road section-block topology using the method, the road sections and intersections are distinguished. It solves the problems of segmentation of the road sections and provides a good basis for the extraction of road centerlines. It is suitable for the construction of geometric road networks in dense road networks and dense blocks.
- topological relationship,
- blocks,
- road network,
- road centerlines

FullText(HTML)

References (20)

References

[1]	朱庆, 李渊. 道路网络模型研究综述[J]. 武汉大学学报·信息科学版, 2007, 32(6): 471-476 http://ch.whu.edu.cn/article/id/1917 Zhu Qing, Li Yuan. Review of Road Network Models[J]. Geomatics and Information Science of Wuhan University, 2007, 32(6): 471-476 http://ch.whu.edu.cn/article/id/1917
[2]	李清泉, 杨必胜, 郑年波. 时空一体化GIS-T数据模型与应用方法[J]. 武汉大学学报·信息科学版, 2007, 32(11): 1 034-1 041 http://ch.whu.edu.cn/article/id/2040 Li Qingquan, Yang Bisheng, Zheng Nianbo. An Integrated Spatio Temporal Data Model for GIS-Transportation and Related Applications[J]. Geomatics and Information Science of Wuhan University, 2007, 32(11): 1 034-1 041 http://ch.whu.edu.cn/article/id/2040
[3]	曹炜威, 张红, 何晶, 等. 顾及结构和几何特征的道路自动选取方法[J]. 武汉大学学报·信息科学版, 2017, 42(4): 520-524 doi: 10.13203/j.whugis20140862 Cao Weiwei, Zhang Hong, He Jing, et al. Road Selection Considering Structural and Geometric Properties[J]. Geomatics and Information Science of Wuhan University, 2017, 42(4): 520-524 doi: 10.13203/j.whugis20140862
[4]	蔡先华, 王炜, 戚浩平. 基于GIS的道路几何网络数据模型及其应用[J]. 测绘通报, 2005(12): 24-27 doi: 10.3969/j.issn.0494-0911.2005.12.007 Cai Xianhua, Wang Wei, Qi Haoping. GIS-Based Road Geometric Net Data Model and Its Application[J]. Bulletin of Surveying and Mapping, 2005(12): 24-27 doi: 10.3969/j.issn.0494-0911.2005.12.007
[5]	Guo Bo. A Feature-Based Linear Data Model Supported by Temporal Dynamic Segmentation[D]. Kansa, USA: University of Kansa, 2001
[6]	Miller H J, Shaw S L. GIS-T Data Models, Geographic Information Systems for Transportation: Principles and Applications[M]. Oxford: Oxford University Press, 2001
[7]	王鹏, 郑贵省, 王元, 等. 以道路空间网络为中心的GIS-T数据模型研究[J]. 军事交通学院学报, 2017, 19(1): 86-90 https://www.cnki.com.cn/Article/CJFDTOTAL-JSTO201701020.htm Wang Peng, Zheng Guisheng, Wang Yuan, et al. Road Spatial Network-Centered GIS-T Data Model[J]. Journal of Military Transportation University, 2017, 19(1): 86-90 https://www.cnki.com.cn/Article/CJFDTOTAL-JSTO201701020.htm
[8]	王慧敏. 基于空间拓扑约束的街区自动综合研究与实现[D]. 武汉: 中国地质大学, 2012 Wang Huimin. Research and Implement of Automatic Block Generalization Based on Spatial Topology Constraints[D]. Wuhan: China University of Geosciences, 2012
[9]	吴华意, 刘波, 李大军, 等. 空间对象拓扑关系研究综述[J]. 武汉大学学报·信息科学版, 2014, 39(11): 1 269-1 276 http://ch.whu.edu.cn/article/id/3108 Wu Huayi, Liu Bo, Li Dajun, et al. Topologocal Relations of Spatial Objects: A Review[J]. Geomatics and Information Science of Wuhan University, 2014, 39(11): 1 269-1 276 http://ch.whu.edu.cn/article/id/3108
[10]	艾廷华, 郭仁忠. 基于约束Delaunay结构的街道中轴线提取及网络模型建立[J]. 测绘学报, 2000, 29(4): 348-354 doi: 10.3321/j.issn:1001-1595.2000.04.012 Ai Tinghua, Guo Renzhong. Extracting Center-lines and Building Street Network Based on Constrained Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2000, 29(4): 348-354 doi: 10.3321/j.issn:1001-1595.2000.04.012
[11]	Olson N. An Algorithm for Generating Road Center-Lines from Road Right-of-Way[C]. The 12th International Symposium on Computer-Assisted Cartography, Charlotte, USA, 1995
[12]	李功权, 蔡祥云. 一种基于约束三角网的道路中心线的提取方法[J]. 长江大学学报(自然科学版), 2013, 10(4): 47-50 https://www.cnki.com.cn/Article/CJFDTOTAL-CJDL201304014.htm Li Gongquan, Cai Xiangyun. A Method for Extracting Road Centerline Based on Constrained Triangulation[J]. Journal of Yangtze University(Natural Science Edition), 2013, 10(4): 47-50 https://www.cnki.com.cn/Article/CJFDTOTAL-CJDL201304014.htm
[13]	艾廷华, 郭仁忠. 支持地图综合的面状目标约束Delaunay三角网剖分[J]. 武汉测绘科技大学学报, 2000, 25(1): 35-41 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200001006.htm Ai Tinghua, Guo Renzhong. A Constrained Delaunay Partitioning of Areal Objects to Support Map Generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000, 25(1): 35-41 https://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200001006.htm
[14]	杨伟, 艾廷华. 运用Delaunay三角网提取OpenStreetMap主干道多边形[J]. 武汉大学学报·信息科学版, 2018, 43(11): 1 725-1 731 doi: 10.13203/j.whugis20160294 Yang Wei, Ai Tinghua. Extracting Arterial Road Polygon from OpenStreetMap Data Based on Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1 725-1 731 doi: 10.13203/j.whugis20160294
[15]	杨伟, 艾廷华. 基于众源轨迹数据的道路中心线提取[J]. 地理与地理信息科学, 2016, 32(3): 1-7 https://www.cnki.com.cn/Article/CJFDTOTAL-DLGT201603001.htm Yang Wei, Ai Tinghua. Road Centerline Extraction from Crowd Sourcing Trajectory Data[J]. Geography and Geo-Information Science, 2016, 32(3): 1-7 https://www.cnki.com.cn/Article/CJFDTOTAL-DLGT201603001.htm
[16]	朱庄生, 王庆, 万德钧. 基于道路轮廓的自动生成道路路心线算法[J]. 中国图象图形学报, 2003, 8(7): 792-797 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB200307014.htm Zhu Zhuangsheng, Wang Qing, Wan Dejun. A Study on Automatic Generation Road Center-Lines Algorithm Based on Road Contour[J]. Journal of Image and Graphics, 2003, 8(7): 792-797 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB200307014.htm
[17]	杨得志, 王杰臣, 闾国年. 一种自动生成曲线间中心线的算法[J]. 测绘通报, 2002(3): 58-60 https://www.cnki.com.cn/Article/CJFDTOTAL-CHTB200203023.htm Yang Dezhi, Wang Jiechen, Lü Guonian. An Algorithm of Central Line Automatically Creating[J]. Bulletin of Surveying and Mapping, 2002(3): 58-60 https://www.cnki.com.cn/Article/CJFDTOTAL-CHTB200203023.htm
[18]	Federico T. Generating Street Centerlines from Vector City Maps[J]. Cartography and Geographic Information Systems, 1998, 25(4): 221-230
[19]	王艳丽. 空间矢量数据的叠置算法研究[D]. 开封: 河南大学, 2010 Wang Yanli. Research on Overlay Algorithm of Spatial Vector Data[D]. Kaifeng: Henan University, 2010
[20]	谢忠, 叶梓, 吴亮. 简单要素模型下多边形叠置分析算法[J]. 地理与地理信息科学, 2007, 23(3): 19-23 https://www.cnki.com.cn/Article/CJFDTOTAL-DLGT200703004.htm Xie Zhong, Ye Zi, Wu Liang. Polygon Overlay Analysis Using the Simple Data Model[J]. Geography and Geo-Information Science, 2007, 23(3): 19-23 https://www.cnki.com.cn/Article/CJFDTOTAL-DLGT200703004.htm

[1]	Guo Fei, Li Xingyu, Yang Yan, Zhang Xiaohong. Modeling and Performance Evaluation of Galileo High Accuracy Service[J]. Geomatics and Information Science of Wuhan University. DOI: 10.13203/j.whugis20240255
[2]	DENG Ken, ZHOU Peiyuan, DU Lan, CAI Wei. GNSS-R Altimetry Method with Multi-system Single-Frequency Tight Integration[J]. Geomatics and Information Science of Wuhan University, 2024, 49(1): 146-155. DOI: 10.13203/j.whugis20220785
[3]	MI Xiaolong, YUAN Yunbin, ZHANG Baocheng. RTK Positioning Performance Analysis for Combined BDS-3 and Galileo[J]. Geomatics and Information Science of Wuhan University, 2023, 48(1): 113-118. DOI: 10.13203/j.whugis20200483
[4]	WEI Erhu, LIU Xuexi, WANG Lingxuan, LIU Jingnan. Analysis and Assessment of BDS/GPS Combined Precise Point Positioning Accuracy[J]. Geomatics and Information Science of Wuhan University, 2018, 43(11): 1654-1660. DOI: 10.13203/j.whugis20160568
[5]	ZENG Anmin, YANG Yuanxi, JING Yifan, MING Feng. Systematic Bias Compensation Model of Inter-system Bias and Its Performance Analysis for BDS/GPS Fusion Positioning[J]. Geomatics and Information Science of Wuhan University, 2017, 42(10): 1423-1430. DOI: 10.13203/j.whugis20150808
[6]	ZHANG Qiuzhao, ZHANG Shubi, LIU Zhiping, ZHENG Nanshan. Tightly-coupled GPS/SINS Integrated System Measurement Model Based on Double-difference Pseudo-range/Pseudo-range Rate[J]. Geomatics and Information Science of Wuhan University, 2015, 40(12): 1690-1694,1700. DOI: 10.13203/j.whugis20130349
[7]	YU Xingwang, ZHANG Xiaohong, NIE Guigen. GPS/GALILEO Multi-frequency Combined Differential Positioning[J]. Geomatics and Information Science of Wuhan University, 2010, 35(7): 821-824.
[8]	WANGZemin, MENGYang, WUYue, LIANGShujun. DOP for GPS,Galileo and Combination Navigation System[J]. Geomatics and Information Science of Wuhan University, 2006, 31(1): 9-11.
[9]	HE Xiufeng, XU Yong, SANG Wengang. MEMS IMU and GPS Integration for Positioning and Direction Finding System[J]. Geomatics and Information Science of Wuhan University, 2005, 30(11): 991-994.
[10]	WANG Zemin, LIU Jingbin. Model of Inter-Frequency Combinations of Galileo GNSS[J]. Geomatics and Information Science of Wuhan University, 2003, 28(6): 723-727.

Cited By

Cited by

Periodical cited type(46)

1.	黄志标，谢斌，赵辉煌. BDS-3/GPS/Galileo双频兼容频率中长基线单历元性能分析. 测绘与空间地理信息. 2025(03): 80-82+86 .
2.	王凯. Galileo双频与三频短基线RTK单历元精度分析. 测绘与空间地理信息. 2025(03): 107-110 .
3.	冯宇航，吕洋，马随阳. QZSS处理策略对BDS-3/GPS/QZSS重叠频率组合短基线影响分析. 测绘与空间地理信息. 2025(03): 147-149 .
4.	孙希艳. BDS-3/GPS/Galileo超长基线解算性能评估. 测绘与空间地理信息. 2024(01): 113-116 .
5.	祝会忠，刘智强. GPS/BDS-3/Galileo/QZSS重叠频率长距离RTK松紧组合定位性能分析. 测绘科学. 2024(02): 1-16 .
6.	柴鑫. BDS-3/GPS/Galileo兼容频率紧组合短基线性能分析. 测绘与空间地理信息. 2024(S1): 249-251 .
7.	Yu Han，Fangjun Qin，Xugang Lian，Shengliang Wang，Leiyuan Qian，Wenhua Huang. Performance analysis of the tight combination of GPS, BDS, GALILEO, and QZSS mixed frequencies signals. Geodesy and Geodynamics. 2024(04): 366-378 .
8.	李兆哲. 四系统组合的RTK定位对不同长度基线性能的评估研究. 测绘标准化. 2024(03): 65-70 .
9.	祝会忠，白云鹏. 北斗三号高精度载波相位差分定位算法. 辽宁工程技术大学学报(自然科学版). 2024(05): 593-599 .
10.	糜晓龙，袁运斌，张宝成. BDS-3和Galileo组合的RTK定位性能分析. 武汉大学学报(信息科学版). 2023(01): 113-118 .
11.	陈昇，钟志强. BDS-3/Galileo重叠频率短基线紧组合相对定位性能初步评估. 测绘与空间地理信息. 2023(02): 139-141 .
12.	贾亚军，都林婷，郐长明，阚中强. BDS-3单频短基线相对定位性能初步评估. 地理空间信息. 2023(02): 46-49 .
13.	祝会忠，李壮，雷啸挺. BDS-2/BDS-3非组合观测模型的中距离相对定位. 导航定位学报. 2023(02): 49-60+79 .
14.	祝会忠，张杰，李军，路阳阳. BDS-3/BDS-2/GPS长距离非差RTK定位性能研究. 测绘科学. 2023(04): 10-21+53 .
15.	胡芳芳. 中国及周边区域BDS-3不同星座与Galileo组合SPP、PPP、RTK性能分析. 测绘与空间地理信息. 2023(08): 154-156 .
16.	王楚扬，陈尚登，杨振林，秘金钟，徐彦田，窦世标. BDS-3/GPS/Galileo紧组合动态差分定位算法研究. 测绘科学. 2023(07): 16-24 .
17.	朱绍涛，孙建霞. BDS-3完整星座多频标准单点定位精度分析. 地理空间信息. 2022(03): 84-87+96 .
18.	陈永健. BDS-3新卫星对BDS-2短基线相对定位精度的影响分析. 测绘地理信息. 2022(02): 6-10 .
19.	文碧龙. 北斗三号正式卫星对标准单点定位的影响分析. 现代测绘. 2022(01): 33-37 .
20.	董方云，陈端云，滕玲，林彧茜，李健，王智慧，丁慧霞. 面向电力应用的低成本导航模块GNSS定位性能评估. 电力信息与通信技术. 2022(04): 63-69 .
21.	侯跃强. 亚太地区BDS-2/BDS-3双频SPP精度评估. 测绘与空间地理信息. 2022(06): 164-166+169 .
22.	刘路，郭金运，周茂盛，鄢建国，纪兵，赵春梅. GNSS广播星历轨道和钟差精度分析. 武汉大学学报(信息科学版). 2022(07): 1122-1132 .
23.	田正华，徐欢，柳新强. 高度角对BDS-3与多系统兼容短基线解算精度影响分析. 地理信息世界. 2022(03): 77-81 .
24.	罗翠翠，王光盈，叶长斌，景国峰，刘刚. QZSS与GPS重叠频率紧组合相对定位精度分析. 测绘地理信息. 2022(04): 13-18 .
25.	柳明. B1C/G-L1/E1两两紧组合相对定位. 测绘与空间地理信息. 2022(08): 130-132+136+139 .
26.	田晓龙. GPS/BDS紧组合模型在超高层变形监测中的应用分析. 测绘与空间地理信息. 2022(08): 234-236+244 .
27.	孙永航. BDS-3双频伪距单点定位精度分析. 测绘与空间地理信息. 2022(12): 191-194 .
28.	吴有龙，杨忠，陈维娜，姚文进，陈闯. 北斗单系统及多全球导航卫星系统组合极区定位性能. 科学技术与工程. 2021(01): 32-39 .
29.	吴有龙，杨忠，陈维娜，姚文进，陈闯，陈帅. 北斗单系统及多GNSS系统组合全球卫星可用性分析. 弹箭与制导学报. 2021(01): 18-23 .
30.	彭劲松. BDS-3新频率与Galileo单频组合伪距单点定位精度分析. 全球定位系统. 2021(01): 57-61 .
31.	刘生锋，杨文龙，谷涛. BDS-3双频组合精密单点定位精度分析. 测绘通报. 2021(03): 7-11+17 .
32.	耿智江. 融合GPS/Galileo/QZSS重叠频率单频短基线解算精度分析. 测绘技术装备. 2021(01): 12-17 .
33.	樊涛. GPS/QZSS重叠频率短基线解算精度分析. 矿山测量. 2021(02): 58-62 .
34.	赵文浩，刘根友，王生亮，高铭. GPS-L1/BDS-B1非重叠频率紧组合相对定位. 大地测量与地球动力学. 2021(06): 618-622+645 .
35.	崔浩猛，王解先，王明华，王虎，朱卫东，侯阳飞. 利用卫星分布概率对BDS-3性能的评估. 武汉大学学报(信息科学版). 2021(06): 938-946 .
36.	王强昆，谢卫杰，王耀鑫. BDS-2/BDS-3伪距单点定位精度分析. 测绘与空间地理信息. 2021(10): 156-159 .
37.	罗杰. 不同截止高度角下BDS-2/BDS-3短基线RTK定位性能分析. 地理空间信息. 2021(11): 44-47+7 .
38.	王鸣. GPS/BDS/GLONASS/Galileo组合相对定位精度分析. 城市勘测. 2020(04): 97-100 .
39.	张澄. BDS-3/GPS/Galileo/QASS兼容频率伪距单点定位精度分析. 地理信息世界. 2020(04): 135-138 .
40.	翟文. 基于GPS/BDS紧组合RTK的桥梁变形监测分析. 城市勘测. 2020(05): 116-119 .
41.	汤门生，袁伟，徐儒林. GPS/Galileo/QZSS中长基线解算精度分析. 经纬天地. 2020(05): 29-32+40 .
42.	张云龙. 严寒地区铁路运营期路基BDS远程变形监测. 铁道勘察. 2020(06): 7-11 .
43.	彭劲松. BDS-3多系统多频组合伪距单点定位精度分析. 地球物理学进展. 2020(06): 2090-2095 .
44.	陈振虎. GPS/Galileo/QZSS双频短基线相对定位精度分析. 经纬天地. 2020(06): 13-17 .
45.	柳浩天，刘承禹，赵娟，吴皓，程熙. Galileo双频/三频SPP定位精度分析. 全球定位系统. 2020(06): 69-73 .
46.	赵立都，向中富，周银，张双成，马下平，胡川，陈茂霖. 北斗三号中长基线定位性能分析. 测绘科学技术学报. 2020(06): 556-561 .

Other cited types(19)

Get Citation

PDF

XML

Article views (1484) PDF downloads (138) Cited by(65)

An Algorithm for Constructing Road Network Using Block Polygon Topology

Abstract

References

Related Articles

Cited by

Periodical cited type(46)

Other cited types(19)

Catalog

Related

An Algorithm for Constructing Road Network Using Block Polygon Topology

Abstract

References

Related Articles

Cited by

Periodical cited type(46)

Other cited types(19)

Catalog

Related

Export File

Citation

Format

Content