留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用街区面块拓扑构建道路网络的算法

蔡先华 刘凯丽 胡卓良 张远

蔡先华, 刘凯丽, 胡卓良, 张远. 利用街区面块拓扑构建道路网络的算法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1170-1177. doi: 10.13203/j.whugis20190348
引用本文: 蔡先华, 刘凯丽, 胡卓良, 张远. 利用街区面块拓扑构建道路网络的算法[J]. 武汉大学学报 ● 信息科学版, 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: 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

利用街区面块拓扑构建道路网络的算法

doi: 10.13203/j.whugis20190348
基金项目: 

国家自然科学基金 41571375

国家自然科学基金 51638004

详细信息
    作者简介:

    蔡先华,博士,教授,主要从事交通地理信息系统(GIS-T)应用与开发、空间信息可视化技术、计算机地图制图等。cai.x.h@seu.edu.cn

  • 中图分类号: P208

An Algorithm for Constructing Road Network Using Block Polygon Topology

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

  • 摘要: 道路交通网络是进行各种道路交通网络分析与可视化的基础。构建道路网络的常用方法是运用已有道路面矢量数据提取道路中心线,并自动生成道路网络。提出了一种根据街区面块拓扑关系自动构建道路网络的算法,首先,根据道路面求反得到街区面块并计算街区面块间的拓扑关系;然后,根据街区面块之间的拓扑关系自动建立道路网络拓扑关系;最后,计算路段(网络弧段)中心线和道路交叉口(节点)的几何位置,完成数字道路网络的构建。与以住算法不同,该算法将拓扑关系构建与中心线提取分开,直接由道路面原始数据构建网络拓扑关系,保证拓扑结构的准确性,且为道路中心线提取提供路段交叉口判别依据。实验表明,所提出算法较好地解决了已有算法在自动计算道路中心线时数据预处理复杂和道路面分割难以处理等问题。
  • 图  1  街区面块示意图

    Figure  1.  Illustration of Blocks

    图  2  路网构建流程图

    Figure  2.  Flowchart of Road Network Construction

    图  3  街区面块数据获取步骤

    Figure  3.  Procedure of Obtaining Blocks

    图  4  近邻关系判断

    Figure  4.  Judgment of Neighborhood Relations

    图  5  近邻街区面块排序表生成

    Figure  5.  Generation of Sequence List of Neighboring Blocks

    图  6  近邻街区面块标记

    Figure  6.  Marking of Neighboring Blocks

    图  7  路网拓扑关系构建

    Figure  7.  Generating Network Topological Relations

    图  8  道路中心线提取

    Figure  8.  Road Centerlines Extraction

    图  9  交叉口处的修整

    Figure  9.  Trim at Intersections

    图  10  道路面实验数据(局部)

    Figure  10.  Experimental Data of Road Surfaces (Part)

    图  11  道路中心线临时成果

    Figure  11.  Interim Result of Road Centerlines

    图  12  道路中心线与街区面块相交

    Figure  12.  Intersection of Road Centerlines and Blocks

    图  13  道路网络构建结果

    Figure  13.  Results of Road Network Construction

    表  1  面块b0的近邻街区标记顺序

    Table  1.   Marking List of Neighboring Blocks of b0

    序号 近邻街区面块 标记
    0 b1 0
    1 b2 1
    2 b3 0
    3 b4 0
    4 b5 0
    下载: 导出CSV

    表  2  算法相关指标对比

    Table  2.   Comparison of Algorithm-Related Indicators

    算法 手动路段分割 道路边线加密 道路面求反 几何特征 拓扑关系
    本文算法 准确
    垂线族法 会出现尖锐拉动 可能歪曲连通关系
    基于约束三角形法 会出现多余分枝 准确
    矢量追踪法 准确
    下载: 导出CSV
  • [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] 王荣, 闫浩文, 禄小敏.  多尺度等高线簇拓扑关系定量表达方法研究 . 武汉大学学报 ● 信息科学版, 2022, 47(4): 579-588. doi: 10.13203/j.whugis20210355
    [2] 卢宾宾, 杨欢, 孙华波, 于清德.  利用Minkowski距离逼近道路网络距离算法研究 . 武汉大学学报 ● 信息科学版, 2017, 42(10): 1373-1380. doi: 10.13203/j.whugis20160225
    [3] 王珂, 张周威.  矢栅一体化拓扑关系的度量描述研究 . 武汉大学学报 ● 信息科学版, 2015, 40(5): 638-643. doi: 10.13203/j.whugis20130357
    [4] 郭继发, 刘玉洁, 毛健, 崔铁军.  高阶模糊区域的交叉拓扑关系形式化研究 . 武汉大学学报 ● 信息科学版, 2014, 39(2): 196-200. doi: 10.13203/j.whugis20120691
    [5] 吴华意, 刘波, 李大军, 凌南燕.  空间对象拓扑关系研究综述 . 武汉大学学报 ● 信息科学版, 2014, 39(11): 1269-1276.
    [6] 黄翌, 汪云甲, 胡召玲, 李陈.  考虑图形关系的中心服务范围确定 . 武汉大学学报 ● 信息科学版, 2013, 38(1): 105-108.
    [7] 沈敬伟, 闾国年, 温永宁, 吴明光.  拓扑和方向空间关系组合描述及其相互约束 . 武汉大学学报 ● 信息科学版, 2011, 36(11): 1305-1308.
    [8] 刘新, 刘文宝, 李成名.  三维体目标间拓扑关系与方向关系的混合推理 . 武汉大学学报 ● 信息科学版, 2010, 35(1): 74-78.
    [9] 杜世宏, 郭泺.  基于拓扑关系的不确定区域方向关系推理 . 武汉大学学报 ● 信息科学版, 2010, 35(4): 388-393.
    [10] 刘波, 李大军, 阮见, 夏元平.  带空洞面对象间拓扑关系形式化描述 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 68-71.
    [11] 郭庆胜, 吕秀琴, 蔡永香.  图形简化过程中空间拓扑关系抽象的规律 . 武汉大学学报 ● 信息科学版, 2008, 33(5): 520-523.
    [12] 肖晖, 杨必胜.  一种改进的基于道路网络距离的K近邻查询算法 . 武汉大学学报 ● 信息科学版, 2008, 33(4): 437-439.
    [13] 郭庆胜, 刘小利, 陈宇箭.  线与线之间的空间拓扑关系组合推理 . 武汉大学学报 ● 信息科学版, 2006, 31(1): 39-42.
    [14] 邓敏, 李志林, 李永礼, 张雪松.  GIS线目标间拓扑关系描述的4交差模型 . 武汉大学学报 ● 信息科学版, 2006, 31(11): 945-948.
    [15] 翁敏, 毋河海, 杜清运, 李林燕.  基于道路网络知识的启发式层次路径寻找算法 . 武汉大学学报 ● 信息科学版, 2006, 31(4): 360-363.
    [16] 郭庆胜, 陈宇箭, 刘浩.  线与面的空间拓扑关系组合推理 . 武汉大学学报 ● 信息科学版, 2005, 30(6): 529-532.
    [17] 郭庆胜, 丁虹, 刘浩, 刘小利.  面状目标之间空间拓扑关系的组合式分类 . 武汉大学学报 ● 信息科学版, 2005, 30(8): 728-731.
    [18] 邓敏, 张雪松, 林宗坚.  拓扑关系形式化描述的Euler示性数模型 . 武汉大学学报 ● 信息科学版, 2004, 29(10): 872-876.
    [19] 罗芳, 艾廷华, 王洪.  闭合坐标链多边形数据的拓扑关系快速构建 . 武汉大学学报 ● 信息科学版, 2004, 29(6): 558-561.
    [20] 王涛, 毋河海.  等高线拓扑关系的构建以及应用 . 武汉大学学报 ● 信息科学版, 2004, 29(5): 438-442. doi: 10.13203/j.whugis2004.05.014
  • 加载中
图(13) / 表(2)
计量
  • 文章访问数:  764
  • HTML全文浏览量:  357
  • PDF下载量:  96
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-12-27
  • 刊出日期:  2021-08-05

利用街区面块拓扑构建道路网络的算法

doi: 10.13203/j.whugis20190348
    基金项目:

    国家自然科学基金 41571375

    国家自然科学基金 51638004

    作者简介:

    蔡先华,博士,教授,主要从事交通地理信息系统(GIS-T)应用与开发、空间信息可视化技术、计算机地图制图等。cai.x.h@seu.edu.cn

  • 中图分类号: P208

摘要: 道路交通网络是进行各种道路交通网络分析与可视化的基础。构建道路网络的常用方法是运用已有道路面矢量数据提取道路中心线,并自动生成道路网络。提出了一种根据街区面块拓扑关系自动构建道路网络的算法,首先,根据道路面求反得到街区面块并计算街区面块间的拓扑关系;然后,根据街区面块之间的拓扑关系自动建立道路网络拓扑关系;最后,计算路段(网络弧段)中心线和道路交叉口(节点)的几何位置,完成数字道路网络的构建。与以住算法不同,该算法将拓扑关系构建与中心线提取分开,直接由道路面原始数据构建网络拓扑关系,保证拓扑结构的准确性,且为道路中心线提取提供路段交叉口判别依据。实验表明,所提出算法较好地解决了已有算法在自动计算道路中心线时数据预处理复杂和道路面分割难以处理等问题。

English Abstract

蔡先华, 刘凯丽, 胡卓良, 张远. 利用街区面块拓扑构建道路网络的算法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(8): 1170-1177. doi: 10.13203/j.whugis20190348
引用本文: 蔡先华, 刘凯丽, 胡卓良, 张远. 利用街区面块拓扑构建道路网络的算法[J]. 武汉大学学报 ● 信息科学版, 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: 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
  • 道路交通网络是交通系统能够存在并发挥作用的载体[1],在地理信息系统(geographic information system,GIS)和交通地理信息系统(geographic information system for transportation,GIS-T)中起着重要作用[2]。其应用范围广泛,除了作为地图综合的数据基础[3]、道路可视化的基本数据外,更是路径规划等交通网络分析的基础[4]。一些具有代表性的道路网络模型已经受到了广泛的认可并投入实际应用中,这些模型有线性数据模型[5]、GIS-T数据模型[6-7]、交通数据模型[1]等。

    道路网络模型构建的方法多种多样,传统道路网络模型常以道路中心线为基础生成网络拓扑关系来构建道路网络数字模型[8]。首先,根据原始道路面数据提取道路中心线;然后,在中心线的基础上建立具有拓扑关系[9]和空间位置的空间网络[10]。由矢量道路面提取中心线构建路网的研究较多,具有代表性的方法有垂线族法[11]、基于约束三角形的方法[12-16]、矢量追踪法[17]

    评价道路网络构建算法主要考虑运算结果的几何特征和拓扑特征保持能力[18],几何特征的保持是指提取的道路中心线是否能准确描述道路中心,线上特征点选取是否适当,是否能正确反映道路的自然形态特征,没有附加的分枝或尖锐的抖动等。

    现有的3种具有代表性的方法采用了以下两个或其中一个策略:一是对道路边线上点进行加密,这种处理对初始边线位置数据进行了改动,增加了数据量,降低了数据精度,且生成中心线会因抖动产生多余分枝或在交叉口处形成尖锐的抖动;二是需要对道路路段与交叉口进行分割,计算机不能自动进行处理,需要手动完成。

    道路交通网络的构建实质是道路几何网络和拓扑关系的构建。现有道路网络模型构建方法都是在确定道路网络几何位置的基础上构建拓扑关系的。构建道路网络的初始道路面数据是一组多孔洞多边形,它们之间可能存在图形的拓扑错误,由于数据是人工采集,往往数字化边界出现抖动甚至回绕等现象,数据的规范性难以保证,无法直接构建道路网络拓扑,若将道路面转化成多个独立的多边形,由于是自动实现,可形成规范的数据集。根据生成的多个多边形间拓扑来构建路网拓扑,则构建难度将大大降低。基于此,本文提出一种基于街区面块拓扑的道路网络构建算法,首先,构建网络拓扑关系后提取道路中心线,将复杂的原始道路面通过求反运算转化成简单的街区面块多边形,构建街区面块之间的拓扑关系,并将街区面块之间的拓扑关系转化为道路网络中路段——交叉口拓扑关系,从而建立网络拓扑;其次,选取合适的道路中心线提取算法进行弧段几何位置的提取;最后,实现道路网络构建。这种方法解决了传统方法存在的问题,不需要对边线上的点进行加密处理,也不需要手动进行路段与交叉口的分割。

    • 为方便描述,对所涉及的基本术语及规则定义如下。

      街区面块:由道路边线构成的简单多边形。在城市中,街区面块是由道路围成的区域,本文以街区面块指代独立的、只与道路面相邻的非道路区域,如图 1所示。

      图  1  街区面块示意图

      Figure 1.  Illustration of Blocks

      街区面块最近邻点:一街区面块边界上与另一街区面块边界上距离最近的点。用于计算两街区面块间的距离及近邻关系。

      设街区面块bi边界上的线段集合为$ {L}_{i}=\left\{{l}_{i1}, {l}_{i2}\cdots {l}_{im}\right\} $,街区面块bj边界上的线段集合为$ {L}_{j}=\left\{{l}_{j1}, {l}_{j2}\cdots {l}_{jn}\right\} $,若bi边界线段存在线段lis,街区面块bj边界上存在线段ljt,使得:

      $$\begin{array}{l} \;\;\;\;\;\;\;\left\| {{p_i} - {p_j}} \right\| = \left\| {{l_{is}} - {l_{jt}}} \right\| = \\ \min \left( {\left\| {{L_i} - {L_j}} \right\|} \right), {l_{is}} \in {L_i}, {l_{jt}} \in {L_j} \end{array}$$ (1)

      式中,点pi为线段lis上某一点;点pj为线段ljt上某一点;pipj为街区面块bibj最近邻点对,点对pipj间连线长度即为bibj间的距离。

      以下的近邻、共路段和共交叉口都是指街区面块之间的拓扑关系,本文简称近邻、共路段和共交叉口。

      近邻:街区面块bi与其他街区面块bj之间的最短距离小于某一阈值t(本文实验中取值为研究区域内最大街道宽度的3倍),且满足其最近邻点间连线l不与其他街区面块bk相交条件下的空间关系,即:

      $$ D\left({b}_{i}, {b}_{j}\right)<t\mathrm{且}l\bigcap {b}_{k}=\mathrm{\varnothing } $$ (2)

      两个街区面块如果满足式(2),则称其关系为近邻。

      共路段:街区面块bibj间的关系为近邻,且关联部分为路段,则称bibj间的关系为共路段。

      共交叉口:街区面块bibj间关系为近邻,且关联部分为交叉口,则称bibj间的关系为共交叉口。

      基于街区面块拓扑的道路网络构建算法的基本思想是将复杂道路面图形通过转换,分解为相互独立的简单多边形,再进行空间关系运算。首先,算法对区域内道路面求反,将复杂的带孔洞多边形转换为相互独立的街区面块;然后,根据街区面块之间的拓扑关系进行路段和交叉口判别,求得每条路段两侧的两个共路段街区面块、每个交叉口周围的所有共交叉口街区面块;根据共一条路段的两个街区面块,及它们共有的两个交叉口,采用中心线提取算法计算路段的中心线位置,并求出路段关联的两个节点;最后,完成道路网络数字模型的构建。

    • 本文算法分为4个阶段实现:第1阶段,根据初始道路面数据求反获取相互独立的街区面块;第2阶段,确定街区面块之间的拓扑关系;第3阶段,根据街区面块间拓扑关系建立道路网络拓扑关系;第4阶段,提取道路中心线并生成交叉口。其整体构建流程如图 2所示。

      图  2  路网构建流程图

      Figure 2.  Flowchart of Road Network Construction

    • 在对道路面进行相关自动预处理的基础上求反,获得独立街区面块。如图 3所示,道路面形状为带孔的复杂多边形b0b0的最小外接矩形为q,道路面与最小外接矩形相交求反后的街区面块为b1b2bn。它们存在以下关系:

      $$ \left\{\begin{array}{l}\stackrel{n}{\mathop \cup \limits_{i=1}}{b}_{i}=q-{b}_{0}\\ {b}_{i}\bigcap {b}_{j}=\mathrm{\varnothing }, i, j>0, i\ne j\end{array}\right. $$ (3)

      图  3  街区面块数据获取步骤

      Figure 3.  Procedure of Obtaining Blocks

      式中,$ \stackrel{n}{\mathop \cup \limits_{i=1}}{b}_{i} $为街区面块的并集,街区面块间互不相交;$ {b}_{0}\subset q $,qb0为属于q而不属于b0的部分,即在道路面最小外接矩形范围内由道路面求反得到的非道路面部分。

      运用多边形与多边形叠置分析[19-20],求出多边形qb0的差集,获得形状为简单多边形的独立街区面块。街区面块数据获取步骤见图 3

    • 近邻是进行街区面块拓扑关系判断的基础。通过对街区面块进行近邻分析,可获得街区面块的近邻街区面块,并确定近邻街区面块之间的关系为共路段还是共交叉口。

      1) 最近邻点生成及近邻街区面块确定。根据式(1)搜索两街区面块间边界线段,比较线段之间距离并计算出线段间距离最小时的最近邻点。连接对应街区面块最近邻点,判断连线与其他街区面块是否相交,若相交,则两街区面块不为近邻;若不相交,则两街区面块互为近邻街区面块。

      图 4所示,街区面块b0与面块b1的最近邻点连线为线段p0p1,线段p0p1不与任何街区相交,故街区面块b0与面块b1为近邻;街区面块b1与面块b2的最近邻点连线为线段p2p3,由于线段p2p3与街区面块b0相交,所以面块b1与面块b2不为近邻。

      图  4  近邻关系判断

      Figure 4.  Judgment of Neighborhood Relations

      对于每个街区面块的近邻街区面块集合,按照围绕该街区面块的逆时针方向进行排序。排序判断的依据是对应最近邻点在街区面块轮廓线上所属的线段顺序。此处默认多边形轮廓线上的线段均为逆时针顺序,若最近邻点在同一条线段上,则按最近邻点到线段起点的距离由小到大排序;若最近邻点重合,则以该最近邻点为极坐标极点,连接近邻街区面块序列中的前一街区面块对应的最近邻点作为极轴,计算重合的最近邻点与对应近邻街区面块上的最近邻点连线的极角,按极角从小到大排序。如图 5(a)所示,重合最近邻点O的近邻街区面块按逆时针排序为面块b1、面块b2、面块b3;如图 5(b)所示,街区面块b0的近邻街区面块排序为面块b1、面块b2、面块b3、面块b4、面块b5

      图  5  近邻街区面块排序表生成

      Figure 5.  Generation of Sequence List of Neighboring Blocks

      2) 近邻街区面块标记。在近邻街区面块排序表中,与当前街区面块的近邻关系有共路段和共交叉口两种。提取路段信息需要明确当前街区面块与其近邻街区面块之间是何种近邻关系。

      通常情况下,共路段街区面块最近邻点对连线与前驱街区面块和后继街区面块间距离之和接近于路段长度,远远大于最近邻点对连线长度,而共交叉口街区面块间最近邻点对连线与前驱或后继街区面块间距离较近,近似于最近邻点对连线长度(道路宽度)。根据这一特性可进行共交叉口街区面块和共路段街区面块的判断。

      图 6所示,街区面块b0与面块b2最近邻点连线为l1,近邻街区面块b0的排序表中面块b2的前驱街区面块b1、后继街区面块b3与线段l1的距离d1d2均小于l1,即d1+d2 < 2l1,因此,判断面块b0与面块b2为共交叉口关系,将近邻街区面块b0的排序表中的面块b2标记为共交叉口街区面块。

      图  6  近邻街区面块标记

      Figure 6.  Marking of Neighboring Blocks

      同理,街区面块b0与面块b5最近邻点连线为l2,近邻街区面块b0的排序表中面块b5的前驱街区面块b4、后继街区面块b1与线段l2的距离为d3d4,根据d3+d4 > 2l2确定面块b0与面块b5为共路段关系,将近邻街区面块b0的排序表中面块b5标记为共路段街区面块。

      表 1所示,对面块b0的所有近邻街区面块进行标记,以0代表共路段,1代表共交叉口,则面块b0的近邻街区面块标记顺序为:面块b1(0)、面块b2(1)、面块b3(0)、面块b4(0)、面块b5(0)。通过该标记顺序表,可确定面块b0的共路段街区面块和共交叉口街区面块。

      表 1  面块b0的近邻街区标记顺序

      Table 1.  Marking List of Neighboring Blocks of b0

      序号 近邻街区面块 标记
      0 b1 0
      1 b2 1
      2 b3 0
      3 b4 0
      4 b5 0

      对所有街区面块进行标记操作,得到各街区面块标记有共路段和共交叉口的近邻街区面块标记顺序表。

    • 确定近邻街区面块间的路段。如图 7所示,由街区面块之间的近邻街区面块标记顺序表 1可知,去除共交叉口街区面块b2后,街区面块b0按逆时针顺序的共路段街区面块为面块b1、面块b3、面块b4、面块b5,共路段街区面块之间一定存在路段,故围绕街区面块b0的路段有4条,定义为路段l1、路段l4、路段l5、路段l6。为每条路段添加左右多边形信息,则街区面块的路段拓扑(关联)关系建立完成。

      图  7  路网拓扑关系构建

      Figure 7.  Generating Network Topological Relations

      建立交叉口的路段拓扑关系。在生成过程中,对已生成的街区面块做标记。以图 7中面块b0为例,面块b0的近邻街区面块标记顺序为面块b1(0)、面块b2(1)、面块b3(0)、面块b4(0)、面块b5(0)。在顺序表 1中,按顺序相邻的两个共路段街区面块(它们之间可能存在一个或多个共交叉口街区面块)与当前街区面块b0共一个交叉口,如图 7所示,面块b1(0)、面块b2(1)、面块b3(0),面块b3(0)、面块b4(0),面块b4(0)、面块b5(0),面块b5(0)、面块b1(0)分别与面块b0共一个交叉口。根据这一特性,构建面块b0关联交叉口的路段拓扑关系,其步骤如下:

      1) 搜索与面块b0关联的所有街区面块。从面块b0近邻街区面块标记顺序表 1中搜索第一个且为共路段关联的街区面块(本例中为面块b1),按表 1顺序依次搜索近邻街区面块,如果近邻街区面块(本例中为面块b2)为共交叉口街区,则继续搜索,直至搜索到共路段街区面块(本例中为面块b3),即当前街区面块b0与面块b1、面块b2、面块b3共一交叉口。

      2) 判断搜索到的交叉口与路段的拓扑关系是否已生成,未生成则进行处理。若面块b1、面块b2、面块b3中存在已被标记的街区面块,则该交叉口处关联关系已生成,否则添加新交叉口I1,依次搜索出面块b0与面块b1之间路段l1、面块b1与面块b2之间路段l2、面块b2与面块b3之间路段l3、面块b3与面块b0之间路段l4,将路段添加到交叉口I1的邻接路段表中,并根据路段方向,将交叉口I1添加为各个路段的起点或终点。

      3) 如果当前街区面块的近邻街区面块标记顺序表搜索完成,则当前街区面块相邻的所有交叉口与路段的关联关系建立完成,否则,继续搜索下一交叉口关联的街区面块。本例中从面块b3开始,直到搜索出下一共路段街区面块(本例中为面块b4),再重复步骤2)。

    • 1) 路段中心线提取。根据§2.3所建立的拓扑关系,可以确定共路段街区面块,采用单位圆滚动追踪算法[17]进行路段中心线提取,如图 8所示。

      图  8  道路中心线提取

      Figure 8.  Road Centerlines Extraction

      首先,遍历路段表 1,获得路段的左右街区面块信息,再以左右街区面块间的最近邻点对连线中点为圆心、连线长度的一半为半径作圆,通过二分法寻找圆上到两侧街区面块距离相等的两点,并作为两个方向上新的中心线追踪点;然后,以新追踪点为圆心分别作圆(滚动圆半径不变),并用同样的方法寻找该方向上的下一个追踪点,直到追踪点到左右街区面块距离与到关联交叉口所关联的其余街区面块的距离接近(距离之差绝对值小于滚动圆半径)时结束追踪;最后,连接追踪点生成线段,并对两个方向上线段进行合并。

      2) 路段交叉口位置确定。不同形状的路口生成交叉口的方法略有不同,如图 9所示。

      图  9  交叉口处的修整

      Figure 9.  Trim at Intersections

      图 9可知,对于十字路口或T型路口,根据路段的延长线交叉的角度判断交叉口关联路段集合中的连续路段并进行连接。对于T型路口,取不相连路段的延长线与相连路段的交点为交叉口中心;对于十字路口,取两对相连路段交点为交叉口中心;在路口的路段较多的情况下,取交叉口附近路段的端点构成的多边形的中心为交叉口中心,连接交叉口中心与各个路段端点,并进行路段合并,最终得到完整的道路中心线。

    • 本文以某市1∶1 000比例尺地形图中的城区道路面为实验数据,图 10为部分实验数据图形。

      图  10  道路面实验数据(局部)

      Figure 10.  Experimental Data of Road Surfaces (Part)

      运用C#语言,基于ArcGIS Engine二次开发组件开发实验软件,实现了本文提出的算法。

    • 在生成道路中心线临时成果时,在极个别路段出现了临时中心线与街区面块相交情况,如图 11所示,图 12图 11中出现错误区域的放大图。

      图  11  道路中心线临时成果

      Figure 11.  Interim Result of Road Centerlines

      图  12  道路中心线与街区面块相交

      Figure 12.  Intersection of Road Centerlines and Blocks

      产生上述情况的原因是街区面块a和面块b之间实际共有两条不连续的路段,算法未能生成第2条路段。针这一特殊情况,采用线与多边形的叠置分析,可自动筛选出与中心线相交的街区面块b作为目标街区面块。添加第2条路段,确定路段与街区面块间拓扑关系和路段交叉口拓扑关系,再进行交叉口处理,最后,生成结果如图 13所示。生成路网的拓扑关系准确,没有出现多余中心线或中心线缺失情况,提取的道路中心线位置精确、形状平滑,与街区间的匹配关系正确,在密集街区的区域仍能取得很好的效果。

      图  13  道路网络构建结果

      Figure 13.  Results of Road Network Construction

    • 传统算法需要手动进行路段分割或道路边线加密。手动路段分割需要人工处理,导致整个路网构建过程效率低,且容易出现错误。道路边线加密可以自动实现,但增加了数据处理量,提取的中心线可能产生多余的分枝。道路面求反可以自动实现,降低了图形的复杂度,能建立准确的图形关系。

      根据手动路段分割、道路边线加密、道路面求反、几何特征和拓扑关系5个指标对本文算法与传统算法进行比较分析,结果如表 2所示。

      表 2  算法相关指标对比

      Table 2.  Comparison of Algorithm-Related Indicators

      算法 手动路段分割 道路边线加密 道路面求反 几何特征 拓扑关系
      本文算法 准确
      垂线族法 会出现尖锐拉动 可能歪曲连通关系
      基于约束三角形法 会出现多余分枝 准确
      矢量追踪法 准确

      垂线族法几何原理简单,但在应用上有不少困难,需要对道路边线作密集分段处理,而且不能自动处理;在交叉口附近,中轴线的连接可能歪曲连通关系,也可能出现尖锐抖动,对数据的处理提出了苛刻的要求。

      基于约束Delaunay三角网提取法可以对道路进行自动分段处理,但算法要求初始数据为规范的街区多边形数据,需要对街区面块边线的特征点进行加密处理,提取的中心线还可能产生多余的分枝。由于只基于两个固定的特征点,线形不能精确地表示道路自然形态特征。

      矢量追踪法中典型算法为单位圆滚动算法[17],顾及了道路一定范围的形态特征,不需要对道路边线进行规则加密处理,提取的中心线可以很好地保持道路几何形态。但需要先将路段与交叉口进行分割,形成简单带状路段,现有文献未见有该处理过程的自动化实现方法的研究。

      利用街区面块拓扑构建道路网络的算法需要对道路面进行求反处理,在极个别地方(如两个街区面块之间共有两条不连续的路段时)需要特殊处理。但不需要手动进行路段分割和道路面边线加密,通过求反将复杂图形进行简化,运用多边形间拓扑关系获取路段信息,用单位圆滚动算法提取道路中心线,结果较好地保持了网络的几何特征,也保证了拓扑关系的准确性。

    • 为准确地构建道路网络拓扑结构并提取道路中心线,本文提出一种基于街区面块拓扑的道路网络构建方法,将道路面转化为独立的街区面块,利用街区面块之间的拓扑关系进行路网拓扑构建并提取道路中心线。以某市城区部分道路面为实验数据进行验证,结果表明,该方法可构建拓扑完整、位置精确、形状平滑的道路网络,可适用于路网密度较大、街区密集的城市道路几何网络的构建。

      该算法将复杂道路面(一种复杂多边形图形)通过空间逻辑运算进行转换,分解为独立的简单多边形,再进行简单多边形空间关系运算。与传统的道路网络构建算法相比,本文提出的算法可获得精度较好、拓扑关系准确的道路网络,且在构建路段的街区面块拓扑的过程中实现了路段与交叉口的自动区分,解决了复杂的路段分割问题,为道路中心线提取提供了帮助。

参考文献 (20)

目录

    /

    返回文章
    返回