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

地理國(guó)情道路中心線提取算法研究

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

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

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

1　引 言

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

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

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

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

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

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

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

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

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

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

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

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

3　道路中心線提取

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

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

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

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

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

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

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

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

3．2起點(diǎn)(終點(diǎn))確定

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

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

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

3．3交叉口處理

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

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

交叉口三角形特征點(diǎn)對(duì)比表 表1

4　應(yīng)用效果

基于本算法實(shí)現(xiàn)的道路中心線提取模塊,可以快速?gòu)牡缆返牡乇砀采w數(shù)據(jù)中提取中心線作為道路的地理國(guó)情要素。在實(shí)際應(yīng)用中,對(duì)一條長(zhǎng)度810 m、節(jié)點(diǎn)數(shù)501個(gè)、2個(gè)三岔口的道路進(jìn)行提取,共花費(fèi)時(shí)間0．2 s,未出現(xiàn)錯(cuò)誤的道路中心線,證明本算法是正確和高效的。

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

圖4　道路自動(dòng)提取示例

5　結(jié) 論

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

參考文獻(xiàn)

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

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

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

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

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

[6] 陳濤,艾廷華．多邊形骨架線與形心自動(dòng)搜尋算法研究[J]．武漢大學(xué)學(xué)報(bào)學(xué)報(bào)·信息科學(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

文章編號(hào):1672-8262(2015)05-65-03中圖分類號(hào):P209

文獻(xiàn)標(biāo)識(shí)碼:B

收稿日期:?2015—07—09

作者簡(jiǎn)介:羅小飛(1987—),男,工程師,主要從事GIS開發(fā)與應(yīng)用工作。