罗小飞,余琳莉(1．深圳市勘察研究院有限公司,广东深圳 51806; ．深圳市规划国土资源委员会第二直属管理局,广东深圳 51805)

地理国情道路中心线提取算法研究

罗小飞1∗,余琳莉2
(1．深圳市勘察研究院有限公司,广东深圳 518026; 2．深圳市规划国土资源委员会第二直属管理局,广东深圳 518052)

摘 要:道路中心线是地理国情普查中的重要国情要素,如何快速准确的提取是地理国情普查工作中面临的重要问题。本文以Delaunay不规则三角网为基础,建立了道路三角网拓扑,提出了三角网中点搜索算法,针对道路起点和终点进行了优化,并提出了复杂路口的处理方法。该算法通过实验证明是准确高效的,在地理国情中心线要素提取工作中具有一定的应用价值。

关键词:地理国情；道路中心线；Delaunay三角网

1　引 言

地理国情普查是一项全国性的普查工作,是基于国情的重要组成部分,是掌握自然资源、生态环境及人类活动情况的综合性、基础性工作,重点是地表自然和人文地理要素的空间分布、特征及其相互关系[1],包括地表形态、地表覆盖和重要地理国情要素三个方面。其中道路作为与人类活动情况密切相关的交通网络,是地理国情要素中的重要采集对象,按照地理国情要素采集内容与指标的要求,道路应采集道路的中心线并赋要素属性[2]。

如果通过人工方式采集道路中心线,工作量大,效率低。目前的做法是先采集道路的地表覆盖数据,即先采集道路范围线,然后由道路范围线生成道路的中心线。基于以上的数据生产流程,本文提出了利用Delaunay不规则三角网生成道路中心线的算法及实现过程。

2　道路Delaunay三角网的建立

Delaunay三角网(以下简称D三角网)具有两个重要的特性:①空外接圆性质:离散点集P的D三角网中,每一个三角形的外接圆不包含P中除该三角形三个顶点外的其他任何点;②三角形最小角最大:离散点集P上的所有不规则三角网中,D三角网的每个三角形的最小角度是最大的[3]。

道路边线是由一系列有顺序的空间点组成的,由于道路的宽度不一致性,需要将道路进行剖分,D三角网则是针对空间离散点集合三角剖分最常用的一种方法,因其具有优良的数学几何性质、能够方便建立空间邻接关系、结构稳定灵活性等优点,在与几何形体有关的信息数据分析处理中得到了广泛应用[4]。

目前常用的生成D三角网的各种算法主要分为三类:三角网生长法、分治算法和逐点插入法。三角生长法由于搜索第三点的过程过长,已经很少用到了,分治法存在大量递归运算,算法复杂而且实现起来需要占用较大内存空间,逐点插入法实现过程相对简单,内存占用较小,时间复杂度基于前两者之间,若点是随机插入,性能将达到O(NlogN)[5]。本文以逐点插入法为基础,加入了道路Delaunay三角网(以下简称道路三角网)的限制条件,即道路三角网仅在道路边线范围内。该算法的主要步骤:

(1)获取道路的所有边界节点,构建一个多边形凸壳,将所有的节点包含在内;

(2)从凸壳边界开始,以边界为三角形的边建立初始三角网;

(3)根据Delaunay三角形特性,逐个将凸壳点以外的点加入到三角网中;

(4)判断新加入的三角形是否位于道路范围内,如果不在则舍弃;

(5)重复步骤(3)和步骤(4),直至所有数据点处理完毕。如图1所示:

图1　三角网的建立过程

3　道路中心线提取

道路通过D三角网剖分后,将生成的三角形边线中点依次连接即可获得道路的中心线。当通过计算机来实现时,需要考虑以下3个问题:①离散的三角形如何有序地连接起来,保证中点的连接顺序正确;②道路中心线的起点和终点的确定;③交叉口处的三角形如何处理。

3．1三角网邻接关系

道路三角网构建后,遍历所有的三角形,计算公共边、边界边(位于道路边界上的三角形边),获得每个三角形的邻接关系,为了加快处理效率,可以将三角网进行分块处理。

通过对三角形的邻接关系进行分析,将道路三角网分为3个类型:①只有一条边有邻接三角形;②有两条边有邻接三角形;③三条边都有邻接三角形[6]。通常①类三角形出现在道路的起点和终点,②类三角形出现在道路三角网连接处,③类三角形出现在道路交叉口。

为了保证中点连接顺序的正确,对三角形进行遍历排序,除了③类三角形外,三角网中每个三角形仅参与一次搜索,搜索过程如图2所示。

图2　三角网搜索过程

(1)从①类三角形开始搜索,计算每个三角形中非边界边的中点,终止于①类三角形或③类三角形,直至所有的①类三角形都处理完毕;

(2)从③类三角形开始搜索,计算每个三角形中非边界边的中点,终止于③类三角形,直至所有的③类三角形处理完毕。

3．2起点(终点)确定

在道路的起点和终点处由①类三角形表示,由于该三角形处于道路边界上,在进行三角形的邻接关系分析时两条边界边没有参与搜索,导致生成的道路中心线起点和终点与道路边界存在一定的距离,如图3示。

其中C点和E点分别为起点三角形边界边的中点,D点为两条边界边的交点,B点和A点分别为道路中心线的第一点和第二点,分别计算夹角ABC、ABD 和ABE,取夹角较大的C点作为道路的起点,通过该处理方式可以获得较平滑的起始线。

图3　道路三角网起点处理

3．3交叉口处理

在道路交叉口处,有时会出现1个～2个③类三角形。以一个③类三角形的情况为例,分别考察三角形的重心、内心、外心、长边中点,得到的结果如表1所示。

从表1中可以看出采用长边中点的处理方式可有效避免出现道路中心线在交叉口处发生较大的转角,符合现实的交叉路口情况。

交叉口三角形特征点对比表 表1

4　应用效果

基于本算法实现的道路中心线提取模块,可以快速从道路的地表覆盖数据中提取中心线作为道路的地理国情要素。在实际应用中,对一条长度810 m、节点数501个、2个三岔口的道路进行提取,共花费时间0．2 s,未出现错误的道路中心线,证明本算法是正确和高效的。

如图4所示,绿色的为道路地表覆盖,红色的为自动提取的道路中心线。

图4　道路自动提取示例

5　结 论

本算法以道路作为研究对象,实现了矢量道路中心线的自动化提取,并用于地理国情普查工作中的国情要素采集,提高了工作效率。本文提出的算法同样适用于河流、水渠等国情要素的提取,在实际应用中获得了良好的效果。

参考文献

[1] 景小元,燕晋宁．地理国情普查中的地理摄影要素与技法[J]．科技信息,2013,20:204～207．

[2] GDPJ 01-2013．地理国情普查内容与指标[S]．

[3] 武晓波,王世新等．Delaunay三角网的生成算法研究[J]．测绘学报,1999,28(1):28～35．

[4] 钟世彬,闫喜凤．道路中心线提取及网络建立的算法研究[J]．测绘科学,2008,33(3):105～106．

[5] 余杰,吕品等．Delaunay三角网构建方法比较研究[J]．中国图象图形学报,2010,15(8):1158～1164．

[6] 陈涛,艾廷华．多边形骨架线与形心自动搜寻算法研究[J]．武汉大学学报学报·信息科学版,2004,29(5):443 ～446．

Algorithm Research of Geographical Conditions Road Centerline Extraction

Luo Xiaofei1,Yu Linli2
(1．Shenzhen Investigation & Research Institute Co．,Ltd．Shenzhen 518026,China; 2．Shenzhen municipal planning and Land Resources Committee second under the authority,Shenzhen 518052,China)

Abstract:Road center line is an important factor in the national census, and how to extract the accurate and fast is an important problem in the general situation of the national census．In this paper,the topology of the road network is built on the basis of the Delaunay triangle network．The point search algorithm is proposed,and the method of complex intersection is put forward．The algorithm is proved to be accurate and efficient,and it has a certain application value in the extraction of the essential factors of the geographic conditions．

Key words:geographical conditions;road center line;delaunay triangulation

文章编号:1672-8262(2015)05-65-03中图分类号:P209

文献标识码:B

收稿日期:∗2015—07—09

作者简介:罗小飞(1987—),男,工程师,主要从事GIS开发与应用工作。