一種基于柵格的加權(quán)Voronoi圖構(gòu)建普適方法

劉 寶 舉，劉 慧 敏，鄧 敏，樊 子 德

(中南大學(xué)地球科學(xué)與信息物理學(xué)院地理信息系，湖南 長(zhǎng)沙 410083)

一種基于柵格的加權(quán)Voronoi圖構(gòu)建普適方法

劉 寶 舉，劉 慧 敏，鄧 敏，樊 子 德

(中南大學(xué)地球科學(xué)與信息物理學(xué)院地理信息系，湖南 長(zhǎng)沙 410083)

Voronoi圖是空間分析的一個(gè)重要工具。該文將Voronoi區(qū)域視為流域，將柵格加權(quán)距離視為高程，提出一種顧及非空間屬性的能夠與ArcGIS無(wú)縫集成的Voronoi圖生成方法。首先，根據(jù)Voronoi圖的原始定義直接計(jì)算柵格的最小生成元加權(quán)距離，并仿D8算法思想，確定每個(gè)柵格的流向。然后，提取所有只有流出沒(méi)有流入的柵格，并對(duì)柵格邊界進(jìn)行去噪處理和矢量化，得到Voronoi區(qū)域公共邊，并生成附生成元屬性的加權(quán)Voronoi圖。最后，基于ArcEngine實(shí)現(xiàn)了任意生成元的帶有非空間屬性的加權(quán)Voronoi圖。通過(guò)對(duì)比實(shí)驗(yàn)表明，該文所提出的方法能夠高精度構(gòu)建包含任意生成元的加權(quán)Voronoi圖。

加權(quán)Voronoi圖；加權(quán)距離柵格；流域；生成元

0 引言

Voronoi圖是由俄國(guó)數(shù)學(xué)家M.G.Voronoi于1908年提出的一種空間分割算法，表達(dá)了在空間分布的若干要素對(duì)空間的最短距離剖分。Voronoi圖最初用于解決計(jì)算幾何的凸殼、Delaunay三角剖分、最小生成樹(shù)等問(wèn)題[1,2]，由于鄰近性、鄰接性等特殊性質(zhì)，其應(yīng)用迅速擴(kuò)展到眾多領(lǐng)域。而在地理信息學(xué)科，Voronoi圖作為表達(dá)空間鄰近關(guān)系與空間劃分的有力工具，應(yīng)用于地圖綜合[3,4]、空間鄰近分析[5,6]、空間聚類分析[7]、空間關(guān)聯(lián)規(guī)則挖掘[8]等方面。

從算法實(shí)現(xiàn)的數(shù)據(jù)模型角度，Voronoi圖生成方法可以分為基于矢量和基于柵格兩大類。矢量算法的提出比較早，算法也較多，大都是通過(guò)精確的數(shù)學(xué)計(jì)算得到垂直平分線，進(jìn)而求取Voronoi圖，最為典型的是增量構(gòu)造法[9,10]。這類算法可以得到精準(zhǔn)的邊界線，時(shí)間和空間效率較高，但是其計(jì)算過(guò)程和數(shù)據(jù)結(jié)構(gòu)復(fù)雜，并且不易于擴(kuò)展到加權(quán)Voronoi圖的生成[11]。柵格算法是基于生長(zhǎng)元柵格按一定的距離模板向外擴(kuò)張最終形成Voronoi圖，具有代表性的是基于動(dòng)態(tài)距離變換的方法[12,13]。以上算法都是從計(jì)算幾何的角度出發(fā)，生成的Voronoi圖不能很好地與GIS結(jié)合，限制了在地學(xué)領(lǐng)域的應(yīng)用。近年來(lái)，Dong[14]和田松[15]等先后以開(kāi)發(fā)組件的形式探討了Voronoi圖與GIS的集成。但文獻(xiàn)[14]方法僅能處理單一生成元，而且Voronoi圖有雜質(zhì)面情況存在，文獻(xiàn)[15]方法未考慮生成元的非空間屬性，不利于Voronoi的空間分析。此外，ArcGIS軟件中Cost Distance和Cost Allocation工具可以實(shí)現(xiàn)加權(quán)Voronoi圖，但誤差較大，不能準(zhǔn)確體現(xiàn)生成元權(quán)重與Voronoi圖的關(guān)系。為此，本文以shp格式矢量數(shù)據(jù)作為輸入輸出，研究了一種顧及非空間屬性并能與GIS軟件集成的高精度Voronoi圖構(gòu)建方法。

1 基于加權(quán)距離柵格的Voronoi圖生成策略

利用加權(quán)距離柵格構(gòu)建Voronoi圖，首先從單個(gè)生成元入手，通過(guò)計(jì)算每個(gè)生成元的加權(quán)距離柵格，根據(jù)匯流思想可提取Voronoi柵格區(qū)域并獲得柵格的生成元距離，同時(shí)保留生成元非空間屬性特征，使之便于空間分析處理。在此基礎(chǔ)上，通過(guò)Voronoi區(qū)域柵格邊界鋸齒消除算法，以提高生成Voronoi圖的精度。

設(shè)S={p1,p2,…,pn}為二維歐氏空間(平面)上的點(diǎn)集，Voronoi圖是根據(jù)最近距離原則對(duì)平面進(jìn)行的一種分割，分割得到的每個(gè)區(qū)域內(nèi)部包含一個(gè)點(diǎn)，并且區(qū)域內(nèi)所有點(diǎn)到該點(diǎn)的距離均小于到其他點(diǎn)的距離，可表達(dá)為：

(1)

式中：d(p,pi)為點(diǎn)p與點(diǎn)pi之間的歐氏距離；點(diǎn)pi(i=1,2,…,n)稱為生成元。

根據(jù)式(1)，則可得到每個(gè)要素的空間影響區(qū)域，它是對(duì)空間的一個(gè)完整劃分，亦稱為普通Voronoi圖，如圖1a所示。這種普通的Voronoi圖不考慮屬性對(duì)距離的影響。在實(shí)際應(yīng)用中，每個(gè)要素對(duì)周?chē)鷧^(qū)域的影響程度通常不同。例如，同樣是購(gòu)物點(diǎn)，大商場(chǎng)比小商鋪供貨能力強(qiáng)，相應(yīng)的正常服務(wù)范圍更廣。為此，需要構(gòu)建加權(quán)Voronoi圖，才能更好地體現(xiàn)每個(gè)要素在屬性上的差異。

加權(quán)Voronoi圖與普通Voronoi圖的區(qū)別是在距離的設(shè)置上增加了一個(gè)權(quán)值(圖1b)，可表達(dá)為：

(2)

式中：d(p,pi)為點(diǎn)p、pi之間的歐氏距離,i=1,2,…,n;λi為對(duì)應(yīng)點(diǎn)元pi的權(quán)重。當(dāng)λ1=λ2=…=λn時(shí)，則對(duì)應(yīng)普通Voronoi圖。加權(quán)Voronoi圖可以很好地模擬不同級(jí)別地物的影響范圍。

圖1 普通Voronoi圖和加權(quán)Voronoi圖

Voronoi圖作為一種具有特定結(jié)構(gòu)的矢量多邊形，公共邊上的點(diǎn)到相鄰生成元的距離或加權(quán)距離相等。因此，根據(jù)距離或加權(quán)距離確定Voronoi公共邊是構(gòu)建Voronoi的一個(gè)主要途徑。距離生成元越遠(yuǎn)的區(qū)域，受到生成元的影響越小，且Voronoi公共邊上的點(diǎn)受與之最鄰近的兩個(gè)生成元的影響相等，可見(jiàn)，Voronoi邊是不同地物影響能力的等值線。如果對(duì)生成元的影響進(jìn)行量化表達(dá)，并用柵格數(shù)據(jù)表示這種影響值，則可以很好地表示這種影響隨距離增長(zhǎng)而減小的趨勢(shì)，這種柵格數(shù)據(jù)即是加權(quán)距離柵格。如圖2所示，柵格距離值隨著生成元的影響能力而逐漸變化，鄰近兩點(diǎn)間影響能力相等的柵格點(diǎn)形成線，即是要提取的Voronoi公共邊。進(jìn)而，加權(quán)Voronoi區(qū)域生成轉(zhuǎn)化為加權(quán)距離柵格構(gòu)建與Voronoi區(qū)域提取。

圖2 生成元影響能力變化

2 加權(quán)距離柵格構(gòu)建

2.1 單個(gè)生成元加權(quán)距離柵格計(jì)算

對(duì)區(qū)域進(jìn)行柵格劃分，并用生成元的加權(quán)距離表示柵格值，即為加權(quán)柵格距離。為構(gòu)建加權(quán)距離柵格，需要從單個(gè)生成元入手，計(jì)算每一個(gè)生成元pi(i=1,2,…,n)的加權(quán)距離柵格fi(i=1,2,…,n)，然后將所有生成元的加權(quán)距離柵格依據(jù)特定關(guān)系進(jìn)行疊加，獲得所有生成元的加權(quán)距離柵格。

如圖3所示，分別表示點(diǎn)、線、面狀生成元影響下的加權(quán)距離變化。其中，xoy為柵格平面，z軸表示加權(quán)距離。加權(quán)距離的變化速度與生成元的權(quán)值直接相關(guān)，權(quán)值越大，傾角α越小，距離增長(zhǎng)越緩慢，反之亦然。普通Voronoi圖中所有生成元對(duì)應(yīng)的α角為45°。隨著權(quán)重的增大，傾角變小，生成元恒定距離以內(nèi)的范圍擴(kuò)大。用一過(guò)點(diǎn)A且平行于z軸的平面切圖3a所示的錐體，得到其縱切面圖，如圖4所示。圖中AK的投影AP表示加權(quán)生成元A的影響區(qū)域，AK上任意一點(diǎn)D表示生成元A在投影位置C處柵格的加權(quán)距離為D的z坐標(biāo)值。AF對(duì)應(yīng)普通生成元的距離柵格，角β為45°，點(diǎn)E的z坐標(biāo)值對(duì)應(yīng)普通生成元A在柵格C處的距離值。

圖3 單一生成元加權(quán)距離柵格示意

圖4 單一點(diǎn)生成元加權(quán)距離投影

設(shè)d((x-x1),(y-y1))為普通距離函數(shù)，f(x,y)為加權(quán)距離函數(shù)，生成元A的權(quán)值為ωα，則有：

(3)

式中：x、y分別表示柵格位置坐標(biāo)，x1、y1分別表示生成元坐標(biāo)。類似地，可計(jì)算其他所有單個(gè)生成元的柵格加權(quán)距離fi(x,y),i=(1,2,…,n)。這種加權(quán)距離采用矢量歐氏距離獲得，其精度始終保持在一個(gè)像元誤差，與傳統(tǒng)的依據(jù)距離模板擴(kuò)散生長(zhǎng)的模型相比精度更高，避免了因?yàn)榉较虿煌a(chǎn)生距離不同和因?yàn)榫嚯x模板的選擇而導(dǎo)致精度不統(tǒng)一的情形，亦保證了后續(xù)生成加權(quán)Voronoi圖的精度。

一般地，要素的幾何類型包括點(diǎn)狀、線狀和面狀，對(duì)于線狀要素，通常將其離散化為多個(gè)點(diǎn)進(jìn)行處理；對(duì)于面狀要素，首先設(shè)置其內(nèi)部點(diǎn)的加權(quán)距離為0，然后將其邊界離散化為多個(gè)點(diǎn)進(jìn)行處理。

2.2 多生成元加權(quán)距離柵格確定

Voronoi圖是多個(gè)生成元對(duì)區(qū)域的分割，如圖5所示，多個(gè)生成元并存，在Voronoi圖對(duì)區(qū)域的劃分中，一個(gè)Voronoi區(qū)域的內(nèi)部有且僅有一個(gè)對(duì)應(yīng)的生成元，而Voronoi公共邊處其所指向的相鄰生成元加權(quán)距離相等。因此，在計(jì)算所有單個(gè)生成元的柵格距離值之后，需要確定最小的加權(quán)距離，即：

F(x,y)=min(fi(x,y)),i=(1,2,…,n)

(4)

圖5 多個(gè)生成元距離柵格示意

圖6 加權(quán)距離柵格示意

3 加權(quán)Voronoi區(qū)域提取

3.1 區(qū)域柵格劃分

如圖7所示，將柵格加權(quán)距離視為高程[16]，由于生成元處的柵格距離值為極小值0，因此，水流匯聚點(diǎn)即為生成元，而匯聚到同一生成元的柵格區(qū)域?qū)?yīng)該生成元的流域，即Voronoi區(qū)域，而相鄰流域的分水嶺即為Voronoi區(qū)域邊界，從而，提取出流域并將其轉(zhuǎn)換為矢量面就可以獲得相應(yīng)的Voronoi圖。為提取流域信息，需要確定各位置的水流方向，即每個(gè)柵格像元水流流出的方向，進(jìn)而獲得水流匯聚情況。

圖7 加權(quán)距離柵格

引入D8算法思想，按八鄰域劃分方向，并按照2n(n=0,1,…，7)對(duì)八鄰域進(jìn)行編碼，如圖8所示。根據(jù)每個(gè)加權(quán)距離柵格像元與周?chē)肃徲蛳裨木嚯x梯度，確定最陡下降方向，作為該柵格的流向，并用流向編碼中表示該方向的值對(duì)輸出像元進(jìn)行編碼，由此，得到流向柵格。然后，從生成元柵格開(kāi)始逆向搜索匯入柵格，歸屬為對(duì)應(yīng)的流域，直至為每個(gè)柵格分配唯一流域，即可得到流域柵格，完成Voronoi區(qū)域劃分。

圖8 流向編碼

Voronoi圖是空間分析的重要工具，空間信息和非空間屬性信息是空間分析的兩個(gè)基礎(chǔ)，附屬非空間屬性的Voronoi圖更利于空間分析。為此，進(jìn)行Voronoi區(qū)域劃分后，為每一個(gè)Voronoi面賦予對(duì)應(yīng)生成元的非空間屬性，生成帶屬性值的矢量面結(jié)構(gòu)。

3.2 邊界處理

在對(duì)每一個(gè)柵格確定流域的過(guò)程中，由于某些位于分水嶺上的特別是多流域交叉點(diǎn)處的柵格的流域歸屬無(wú)法準(zhǔn)確確定，所以在將柵格區(qū)域轉(zhuǎn)換為矢量格式過(guò)程中，某些結(jié)點(diǎn)或邊界處會(huì)生成如圖9a所示的雜質(zhì)面，這種雜質(zhì)面只有一個(gè)像元大小，但形成了區(qū)域空洞，同時(shí)影響基于Voronoi圖的統(tǒng)計(jì)分析，因此，有必要在轉(zhuǎn)換為Voronoi區(qū)域之前對(duì)流域柵格邊界進(jìn)行雜質(zhì)面去除處理。

分析發(fā)現(xiàn)，在流域分區(qū)柵格中，當(dāng)邊界上的中心像元與上下左右四鄰域像元值均不相同時(shí)，會(huì)產(chǎn)生雜質(zhì)面，按照四鄰域像元值是否相同分為4種情形，即四鄰域分別取2種、3種和4種值的情況，如圖10所示。對(duì)于四鄰域?qū)ο蛳嗤那樾?，如圖10e所示，表示匯水流域或Voronoi區(qū)域交叉，與實(shí)際情形不符，不予考慮。針對(duì)圖10a-圖10d所示的四鄰域模板及其旋轉(zhuǎn)形式，用鄰域柵格代替中心像元，其中：圖10b與圖10c所示情形用a代替，圖10a所示情形用a或b代替，圖10d所示情形用a、b、c、d任一值代替，使得Voronoi圖邊界存在一個(gè)像元的誤差。經(jīng)過(guò)代替處理后，轉(zhuǎn)換得到的矢量Voronoi圖不包含雜質(zhì)面，鋸齒效應(yīng)亦得到明顯改善，如圖9b所示。

圖9 流域柵格處理前后生成的Voronoi圖

圖10 中心像元與四鄰域值不同的情形

由以上步驟，通過(guò)對(duì)研究區(qū)域的柵格劃分，生成任意生成元的加權(quán)距離柵格，根據(jù)流域思想提取Voronoi邊界，并對(duì)Voronoi圖進(jìn)行邊界處理，生成加權(quán)Voronoi圖，最后將生成元專題屬性關(guān)聯(lián)到Voronoi圖中。這種帶有非空間屬性的Voronoi圖可以直接用于空間分析處理，擴(kuò)展了其應(yīng)用。

4 實(shí)驗(yàn)與分析

4.1 方法驗(yàn)證

為了驗(yàn)證本文方法的有效性，首先用一組模擬的任意生成元進(jìn)行實(shí)驗(yàn)。如圖11所示，該組生成元包括點(diǎn)、線、面3類不同要素，并被賦予不同的權(quán)值。采用本文方法，構(gòu)建其加權(quán)Voronoi圖(圖11b)，并輸出加權(quán)距離柵格(圖11c)。從圖中可以看出，本文方法能夠生成不同類別生成元的加權(quán)Voronoi圖，然而，劃分柵格的大小不可避免地影響Voronoi圖的精度并導(dǎo)致邊界的鋸齒效應(yīng)。在計(jì)算效率方面，由于涉及處理過(guò)程較多無(wú)法準(zhǔn)確給出時(shí)間復(fù)雜度，但通過(guò)實(shí)驗(yàn)證明在250*250的柵格大小情況下，構(gòu)建包含50個(gè)生成元的Voronoi圖所耗費(fèi)時(shí)間為50 s左右(i3，2.27GHz，2GB RAM)，隨著柵格分辨率的變大，耗費(fèi)時(shí)間也會(huì)有所增加。

圖11 不同生成元加權(quán)Voronoi圖

為定量分析本文方法的精度效果，設(shè)計(jì)了第二組實(shí)驗(yàn)來(lái)檢驗(yàn)本文方法的精度。如圖12所示，采用6組點(diǎn)狀分布生成元數(shù)據(jù)，每組數(shù)據(jù)包含14個(gè)隨機(jī)點(diǎn)，用本文方法構(gòu)建其等權(quán)Voronoi圖，將其與普通Voronoi圖進(jìn)行對(duì)比，選取對(duì)應(yīng)的Voronoi區(qū)域的面積誤差百分比作為精度評(píng)價(jià)指標(biāo)，對(duì)本文方法的精度進(jìn)行檢驗(yàn)。表1列出了由6組實(shí)驗(yàn)數(shù)組計(jì)算得到的平均誤差與最大誤差。從表中可以看出，本文方法的平均誤差均在1%以下，具有較高的精度。本文方法在計(jì)算柵格距離時(shí)，直接采用普通距離作為基準(zhǔn)，再進(jìn)行加權(quán)掩膜，與傳統(tǒng)的依據(jù)距離模板擴(kuò)散生長(zhǎng)的模型相比，避免了柵格距離與生成元方向相關(guān)而導(dǎo)致精度不統(tǒng)一的問(wèn)題，從而提高了最終Voronoi圖的精度。需要補(bǔ)充說(shuō)明的是，可結(jié)合應(yīng)用需要設(shè)定加權(quán)距離柵格的大小，精度要求越高，設(shè)定柵格越小，分辨率的提高還可以有效地避免多生成元共面的情形。

圖12 6組隨機(jī)數(shù)據(jù)生成的普通Voronoi圖

表1 面積誤差率

Table 1 Area error rate

第一組第二組第三組第四組第五組第六組最大誤差1.788%0.893%1.044%1.558%1.202%0.887%平均誤差0.590%0.352%0.462%0.579%0.421%0.336%

4.2 對(duì)比分析

ArcGIS中的Cost Distance和Cost Allocation工具也可以實(shí)現(xiàn)加權(quán)Voronoi圖，為了比較其與本文方法的差異，采用圖1所示數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn)，生成結(jié)果如圖13所示，上標(biāo)數(shù)字表示權(quán)重。由于加權(quán)距離柵格本身就體現(xiàn)了生成元的影響范圍，所以本文方法直接提取加權(quán)距離柵格中“分水嶺”作為Voronoi邊界，而ArcGIS方法通過(guò)統(tǒng)計(jì)加權(quán)距離柵格中各像元到鄰近生成元的最小加權(quán)距離以確定像元?dú)w屬，即Voronoi邊界上像元到鄰近兩個(gè)生成元的加權(quán)距離相等，由于生成元權(quán)重和影響范圍呈正比，因此這種累加距離必然導(dǎo)致Voronoi邊相對(duì)靠近權(quán)值較大的生成元，弱化了相對(duì)重要生成元的影響力。所以當(dāng)相鄰生成元權(quán)重相差比較大時(shí)，本文方法生成的Voronoi圖能夠更加準(zhǔn)確地體現(xiàn)不同權(quán)重生成元的影響區(qū)域。

圖13 不同方法生成加權(quán)Voronoi圖

Voronoi圖與GIS軟件的結(jié)合是Voronoi圖生成方法廣泛推廣應(yīng)用的重要前提，本文基于ArcEngine實(shí)現(xiàn)了能夠與GIS軟件完全集成的Voronoi構(gòu)建過(guò)程。與文獻(xiàn)[14]的方法相比，本文方法可以生成任意生成元及其組合的加權(quán)Voronoi圖，與文獻(xiàn)[14]的方法僅能處理單一生成元的情況。為了驗(yàn)證兩種方法在實(shí)際應(yīng)用中的效果，采用2013年中國(guó)西部七省3.5級(jí)以上地震分布點(diǎn)數(shù)據(jù)作為驗(yàn)證數(shù)據(jù)，震級(jí)作為生成元權(quán)重。結(jié)果如圖14所示，兩種方法生成的加權(quán)Voronoi圖大致相同，但是在細(xì)節(jié)處理上文獻(xiàn)[14]方法生成的Voronoi圖在部分邊界上有雜質(zhì)面產(chǎn)生，需要采用本文邊界處理方法對(duì)其進(jìn)一步優(yōu)化處理方可得到平滑邊界。

圖14 中國(guó)西部2013年3.5級(jí)以上地震分布Voronoi圖

5 結(jié)論

本文結(jié)合Voronoi圖的結(jié)構(gòu)特性，從其基本定義出發(fā)，利用普通距離柵格與生成元權(quán)值掩膜運(yùn)算構(gòu)建加權(quán)距離柵格，進(jìn)而提出了一種加權(quán)Voronoi圖生成的普適方法，避免了在歐氏距離下擴(kuò)散模板的選擇導(dǎo)致的精度不統(tǒng)一問(wèn)題[13]，使整個(gè)Voronoi圖保持同一精度，并有效解決了許多柵格方法存在的鋸齒問(wèn)題。同時(shí)，此方法可以與GIS軟件完全集成，顧及非空間屬性和伴生加權(quán)距離柵格的特性使得該方法得到的結(jié)果可直接用于GIS的空間分析處理。實(shí)驗(yàn)證明，與現(xiàn)有方法相比，本文方法精度高，能夠處理任意種類生成元，并且與GIS軟件無(wú)縫集成，同時(shí)有效避免了矢量算法的結(jié)構(gòu)復(fù)雜性。另外，該方法產(chǎn)生的任意中間數(shù)據(jù)和最終生成的加權(quán)距離柵格、Voronoi圖都可以直接作為軟件輸入數(shù)據(jù)進(jìn)行后續(xù)處理。然而，對(duì)于各生成元的權(quán)重差異很大的情形，還不能較好地生成多孔洞形態(tài)的Voronoi圖;其次，算法的效率依然較為低下，生成效率和柵格精度難以兼顧，今后需進(jìn)一步研究其效率優(yōu)化問(wèn)題，使其能在精度和效率方面得到共同提高。

[1] OKABE A,BOOTS B,SUGIHARA K,et al.Spatial Tessellations:Concepts and Applications of Voronoi Diagrams[M].2nd,New York:Wiley Press,2000.

[2] DU Q,FABER V,GUNZBURGER M.Centroidal Voronoi tessellations:Applications and algorithms[J].SIAM Review,1999,41(4):637-676.

[3] 閆浩文,王邦松.地圖點(diǎn)群綜合的加權(quán) Voronoi 算法[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2013,38(9):1088-1090.

[4] 李佳田,康順,羅富麗.利用層次 Voronoi 圖進(jìn)行點(diǎn)群綜合[J].測(cè)繪學(xué)報(bào),2014,43(12):1300-1306.

[5] LI Z L,HUANG P Z.Quantitative measures for spatial information of maps[J].International Journal of Geographical Information Science,2002,16(7):699-709.

[6] 劉慧敏,鄧敏,樊子德,等.地圖上居民地空間信息的特征度量法[J].測(cè)繪學(xué)報(bào),2014,43 (10):1092-1098.

[7] YAN H W,WEIBEL R.An algorithm for point cluster generalization based on the Voronoi diagram[J].Computers & Geosciences,2008,34(8):939-954.

[8] 李光強(qiáng),鄧敏,朱建軍.基于 Voronoi 圖的空間關(guān)聯(lián)規(guī)則挖掘方法研究[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2009,33(12):1242-1245.

[9] 張有會(huì).加權(quán) Voronoi 圖畫(huà)法的研究[J].計(jì)算機(jī)科學(xué),2001,28(6):126-128.

[10] GONG Y,LI G,TIAN Y,et al.A vector-based algorithm to generate and update multiplicatively weighted Voronoi diagrams for points,polylines,and polygons[J].Computers & Geosciences,2012,42:118-125.

[11] LETSCHER D.Vector Weighted Voronoi Diagrams and Delaunay Triangulations[C].Proceedings of the 19th Annual Canadian Conference on Computational Geometry.2007.

[12] 李成名,陳軍.Voronoi 圖生成的柵格算法[J].武漢測(cè)繪科技大學(xué)學(xué)報(bào),1998,23(3):208-210.

[13] CHEN J.A raster-based method for computing Voronoi diagrams of spatial objects using dynamic distance transformation[J].International Journal of Geographical Information Science,1999,13(3):209-225.

[14] DONG P.Generating and updating multiplicatively weighted Voronoi diagrams for point,line and polygon features in GIS[J].Computers & Geosciences,2008,34(4):411-421.

[15] 田松,崔希民,孫云華,等.顧及障礙物的一般圖形 Voronoi 圖及其加權(quán)圖的 ArcGIS 柵格實(shí)現(xiàn)[J].地理與地理信息科學(xué),2014,30(4):42-45.

[16] 艾廷華,禹文豪.水流擴(kuò)展思想的網(wǎng)絡(luò)空間Voronoi圖生成[J].測(cè)繪學(xué)報(bào),2013,42(5):760-766.

A General Raster-Based Approach for Generating Weighted Voronoi Diagrams

LIU Bao-ju,LIU Hui-min,DENG Min,FAN Zi-de

(DepartmentofGeographicInformatics,CentralSouthUniversity,Changsha410083,China)

Voronoi diagram plays a very important role in spatial analysis.Existing methods of generating Voronoi diagrams seldom consider the effect of non-spatial attributes,in this case the partition of geographical space is inconsistent with human cognition.To solve this problem,a unified raster-based algorithm is presented for generating weighted Voronoi diagrams in this paper.First,the region is divided into a set of small regular grids,and the weighted distance of each grid generator is calculated based on the original definition of Voronoi diagram.Second,flow direction of each grid is calculated by using an eight direction (abbreviated as D8) flow model,where the weighted distance is regarded as the elevation and the Voronoi region as being a basin.In this situation,the collection of grids which has no any inflow consists of the extract common edges of adjacent Voronoi regions.The weighted Voronoi diagrams are further built with a modification of the common edges by considering non-spatial attributes,which is implemented by means of ArcEngine software.Finally,practical examples are provided to illustrate the advantages of the proposed method in this paper,compared with current methods.

weighted Voronoi diagram;weighted distance grid;watershed;generator

2015-11-23；

2016-04-05

國(guó)家自然科學(xué)基金項(xiàng)目(41301515)；地理空間信息工程國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室經(jīng)費(fèi)資助項(xiàng)目(201413)；中國(guó)博士后科學(xué)基金(2014M562134)

劉寶舉(1989-)，男，碩士研究生，主要從事GIS空間分析研究。*通訊作者 E-mail：lhmgis@163.com

10.3969/j.issn.1672-0504.2016.04.004

P208

A

1672-0504(2016)04-0017-06