利用層次Voronoi圖進(jìn)行點(diǎn)群綜合

李佳田,康 順,羅富麗

昆明理工大學(xué)國土資源工程學(xué)院,云南昆明 650093

利用層次Voronoi圖進(jìn)行點(diǎn)群綜合

李佳田,康 順,羅富麗

昆明理工大學(xué)國土資源工程學(xué)院,云南昆明 650093

通過距離權(quán)重描述點(diǎn)的重要程度,采用改進(jìn)的k-means算法得到點(diǎn)群的聚類中心,進(jìn)而以聚類中心為基礎(chǔ),構(gòu)建了層次加權(quán)Voronoi圖與Voronoi層次樹結(jié)構(gòu)。以點(diǎn)群的分布范圍、排列方式與密度為度量,給出了基于Voronoi層次樹結(jié)構(gòu)的點(diǎn)群綜合方法,確保了點(diǎn)群綜合前后在空間形態(tài)分布上的一致性。結(jié)合地理統(tǒng)計(jì)學(xué)計(jì)算,對綜合方法作了進(jìn)一步的量化評估與優(yōu)化。經(jīng)驗(yàn)證,本文方法是可行、有效的。

點(diǎn)群綜合;權(quán)重;空間聚類;層次Voronoi圖;樹結(jié)構(gòu)

1 引 言

點(diǎn)群綜合的目的是在點(diǎn)數(shù)目減少的情況下盡量正確表達(dá)點(diǎn)群的整體信息,即采用一定的模型或算法從原始的點(diǎn)群中抽取出含有一定數(shù)量點(diǎn)的子集合。當(dāng)制圖對象的質(zhì)量、數(shù)量特征過于詳細(xì)時,就要采取聚類和擴(kuò)差措施進(jìn)行概括,減少其質(zhì)量和數(shù)量特征的差別,以達(dá)到地物類別清楚、層次分明的效果[1]。

許多學(xué)者對點(diǎn)群目標(biāo)的綜合選取進(jìn)行了不同方法的試驗(yàn)與研究。目前,基本方法是首先對點(diǎn)的重要性進(jìn)行判斷,然后以取舍方式進(jìn)行點(diǎn)群綜合。該方法存在一定的弊端,例如點(diǎn)狀居民地選取算法不能很好地處理拓?fù)湫畔?而基于Voronoi圖的綜合算法又沒有考慮到點(diǎn)的重要性程度[2-7]。基于以上考慮,本文結(jié)合聚類方法提取聚類中心點(diǎn),并用層次Voronoi圖結(jié)構(gòu)逐步細(xì)化地表達(dá)聚類中心點(diǎn),進(jìn)而實(shí)現(xiàn)點(diǎn)群由繁到簡綜合。通過采取逐層次的聚類中心點(diǎn)概括,更加便于點(diǎn)群分布表達(dá)與拓?fù)鋷缀涡畔⒂?jì)算,而且可以有效實(shí)現(xiàn)類簇點(diǎn)的圖形化,優(yōu)化點(diǎn)群綜合過程。

2 層次Voronoi圖

2.1 空間點(diǎn)群權(quán)重值分配

空間點(diǎn)的權(quán)重值反映了該空間點(diǎn)在空間點(diǎn)群整體中的個體重要程度。集合P＝{p1,p2,…, pn}代表二維空間的點(diǎn)群整體,其中,空間點(diǎn)pi∈P描述為平面坐標(biāo)(xi,yi)形式。集合P中共有n個空間點(diǎn),采用歐氏距離作為權(quán)重度量確定點(diǎn)群中各點(diǎn)的權(quán)重值[8]。使用n×n形式的距離矩陣D表達(dá)空間點(diǎn)群中點(diǎn)之間的距離關(guān)系

距離矩陣D是對角線元素為0的對稱矩陣,即D＝DT,dii＝0,dij＝dji。其中dij表示點(diǎn)pi到點(diǎn)pj的歐氏距離。dis(·)為歐氏距離算子,dij計(jì)算如式(2)

點(diǎn)pi與點(diǎn)群P中各點(diǎn)的距離之和等價于行向量μi的各元素之和

根據(jù)式(3),點(diǎn)群P中各點(diǎn)之間所構(gòu)成的距離總和為

以點(diǎn)pi距離和與點(diǎn)群P的距離總和之比為權(quán)重,點(diǎn)pi的權(quán)重值wi描述為式(5)

此處,因各點(diǎn)的權(quán)重值均為與點(diǎn)群P的距離總和之比,所以,滿足歸一化條件,即各點(diǎn)權(quán)重值之和為1。

2.2 空間點(diǎn)群聚類

點(diǎn)群聚類將點(diǎn)群劃分為簇(cluster)的過程,使得位于不同簇中的點(diǎn)之間差別較大,而處于同一簇中的點(diǎn)之間具有較小的差異。點(diǎn)群聚類算法多數(shù)是以距離為基礎(chǔ)的簇識別過程,最為典型的是k-means算法[9]。本文采用戴維斯·鮑爾丁指數(shù)(Davies Bouldin index,DBI)[10]來判定當(dāng)前聚類結(jié)果是否達(dá)到最優(yōu)。DBI指數(shù)的物理意義是簇內(nèi)之間距離之和與簇外之間距離之比,能夠有效地使k-means算法得到整體最優(yōu)解?？臻g點(diǎn)群聚類算法過程如下:

輸入:空間點(diǎn)群集合P。

輸出:空間類簇集合R。

(1)對于任意?pi∈P,根據(jù)式(1)計(jì)算距離矩陣D并得出行向量μi,將行向量μi的元素按降序排列,取前兩個值與其對應(yīng)的兩個點(diǎn)p1、p2,作為初始聚類中心o1←p1、o2←p2,并將聚類中心置于數(shù)組cluster Array←o1、o2。

(2)根據(jù)式(2),對于任意?pi∈P,?oi∈cluster Array,分別計(jì)算出pi到元素oi的距離值,并以到聚類中心的距離最小為原則,將pi分類,標(biāo)記類別,并置于數(shù)組class Array←pi。

(3)根據(jù)文獻(xiàn)[10],計(jì)算此時的class Array中的類簇最大相似度均值,置于curr Index。

(4)遍歷數(shù)組class Array:①根據(jù)式(2),計(jì)算pi至各聚類中心的最小距離,并構(gòu)成序列O (min(dis(o1,pi),dis(o2,pi),…,dis(on,pi));②取O中的最大值及其相關(guān)點(diǎn)oi。

(5)計(jì)算class Array中的類簇最大相似度均值,置于newIndex。

(6)如果currIndex＜new Index,將距離cluster Array中各聚類點(diǎn)最遠(yuǎn)的數(shù)據(jù)點(diǎn)oi置入cluster Array,cluster Array←oi,返回至步驟(2)。

(7)如果currIndex≥newIndex,根據(jù)式(5),計(jì)算各聚類中心點(diǎn)的權(quán)重值,輸出聚類結(jié)果集R。

(8)算法結(jié)束。

2.3 空間點(diǎn)群的層次Voronoi圖

用Voronoi圖數(shù)據(jù)結(jié)構(gòu)進(jìn)行空間點(diǎn)群的二維空間剖分。首先,點(diǎn)的Voronoi子區(qū)域?yàn)辄c(diǎn)的凸域(convex domain)表達(dá),并且點(diǎn)與其凸域之間為一一對應(yīng)關(guān)系;其次,Voronoi圖是一種無縫隙無重疊的連續(xù)空間覆蓋,可以消除層次結(jié)構(gòu)邊界的二義性;第三,可避免長、寬比率過高的子區(qū)域出現(xiàn),能夠更好地真實(shí)表達(dá)點(diǎn)群在空間上的形態(tài)分布。

以點(diǎn)群聚類中心為支撐,可以有效地刻畫點(diǎn)群層次性,即每一層次的聚類中心點(diǎn)可順序地構(gòu)成點(diǎn)群由總體粗略至局部細(xì)致的表達(dá)。以每一層聚類中心點(diǎn)構(gòu)成的普通Voronoi圖為基礎(chǔ),存在某一層次聚類中心點(diǎn)群C,并且,由C構(gòu)成普通Voronoi圖,vor(C)＝{vor(c1),vor(c2),…,vor(cn)}。設(shè)每個聚類中心點(diǎn)的Voronoi子區(qū)域內(nèi)存在聚類中心點(diǎn)群C′。給出層次Voronoi圖的定義如下。

定義2中,式(8)說明上層某一聚類中心的Voronoi子區(qū)域包含下層聚類中心點(diǎn)群。與此同時,式(9)說明下層聚類中心點(diǎn)群的Voronoi子區(qū)域的并集等價于它們所對應(yīng)的上層聚類中心點(diǎn)的Voronoi子區(qū)域。引入加權(quán)重距離(additively weighted distance,AWD)[13-15]進(jìn)一步描述聚類中心點(diǎn)的Voronoi子區(qū)域

式中,ci為某一聚類中心點(diǎn);wi為根據(jù)式(8)得到ci的類簇權(quán)重值,即ci的Voronoi子區(qū)域所包含的下一層次聚類中心點(diǎn)的權(quán)重值之和。

普通Voronoi圖(實(shí)心點(diǎn)群)與權(quán)重Voronoi圖(空心點(diǎn)群)的示例,如圖1所示。

圖1 普通Voronoi圖與權(quán)重Voronoi圖Fig.1 Ordinary Voronoi diagram and weighted Voronoi diagram

將每一層次的聚類中心點(diǎn)集合C表達(dá)為普通Voronoi圖數(shù)據(jù)結(jié)構(gòu),進(jìn)而將其描述為樹結(jié)構(gòu)的結(jié)點(diǎn),結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)描述如下:

其中,_center為二維點(diǎn)類型〈id,x,y〉,用于存儲當(dāng)前的聚類中心點(diǎn);_regions為二維面類型〈id, point Array〉,用于存儲聚類中心點(diǎn)的Voronoi子區(qū)域;_lev描述當(dāng)前層節(jié)點(diǎn)位于樹結(jié)構(gòu)中的層次; _wt記錄當(dāng)前節(jié)點(diǎn)的權(quán)重值;_dis記錄當(dāng)前結(jié)點(diǎn)與其父節(jié)點(diǎn)的距離值;_rad記錄當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)的角度值;_childs代表當(dāng)前節(jié)點(diǎn)的葉子節(jié)點(diǎn),為tree Node類型的數(shù)組。

根據(jù)以上定義與樹結(jié)構(gòu)結(jié)點(diǎn)描述,層次權(quán)重Voronoi圖可描述為層次Voronoi圖樹結(jié)構(gòu)(Voronoi hierarchical tree,VHT),如圖2所示。需要說明的是,鑒于點(diǎn)群在空間分布上的不均勻性,VHT樹結(jié)構(gòu)整體表現(xiàn)為非平衡多叉樹(nonbalanced and multi-way tree)形式,即處于樹結(jié)構(gòu)同一層中的結(jié)點(diǎn)所包含的孩子節(jié)點(diǎn)數(shù)不相同,并且,各葉子結(jié)點(diǎn)的層數(shù)不相同。

圖2 層次Voronoi圖的樹結(jié)構(gòu)Fig.2 Tree of hierarchical Voronoi diagram

3 層次Voronoi圖的點(diǎn)群綜合方法

點(diǎn)群是空間分布分析的主要對象,點(diǎn)群分布的定量特征主要由分布范圍、排列方式和密度3個方面決定[16-20]。

3.1 分布范圍(scope)

由于空間點(diǎn)群分布的不規(guī)則性,需要一種能夠根據(jù)點(diǎn)群的分布特點(diǎn)來實(shí)現(xiàn)點(diǎn)群分布范圍表達(dá)的圖形結(jié)構(gòu)。根據(jù)上述基于聚類的權(quán)重層次Voronoi圖結(jié)構(gòu),能夠有效地描述點(diǎn)群分布趨勢。在VHT樹中,以父節(jié)點(diǎn)的權(quán)重值表示該點(diǎn)群的分布范圍,通過權(quán)重Voronoi圖將其分布范圍以區(qū)域面積大小的形式表達(dá)并計(jì)算。設(shè)VHT樹結(jié)構(gòu)的當(dāng)前層存在n個結(jié)點(diǎn),并且當(dāng)前結(jié)點(diǎn)為node,那么,node的分布范圍大小由下式計(jì)算式中,node〈wi〉為當(dāng)前結(jié)點(diǎn)的權(quán)重值;area(node)為當(dāng)前結(jié)點(diǎn)的權(quán)重Voronoi子區(qū)域面積值。

3.2 排列方式(arrangement)

以正北方向?yàn)闃?biāo)準(zhǔn)方向,按順時針順序,以父節(jié)點(diǎn)C為中心,其子節(jié)點(diǎn)與父節(jié)點(diǎn)的相對象限位置為橫軸,子節(jié)點(diǎn)與父節(jié)點(diǎn)的相對方位角度為縱軸,抽象表達(dá)出點(diǎn)群的排列方式,如圖3—圖5所示。

圖3 環(huán)狀排列Fig.3 Circular arrangement

圖4 條帶狀排列Fig.4 Banded arrangement

圖5 塊狀排列Fig.5 Massive arrangement

從描繪的曲線圖中可得出,圖3在整個象限上弧度值均有分配,全局上呈現(xiàn)出連續(xù)分布,據(jù)此推斷出此點(diǎn)群的排列方式為中心環(huán)狀分布。如果弧度值的分配集中于象限的兩端,即弧度值在各自的象限邊界處連續(xù),如圖4所示,則此點(diǎn)群為按條帶狀分布排列。若點(diǎn)群的弧度值在整體范圍內(nèi)的某一局部區(qū)域內(nèi)連續(xù),則點(diǎn)群是按塊狀方式排列,如圖5所示。通過點(diǎn)群方向的變差函數(shù)(γ?),可確定點(diǎn)群的排列方式以及空間點(diǎn)群間的拓?fù)溧徑?/p>

式中,?為角度參數(shù);Z(x)與Z(x＋?)為區(qū)域化變量;N(?)為點(diǎn)對數(shù)目。

在層次權(quán)重Voronoi圖中應(yīng)用自適應(yīng)聚類算法,可以確定點(diǎn)群類簇點(diǎn)的排列方式,進(jìn)而確定其內(nèi)部點(diǎn)的排列方式。通過聚類運(yùn)算獲得的類簇點(diǎn)坐標(biāo)確定相對的位置和方向、通過構(gòu)造的點(diǎn)群拓?fù)浒P(guān)系可確定點(diǎn)之間的拓?fù)潢P(guān)系。

3.3 密度控制(density)

點(diǎn)群綜合的整體性特征要求是,在點(diǎn)群密集的區(qū)域綜合后仍然保持相對密集,而稀疏區(qū)域仍然保持相對的稀疏。相對于VHT樹的根節(jié)點(diǎn),取樹結(jié)構(gòu)第2層中的最小權(quán)重值節(jié)點(diǎn)min (nod ei)為基準(zhǔn),統(tǒng)計(jì)其Voronoi子區(qū)域中包含的點(diǎn)目標(biāo)個數(shù)num,計(jì)算如下

式中,vor為結(jié)點(diǎn)的Voronoi子區(qū)域邊界所包含的點(diǎn);nod ei(·)為結(jié)點(diǎn)Voronoi區(qū)域子區(qū)域范圍所包含的點(diǎn)?？紤]綜合前后比例尺的變化,該節(jié)點(diǎn)下的綜合目標(biāo)點(diǎn)個數(shù)num(P′)需滿足以下條件

式中,S為原始比例尺;S′為綜合比例尺。根據(jù)該結(jié)點(diǎn)所包含的綜合節(jié)點(diǎn)總數(shù),計(jì)算該結(jié)點(diǎn)分支下需要剖分的層次數(shù),即決定結(jié)點(diǎn)分枝樹的層數(shù)。該層次中的其他節(jié)點(diǎn)與該最小權(quán)重值節(jié)點(diǎn)需滿足以下條件

式中,min(·)代表層次中面積最小的Voronoi子區(qū)域。確定其節(jié)點(diǎn)的點(diǎn)群目標(biāo)綜合后的數(shù)據(jù)點(diǎn)個數(shù)相對于最小節(jié)點(diǎn)綜合數(shù)據(jù)點(diǎn)的倍數(shù)

根據(jù)m值,進(jìn)而確定其分支樹的層次,以保證綜合后的密度疏密程度和原始數(shù)據(jù)相一致。在式(16)與式(17)中,nod eki為根節(jié)點(diǎn)下第k個權(quán)重子節(jié)點(diǎn); m為當(dāng)前層中面積最小的Voronoi子區(qū)域所包含的聚類中心數(shù)與當(dāng)前層聚類中心點(diǎn)數(shù)之比;num (nod eki)為結(jié)點(diǎn)nod ei的Voronoi子區(qū)域所包含的數(shù)據(jù)點(diǎn)個數(shù);num(nod eki′)為點(diǎn)群綜合后結(jié)點(diǎn)nod ei的Voronoi子區(qū)包含的數(shù)據(jù)點(diǎn)個數(shù)。

4 算例與分析

算例由空間點(diǎn)群聚類、層次加權(quán)Voronoi圖構(gòu)建、VHT樹構(gòu)建與點(diǎn)群綜合方法4個部分構(gòu)成,相關(guān)數(shù)據(jù)結(jié)構(gòu)與算法在Visual Studio 2010 C＃、ESRI ArcGIS Engine 10環(huán)境實(shí)現(xiàn)。根據(jù)給定的點(diǎn)群數(shù)據(jù),首先得到點(diǎn)群的最小外接矩形(minimum boundary rectangle,MBR)代表計(jì)算域,由聚類的類簇點(diǎn)建立權(quán)重Voronoi圖,并在每個權(quán)重Voronoi圖形中順次調(diào)用聚類算法、權(quán)重點(diǎn)的層次Voronoi圖剖分方法,建立VHT樹結(jié)構(gòu),進(jìn)而實(shí)現(xiàn)空間點(diǎn)群的不同層次綜合。

如圖6所示,圖6(a)為1∶50 000比例尺云南省騰沖市居民地點(diǎn)群目標(biāo)數(shù)據(jù),共計(jì)1000個數(shù)據(jù)點(diǎn);圖6(b)為第1次點(diǎn)群聚類與權(quán)重Voronoi圖剖分結(jié)果,可以看出點(diǎn)群分布由4個聚類中心點(diǎn)表示;圖6(c)為對每個權(quán)重Voronoi子區(qū)域進(jìn)行再次聚類、剖分,每個子區(qū)域內(nèi)點(diǎn)數(shù)量增加,此時,由第1次的4個聚類中心點(diǎn)擴(kuò)展到11個聚類中心點(diǎn),由于具有層次性,因此,這11個點(diǎn)分別代表點(diǎn)群在4個Voronoi子區(qū)域內(nèi)的分布趨勢;圖6(d)是第3次Voronoi綜合后的結(jié)果,可以看出,點(diǎn)群在第3層次被細(xì)化表達(dá)為49個聚類中心,且是第2層11個Voronoi子區(qū)域的細(xì)化,聚類中心與原始點(diǎn)群在點(diǎn)密度上、分布上趨于一致。

多數(shù)地理現(xiàn)象都具有空間相關(guān)特性,即距離越近的兩事物越相似。在實(shí)際應(yīng)用中,各向異性現(xiàn)象表現(xiàn)更為普遍,即將方向因素納入考慮范疇時,有可能在某個方向距離更遠(yuǎn)的事物存在更大的相似性,這種現(xiàn)象被稱為半變異和協(xié)方差分析中的方向效應(yīng)。

圖6 層次Voronoi圖的點(diǎn)群綜合過程Fig.6 Process of point group generalization based on hierarchical Voronoi

如圖7—圖9所示,以提取出數(shù)據(jù)的東北—西南方向?yàn)槔?獲得點(diǎn)群對的半變異云圖(semivariogram/covariance cloud),其中縱坐標(biāo)γ為變異函數(shù)值,橫坐標(biāo)h為點(diǎn)對之間的距離。

圖7 第1次提取的半變異點(diǎn)對云圖Fig.7 The first covariance cloud

圖8 第2次提取的半變異點(diǎn)對云圖Fig.8 The second covariance cloud

圖9 第3次提取的半變異點(diǎn)對云圖Fig.9 The third covariance cloud

點(diǎn)群的范圍、排列、密度與幾何均值的參數(shù)統(tǒng)計(jì)如表1所示。

表1 點(diǎn)群綜合方法的評估參數(shù)Tab.1 Assessment parameters of point group generalization

試驗(yàn)表明,隨著剖分層次的遞增,對點(diǎn)群的表達(dá)會越來越詳細(xì)。據(jù)此,可針對不同比例尺地圖和實(shí)際需求提取不同程度的點(diǎn)群綜合圖,獲得滿足需求的比例尺地圖要素,避免點(diǎn)取舍過程的繁瑣判斷。

5 結(jié) 論

本文通過在層次Voronoi圖中應(yīng)用本文的自適應(yīng)聚類算法,實(shí)現(xiàn)了空間點(diǎn)群目標(biāo)的制圖綜合。該方法不僅無需獲得點(diǎn)群中點(diǎn)的重要性先驗(yàn)知識,而且可以表現(xiàn)出點(diǎn)群的空間范圍特征、點(diǎn)群的空間排列,以及點(diǎn)群在不同概括程度上的分布狀況。但具體的綜合要求、算法精度以及不同類型空間目標(biāo)之間的協(xié)調(diào)一致等問題還有待于作進(jìn)一步的研究。此外,層次Voronoi圖亦可作為空間索引與空間數(shù)據(jù)可視化的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu),如何構(gòu)建多路平衡形式VHT樹是非常值得關(guān)注的問題。

[1] MA Yongli.Cartography Course[M].Nanjing:Nanjing University Press,2003.(馬永立.地圖學(xué)教程[M].南京:南京大學(xué)出版社,2003.)

[2] YU Yanping,SHEN Jie,SHANG Zaiying.A Study on the Time Complexity of Point Cluster Selection and Simplification Algorithms[J].Journal of Nanjing Normal University:Natural Science Edition,2012,35(1):111-116.(于艷平,沈婕,尚在穎.點(diǎn)群選取與化簡算法時間復(fù)雜度研究[J].南京師范大學(xué)報:自然科學(xué)版,2012,35(1): 111-116.)

[3] WANG Jiayao,DENG Hongyan.A Model of Cartographical Generalization Based on Genetic Algorithm[J].Geomatics and Information Science of Wuhan University,2005, 30(7):565-569.(王家耀,鄧紅艷.基于遺傳算法的制圖綜合模型研究[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2005, 30(7):565-569.)

[4] QIAN Haizong,WU Fang,ZHANG Linlin,et al.Quality Assessment of Point Group Geometry Generalization with Polarization Transformation[J].Acta Geodaetica et Cartographica Sinica,2005,34(4):261-269.(錢海忠,武芳,張琳琳,等.基于極化變換的點(diǎn)群綜合幾何質(zhì)量評估[J].測繪學(xué)報,2005,34(4):261-269.)

[5] LU Yi,ZHAI Jingsheng,DU Jinghai,et al.Recognition, Measurement and Generalization for Point Cluster Features in Digital Nautical Chart[J].Geomatics and Information Science of Wuhan University,2001,26(2): 133-139.(陸毅,翟京生,杜景海,等.數(shù)字海圖點(diǎn)群狀特征的識別、量測與綜合[J].武漢大學(xué)學(xué)報:信息科學(xué)版, 2001,26(2):133-139.)

[6] GUO Qingsheng.Structuralizing Point Features and Its’s Application in Map Generalization[J].Journal of the PLA Institute of Surveying and Mapping,1999,16(3):210-213.(郭慶勝.點(diǎn)狀要素群的結(jié)構(gòu)化及其在綜合中的應(yīng)用[J].解放軍測繪學(xué)院學(xué)報,1999,16(3):210-213.)

[7] AI Tinghua,LIU Yaolin.A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J].Acta Geodaetica et Cartographica Sinica,2002,31(2): 175-181.(艾延華,劉耀林.保持空間分布特征的群點(diǎn)化簡方法[J].測繪學(xué)報,2002,31(2):175-181.)

[8] ELENA D,MICHEL M D.Encyclopedia of Distance[M].[S.l]:Luthaze Press,2009.

[9] GUO Qingsheng,ZHENG Chunyan,HU Huake.Hierarchical Clustering Method of Group of Points Based on the Neighborhood Graph[J].Acta Geodaetica et Cartographica Sinica,2008,37(2):256-261.(郭慶勝,鄭春燕,胡華科.基于鄰近圖的點(diǎn)群層次聚類方法的研究[J].測繪學(xué)報, 2008,37(2):256-261.)

[10] DAVIES D L,BOULDIN D W.A Cluster Separation Measure [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1979,1(2):224-227.

[11] CHEN Jun.Voronoi-based Dynamic Spatial Data Model[M].Beijing:Surveying and Mapping Press,2002.(陳軍.Voronoi動態(tài)空間數(shù)據(jù)模型[M].北京:測繪出版社,2002.)

[12] ZHAO Renliang.Voronoi Methods for Computing Spatial Relations in GIS[M].Beijing:Surveying and Mapping Press,2006.(趙仁亮.基于Voronoi圖的GIS空間關(guān)系計(jì)算[M].北京:測繪出版社,2006.)

[13] BALZER M,DEUSSEN O.Voronoi Treemaps[C]∥IEEE Symposium on Information Visualization 2005:INFOVIS.New York:IEEE,2005:49-56.

[14] DONG P L.Generating and Updating Multiplicatively Weighted Voronoi Diagrams for Point,Line and Polygon Features in GIS[J].Computers&Geosciences,2008,34(4):411-421.

[15] AURENHAMMER F,EDELSBRUNNER H.An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane[J].Pattern Recognition,1984,17(2):251-257.

[16] LIU Tao,DU Qingyun,YAN Haowen.Spatial Similarity Assessment of Point Clusters[J].Geomatics and Information Science of Wuhan University,2011,36(10):1149-1153.(劉濤,杜清運(yùn),閆浩文.空間點(diǎn)群目標(biāo)相似度計(jì)算[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2011,36(10):1149-1153.)

[17] BONAN L,FREDERICO F.TDD:A Comprehensive Model for Qualitative Spatial Similarity Assessment[J].Spatial Cognition and Computation,2006,6(1):31-62.

[18] CAI Y X,GUO Q S.Point Set Generalization Based on the Kohonet Net[J].Geo-spatial Information Science,2008, 11(3):221-227.

[19] LI Yulong,ZHU Huahua.Automated Recognition of Point Cluster Scope with Voronoi Diagram[J].Journal of Engineering Graphics,2007,28(3):73-77.(李玉龍,朱華華.應(yīng)用Voronoi圖的點(diǎn)群范圍自動識別[J].工程圖學(xué)學(xué)報, 2007,28(3):73-77.)

[20] PATRICIA F,RAY L,JOHN R.A Comparison of Geometric Approaches to Assessing Spatial Similarity for GIR[J]. International Journal of Geographical Information Science, 2008,22(3):337-360.

(責(zé)任編輯:叢樹平)

Point Group Generalization Method Based on Hierarchical Voronoi Diagram

Ll Jiatian,KANG Shun,LUO Fuli
Faculty of Land Resources Engineering,Kunming University of Science and Technology,Kunming 650093,China

The importance of the point is described by distance weight and the clustering center point of a point group is obtained by modified k-means algorithm.Furthermore,the clustering center is taken as base to construct hierarchical weighted Voronoi diagram and hierarchical tree structure.Distribution scope, arrangement,and density of the group is taken as the measurement to construct the point generalization method based on hierarchical Voronoi diagram tree structure,thus ensuring the consistency in spatial morphology before and after.Combination with geological statistics calculation,this generalization method is estimated and optimized.Finally,the practicability and availability of this method is confirmed through concrete experiment.

point group generalization;weight;spatial clustering;hierarchical Voronoi diagram; tree structure

Ll Jiatian(1975—),male,PhD, associate professor,majors in model of irregular space subdivision and algorithm in GlS.

P283

A

1001-1595(2014)09-1300-07

國家自然科學(xué)基金(41161061;40901197)

2013-06-03

李佳田(1975—),男,博士,副教授,研究方向?yàn)镚lS不規(guī)則空間剖分模型與算法。

E-mail:ljtwcx＠163.com

LI Jiatian,KANG Shun,LUO Fuli.Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J].Acta Geodaetica et Cartographica Sinica,2014,43(9):1300-1306.(李佳田,康順,羅富麗.利用層次Voronoi圖進(jìn)行點(diǎn)群綜合[J].測繪學(xué)報,2014, 43(9):1300-1306.)

10.13485/j.cnki.11-2089.2014.0166

修回日期:2014-01-01