一般城市Voronoi圖結(jié)晶生成算法研究.pdf

1、Voronoi圖是一個關(guān)于空間分割的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，它以某種距離作為度量，以近鄰原則對空間點集進行剖分。這種剖分結(jié)果能夠很好地表達點與點之間的鄰近關(guān)系以及點的影響范圍等重要的空間關(guān)系信息，在求解點集或其它幾何對象與距離有關(guān)的問題時起重要作用。城市Voronoi圖是以Ll平面上任意兩點之間花費的最短時間為距離的一種新型Voronoi圖，它解決了人們?nèi)绾卫媒煌ňW(wǎng)絡(如城市中的街道、地鐵等)進行快速移動的問題。使用這樣的交通網(wǎng)絡尋找最短(時間

2、)路徑是相當重要的，因為人們總是傾向于用最短的時間來移動。在這種情況下，假設存在若干服務場所(如郵局、超市等)，其中每一個服務場所都能滿足需要，利用城市Voronoi圖便可以解決借助交通網(wǎng)絡到達所需時間最短的那個服務場所的問題。 然而，城市Voronoi圖要求交通網(wǎng)絡路線僅為水平或垂直方向，這使它的應用受到了很大程度的限制，因為在客觀世界中存在大量的具有一定傾斜度的交通路線，曲線交通路線則更具有一般性。為了使城市Voronoi圖

3、理論研究進一步貼近現(xiàn)實，進而應用于實際，本文將交通路線擴展為曲線，提出了一種新的城市Voronoi圖--一般城市Voronoi圖。主要工作如下： 1.在城市Voronoi圖的基礎(chǔ)上，將交通路線由僅為水平或垂直方向的線段擴展為曲線，得到一般城市Voronoi圖，給出了一般城市Voronoi圖的定義、性質(zhì)。 2.給出了基于結(jié)晶生長方式構(gòu)造一般城市Voronoi圖的基本思想和生成算法，并用VC++編程實現(xiàn)。為了既能滿足Ll平面

4、中距離的要求，又能夠有效地跟蹤曲線交通路線，采用了4-鄰域結(jié)晶生長和8-鄰域結(jié)晶生長相結(jié)合的結(jié)晶生長方式。算法思路清晰，可讀性好，易于理解。 3.給出了一種在一般城市Voronoi圖中得到最短路徑的簡單方法。最短路徑圖是對空間的一個細分，它用于找到一個源點和一個查詢點之間的最短路徑。由于在一般城市Voronoi圖結(jié)晶生長的過程中存在一條從源點到各個生長點的最短路徑，故只要從查詢點開始逆向跟蹤生長點的生長過程，直至到達源點，便可以