地理國情道路中心線提取算法研究

羅小飛,余琳莉(1．深圳市勘察研究院有限公司,廣東深圳 51806; ．深圳市規(guī)劃國土資源委員會第二直屬管理局,廣東深圳 51805)

地理國情道路中心線提取算法研究

羅小飛1?,余琳莉2
(1．深圳市勘察研究院有限公司,廣東深圳 518026; 2．深圳市規(guī)劃國土資源委員會第二直屬管理局,廣東深圳 518052)

摘 要:道路中心線是地理國情普查中的重要國情要素,如何快速準確的提取是地理國情普查工作中面臨的重要問題。本文以Delaunay不規(guī)則三角網(wǎng)為基礎(chǔ),建立了道路三角網(wǎng)拓撲,提出了三角網(wǎng)中點搜索算法,針對道路起點和終點進行了優(yōu)化,并提出了復(fù)雜路口的處理方法。該算法通過實驗證明是準確高效的,在地理國情中心線要素提取工作中具有一定的應(yīng)用價值。

關(guān)鍵詞:地理國情；道路中心線；Delaunay三角網(wǎng)

1　引 言

地理國情普查是一項全國性的普查工作,是基于國情的重要組成部分,是掌握自然資源、生態(tài)環(huán)境及人類活動情況的綜合性、基礎(chǔ)性工作,重點是地表自然和人文地理要素的空間分布、特征及其相互關(guān)系[1],包括地表形態(tài)、地表覆蓋和重要地理國情要素三個方面。其中道路作為與人類活動情況密切相關(guān)的交通網(wǎng)絡(luò),是地理國情要素中的重要采集對象,按照地理國情要素采集內(nèi)容與指標的要求,道路應(yīng)采集道路的中心線并賦要素屬性[2]。

如果通過人工方式采集道路中心線,工作量大,效率低。目前的做法是先采集道路的地表覆蓋數(shù)據(jù),即先采集道路范圍線,然后由道路范圍線生成道路的中心線?；谝陨系臄?shù)據(jù)生產(chǎn)流程,本文提出了利用Delaunay不規(guī)則三角網(wǎng)生成道路中心線的算法及實現(xiàn)過程。

2　道路Delaunay三角網(wǎng)的建立

Delaunay三角網(wǎng)(以下簡稱D三角網(wǎng))具有兩個重要的特性:①空外接圓性質(zhì):離散點集P的D三角網(wǎng)中,每一個三角形的外接圓不包含P中除該三角形三個頂點外的其他任何點;②三角形最小角最大:離散點集P上的所有不規(guī)則三角網(wǎng)中,D三角網(wǎng)的每個三角形的最小角度是最大的[3]。

道路邊線是由一系列有順序的空間點組成的,由于道路的寬度不一致性,需要將道路進行剖分,D三角網(wǎng)則是針對空間離散點集合三角剖分最常用的一種方法,因其具有優(yōu)良的數(shù)學(xué)幾何性質(zhì)、能夠方便建立空間鄰接關(guān)系、結(jié)構(gòu)穩(wěn)定靈活性等優(yōu)點,在與幾何形體有關(guān)的信息數(shù)據(jù)分析處理中得到了廣泛應(yīng)用[4]。

目前常用的生成D三角網(wǎng)的各種算法主要分為三類:三角網(wǎng)生長法、分治算法和逐點插入法。三角生長法由于搜索第三點的過程過長,已經(jīng)很少用到了,分治法存在大量遞歸運算,算法復(fù)雜而且實現(xiàn)起來需要占用較大內(nèi)存空間,逐點插入法實現(xiàn)過程相對簡單,內(nèi)存占用較小,時間復(fù)雜度基于前兩者之間,若點是隨機插入,性能將達到O(NlogN)[5]。本文以逐點插入法為基礎(chǔ),加入了道路Delaunay三角網(wǎng)(以下簡稱道路三角網(wǎng))的限制條件,即道路三角網(wǎng)僅在道路邊線范圍內(nèi)。該算法的主要步驟:

(1)獲取道路的所有邊界節(jié)點,構(gòu)建一個多邊形凸殼,將所有的節(jié)點包含在內(nèi);

(2)從凸殼邊界開始,以邊界為三角形的邊建立初始三角網(wǎng);

(3)根據(jù)Delaunay三角形特性,逐個將凸殼點以外的點加入到三角網(wǎng)中;

(4)判斷新加入的三角形是否位于道路范圍內(nèi),如果不在則舍棄;

(5)重復(fù)步驟(3)和步驟(4),直至所有數(shù)據(jù)點處理完畢。如圖1所示:

圖1　三角網(wǎng)的建立過程

3　道路中心線提取

道路通過D三角網(wǎng)剖分后,將生成的三角形邊線中點依次連接即可獲得道路的中心線。當通過計算機來實現(xiàn)時,需要考慮以下3個問題:①離散的三角形如何有序地連接起來,保證中點的連接順序正確;②道路中心線的起點和終點的確定;③交叉口處的三角形如何處理。

3．1三角網(wǎng)鄰接關(guān)系

道路三角網(wǎng)構(gòu)建后,遍歷所有的三角形,計算公共邊、邊界邊(位于道路邊界上的三角形邊),獲得每個三角形的鄰接關(guān)系,為了加快處理效率,可以將三角網(wǎng)進行分塊處理。

通過對三角形的鄰接關(guān)系進行分析,將道路三角網(wǎng)分為3個類型:①只有一條邊有鄰接三角形;②有兩條邊有鄰接三角形;③三條邊都有鄰接三角形[6]。通常①類三角形出現(xiàn)在道路的起點和終點,②類三角形出現(xiàn)在道路三角網(wǎng)連接處,③類三角形出現(xiàn)在道路交叉口。

為了保證中點連接順序的正確,對三角形進行遍歷排序,除了③類三角形外,三角網(wǎng)中每個三角形僅參與一次搜索,搜索過程如圖2所示。

圖2　三角網(wǎng)搜索過程

(1)從①類三角形開始搜索,計算每個三角形中非邊界邊的中點,終止于①類三角形或③類三角形,直至所有的①類三角形都處理完畢;

(2)從③類三角形開始搜索,計算每個三角形中非邊界邊的中點,終止于③類三角形,直至所有的③類三角形處理完畢。

3．2起點(終點)確定

在道路的起點和終點處由①類三角形表示,由于該三角形處于道路邊界上,在進行三角形的鄰接關(guān)系分析時兩條邊界邊沒有參與搜索,導(dǎo)致生成的道路中心線起點和終點與道路邊界存在一定的距離,如圖3示。

其中C點和E點分別為起點三角形邊界邊的中點,D點為兩條邊界邊的交點,B點和A點分別為道路中心線的第一點和第二點,分別計算夾角ABC、ABD 和ABE,取夾角較大的C點作為道路的起點,通過該處理方式可以獲得較平滑的起始線。

圖3　道路三角網(wǎng)起點處理

3．3交叉口處理

在道路交叉口處,有時會出現(xiàn)1個～2個③類三角形。以一個③類三角形的情況為例,分別考察三角形的重心、內(nèi)心、外心、長邊中點,得到的結(jié)果如表1所示。

從表1中可以看出采用長邊中點的處理方式可有效避免出現(xiàn)道路中心線在交叉口處發(fā)生較大的轉(zhuǎn)角,符合現(xiàn)實的交叉路口情況。

交叉口三角形特征點對比表 表1

4　應(yīng)用效果

基于本算法實現(xiàn)的道路中心線提取模塊,可以快速從道路的地表覆蓋數(shù)據(jù)中提取中心線作為道路的地理國情要素。在實際應(yīng)用中,對一條長度810 m、節(jié)點數(shù)501個、2個三岔口的道路進行提取,共花費時間0．2 s,未出現(xiàn)錯誤的道路中心線,證明本算法是正確和高效的。

如圖4所示,綠色的為道路地表覆蓋,紅色的為自動提取的道路中心線。

圖4　道路自動提取示例

5　結(jié) 論

本算法以道路作為研究對象,實現(xiàn)了矢量道路中心線的自動化提取,并用于地理國情普查工作中的國情要素采集,提高了工作效率。本文提出的算法同樣適用于河流、水渠等國情要素的提取,在實際應(yīng)用中獲得了良好的效果。

參考文獻

[1] 景小元,燕晉寧．地理國情普查中的地理攝影要素與技法[J]．科技信息,2013,20:204～207．

[2] GDPJ 01-2013．地理國情普查內(nèi)容與指標[S]．

[3] 武曉波,王世新等．Delaunay三角網(wǎng)的生成算法研究[J]．測繪學(xué)報,1999,28(1):28～35．

[4] 鐘世彬,閆喜鳳．道路中心線提取及網(wǎng)絡(luò)建立的算法研究[J]．測繪科學(xué),2008,33(3):105～106．

[5] 余杰,呂品等．Delaunay三角網(wǎng)構(gòu)建方法比較研究[J]．中國圖象圖形學(xué)報,2010,15(8):1158～1164．

[6] 陳濤,艾廷華．多邊形骨架線與形心自動搜尋算法研究[J]．武漢大學(xué)學(xué)報學(xué)報·信息科學(xué)版,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開發(fā)與應(yīng)用工作。