一种面向对象的模糊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）。