基于ArcEngine的似Voronoi多边形生成方法

摘要：Voronoi图是对空间的一种无缝分割方式，是GIS空间分析中一个十分重要的工具，但是目前尚缺乏一些高效稳定的构建任意地理实体（点、线、面）Voronoi图的方法。本文在ArcGIS软件稳定生成点集V图功能的基础上，采用ArcEngine组件技术，利用C#开发语言构建了任意地理实体的似Voronoi图。

关键字：似Voronoi图；ArcEngine；空间分析

Voronoi结构是由俄国数学家M.G.Voronoi于1908年发现并以他的名字命名的。它的实质是一个不规则多边形剖分结构，每个多边形内的点到相应离散点的距离比其他离散点的距离要近。然而，Voronoi图的起源最早可以追溯到17世纪。1644年，R.Descartes用类似Voronoi图的结构显示太阳系中物质的分布。数学家G.L.Dirichlet于1850年同样研究过它，所以有时把Voronoi图又叫Dirichlet Tessellation[1]。在地理学界最先应用Voronoi图的是荷兰气象学家A.H.Thiesssen，他利用 Voronoi图研究气象观测站随机分布，所以这个多边形也被称为泰森（Thiesssen）多边形[2]。

Voronoi图是对空间的一种无缝分割方式，是一种十分重要的空间分析工具[3]。到20世纪60年代，Voronoi图概念在自然科学和社会科学中已被广为接受，但在算法研究领域，多数集中在离散点集上，目前仍然缺乏一些简单的高效稳定的构建任意发生元Voronoi图的方法，为此本文利用文献[3， 4]的思想，采用ArcEngine组件技术构建了任意地理实体（点、线、面）的Voronoi图，以满足地理信息系统中空间分析的需要。

1.Voronoi图生成方法

Voronoi图按照对象集合中元素的最近属性将空间划分成许多单元区域，有着按距离划分邻近区域的普遍特性，因此它应用领域非常广阔，也得到了广泛研究，产生了生成V图的多种方法。对其构造算法的研究，从对象的几何属性分类，有点生成方法、线生成方法[5， 6]和面生成方法[5， 7]；从生成算法的方式分类，有直接方法和间接方法[2]；从生成算法的特点分类，有矢量方法和栅格方法[3]。

2.基于GIS軟件生成任意目标似Voronoi图的总体思想

目前，点状要素的Voronoi图生成算法已经成熟，虽然我们尚不能直接构建复杂地理实体的Voronoi图，但是可以将复杂形状的地理实体分解为点集来处理。文献[3]给出了一般图形Voronoi图的构建方法——近似构造法，其基本思想是，用有限点来逼近原始图形（目标对象），从而代替原始图形，然后构建这些离散点集的Voronoi图，最后消除一些多余的Voronoi边和多余的Voronoi顶点，最终得到原始图形的逼近Voronoi图。

基于GIS软件的基本步骤：

第一步，对于每个原始目标（线、面）Ai，用有限的点集Pi来逼近Ai的边界，即在Ai边界上增加节点，并转换为点集；

第二步，构建所有点集P的Voronoi图V；

第三步，从V中消除那些属于同一目标点集所产生Voronoi边和那些孤立的点；

第四步，输出V图。

但是，这种方法只能生成以点集包络矩形（Envelope）为边界的V图，因此它只能作为一种表现形式，不能作为空间分析的工具。因为所有的地理分析都是在一定的区域范围内进行的，而区域的形状是多样的。为了生成目标区域边界V图，还必须将上述第三步后的V图与目标区域求交，但是如果V图的包络矩形的范围小于目标区域包络线范围，这种情况下得到的V图见图1（粗线为目标区域边界），很明显这种V图也不能满足地理分析的需要，因此在上述第三步中须生成以目标区域包络矩形为边界的V图。

对于近似构造法，拟合点数量越多，近似程度就越好，但是由于受时间、空间的限制，不可能无限度地使用大量拟合点，因此近似构造法关键的问题是如何设置拟合点，文献[3]并没有给出设置拟合点的原则。关于如何设置拟合点可以参考文献[ 4]，文献提出了用点近似V图与一般V图中对应Voronoi多边形的面积作为近似程度的度量的观点，即用两者面积差的大小来衡量近似程度的高低，并建立了面积差与拟合点间距的数学模型。

3.基于ArcEngine实现任意目标似V图的算法

ArcEngine是ESRI公司推出的一组完备的并且打包的嵌入式GIS组件库和工具库，不依赖ArcGIS Desktop桌面平台，直接安装ArcEngine Runtime和DeveloperKit后，即可利用其在不同开发语言环境下开发，具有简洁、灵活、易用、可移植性强等的特点。因此，我们可以充分利用ArcGIS软件稳健生成点状要素Voronoi图、多边形的融合等功能来实现任意复杂地理实体的普通Voronoi图的构建。

本文利用ArcEngine（10.1）组件，采用C#.Net（2008）开发语言，实现了任意复杂地理实体的普通近似Voronoi图。其算法流程图如图2所示。

算法流程具体描述如下：

（1）要素边界插入节点。获取需要生成V图的图层（主要指线、面图层）后，通过要素Densify（double，double）方法给要素边界按一定距离插入节点，该方法的第一个参数是距离阈值，其值可以根据实际对Voronoi图精度的需要来确定；第二个参数是最大偏差值，偏差为0 时表示距离阈值按边界曲线计算。

（2）将节点生成点要素。首先通过InMemoryWorkspaceFactoryClass类在计算机内存中创建工作区，然后通过IFeatureWorkspace.CreateFeatureClass方法建立一个点要素类，并生成点图层，最后将IPointCollection接口获得的要素边界节点存入点图层中。

（3）构建点集V图。利用ITinNodeCollection.ConvertToVoronoiRegions方法生成點集V图，该方法有五个参数，第一个IFeatureClass为空的面要素类，用于写入V多边形；第二个参数 ITinFilter为过滤条件（本文设置为null，即让所有的点都参与V图计算）；第三个参数IPolygon为Clip多边形，值得注意的是，如果将此参数设置为目标区域多边形，那么就不用进行（5）的操作，通过实验发现这种方式的效率极低，因此，本文将此参数设置为目标区域的包络矩形；第四个参数 string为Tin中点集索引字段；第五个参数 string位Tin点集标识字段，也就是点集V图融合字段。

（4）点集V图融合操作。这步是将（3）中产生的点集V图按标识字段进行融合，用到的方法主要是ITopologicalOperator.ConstructUnion，该方法的唯一参数是IEnumGeometry，即按标识字段获得的V多边形集合，合并操作完成后，需删除点集的Voronoi多边形，否则会产生冗余多边形。

（5）V图求交。这属于GIS矢量图层的叠加操作，在ArcEngine中也有多种方法可以实现，本文提供两种简便方法，第一种是采用ITopologicalOperator.Intersect的方法；第二种是通过Geoprocessor类调用ESRI.ArcGIS.AnalysisTools.Intersect工具，这种方法相对第一种更加简单，效率较高。

4.实例与分析

为了验证该方法的可行性，笔者以数字湘西州1：2000DLG数据中面状要素（居民地）为例予以说明，并与利用ModelBuilder数据建模工具建立的似V图模型进行时间复杂性的对比分析。本文选取的距离阈值分别为：4m、8m、12m、16m、20m，节点个数分别为：13542个、8452个、6831个、5707个、5366个。然后分别用AE算法和似V图模型构建了Voronoi多边形，实际计算结果如表1所示（Pentium（R）处理器 @ 3.20GHz，2.00内存），图3是依据计算结果绘制的折线图。

从计算结果中可以清楚的看出，虽然都是基于ArcGIS软件，但采用AE的方法在时间效率上明显高于似V图模型（ArcToolBoxs中的分析工具）。通过对生成似V图的每一步分析发现，在构建以目标区域包络矩形为边界的点集V图上耗时较多，AE算法约占整个算法的85%，而似V图模型则占90%左右。该方法易于实现，但其时效性由ArcGIS软件自身决定。关于插值距离如何确定，可以参考文献[4]的公式（3.3），也可根据其应用领域的精度要求进行设置。

结束语

Voronoi图可以提供诸如影响范围、邻近、局域动态、几何重要度衡量等重要特性，因而具有广泛的应用领域。本文基于ArcEngine构建任意地理实体似Voronoi图的方法，能够稳健地生成复杂地理实体（线状要素和面状要素）的近似Voronoi图，在一定误差范围内基本上能满足大多GIS分析的需要。

参考文献

[1] 杨承磊. 多边形的Voronoi图及其应用研究[D]. 山东大学， 2004.

[2] 王家耀，李志林，武芳. 数字地图综合进展[M]. 北京： 科学出版社， 2011.

[3] 王新生，刘纪远，庄大方，等. 基于GIS的任意发生元Voronoi图逼近方法[J]. 地理科学进展. 2004， 23（4）： 97-102.

[4] 张有会，浅野哲夫，小保方幸次. 关于一般图形Voronoi图的近似构造法的研究[J]. 数值计算与计算机应用. 2002， 9 （3）： 216-225.

[5] 王新生，李全，郭庆胜，等. Voronoi图的扩展、生成及其应用于界定城市空间影响范围[J]. 华中师范大学学报（自然科学版）. 2002， 36（1）： 107-111.

[6] 董蕊. 线段加权Voronoi图的离散生成[D]. 河北师范大学， 2006.

[7] 李成名，陈军. 面条目标Voronoi图生成的动态距离变换策略[J]. 遥感信息. 2000（1）： 6-11.

作者简介：张奎（1986-），男，硕士，2012年毕业于武汉大学地图学与地理信息系统专业，目前主要从事“数字城市”建设与应用和测绘管理等工作。