一種面向對象的模糊Voronoi圖動態生成方法

湯陽城，王長栓，朱文德

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

一種面向對象的模糊Voronoi圖動態生成方法

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

在對空間關系計算目標對象化的基礎上，根據 Voronoi圖的幾何特性，引入模糊思想，對基于活動像素主動生長技術生成的 Voronoi圖進行模糊處理，提出了一種面向對象的模糊Voronoi圖動態生成方法，為復雜的空間關系計算提供理論基礎和現實依據。

Voronoi；面向對象；模糊；空間關系

在地理信息系統中，空間關系的理論研究直接影響著地理信息系統的設計、開發和應用[1]，所以一直倍受重視。隨著對空間關系研究的不斷深入，傳統的空間關系計算方法和模型因其理論缺陷，無法滿足新時期地理對象間空間關系計算的要求。為了克服現有計算方法和模型的不足，本文在全面分析和比較現有空間關系計算模型優缺點的基礎之上[2-3]，引入面向對象理論，將空間關系的計算目標進行對象化處理。根據Voronoi圖良好的幾何特性，結合模糊思想，提出了一種面向對象的模糊Voronoi圖動態生成方法。

1 Voronoi圖的基本概念

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

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

圖1 傳統的Voronoi圖

2 面向對象Voronoi圖的動態生成

2.1 空間關系計算目標對象化

地理空間中，可將地理實體和現象抽象為空間對象，空間對象又可進一步區分為點對象、線對象、面對象、體對象、環對象和復雜子對象，空間對象可用一個四元組來表示[5]：

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

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

圖2 空間對象的組成結構及其相互聯系

2.2 基于活像素的主動生長技術

將研究空間中的空間生長對象抽象為像素，像素會在柵格空間的各個方向體現出生長特性。柵格空間中能夠在任意方向等速生長的像素稱之為活像素，遇到其他的活像素立即停止生長，當所有的活像素在各個方向都不再生長時，即生成空間對象的Voronoi圖。活像素周圍必存在空白像素，若像素周圍沒有空白像素則稱之為非活動像素。在Voronoi圖的生成過程中，只考慮活動像素，不考慮非活動像素，這樣可以減少冗余操作。與通過空間對象之間距離變化生成Voronoi圖的方法相比，該方法是通過柵格空間中活像素占領其周圍的空白像素，直到柵格空間不存在空白像素為止，從而動態生成Voronoi圖，是一種主動的Voronoi圖生長技術。活動像素與非活動像素的區分如圖3所示。

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

2.3 基于主動生長技術的Voronoi圖的生成過程

以生長技術為基礎，按照距離定義，計算活動像素和與之鄰近的空白像素之間的距離，若小于鄰近空白像素定義的柵格距離參數，則使用計算值代替鄰近空白像素的距離值，該空白像素變為活動像素；若大于或等于鄰近空白像素定義的柵格距離參數，則保持不變。當活動像素周圍不再存在空白像素時，活像素停止生長，并重新定義為非活動像素。活像素的生長原理可用式（3）表示：

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

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

圖4 面向對象Voronoi圖生成過程

3 面向對象模糊Voronoi圖的生成

3.1 面向對象Voronoi圖的模糊化處理

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

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

3.2 Voronoi圖的模糊隸屬度

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

確定R值后,就可以通過計算Voronoi多邊形的每條邊向內向外擴展模糊邊界對應的多邊形，每個模糊區域包含4個頂點。圖5為生成的面向對象的模糊Voronoi圖。

圖5 面向對象的模糊Voronoi圖

4 基于模糊Voronoi圖的面向對象空間關系計算方法

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

基于模糊Voronoi圖的面向對象空間關系計算的代數方法，其計算思路總結如下：

1）直接利用空間對象的整體進行處理。

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

3）引入多集合算子對空間對象進行集合操作。

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

空間對象本身和以其為生長對象所對應的模糊Voronoi區域作為該方法的操作對象，該方法的操作集由多集合算子組成。空間對象、模糊Voronoi區域和多集合算子共同形成一代數空間，如式（7）所示：

式中，O表示研究空間中的空間對象；V表示模糊Voronoi區域；λ表示多集合算子；SR表示代數空間中所存在的空間關系。空間對象之間的空間關系即為對O、V和λ的計算結果。

設Oi和Oj為研究空間中的空間對象，、分別表示空間對象Oi和Oj的模糊Voronoi區域，則空間對象Oi和Oj之間的空間關系表示如下：

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

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

5 結 語

Voronoi圖是用來解決地理空間中地理對象間空間關系計算的重要工具。本文在對空間關系計算目標對象化的基礎之上，根據 Voronoi圖本身的幾何特性，引入模糊思想，對基于活動像素主動生長技術所生成的 Voronoi圖進行模糊處理，構建面向對象的模糊Voronoi圖，再進行復雜的空間關系計算，能提高計算速率。

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

[2] 何建華,劉耀林.GIS中拓撲和方向關系推理模型[J].測繪學報,2004,33(2)：156-162

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

[4] 謝順平,馮學智,王結臣.基于網絡加權Voronoi圖分析的南京市商業中心輻射域研究[J].地理學報,2009,64(12)：1 467-1 476

[5] 李景文,田麗亞,張燕,等.面向對象的空間數據模型設計方法[J].地理空間信息,2011,9(5)：9-14

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

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

本 刊 聲 明

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

（本刊編輯部）

P208

B

1672-4623（2016）08-0026-03

10.3969/j.issn.1672-4623.2016.08.009

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

2016-05-05。

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