湯陽城，王長栓，朱文德

（1.湖省國土測繪院，湖武漢 430010；2.廣西壯族自治區(qū)地理信息測繪院，廣西 柳州 545006）

一種面向?qū)ο蟮哪：齎oronoi圖動態(tài)生成方法

湯陽城1，王長栓2，朱文德2

在對空間關(guān)系計算目標(biāo)對象化的基礎(chǔ)上，根據(jù) Voronoi圖的幾何特性，引入模糊思想，對基于活動像素主動生長技術(shù)生成的 Voronoi圖進(jìn)行模糊處理，提出了一種面向?qū)ο蟮哪：齎oronoi圖動態(tài)生成方法，為復(fù)雜的空間關(guān)系計算提供理論基礎(chǔ)和現(xiàn)實依據(jù)。

Voronoi；面向?qū)ο?；模糊；空間關(guān)系

在地理信息系統(tǒng)中，空間關(guān)系的理論研究直接影響著地理信息系統(tǒng)的設(shè)計、開發(fā)和應(yīng)用[1]，所以一直倍受重視。隨著對空間關(guān)系研究的不斷深入，傳統(tǒng)的空間關(guān)系計算方法和模型因其理論缺陷，無法滿足新時期地理對象間空間關(guān)系計算的要求。為了克服現(xiàn)有計算方法和模型的不足，本文在全面分析和比較現(xiàn)有空間關(guān)系計算模型優(yōu)缺點的基礎(chǔ)之上[2-3]，引入面向?qū)ο罄碚?，將空間關(guān)系的計算目標(biāo)進(jìn)行對象化處理。根據(jù)Voronoi圖良好的幾何特性，結(jié)合模糊思想，提出了一種面向?qū)ο蟮哪：齎oronoi圖動態(tài)生成方法。

1 Voronoi圖的基本概念

將研究空間中的空間對象抽象為Voronoi 圖的生長對象，分別設(shè)為O1，O2，…，On，3≤n＜∞，將任意點的Voronoi圖定義為：

式中，V為Voronoi 圖；Oiv表示研究空間中的空間對象，即Voronoi 圖中的Voronoi 多邊形。所有空間對象的Voronoi多邊形構(gòu)成了研究空間的Voronoi 圖（如圖1）。該式是研究空間中Voronoi圖的最簡單的表達(dá)形式，在此基礎(chǔ)之上，根據(jù)空間生長對象自身或相互之間的一些屬性和特征，如距離、方向、維數(shù)和權(quán)重等，可對簡單的Voronoi圖進(jìn)一步研究得到距離Voronoi圖、方向Voronoi圖、球面Voronoi圖和權(quán)重Voronoi圖等。通過分析Voronoi圖及其圖形結(jié)構(gòu)的特征，Voronoi圖具有最鄰近特征、線性特征、勢力范圍特征、狄洛尼三角網(wǎng)（Delaunay 三角網(wǎng)）對偶特征、局域動態(tài)特性、層次性特征和認(rèn)知合理性特征，共6種特征。在利用Voronoi圖計算空間對象之間的空間關(guān)系時會起到重要作用[4]。

圖1 傳統(tǒng)的Voronoi圖

2 面向?qū)ο骎oronoi圖的動態(tài)生成

2.1 空間關(guān)系計算目標(biāo)對象化

地理空間中，可將地理實體和現(xiàn)象抽象為空間對象，空間對象又可進(jìn)一步區(qū)分為點對象、線對象、面對象、體對象、環(huán)對象和復(fù)雜子對象，空間對象可用一個四元組來表示[5]：

其中，ID為對象標(biāo)識；S表示空間對象所具有的屬性；C表示多種分類對象的集合；P（i）表示點對象集；L（i）表示線對象集；O（i）表示面對象集；B（i）表示體對象集；R（i）表示環(huán)對象集；Object（i）表示復(fù)雜子對象集；M表示對空間對象進(jìn)行操作的集合?？臻g對象定義后的對象標(biāo)識是唯一的，即ID唯一。若兩個空間對象的S和M相同，則稱這兩個空間對象相等，相同的空間對象的ID必須是相同的。空間對象的屬性與操作分為空間和非空間兩種表現(xiàn)形式（空間屬性、非空間屬性和空間操作、非空間操作）。

元對象是對地理空間中最小的空間對象的抽象，是無法繼續(xù)進(jìn)行分離歸類的最小單位。點元素、線元素和面元素是構(gòu)成元對象的基本3元素。通過對空間對象、元對象的分析，可以對空間對象的組成結(jié)構(gòu)以及相互關(guān)系進(jìn)行描述（如圖2）。

圖2 空間對象的組成結(jié)構(gòu)及其相互聯(lián)系

2.2 基于活像素的主動生長技術(shù)

將研究空間中的空間生長對象抽象為像素，像素會在柵格空間的各個方向體現(xiàn)出生長特性。柵格空間中能夠在任意方向等速生長的像素稱之為活像素，遇到其他的活像素立即停止生長，當(dāng)所有的活像素在各個方向都不再生長時，即生成空間對象的Voronoi圖?；钕袼刂車卮嬖诳瞻紫袼?，若像素周圍沒有空白像素則稱之為非活動像素。在Voronoi圖的生成過程中，只考慮活動像素，不考慮非活動像素，這樣可以減少冗余操作。與通過空間對象之間距離變化生成Voronoi圖的方法相比，該方法是通過柵格空間中活像素占領(lǐng)其周圍的空白像素，直到柵格空間不存在空白像素為止，從而動態(tài)生成Voronoi圖，是一種主動的Voronoi圖生長技術(shù)。活動像素與非活動像素的區(qū)分如圖3所示。

圖3 非活動像素與活動像素

2.3 基于主動生長技術(shù)的Voronoi圖的生成過程

以生長技術(shù)為基礎(chǔ)，按照距離定義，計算活動像素和與之鄰近的空白像素之間的距離，若小于鄰近空白像素定義的柵格距離參數(shù)，則使用計算值代替鄰近空白像素的距離值，該空白像素變?yōu)榛顒酉袼兀蝗舸笥诨虻扔卩徑瞻紫袼囟x的柵格距離參數(shù)，則保持不變。當(dāng)活動像素周圍不再存在空白像素時，活像素停止生長，并重新定義為非活動像素?；钕袼氐纳L原理可用式（3）表示：

式中，（i，j）表示柵格影像的中心像素；（p，q）表示柵格影像的結(jié)構(gòu)像素；（i+p，j+q）表示柵格影像中活動像素周圍的空白像素；d（p，q）為柵格影像所定義的柵格距離參數(shù)。

基于主動生長技術(shù)生成空間對象Voronoi圖的生成過程如圖4所示，圖中T表示柵格空間中活動像素的像素集。

圖4 面向?qū)ο骎oronoi圖生成過程

3 面向?qū)ο竽：齎oronoi圖的生成

3.1 面向?qū)ο骎oronoi圖的模糊化處理

本文采用基于活動像素的方法來生成Voronoi圖，以此為基礎(chǔ)，對具有模糊邊界的模糊Voronoi圖的基本定義如下[6]：

式中，VIOi是以O(shè)i為空間生長對象的具有帶狀模糊邊界的Voronoi多邊形；VOiF表示模糊區(qū)域；VOiN表示非模糊區(qū)域；VOi為初始的Voronoi多邊行為VOi的頂點集；為VOi的邊集合，Lk=VekVek+1（1＜k＜n-1），Ln=VenVe1，n為VOi頂點的總個數(shù)，也是總邊數(shù)。d（O，lk）為任意目標(biāo)到與其生長目標(biāo)Oi對應(yīng)的Voronoi邊Lk的直線距離；HVek是以O(shè)i為極點、水平向右的射線為極軸的極坐標(biāo)系中Voronoi頂點Vek的極角；R是由綜合考慮的各影響因子共同決定的一個比值。

3.2 Voronoi圖的模糊隸屬度

R值表示的即模糊區(qū)間的大小，它是綜合考慮各因素后確定的比值。R值作用的對象是Voronoi任意目標(biāo)O到其生長目標(biāo)Oi對應(yīng)的Voronoi邊Lk的直線距離d（O，lk）。Voronoi圖內(nèi)，隨著任意目標(biāo)O與空間生長對象Oi之間距離的增加，任意目標(biāo)O隸屬于對象Oi的可能性也隨之變小。但在傳統(tǒng)的Voronoi圖中，任意目標(biāo)O與空間生長對象Oi之間的距離并不能判定目標(biāo)O的隸屬問題。因此R值與d（O，lk）成正比，取值范圍為（0，1），當(dāng)R=0時，具有模糊邊界的Voronoi圖變?yōu)閭鹘y(tǒng)的Voronoi圖。

確定R值后,就可以通過計算Voronoi多邊形的每條邊向內(nèi)向外擴(kuò)展模糊邊界對應(yīng)的多邊形，每個模糊區(qū)域包含4個頂點。圖5為生成的面向?qū)ο蟮哪：齎oronoi圖。

圖5 面向?qū)ο蟮哪：齎oronoi圖

4 基于模糊Voronoi圖的面向?qū)ο罂臻g關(guān)系計算方法

在將計算目標(biāo)（空間對象）進(jìn)行分解從而計算空間關(guān)系的方法中，對研究空間中的空間對象按照一定的邏輯關(guān)系劃分為多個組成部分，通過比較不同空間對象的各組成部分之間的關(guān)系，來判定空間對象之間的空間關(guān)系。在此類方法中，4交和9交模型最為經(jīng)典。9交模型是在4交模型的基礎(chǔ)上引入空間對象的外部空間這一概念進(jìn)行改進(jìn)的方法，空間對象的外部即為空間對象的“補(bǔ)”[7]。在整個研究空間，除了空間對象本身，其他空間都為此空間對象的“補(bǔ)”，所以可以將研究空間抽象為由空間對象的內(nèi)部、邊界和補(bǔ)共同組成。在空間關(guān)系計算的實際操作中，空間目標(biāo)的“補(bǔ)”幾乎是無限的，而空間對象的內(nèi)部和邊界等概念又過于抽象，研究空間中包含了無數(shù)的空間數(shù)據(jù)，在這些空間數(shù)據(jù)中很難確定哪些是描述空間對象的“補(bǔ)”，哪些是描述空間對象內(nèi)部的數(shù)據(jù)，哪些是描述空間對象邊界的數(shù)據(jù)，雖然可以用空間對象的內(nèi)部、邊界和“補(bǔ)”來對空間關(guān)系進(jìn)行定義，但在實際應(yīng)用中卻很難進(jìn)行操作。本文采用基于目標(biāo)整體的空間關(guān)系計算方法，不再分解將要進(jìn)行空間關(guān)系計算的空間對象，而是直接考慮空間對象的整體，用模糊Voronoi區(qū)域替換空間對象的“補(bǔ)”，計算出空間對象之間存在的空間關(guān)系，不僅縮小了空間對象“補(bǔ)”的范圍，也在實際應(yīng)用中便于操作。并且，模糊Voronoi圖是對原Voronoi圖的Voronoi多邊形進(jìn)行模糊處理所得，簡化了處于Voronoi多邊形邊界的離散目標(biāo)空間關(guān)系的計算，在實際應(yīng)用中也便于操作。

基于模糊Voronoi圖的面向?qū)ο罂臻g關(guān)系計算的代數(shù)方法，其計算思路總結(jié)如下：

1）直接利用空間對象的整體進(jìn)行處理。

2）模糊Voronoi區(qū)域作為空間對象的外部。

3）引入多集合算子對空間對象進(jìn)行集合操作。

4）利用多集合算子的類型判定空間關(guān)系的異同。

空間對象本身和以其為生長對象所對應(yīng)的模糊Voronoi區(qū)域作為該方法的操作對象，該方法的操作集由多集合算子組成?？臻g對象、模糊Voronoi區(qū)域和多集合算子共同形成一代數(shù)空間，如式（7）所示：

式中，O表示研究空間中的空間對象；V表示模糊Voronoi區(qū)域；λ表示多集合算子；SR表示代數(shù)空間中所存在的空間關(guān)系。空間對象之間的空間關(guān)系即為對O、V和λ的計算結(jié)果。

設(shè)Oi和Oj為研究空間中的空間對象，、分別表示空間對象Oi和Oj的模糊Voronoi區(qū)域，則空間對象Oi和Oj之間的空間關(guān)系表示如下：

其中，λ表示空間對象Oi和Oj之間的空間關(guān)系可以通過多集合算子來計算。每個集合算子的結(jié)果取值是其操作算子的結(jié)果，主要包括內(nèi)容、維數(shù)、連通數(shù)等。

式中，σ記為操作算子；e記為操作算子的值；f為取值函數(shù)。內(nèi)容為空集和非空集只是粗略的量測結(jié)果。維數(shù)的最小值為-1，當(dāng)結(jié)果為空集時，取維數(shù)為-1，若結(jié)果不為空，則取最大維數(shù)值。連通數(shù)結(jié)果內(nèi)容為空集時，取值為0，結(jié)果內(nèi)容為非空集時，取值為自然數(shù)。這些不同的取值實質(zhì)上是一種層次化的空間關(guān)系結(jié)算途徑，在具體的操作過程中，按計算復(fù)雜程度，比較操作算子的值，直到滿足精度要求為止。

5 結(jié) 語

Voronoi圖是用來解決地理空間中地理對象間空間關(guān)系計算的重要工具。本文在對空間關(guān)系計算目標(biāo)對象化的基礎(chǔ)之上，根據(jù) Voronoi圖本身的幾何特性，引入模糊思想，對基于活動像素主動生長技術(shù)所生成的 Voronoi圖進(jìn)行模糊處理，構(gòu)建面向?qū)ο蟮哪：齎oronoi圖，再進(jìn)行復(fù)雜的空間關(guān)系計算，能提高計算速率。

[1] 閆浩文,郭仁忠.基于Voronoi的空間方向關(guān)系形式化描述研究[J].測繪科學(xué),2002(27)：1-2

[2] 何建華,劉耀林.GIS中拓?fù)浜头较蜿P(guān)系推理模型[J].測繪學(xué)報,2004,33(2)：156-162

[3] 謝順平,馮學(xué)智,魯偉.基于道路網(wǎng)絡(luò)分析的Voronoi面域圖構(gòu)建算法[J].測繪學(xué)報,2010,39(1)：88-90

[4] 謝順平,馮學(xué)智,王結(jié)臣.基于網(wǎng)絡(luò)加權(quán)Voronoi圖分析的南京市商業(yè)中心輻射域研究[J].地理學(xué)報,2009,64(12)：1 467-1 476

[5] 李景文,田麗亞,張燕,等.面向?qū)ο蟮目臻g數(shù)據(jù)模型設(shè)計方法[J].地理空間信息,2011,9(5)：9-14

[6] 邵振峰,閆貝貝,周楊,等.基于模糊思想的改進(jìn)Vornoi圖模型[J].武漢大學(xué)學(xué)報(信息科學(xué)版),2009,34(11)：1-2

[7] 李成名,陳軍.空間關(guān)系描述的9-交模型[J].武漢測繪科技大學(xué)學(xué)報,1997,22(3)：207-211

本 刊 聲 明

為適應(yīng)我國信息化建設(shè)，擴(kuò)大本刊及作者知識信息交流渠道，本刊數(shù)據(jù)已被《中國核心期刊（遴選）數(shù)據(jù)庫》《CNKI 中國期刊全文數(shù)據(jù)庫》和《中文科技期刊數(shù)據(jù)庫（全文版）》等收錄。在《地理空間信息》發(fā)表的論文均默認(rèn)將其在著作權(quán)保護(hù)期內(nèi)的復(fù)制權(quán)、發(fā)行權(quán)、匯編權(quán)、翻譯權(quán)以及網(wǎng)絡(luò)傳播權(quán)授權(quán)給《地理空間信息》編輯部，編輯部可將上述權(quán)利轉(zhuǎn)授給第三方使用。作者不再許可他人以任何形式使用該篇論文，但可以在其后續(xù)作品中引用（或翻譯）該論文中部分內(nèi)容或?qū)⑵鋮R編在作者的非期刊類文集中。如不同意，請事先聲明，本刊另作處理。其文章的著作權(quán)使用費與本刊稿酬一次性給付（已在收取發(fā)表費時折減和換算為雜志贈閱）。

（本刊編輯部）

P208

B

1672-4623（2016）08-0026-03

10.3969/j.issn.1672-4623.2016.08.009

湯陽城，工程師，主要從事地形測量、GPS測量、地理信息系統(tǒng)等方面的工作。

2016-05-05。

項目來源：廣西自然科學(xué)基金資助項目（2014GXNSFDA118032）。