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

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

1 鄰近圖理論簡介

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

(1) 近鄰鄰近圖( nearest neighbor graph，NNG) :平面點集中每個點與最近的若干個點連接形成結果圖

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

(3) 相關鄰近圖 ( relative neighborhood graph，ＲNG) : 即若u，v∈V，邊( u，v) ∈ＲNG; 若不存在點w，則 max{ d( u，w) ，d( v，w) } ＜d( u，v

(4) Gabriel 圖( gabriel graph，GG) : 若u，v∈ V，邊( u，v) ∈GG; 若不存在點 w，則 max{ d2( u，w) ， d2( v，w) } ＜d2( u，v) 。

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

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

更多內容請點擊下方的PDF下載