资源描述：
《几何邻近空间关系形式化描述与计算的voronoi方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、∗几何邻近空间关系形式化描述与计算的Voronoi方法1,2李佳田(1.国家基础地理信息中心,北京100044,ljtwcx@163.com)(2.中国矿业大学(北京校区)资源与安全学院,北京100083)摘要:以Voronoi图为工具,用拓扑与度量相结合的方法对几何邻近空间关系形式化描述.证明了几何邻近关系是一种目标集合等价关系,进而用Voronoi邻接图结构对其表达.在距离法确定影响邻元基础上,提出了基于Voronoi邻接图的几何邻近空间关系局部计算方法-V2,并以3种几何邻近空间查询为例对V2方法进行了验证.关键词:Voronoi图
2、;几何邻近;空间关系1引言根据空间目标之间是否具有公共部分,空间邻近关系可以分为两类,一类是空间相接目标之间的邻近关系,称为拓扑邻近(topologicaladjacency)或相邻(A
3、B⇔A∩B=∂A∩∂B≠∅);另一类是空间上不相连目标之间的邻近关系,其存在于相离目标之间,称为几何邻近(geometryadjacency)或相离(A
4、
5、B⇔A∩B=∅)(Gold,1992).邻近关系实质上由两部分构成,一部分是拓扑关系,另一部分是一种定性的度量关系.对于前者,可以通过它们之间的公共部分进行定义与区分,较为固定与明确.对于相离目标之间
6、的邻近关系,尤其是在空间目标不规则分布情况下,几何邻近往往具有一定的模糊性,其定义依赖于具体的应用环境,目前没有统一的定义与区分方法(Huangetal.,1999;Gahegan,2000).Gold(1994)从空间插值的角度给出了空间目标邻接(neighbors)的形式化定义.Zhaoetal.(2000)从空间分析与制图综合的角度对几何邻近关系做了较为详细的分析,将空间目标之间的欧氏距离用Voronoi距离代替来反映两目标的邻近情况,提出了Voronoik阶邻近的概念.然而,上述形式化描述不能用来反映一般意义下的几何邻近关系并且缺
7、少有效的计算方法.本文用Voronoi图对几何邻近空间关系进行形式化定义,并提出一种基于局部Voronoi图更新的几何邻近空间关系计算方法.2几何邻近的形式化定义与计算方法2.1几何邻近的形式化定义Voronoi图是对空间的一种剖分,得到的每一个空间目标的子空间(Voronoi多边形)是相互不重合的,所有子空间是对空间的一种铺盖.空间目标的Voronoi多边形是相互不重叠的.因此,任意两个Voronoi多边形之间只存在三种情况,点邻接(即共享Voronoi边界结点),线邻接(即共享Voronoi边界)与相隔(即没有公共部分).如图1所示.
8、运用维数扩展方法,将Voronoi多边形的交集的维数作为几何邻近关系的描述参数,对于点邻接,线邻接情况下的邻近关系定义如下.2定义1(半几何邻近)设P是中有限凸域上空间目标p1,p2,…,pn的集合pi,pj∈P(i≠j,i,j=1,…n),pi的Voronoi区域为V(pi),pj的Voronoi区域为V(pj).如果V(pi),V(pj)存在且为真(true),则称pi与pj之间存在半几何邻近关系,⇔Dim(V(pi)∩V(pj))=0.2定义2(直接
9、几何邻近)设P是中有限凸域上空间目标p1,p2,…pn的集合,pi,pj∈P(i≠j,i,j=1,…,n),pi的Voronoi区域为V(pi),pj的Voronoi区域为V(pj).如果V(pi),V(pj)存在且为真,则称pi与pj之间存在直接几何邻近关系,⇔Dim(V(pi)∩V(pj))=1.如图1(a)所示,点1与点2的Voronoi区域相交为1条Voronoi边(点划线),其维数为1,即点1与点2之间存在直接几何邻近关系.2定义3(Vorono
10、i距离)设P是中有限凸域上空间目标p1,p2,…pn的集合,pi,pj∈P(i≠j,i,j=1,…n),在其剖分后所形成的Voronoi图V(P)上,pi,pj的Voronoi区域分别为V(pi),V(pj),将V(pi)与V(pj)之间所经过∗基金项目:国家自然科学基金项目(40337055,40301042).指导教师:陈军,赵仁亮.的Voronoi边界及Voronoi结点(node)的最小维数和k称为空间目标pi与pj的Voronoi距离,记为vd(pi,pj),且vd(pi,pj)≥0;当pi=pj时,vd(pi,pj)=∅.如图
11、1(b)所示,从A的Voronoi区域到C的Voronoi区域最少要经过3条Voronoi边界,维数和为3,即它们之间有3阶几何邻近关系.而从A的Voronoi区域到C,D的Voronoi区域
