王少華，鐘耳順，廖華軍，左 堯，蔡文文，龍 亮

(1. 中國科學(xué)院地理科學(xué)與資源研究所，北京 100101; 2. 北京超圖軟件股份有限公司，北京 100015;3. 北京市地理信息核心軟件與應(yīng)用工程技術(shù)研究中心，北京 100015)

基于鄰近圖的道路網(wǎng)絡(luò)特征分析

王少華1,2,3，鐘耳順1,2，廖華軍1,2，左 堯2，蔡文文2，龍 亮1

(1. 中國科學(xué)院地理科學(xué)與資源研究所，北京 100101; 2. 北京超圖軟件股份有限公司，北京 100015;3. 北京市地理信息核心軟件與應(yīng)用工程技術(shù)研究中心，北京 100015)

基于鄰近圖理論針對北京道路網(wǎng)絡(luò)數(shù)據(jù)并結(jié)合道路網(wǎng)絡(luò)特征參數(shù)進(jìn)行了試驗(yàn)分析，進(jìn)而研究了北京道路網(wǎng)絡(luò)特征。結(jié)果表明，相關(guān)鄰近圖能較好地反映北京道路網(wǎng)絡(luò)特征，基于鄰近圖分析道路網(wǎng)絡(luò)特征為道路網(wǎng)絡(luò)分析提供了理論支撐。

鄰近圖；道路網(wǎng)絡(luò)；空間分析;空間索引

鄰近圖分析始于20世紀(jì)80年代。近年來，隨著對鄰近圖研究的深入[1]，基于鄰近圖理論的相關(guān)研究在地理空間分析中得到應(yīng)用。郭慶勝等驗(yàn)證了基于鄰近圖的點(diǎn)集聚類分析的可行性，并使用不同的鄰近圖分析得到不同的聚類效果[2]；宋曉梅等通過k階空間鄰近圖處理空間聚類問題[3]；Adamatzky等使用鄰近圖進(jìn)行道路演化分析[4]，并使用微觀模擬得到較好的研究結(jié)果。道路網(wǎng)絡(luò)是道路網(wǎng)絡(luò)分析的空間地理對象[5-7]，道路網(wǎng)絡(luò)特征分析在道路網(wǎng)絡(luò)演化分析中具有重要作用[8-9]。鄰近性特征分析是進(jìn)行道路網(wǎng)絡(luò)結(jié)構(gòu)分析、道路網(wǎng)絡(luò)數(shù)據(jù)模擬、道路網(wǎng)絡(luò)演化等空間網(wǎng)絡(luò)分析采用的基礎(chǔ)方法，本文采用基于鄰近圖理論的方法分析北京道路網(wǎng)絡(luò)的鄰近圖特征。

1 鄰近圖理論簡介

考慮到鄰近圖的相關(guān)性質(zhì)與道路網(wǎng)絡(luò)特征，本節(jié)選取6種鄰近圖類型進(jìn)行分析。

(1) 近鄰鄰近圖(nearest neighbor graph，NNG)：平面點(diǎn)集中每個點(diǎn)與最近的若干個點(diǎn)連接形成結(jié)果圖。

(2) 最小生成樹(minimum spanning tree，MST)：平面點(diǎn)集之間的生成樹，要求滿足邊集合的長度總和最小。

(3) 相關(guān)鄰近圖(relative neighborhood graph，RNG)：即若?u,v∈V，邊(u,v)∈RNG；若不存在點(diǎn)w，則max{d(u,w),d(v,w)}

(4) Gabriel圖(gabriel graph,GG)：若?u,v∈V，邊(u,v)∈GG；若不存在點(diǎn)w，則max{d2(u,w),d2(v,w)}

(5) 德羅內(nèi)三角網(wǎng)(delaunay triangulation,DT)：平面點(diǎn)集生成鄰接不重疊的三角形，每個三角形的外接圓中不包含點(diǎn)集中任何其他點(diǎn)。

(6) Urquhart圖(urquhart graph,UG)；平面節(jié)集的DT圖中去掉每個三角網(wǎng)中長度最長的那條邊之后所生成的圖。

由上述描述和性質(zhì)可知，基于平面點(diǎn)集的鄰近圖滿足如下關(guān)系

NNG?MST?RNG?GG?UG?DT

Beta骨架圖(beta-skeleton graph，BG)也是一種常見的鄰近圖，由于BG的參數(shù)靈活[10-11]，OSaragi等將其應(yīng)用到道路網(wǎng)絡(luò)分析中[12]。Beta骨架圖中，當(dāng)β=0時，BG圖為DT；當(dāng)β=1時，BG圖為GG；當(dāng)β=2時BG圖對應(yīng)為RNG。

為了更好地理解鄰近圖，圖1為基于相同100個網(wǎng)絡(luò)節(jié)點(diǎn)的6種類型鄰近圖的示意圖。

2 北京道路網(wǎng)絡(luò)節(jié)點(diǎn)的鄰近圖特征研究

2.1 北京道路網(wǎng)絡(luò)節(jié)點(diǎn)的鄰近圖計(jì)算

在鄰近圖構(gòu)建過程中，需要運(yùn)行多次鄰近點(diǎn)查詢，鄰近點(diǎn)查詢的效率直接影響鄰近圖分析的效率，特別是網(wǎng)絡(luò)節(jié)點(diǎn)GG和DT圖的構(gòu)建計(jì)算中，鄰近點(diǎn)查詢次數(shù)最多。為了提高道路網(wǎng)絡(luò)節(jié)點(diǎn)的鄰近點(diǎn)查詢效率，針對道路網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)較大的情況，采用基于空間索引[13-14](KD-Tree索引)的方法進(jìn)行鄰近節(jié)點(diǎn)查詢，從而提高基于道路網(wǎng)絡(luò)節(jié)點(diǎn)集的鄰近圖的構(gòu)建效率。

研究數(shù)據(jù)選取北京六環(huán)內(nèi)道路網(wǎng)絡(luò)數(shù)據(jù)，其道路網(wǎng)絡(luò)的網(wǎng)絡(luò)弧段為雙向道路，而基于網(wǎng)絡(luò)節(jié)點(diǎn)的鄰近圖的弧段是由直線組成的，需要對道路網(wǎng)絡(luò)進(jìn)行拓?fù)涮幚?。采用基于KD-Tree索引的鄰近圖計(jì)算后，得到6種鄰近圖的計(jì)算結(jié)果，如圖2所示。

2.2 北京道路網(wǎng)絡(luò)節(jié)點(diǎn)的鄰近圖特征分析

為了評估道路網(wǎng)絡(luò)與其對應(yīng)的網(wǎng)絡(luò)鄰近圖的關(guān)系，本節(jié)結(jié)合道路網(wǎng)絡(luò)構(gòu)成比率指數(shù)(包括道路網(wǎng)絡(luò)構(gòu)成比率、鄰近圖構(gòu)成比率、全局構(gòu)成比率)、格網(wǎng)樹指數(shù)和網(wǎng)絡(luò)節(jié)點(diǎn)因子等分析其道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖特征。

圖2 基于北京道路網(wǎng)絡(luò)節(jié)點(diǎn)的鄰近圖與道路網(wǎng)絡(luò)匹配圖

(1) 道路網(wǎng)絡(luò)構(gòu)成比率(roadgraphedgeratio,RR)反映的是道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖與道路網(wǎng)絡(luò)的弧段匹配絕對程度，其數(shù)值為道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖與道路網(wǎng)絡(luò)中相同的弧段數(shù)，與道路網(wǎng)絡(luò)中的弧段個數(shù)的比值。不同鄰近圖中與道路網(wǎng)絡(luò)中相同的弧段數(shù)越多，該比率越大，其計(jì)算公式為

(1)

式中，ERN和EPG分別對應(yīng)道路網(wǎng)絡(luò)和鄰近圖的弧段數(shù)目。

(2) 鄰近圖構(gòu)成比率(proximitygraphedgeratio,PR)是衡量道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖與道路網(wǎng)絡(luò)的弧段匹配程度的相對指標(biāo)，是道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖與道路網(wǎng)絡(luò)中相同的弧段數(shù)，與網(wǎng)絡(luò)鄰近圖中的弧段數(shù)的比值。不同鄰近圖中和道路網(wǎng)絡(luò)中相同的弧段數(shù)越多，該比率越大，其計(jì)算公式為

(2)

式中，ERN和EPG分別對應(yīng)道路網(wǎng)絡(luò)和鄰近圖的弧段數(shù)目。

(3) 全局構(gòu)成比率(entiregraphedgeratio,ER)反映的是道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖與道路網(wǎng)絡(luò)的弧段匹配的綜合程度，是道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖與道路網(wǎng)絡(luò)中相同的弧段，與網(wǎng)絡(luò)鄰近圖中的弧段個數(shù)的比值。該比率增加時取決于不同鄰近圖中與道路網(wǎng)絡(luò)中相同的弧段數(shù)，與鄰近圖的弧段數(shù)的比例關(guān)系，計(jì)算公式為

(3)

式中，ERN和EPG分別對應(yīng)道路網(wǎng)絡(luò)和鄰近圖的弧段數(shù)目。

(4) 網(wǎng)格樹指數(shù)是表征道路網(wǎng)絡(luò)類型的因子，計(jì)算公式為

(4)

式中，n為道路網(wǎng)絡(luò)節(jié)點(diǎn)個數(shù)；m為弧段個數(shù)

(5)網(wǎng)絡(luò)交點(diǎn)因子(crossfactor，CF)，即道路網(wǎng)絡(luò)節(jié)點(diǎn)的密度與道路網(wǎng)絡(luò)密度平方的比值，計(jì)算公式為

(5)

式中，n為弧段個數(shù)；S區(qū)域面積；L為道路網(wǎng)絡(luò)長度。

由上述計(jì)算公式，結(jié)合北京道路網(wǎng)絡(luò)數(shù)據(jù)和其網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖數(shù)據(jù)，統(tǒng)計(jì)結(jié)果見表1。

表1 道路網(wǎng)絡(luò)節(jié)點(diǎn)的鄰近圖計(jì)算結(jié)果

為了分析道路網(wǎng)絡(luò)的鄰近圖與相關(guān)參數(shù)的關(guān)系，需要分析北京道路網(wǎng)絡(luò)鄰近圖的各參數(shù)的關(guān)系。分析北京道路網(wǎng)絡(luò)的弧段數(shù)、匹配弧段與道路構(gòu)成率之間的關(guān)系，如圖3所示。分析道路的統(tǒng)計(jì)參數(shù)GTP、CF與道路構(gòu)成率之間的關(guān)系，如圖4所示。

對道路構(gòu)成率的絕對比較參數(shù)RR進(jìn)行分析，RR是表征基于道路網(wǎng)絡(luò)節(jié)點(diǎn)與其生成鄰近圖的絕對參量，鄰近圖與道路網(wǎng)絡(luò)匹配的弧段數(shù)目越多，其值越大。DT圖生成的弧段多，其匹配到的道路網(wǎng)絡(luò)的弧段數(shù)就大，則其道路構(gòu)成率參數(shù)RR數(shù)值大。

圖3 北京道路網(wǎng)絡(luò)鄰近圖道路構(gòu)成率關(guān)系

圖4 GTP和CF與道路網(wǎng)絡(luò)構(gòu)成率關(guān)系

由于RR是基于道路網(wǎng)絡(luò)節(jié)點(diǎn)與其生成鄰近圖相對衡量參數(shù)，通過分析北京道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的鄰近圖構(gòu)成率相對比較參數(shù)PR結(jié)果不難發(fā)現(xiàn)，NNG圖的匹配弧段不多，但是其NNG圖本身的弧段數(shù)目也不多，從而使得道路構(gòu)成率相對衡量指標(biāo)RR數(shù)值大。ER參數(shù)綜合考慮了鄰近圖匹配的弧段數(shù)與鄰近圖本身的弧段數(shù)目，由計(jì)算結(jié)果可知，從這點(diǎn)分析，北京道路網(wǎng)絡(luò)節(jié)點(diǎn)生成的RNG圖的ER指數(shù)最大，在北京道路節(jié)點(diǎn)生成的鄰近圖中，RNG圖最符合北京道路網(wǎng)絡(luò)鄰近特征。

分析鄰近圖的GTP與道路構(gòu)成率的關(guān)系可知，隨著GTP指數(shù)的增大，RR指數(shù)逐漸增大，PR指數(shù)隨之減少，ER指數(shù)先增大后減小(拐點(diǎn)出現(xiàn)在NNG圖中，NNG的ER參數(shù)值最大)。由于GTP與道路網(wǎng)絡(luò)節(jié)點(diǎn)生成圖的弧段和節(jié)點(diǎn)相關(guān)，而6種鄰近圖中的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)相同，這樣GTP的數(shù)值直接與其鄰近圖的弧段數(shù)目相關(guān)。由6種鄰近圖的包含關(guān)系可知，NNG的弧段數(shù)目最少，其GTP指數(shù)最小，DT圖的弧段數(shù)目最多，從而其GTP指數(shù)最大。

分析鄰近圖的CF與道路構(gòu)成率的關(guān)系可知，隨著CF指數(shù)的減少，RR指數(shù)逐漸增大，PR指數(shù)隨之減少，ER指數(shù)先減小后增大(拐點(diǎn)出現(xiàn)在NNG圖中，NNG的ER參數(shù)值最大)。從CF的計(jì)算公式可看出，該參數(shù)的數(shù)值與生成鄰近圖的節(jié)點(diǎn)個數(shù)、鄰近圖整個區(qū)域的面積及弧段的弧段長度總和相關(guān)。由于6種近鄰圖有相同的節(jié)點(diǎn)個數(shù)、相同的面積，因此其參數(shù)數(shù)值與鄰近圖的長度總和成反比，鄰近圖DT的CF數(shù)值最低。

為了比較北京道路網(wǎng)絡(luò)與基于其網(wǎng)絡(luò)節(jié)點(diǎn)生成的6種類型的鄰近圖的匹配特征，將不同類型的鄰近圖按照與道路網(wǎng)絡(luò)匹配的匹配弧段關(guān)系繪制專題圖，結(jié)果如圖5所示。

圖5 道路網(wǎng)絡(luò)鄰近圖匹配特征

從結(jié)果可以看出，基于北京道路網(wǎng)絡(luò)節(jié)點(diǎn)的RNG與北京道路網(wǎng)絡(luò)匹配度最高，北京道路網(wǎng)絡(luò)節(jié)點(diǎn)的RNG與道路網(wǎng)絡(luò)匹配的弧段密度較高部分集中在中心城區(qū)。

3 結(jié) 語

本文針對北京道路網(wǎng)絡(luò)特征，基于鄰近圖理論，并結(jié)合道路網(wǎng)絡(luò)參數(shù)對北京道路網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行了分析研究。通過分析得出，北京道路網(wǎng)絡(luò)節(jié)點(diǎn)的RNG與北京道路網(wǎng)絡(luò)匹配度最高，從而為基于鄰近圖RNG進(jìn)行道路網(wǎng)絡(luò)分析(道路網(wǎng)絡(luò)模擬、道路網(wǎng)絡(luò)演化等)提供了理論支撐。不同城市道路網(wǎng)絡(luò)結(jié)構(gòu)不同，基于鄰近圖分析的道路網(wǎng)絡(luò)特征分析結(jié)果也可能不同，分析道路網(wǎng)絡(luò)特征需要針對道路網(wǎng)絡(luò)數(shù)據(jù)本身的特征。在該方法的應(yīng)用推廣方面，基于空間索引可有效提高鄰近圖構(gòu)成的效率。

[1] 路綱, 周明天, 牛新征,等. 無線網(wǎng)絡(luò)鄰近圖綜述[J]. 軟件學(xué)報(bào)，2008, 19(4): 888-911.

[2] 郭慶勝, 鄭春燕, 胡華科. 基于鄰近圖的點(diǎn)群層次聚類方法的研究[J]. 測繪學(xué)報(bào)，2008, 37(2): 256-261.

[3] 宋曉眉, 程昌秀, 周成虎,等. 利用 k 階空間鄰近圖的空間層次聚類方法[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2010, 35(12)：1496-1499.

[4] ADAMATZKY A,MARTNEZ G J,CHAPA-VERGARA S V,et al. Approximating Mexican Highways with Slime Mould[J]. Natural Computing，2011, 10(3): 1195-1214.

[5] 蔡先華, 王煒, 戚浩平. 基于 GIS 的道路幾何網(wǎng)絡(luò)數(shù)據(jù)模型及其應(yīng)用[J]. 測繪通報(bào), 2005(12)：24-27.

[6] 莫輝輝,王姣娥,金鳳君. 交通運(yùn)輸網(wǎng)絡(luò)的復(fù)雜性研究[J].地理科學(xué)進(jìn)展，2010,27(6): 112-120.

[7] 田晶, 吳蕩, 湛逸飛. 城市道路網(wǎng)的度相關(guān)性研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2014，39(3): 332-334.

[8] 王少華, 鐘耳順, 張小虎,等.北京交通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及可達(dá)性格局歷史變化研究[J].測繪與空間地理信息, 2014, 37(1)：9-12.

[9] 方華強(qiáng),劉金林,葉寧,等.城市道路網(wǎng)拓?fù)淠Ｊ椒治鰧?shí)證研究[J].測繪通報(bào), 2015(S2)：89-92.

[10] ADAMATZKY A. On Excitable β-skeletons[J]. Journal of Computational Science，2010, 1(3): 175-186.

[11] WATANABE D. A Study on Analyzing the Grid Road Network: Patterns Using Relative Neighborhood Graph[C]∥The Ninth International Symposium on Operations Research and Its Applications (ISORA’10). Chengdu：[s.n.]，2010: 112-119.

[12] OSARAGI T, HIRAGA Y. Road Network Analysis Using Geometric Graphs of β-skeleton[C]∥The 11th International Conference on Geocomputation.[S.l.]:[s.n.]，2011.

[13] 吳敏君. GIS空間索引技術(shù)的研究[D].鎮(zhèn)江：江蘇大學(xué)，2006.

[14] 張小虎,鐘耳順,王少華,等.多尺度空間格網(wǎng)數(shù)據(jù)的索引編碼研究[J].測繪通報(bào),2014(7)：35-38.

Research on Road Network Characteristics Based on Proximity Graph

WANG Shaohua1,2,3,ZHONG Ershun1,2,LIAO Huajun1,2,ZUO Yao2,CAI Wenwen2,LONG Liang1

(1. Institute of Geographic Sciences and Nature Resources Research, CAS, Beijing 100101, China; 2. SuperMap Software Co.，Ltd., Beijing 100015,China; 3. Beijing Research Center of Geography Information Core Software and Applied Engineering Technology, Beijing 100015, China)

Beijing road network characteristics were analyzed by employing statistical methods, proximity graph theory and method. The results showed that the relative neighborhood graph can be seemed as characteristics of Beijing road network. Therefore, the research about road network characteristics based on proximity graph provided theoretical support to road network analysis.

proximity graph; road network; spatial analysis; spatial index

王少華，鐘耳順，廖華軍,等.基于鄰近圖的道路網(wǎng)絡(luò)特征分析[J].測繪通報(bào)，2017(8)：80-83.

10.13474/j.cnki.11-2246.2017.0260.

2016-12-26

北京市科技專項(xiàng)(Z151100003615012；Z151100003115007)；國家科技支撐計(jì)劃(2009AA12Z331)；資源與環(huán)境信息系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室自主研究項(xiàng)目(088RAC00YA)；測繪公益項(xiàng)目(201512015)；北京市優(yōu)秀人才項(xiàng)目(201500002685XG242)；全國博士后國際交流計(jì)劃(20150081)

王少華(1983—)，男，博士后，主要研究方向?yàn)榈乩硇畔④浖夹g(shù)。E-mail：wangshaohua@supermap.com

鐘耳順

P208

A

0494-0911(2017)08-0080-04