基于約束Delaunay三角網(wǎng)的道路密度算法

金 澄, 安曉亞，徐道柱

1.西安測繪研究所，陜西 西安，710054;2. 地理信息工程國家重點實驗室，陜西 西安，710054

?

基于約束Delaunay三角網(wǎng)的道路密度算法

金 澄1,2, 安曉亞1,2，徐道柱1,2

1.西安測繪研究所，陜西 西安，710054;2. 地理信息工程國家重點實驗室，陜西 西安，710054

本文針對道路密度求解過程中道路覆蓋區(qū)域面積難以確定的問題，提出一種基于約束Delaunay三角網(wǎng)的道路覆蓋區(qū)面積計算方法。采取化整為零的思想，先對道路網(wǎng)分布區(qū)域進行約束Delaunay三角網(wǎng)(D-TIN)剖分，并根據(jù)道路所關(guān)聯(lián)三角形對覆蓋區(qū)面積的貢獻度，將三角形分為四類，給出每類三角形面積貢獻度的計算方法，通過累加所有關(guān)聯(lián)三角形貢獻的面積，得到道路覆蓋區(qū)的面積；然后計算道路的密度。實驗結(jié)果表明，此算法簡化了道路密度計算過程中覆蓋區(qū)域面積的求解過程，算法可靠和高效。

地圖綜合；道路密度；Delaunay三角網(wǎng)

1 引 言

線狀道路是一種重要的人文地理要素，道路網(wǎng)密度是體現(xiàn)城市道路建設(shè)數(shù)量、水平以及城市路網(wǎng)布局是否合理和均衡的重要評價指標之一[1]，也是地圖綜合選取操作的重要綜合指標之一[2]。在進行道路網(wǎng)制圖綜合選取時，一般根據(jù)地圖比例尺和地圖綜合區(qū)域的特點制定不同的密度指標，然后根據(jù)密度選取[3]。由于目前計算機的軟硬件技術(shù)還無法達到人腦的智能化識別能力，無法做到像人眼一樣、一眼看出路網(wǎng)的疏密程度，因此，如何自動計算道路的密度是實施路網(wǎng)自動綜合選取的關(guān)鍵所在。本文提出的道路網(wǎng)密度計算方法主要用于道路網(wǎng)制圖綜合與密度合理性評價、與道路關(guān)系緊密的居民地制圖綜合，并可推廣到水系網(wǎng)密度的計算與制圖綜合。目前的研究中，文獻[1]利用GIS軟件計算道路網(wǎng)的密度，但沒有給出具體的實現(xiàn)方法；胡云崗等提出一種基于道路網(wǎng)眼的路網(wǎng)密度計算方法[4]，先將道路網(wǎng)縱橫交錯形成的最小閉合區(qū)塊稱為“道路網(wǎng)眼”，以網(wǎng)眼密度代替道路的真實密度實施道路綜合選取。這種方法一般只適合存在網(wǎng)絡(luò)回路的小比例尺地圖道路或路網(wǎng)比較發(fā)達的城市區(qū)域路網(wǎng)密度的計算，對于道路比較稀疏的地區(qū)，由于道路沒有形成網(wǎng)絡(luò)回路，所以此方法不適用。文獻[5]提出了一種基于道路網(wǎng)架的計算方法，先構(gòu)建路網(wǎng)的骨架線；然后將骨架線連成封閉的多邊形，構(gòu)成道路的覆蓋區(qū)域，并計算多邊形面積；最后根據(jù)道路的長度和覆蓋區(qū)域的面積計算道路的密度。該方法能夠?qū)崿F(xiàn)每條道路的密度計算，但由于數(shù)據(jù)的復雜性，很難將骨架線提取完整，導致構(gòu)建道路覆蓋區(qū)域多邊形失敗。本文提出一種基于約束Delaunay三角網(wǎng)的道路密度分析方法，采取化整為零的思想，先對道路網(wǎng)分布區(qū)域進行約束Delaunay三角網(wǎng)(D-TIN)剖分，同時根據(jù)每條道路所關(guān)聯(lián)的三角形對覆蓋區(qū)域面積的貢獻度，將三角形分為四類，給出每類三角形面積貢獻度的計算方法，通過累加所有關(guān)聯(lián)三角形貢獻的面積，得到道路覆蓋區(qū)的面積，然后計算道路的密度。

2 基于D-TIN計算道路密度方法

2.1 道路密度計算公式

道路密度一般是指一定區(qū)域內(nèi)道路長度與該區(qū)域面積的比值，可理解為一種線密度，其計算公式為[4]：

D=L/A

(1)

其中，D表示道路密度，A表示區(qū)域面積，L表示區(qū)域內(nèi)道路的總長度。

2.2 用D-TIN計算道路密度的方法

根據(jù)公式(1)可知，要計算某條道路的密度，就要分別計算其長度L以及對應(yīng)生長區(qū)域的面積A。道路的長度很容易計算，但其輻射區(qū)域的面積比較難確定。該區(qū)域可以看作是以道路網(wǎng)中每條道路為中心，以相同的速率向外擴張，直到彼此相遇為止而在平面上形成的圖形；除最外圍的道路形成的是開放區(qū)域外，其余每條道路將被一個多邊形所包圍，這個多邊形就是道路所輻射的區(qū)域，稱之為道路的“生長區(qū)”。這一幾何構(gòu)造與Voronoi圖類似(Voronoi圖又稱泰森多邊形)，但按照計算幾何的嚴格定義[6]，它并不是Voronoi圖。Voronoi圖是針對點群目標的，具有以下性質(zhì)：①剖分元多邊形是凸的；②相鄰多邊形中點的連接得到其對偶Delaunay三角網(wǎng)[7]。顯然，道路的“生長區(qū)”幾何構(gòu)造不滿足這2個性質(zhì)。從空間相關(guān)性上分析，生長區(qū)域多邊形可以認為是其包含線狀道路的生存范圍，是與相鄰道路競爭的結(jié)果，這一特征與二維平面進行D-TIN剖分后形成的結(jié)構(gòu)骨架線表達的區(qū)域等分性相似。因此，對道路網(wǎng)進行D-TIN剖分，然后用其結(jié)構(gòu)骨架線來表達道路的生長區(qū)域是比較合適的方法。當確定了道路生長區(qū)域的邊界后，就可以依次連接這些邊界構(gòu)成一個封閉的多邊形，然后計算其面積A，從而用公式(1)即可計算每條道路的密度。

根據(jù)這一思想，用D-TIN計算道路網(wǎng)密度的方法如下：

(1)以道路的弧段集{Li}作為約束邊，對道路網(wǎng)構(gòu)建D-TIN；

(2)對D-TIN剖分的區(qū)域提取骨架線；

(3)對所有骨架線進行線拓撲成區(qū)(成區(qū)方法參考文獻[11])，構(gòu)成道路弧段生長的多邊形集{Pi}；

(4)將{Li}和{Pi}進行空間位置匹配，依次計算出每條弧段Li的長度和對應(yīng)生長區(qū)域Pi的面積，然后用公式(1)計算該弧段的密度。

筆者根據(jù)以上步驟進行初步試驗，在對道路網(wǎng)數(shù)據(jù)構(gòu)建D-TIN后，發(fā)現(xiàn)第2步提取剖分區(qū)域的骨架線非常復雜，容易漏提和重復提取骨架線；并且所提取的骨架線通常不封閉，導致第3步由線自動生成區(qū)時失敗，從而無法進行第4步處理。因此，筆者經(jīng)過仔細研究，提出了一種可以回避第2步和第3步的處理過程，直接計算道路生長區(qū)面積的方法。

3 道路生長區(qū)面積計算優(yōu)化

由于道路的密度計算只與道路的長度和面積相關(guān)，通過分析道路所關(guān)聯(lián)三角形的面積與要求解生長區(qū)面積的關(guān)系，得出一種直接計算道路生長區(qū)面積的方法。其基本思想是：將道路生長區(qū)看作是所關(guān)聯(lián)的三角形切割部分后的集合，采取化整為零的思想，根據(jù)每條道路所關(guān)聯(lián)的三角形對生長區(qū)面積貢獻度的差異，將其分為4類，計算每類三角形對生長區(qū)面積的貢獻度，然后累加所有關(guān)聯(lián)的三角形的貢獻面積，從而直接得到道路生長區(qū)的面積。下面詳細介紹4類三角形的分法和每類三角形對生長區(qū)面積貢獻度的計算方法。

3.1 三角形的分類

圖1是道路網(wǎng)進行D-TIN剖分后截取的部分區(qū)域，P為道路L1的生長區(qū)，其通過連接道路L1所關(guān)聯(lián)的三角形的邊界的中點所得。根據(jù)L1所關(guān)聯(lián)三角形對生長區(qū)面積貢獻度的差異，可以將其分為以下4類，如圖2所示：

Ⅰ型：三角形的三個頂點都落在弧段上，如△abc的三個頂點都落在L1上；

Ⅱ型：三角形有兩個頂點落在弧段上，如△cde的兩個頂點c和d，△ace的兩個頂點a和c落在弧段L1上；

Ⅲ型：三角形只有一個頂點落在弧段上，如△dfe只有一個頂點d落在弧段L1上；

Ⅳ型：三角形有兩個頂點落在弧段上，但其中有一個頂點被其它弧段共享為路網(wǎng)的結(jié)點，如△aeg的兩個頂點a和g都在弧段L1上，g為結(jié)點。

圖1 道路剖分后形成的生長區(qū)及其所關(guān)聯(lián)的4類三角形

圖2 各類三角形對道路生長區(qū)面積的貢獻度

這4類三角形包含了道路網(wǎng)進行D-TIN剖分后形成的所有三角形的類型，根據(jù)每類三角形對生長區(qū)面積的貢獻量，可以計算每類三角形對生長區(qū)面積的貢獻度，通過累加道路所關(guān)聯(lián)的所有三角形的面積貢獻度，即可得到該道路生長區(qū)的面積。下面介紹其具體計算方法。

3.2 道路生長區(qū)域面積計算

用S表示面積，則L1生長區(qū)P的面積可以表示為：

Sp=∑SⅠ+∑SⅡ+∑SⅢ+∑SⅣ

(2)

其中，Sp表示道路生長區(qū)的面積，SⅠ、SⅡ、SⅢ、SⅣ分別表示Ⅰ型、Ⅱ型、Ⅲ型、Ⅳ型三角形對生長區(qū)P的面積貢獻度。

圖2中，陰影表示每類三角對生長區(qū)面積的貢獻度，e和f分別為三角形對應(yīng)邊上的中點。根據(jù)三角形的中線特征和面積割補法求解4類三角形的陰影面積如下：

SⅠ=SΔabc；

SⅡ=SΔabc-SΔaef=3/4SΔabc;

SⅢ=SΔaef=1/4SΔabc；

SⅣ=1/2SΔabc;

計算出4類三角形的面積貢獻度后，通過道路L1上的坐標點搜索出所有關(guān)聯(lián)的三角形，并將其分類，然后用公式(2)即可得到生長區(qū)p的面積。

4 算法步驟

綜上所述，道路網(wǎng)密度計算的優(yōu)化方法如下：

(1)道路網(wǎng)自動相交打斷，清除道路重疊坐標及重疊弧段，形成路網(wǎng)弧段集{Li}；

(2)以{Li}的弧段邊界為約束，構(gòu)建約束D-TIN；

(3)依次取{Li}中每條弧段Li，根據(jù)Li上的坐標點搜索該弧段關(guān)聯(lián)的所有三角形{Ti}；

(4)根據(jù)2.1節(jié)的分類規(guī)則對{Ti}進行分類，根據(jù)2.2節(jié)的4類三角形面積計算方法計算{Ti}中每個三角形面積的貢獻度，然后用公式(2)計算弧段Li生長區(qū)域面積Si；

(5)計算弧段Li的長度，然后根據(jù)公式(1)計算該弧段的密度。

遍歷完{Li}中所有弧段后即可計算出每條道路的密度。步驟(1)是對道路網(wǎng)數(shù)據(jù)進行預處理，以防止重疊的弧段和重疊坐標對構(gòu)建約束D-TIN產(chǎn)生干擾，若數(shù)據(jù)質(zhì)量符合要求，可以直接進行第(2)步計算。

5 算法應(yīng)用實例(實驗與分析)

本算法采用在MapGIS K9平臺上進行C++二次開發(fā)的方式進行試驗，以便利用平臺提供數(shù)據(jù)處理和可視化等基本功能。實驗數(shù)據(jù)為某地區(qū)1∶10萬公路網(wǎng)，如圖3所示。圖4是對道路網(wǎng)數(shù)據(jù)構(gòu)建的D-TIN，利用本文提出的密度計算方法得到結(jié)果如圖5所示。圖中道路顏色越深則表明密度越大，越淺則表明密度越小。從路網(wǎng)的整體分布情況來看，本文提出的道路密度分析算法所計算的結(jié)果與路網(wǎng)的稀疏分布程度一致。

圖3 實驗道路網(wǎng)數(shù)據(jù)

圖4 對道路網(wǎng)構(gòu)建D-TIN

圖5 道路密度計算結(jié)果

6 結(jié) 論

道路密度分析是制圖綜合及城市道路規(guī)劃重要參考指標之一。本文在對道路網(wǎng)區(qū)域進行D-TIN剖分的基礎(chǔ)上，提出一種直接計算道路生長區(qū)面積的方法。該方法避免了構(gòu)建道路生長區(qū)域的中間過程，采取化整為零的思想，將道路生長區(qū)域面積轉(zhuǎn)化為對關(guān)聯(lián)的三角形面積貢獻度的求解，簡化了面積計算過程，提高了算法效率，增強了算法的可靠度。該方法為道路網(wǎng)的選取和城市路網(wǎng)結(jié)構(gòu)合理性的評價，提供了有力的道路密度分析工具。

[1]任慧，周振紅，周鑫鑫. 基于RS與GIS的城市道路網(wǎng)密度計算[J]. 計算機輔助工程. 2009, 18(2):85-87.

[2]黃遠林. 地圖圖形綜合指標體系框架與圖形結(jié)構(gòu)識別研究[D]. 武漢：武漢大學, 2012.

[3]陳波，武芳，錢海忠. 道路網(wǎng)自動選取方法研究[J]. 中國圖象圖形學報，2008(12): 2388-2393.

[4]胡云崗，陳軍，李志林等. 基于網(wǎng)眼密度的道路選取方法[J]. 測繪學報，2007(3): 351-357.

[5]Liu Xing-jian, Ai Ting-hua, Liu Yao-lin. Road Density Analysis Based on Skeleton Partitioning for Road Generalization[J]. Geo-spatial Information Science，2009, 12(2): 110-116.

[6]周培德. 計算幾何——算法分析與設(shè)計[M]. 北京: 清華大學出版社, 2000.

[7]艾廷華. 基于場論分析的建筑物群的移位[J]. 測繪學報，2004(1): 89-94.

[8]武曉波，王世新，肖春生. Delaunay三角網(wǎng)的生成算法研究[J]. 測繪學報，1999(1): 30-37.

[9]劉學軍，龔健雅. 約束數(shù)據(jù)域的Delaunay三角剖分與修改算法[J]. 測繪學報，2001(1): 82-88.

[10]艾廷華，劉耀林，黃亞鋒. 河網(wǎng)匯水區(qū)域的層次化剖分與地圖綜合[J]. 測繪學報，2007(2): 231-236.

[11]齊華. 自動建立多邊形拓撲關(guān)系算法步驟的優(yōu)化與改進[J]. 測繪學報，1997, 26(3): 254-260.

Road Density Algorithm Based on Constrained Delaunay Triangulated Irregular Network

Jin Cheng1,2, Aa Xiaoya1,2, Xu Daozhu1,2

1. Xi’an Research Institute of Surveying and Mapping, Xi’an 710054, China;2.State Key Laboratory of Geo-information Engineering, Xi’an 710054, China

Aiming at the problem that it is difficult to calculate the area of road covered region in road density analysis, this paper proposes an algorithm for calculating the area of road covered region based on the constrained Delaunay triangulation irregular network (D-TIN). Taking the idea of breaking up the whole into parts, the triangulations are classified into four types according to the contribution of triangulations associated with road to the area of road covered region, and the method for calculating the area of each type triangulation is presented. Meanwhile the area of the road covered region is calculated by accumulating all the area of triangulations related to the road. Then the road network density is calculated. The experiment results show that the algorithm simplifies the road covered area calculation in road density analysis, also it is reliable and efficient.

map generalization; road density; Delaunay triangulation network

2015-02-12。

國家自然科學基金資助項目(41201469)，地理信息工程國家重點實驗室開放基金資助項目(NO.SKLGIE2014-M-4-3)。

金澄(1976—)，男，高級工程師，主要從事地理信息處理與服務(wù)方面的研究。

P283.1

A