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

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

2、)路徑是相當(dāng)重要的，因?yàn)槿藗兛偸莾A向于用最短的時(shí)間來(lái)移動(dòng)。在這種情況下，假設(shè)存在若干服務(wù)場(chǎng)所(如郵局、超市等)，其中每一個(gè)服務(wù)場(chǎng)所都能滿足需要，利用城市Voronoi圖便可以解決借助交通網(wǎng)絡(luò)到達(dá)所需時(shí)間最短的那個(gè)服務(wù)場(chǎng)所的問(wèn)題。 然而，城市Voronoi圖要求交通網(wǎng)絡(luò)路線僅為水平或垂直方向，這使它的應(yīng)用受到了很大程度的限制，因?yàn)樵诳陀^世界中存在大量的具有一定傾斜度的交通路線，曲線交通路線則更具有一般性。為了使城市Voronoi圖

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

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