对Voronoi图生成矢量和栅格算法分析评价.docVIP

对Voronoi图生成矢量和栅格算法分析评价 　　[摘 要]对现有Voronoi图的生成算法进行深入研究,从多种角度对Voronoi图生成的矢量算法和栅格算法进行了分析,并针对这两种算法的优点与不足进行了比较和评价。 　　[关键词]Voronoi图 基于矢量的算法 基于栅格的算法 算法评述 　　[中图分类号]O1 [文献标识码]A [文章编号]1009-5489(2009)12-0198-03 　　 　　Voronoi图在不同的科学领域都有应用和发展,许多人对Voronoi图进行了综述和评价。Aurenhammmer于1991年发表了一篇关于Voronoi图的历史、定义、性质、算法、扩展和应用的综述。Fortune于1992年侧重对Voronoi图的算法进行了比较和分析。关于Voronoi图生成算法的文献已有很多,但很少涉及到Voronoi图生成的矢量和栅格算法比较分析。本文在介绍Voronoi图的基础上,侧重对这两种进行分析和评价。 　　 　　一、Voronoi图的定义 　　 　　Voronoi图是在计算几何中被广泛研究的一个问题,其原理非常简单,是一种由点内插生成面的方法。根据有限的采样点数据生成多个面区域,每个区域内,包含一个采样点,且各个面区域到其内采样点的距离小于任何到其他采样点的距离,那么该区域内其他未知点的最佳值就由该区域内的采样点决定,该方法也称最近邻点法,用于邻域分析。其几何定义为:假设P={P1,P2,...,Pn}(3≤n≤∞)是欧几里德平面上的一个离散点集,并且这些点不共线,四点不共圆,用d(Pi,Pj)表示点Pi,Pj的欧几里德距离。设x为点集P上的点,则区域V={x∈E2|d(x,pi)≤d(x,pj),j=1,2,...,n,j≠i}称为Voronoi多边形,各点的Voronoi多边形共同组成Voronoi图(如图1所示)。 　　图1 Voronoi图 　　 　　二、Voronoi图生成算法评价 　　 　　Voronoi图的构建构建方法很多,可归结为基于离散点的矢量坐标来实现和基于栅格的扩张原理来进行。 　　1.矢量Voronoi图生成算法评价 　　矢量Voronoi图的生成方法有多种,散见于国内外不同领域的研究刊物和文献上,如根据周培德研究,构建Voronoi图的矢量算法有分治算法、减量算法、增量构造算法、平面扫瞄算法、间接法等几种。 　　利用基于矢量方法生成Voronoi图,优点是:Voronoi数据的存储结构简单,存取便捷,便于实际应用。缺点是:①生成Voronoi图算法不仅计算复杂,而且占用的计算机空间开销大,由该类方法产生的数据结构复杂,其存储量可达到原几何数据的9～10倍,因此,虽然Voronoi图应用到GIS中使查询效率提高,但这种查询效率的提高是建立在空间开销增大基础之上的。②矢量法构建Voronoi图,处理的生成元只能是点和线(或半线),生成线集的Voronoi图比较困难,对于面和其他更复杂的空间目标要分解为点和线(半线)来处理,这种分解破坏了空间目标的完整性。③由于算法复杂,计算机难于实现,不易向高维目标或高维空间扩展。 　　Aurenhammer和Edelsbrunner提出了构建倍增的加权Voronoi图的算法,是一种基于矢量方法的算法,实现了点的加权Voronoi图,可基于这种算法,生成某省份多个城市(如河南省38个城市)的加权Voronoi图,分别计算一这些城市单元影响区的变化,一方面可得出城市中心性强度的差异性,另一方面也可直观地看出这些城市在空间分布上的不均衡性。 　　当前,较高版本的GIS软件(如Arc/Info)可以实现普通的Voronoi图,但在具体实现过程中仍存在着问题,如:美国的Gahegan和澳大利亚的Lee共同开发的软件可生成六种Voronoi图,用其开发的Demo软件课可实现点集的动态倍增的加权Voronoi图,但其演示效果并不理想,如,当点的数量较多时会出现错误。在对大量的点集或遇到复杂发生元的情况下,基于矢量方法的算法的有效性和稳健性受到限制,构建Voronoi图有一定的困难。 　　2.栅格Voronoi图生成算法评价 　　栅格Voronoi图的生成算法主要有距离变换算法、邻近栅格扩张法、栅格邻近归属法等几种。 　　利用基于栅格方法生成的栅格Voronoi图的优点表现在:①Voronoi图及其直线对偶的算法更容易从低维目标和低维空间向高维扩展。②处理GIS中线、面或更复杂的空间目标同处理点的方式方法一样。③基于栅格方法生成Voronoi图的算法复杂性小,易于在计算机上实现。 　　利用基于栅格方法生成的栅格Voronoi图的缺点表现在:①Voronoi数据的存储结构复杂,占据的存储空间大;②计算欧几里