李功權，蔡祥云 (長江大學地球科學學院，湖北 武漢 430100)

一種基于約束三角網(wǎng)的道路中心線的提取方法

李功權，蔡祥云 (長江大學地球科學學院，湖北 武漢 430100)

鑒于道路中心線應用的廣泛性，研究了基于約束Delaunay三角網(wǎng)的道路中心線的提取算法。以道路邊界線作為約束線，采用Delaunay方法構建三角網(wǎng)。通過確定相鄰三角形的類型，把獲取的節(jié)點分為3類，其對應道路網(wǎng)絡中的十字路、T型路和環(huán)島路，對其分別進行優(yōu)化處理，從而形成道路的中心線。在給出詳細的算法步驟的同時，并用C#語言實現(xiàn)該算法。實測數(shù)據(jù)應用分析表明，該算法生成的道路中心線符合原道路多邊形的形態(tài)，保持了原圖形的拓撲特征。

道路中心線；約束Delaunay三角網(wǎng)；道路網(wǎng)絡模型

根據(jù)道路中心線建立的道路網(wǎng)絡模型，充分利用了GIS的網(wǎng)絡分析功能，在交通管理和汽車導航中有著廣泛的應用。道路中心線的數(shù)據(jù)一般無法直接得到，在道路規(guī)劃設計中可能使用的是道路兩邊的邊界線，城市土地管理部門可能有各個地塊的邊界信息，這就需要從這些數(shù)據(jù)中提取道路中心線，而不是去實地人工采集。如果把需要求取道路中心線的區(qū)域看作一個多邊形，不是道路的相關空間信息作為約束信息，道路中心線的求取問題就可以轉(zhuǎn)化為多邊形骨架線的求取。所謂骨架線，就是用與原形狀連通性和拓撲結構相一致的細曲線作為原對象的一種抽象表示，多邊形骨架線的本質(zhì)是對多邊形形狀的抽象描述，它反映了多邊形的延伸方向和形狀特征[1-3]。在GIS中，面狀地理空間對象的分析等很多空間操作都需要提取骨架線[4-6]。

1 算法原理

多邊形骨架線提取的關鍵是搜尋多邊形內(nèi)部到邊界線上的等距離點集，本質(zhì)上屬于空間鄰近分析問題。一般的骨架線的提取算法有：①數(shù)學形態(tài)學提取骨架線，這種方法本質(zhì)是矢量化方法；②最大內(nèi)切圓盤法，最大圓盤完全落于目標圖像內(nèi)，并且至少有2點與目標邊界相切。骨架的每一個點都對應于一個最大圓盤的圓心和半徑，圓盤的構建特別是小圓盤的構建是該算法的最大難題；③基于Delaunay三角網(wǎng)的多邊形骨架線提取算法，Delaunay 三角網(wǎng)是一系列相連但不重疊的三角形的集合，而且這些三角形的外接圓不包含面域中其他任意點，且是Voronoi圖的對偶[7]。Delaunay三角剖分可以最大限度地避免狹長三角形的出現(xiàn)，并且可以不管何處開始都能保持三角網(wǎng)絡的唯一性，Delaunay三角網(wǎng)是探測空間圖形鄰近關系的優(yōu)秀工具。因此，筆者采用Delaunay三角網(wǎng)作為提取骨架線的理論工具。以多邊形的邊界為約束條件構建三角網(wǎng)，取三角形邊線的中點作為骨架線的節(jié)點，順次連接這些節(jié)點，得到多邊形的骨架線[7]。

1.1約束Delaunay三角網(wǎng)的構建

對于約束Delaunay三角網(wǎng)生成算法，大致可以分為3種：分治算法、逐點插入法和三角網(wǎng)生長法。而逐點插入算法的特點是實現(xiàn)比較簡單，占用內(nèi)存小，因此筆者采用逐點插入法生成無約束的Delaunay三角網(wǎng)，再根據(jù)約束邊刪除多邊形外部多余的三角形。具體過程如下：

1)將離散后多邊形的頂點，建立一個包含其他數(shù)據(jù)點的初始多邊形，稱其為凸包；

圖1 約束Delaunay三角行的生成過程

2)在初始多邊形中建立初始三角網(wǎng)，對所有初始多邊形中數(shù)據(jù)點循環(huán)處理(見圖1(a))。

3)插入一個數(shù)據(jù)點P，在已有三角網(wǎng)中找出包含P的三角形T，把P與T的3個頂點相連，生成

3個新的三角形，用LOP算法優(yōu)化三角網(wǎng)(見圖1(b))。

4)刪除不在多邊形內(nèi)部的三角形。判斷三角形的一邊是否在多邊形的內(nèi)部，如果在其內(nèi)部保留該邊，如果不在則舍棄。具體的實現(xiàn)過程是每次選取一個三角形一邊的中點，從該點根據(jù)射線法進行判定，最后結果如圖1(c)所示。

1.2三角形類型的確定

圖2 三角形類型的劃分

三角形類型的確定是在Delaunay三角剖分的同時確定三角形的類型。在該過程中，還要標記出新生成的三角形為何種類型，目的是用來識別道路中心線節(jié)點的類型。從多邊形內(nèi)部三角形的鄰近關系來看，可以分為3種類型的三角形：第Ⅰ類三角形是只有1個鄰接三角形；第Ⅱ類三角形是有2個鄰接三角形；第Ⅲ類三角形是3條邊都有鄰接三角形。根據(jù)鄰近三角形的數(shù)目，將三角形分為3類(見圖2)：第Ⅰ類三角形是三角網(wǎng)中的邊界節(jié)點，其中一邊的中點作為骨架線的端點；第Ⅱ類三角形是三角網(wǎng)中的橋接三角形，是道路中心線的骨干結構，描述了中心線的延展方向；第Ⅲ類三角形作為中心線分支的交匯處，是向3個方向伸展的出發(fā)點。

三角形類型的確定方法主要依據(jù)與某個三角形相鄰三角形的個數(shù)。首先統(tǒng)計分別與三角形的三條邊相鄰三角形的個數(shù)總和，默認的情況下設置與三角形的一條邊的鄰接三角形的個數(shù)為0；其次，根據(jù)三角形三邊相鄰三角形的總和判斷三角形的類型，當值為1時就是第Ⅰ類三角形，值為2時就是第Ⅱ類三角形，值為3時就是第Ⅲ類三角形。這樣就能判斷出三角形的類型。

1.3中心線的提取

首先，判斷三角形是否是多余三角形，如果不是就判斷它是哪種類型的三角形。如果是第Ⅰ類的三角形，提取橋接邊的中點和另外2邊中較長的一邊的中點；第Ⅱ類的三角形提取2個橋接邊的中點；第Ⅲ類三角形則需要提取該三角形的重心和3條橋接邊的中點。其次，對于第Ⅰ類和第Ⅱ類的三角形來說提取的2個點便是中心線；對于第Ⅲ類三角形來說，將重心分別和其他的3個點相連便也是中心線。但求出的中點是事先需知道該三角形的哪條邊是橋接邊，這樣便于找出橋接點、端點、分支點，從而確定中心線各節(jié)點的類型。這樣把Delaunay三角形一個個的單獨處理，提取他們各自的這些端點、橋接點、分支點連起來，便可獲得最終的結果(見圖3)。

圖3 中心線的提取

2 算法實現(xiàn)

根據(jù)道路多邊形提取道路中心線，涉及到2個基本的數(shù)據(jù)結構。一是三角形的定義，作為三角網(wǎng)的構成基本單元，不僅需要表達自身三角網(wǎng)的特征，還需要考慮三角形之間的關系；二是道路中心線的表達，可以看成是一系列具有特定屬性的頂點的集合。

三角形的數(shù)據(jù)結構可以用一個結構體來定義，具體的數(shù)據(jù)結構如下：

struct Triangle

{

public long V1Index; //三角形的三個頂點

public long V2Index;

public long V3Index;

public bool edge1; //(v1,v2)是否已經(jīng)存在

public bool edge2; //(v2,v3)是否已經(jīng)存在

public bool edge3; //(v1.v3)是否已經(jīng)存在

public int AdjIndexE1; //edge1的鄰近三角形的索引

public int AdjIndexE2; //edge2的鄰近三角形的索引

public int AdjIndexE3; //edge3的鄰近三角形的索引

public bool bDelete ; //判斷多余的Delaunay三角形是否被刪

public bool Fkind; //第Ⅰ類三角形

public bool Skind; //第Ⅱ類三角形

public bool Tkind; //第Ⅲ類三角形

}

其中，AdjIndexE1、AdjIndexE2、AdjIndexE3分別用來存儲(v1，v2)邊、(v2，v3)邊、(v1，v3)邊的鄰近三角形的索引，默認賦值為-1；Fkind、Skind、Tkind 3個bool變量分別用來判斷該三角形屬于那種類型，F(xiàn)kind代表第Ⅰ類三角形，Skind代表第Ⅱ類三角形，Tkind代表第Ⅲ類三角形，默認值都為false。

根據(jù)相鄰三角形的類型可以把形成的中心線節(jié)點分為端點、橋接點和分支點，具體的數(shù)據(jù)結構如下：

struct Vertex

{

public long x; //頂點的x坐標

public long y; //頂點的y坐標

public long ID; //頂點的索引

public int isHullEdge; //凸殼頂點標記

}

在定義了這2個數(shù)據(jù)結構后，用C#語言根據(jù)上述原理實現(xiàn)了道路多邊形文件的讀取、道路邊界點加密、約束三角網(wǎng)的構建、三角形中心點的提取、道路中心線各節(jié)點的優(yōu)化處理5個模塊。

3 應用效果評價

如果道路線上的邊界點過于稀疏，在生成的三角網(wǎng)中容易出現(xiàn)小內(nèi)角的狹長三角形。為了解決該問題，可以采用對道路多邊形邊界點作適當加密的辦法，首先對各邊界點作3次樣條函數(shù)擬合，然后把道路的平均寬度作為間距加到邊界點中。

為了驗證該算法，把同樣的數(shù)據(jù)用ArcGIS 9進行了處理。在ArcGIS中，如果要提取道路的中心線，如果是面要素，要先將面要素轉(zhuǎn)換為線要素(此處的線要素是雙線要素)，然后利用制圖工具中的提取中心線工具，設定最大值和最小值參數(shù)，且必須給定最大值。設計的測試數(shù)據(jù)不僅考慮了實際數(shù)據(jù)的特點，而且還設計了多種道路類型。ArcGIS提取的結果如圖4所示，雖然在多數(shù)區(qū)域提取的道路中心線符合實際，但在圖4中圓圈和矩形所圈定的區(qū)域都存在著明顯錯誤，圓圈所指示的道路中心線明顯不存在；對于某些交叉路口(矩形所指示的范圍)，和實際的道路網(wǎng)絡模型不符。筆者設計的算法提取的道路中心線如圖5所示，對于任何類型的道路限制條件都能適用。

圖4 ArcGIS提取的道路中心線 圖5 筆者設計算法提取的道路中心線

4 結 語

由于形成道路的多邊形樣式變化多端，道路中心線的提取是一個復雜的過程。 筆者運用約束的Delaunay 三角網(wǎng)法提取道路中心線，算法完全基于矢量數(shù)據(jù)結構實現(xiàn)，算法建立在多邊形的形狀分析基礎上，高效穩(wěn)定。從試驗結果來看，提取的道路中心線能反映出道路的基本特征?？梢姽P者設計的算法可以用來求取道路中心線。但該算法可能產(chǎn)生不需要的細長三角形，多邊形邊界的細微波動可能會導致道路中心線的明顯偏移，這個問題值得進一步研究。

[1]Shaked D,Bruckstein A M. The curve axis [J].Computer Vision and Image Understanding, 1996, 63(2):367-369.

[2] LI Z L. Algorithmic Foundation of Multi-scale Spatial Representation [M].CRC Press, 2007：20-23.

[3]Attneav E F. Some informational aspects of visual perception [J].Psychological Review, 1954, 61(3):183-193.

[4] Mcmaster R B. A statistical analysis of mathematical measures for line simplification[J]. The American Cartographer, 1986, 13: 103-116.

[5] Mcmaster R B. Automated line generalization [J]. Cartographica, 1987, 24(2): 74-111.

[6] LI Z L. An examination of algorithms for detection of critical points on digital lines [J]. The Cartographic Journal, 1995, 32(2): 121-125.

[7]Haunert J H,Sester M. Area Collapse and Road Centerlines based on Straight Skeletons [J]. Geoinformatica,2008,12:169-191.

[8] Paul C L. Constrained Delaunay Triangulations [J]. Algorithmica, 1989, 4:97-108.

2012-11-24

中國石油科技創(chuàng)新基金(2010D-5006-0205)

李功權(1971-)，男，博士，副教授，現(xiàn)主要從事GIS、數(shù)字油藏方面的教學與研究工作。

TP391.4

A

1673-1409(2013)04-0047-04

[編輯] 洪云飛