一种基于空间层次分解的Hilbert码生成算法_陆锋(2)

一种基于空间层次分解的Hilbert码生成算法_陆锋

解来递归构造;

(3)单调性　在栅格格网中对于一个固定的x(y)坐标,其空间排列码值将随着y(x)方向上特定移动方向的变化而呈现单增或单减.

引效率也不相同.专家学者们曾先后对应用最广泛的Morton码、Gray码、Sierpinsky及Hilbert码空间排列进行了比较,结果显示,Hilbert空间排列的聚集性能最好[3,5,6],因而Hilbert空间排列已被应

[7]

用于空间数据库的几何索引中.

传统的Hilbert空间排列码生成算法由

[2]

Faloutsos和Roseman(1989)提出,这种算法是基于空间目标栅格格网行列数的二进制操作,复杂度为O(n),本文则提出一种栅格空间层次分解与区域状态转移向量相结合的Hilbert码算法,其复杂度为O(max(ni)).其中,ni为与空间目标二维笛卡尔坐标xi、yi所对应的栅格行列数值的二进制位数中的较大者.

2i

2　Hilbert空间排列码

Hilbert空间排列码源于经典的Peano曲线族.该Peano曲线族是闭合间隔单元I=[0,1]到闭合矩形单元S=[0,1]2的连续映射,也是所有能够填满二维或更高维空间的连续分形曲线的总称,故又称为空间填充曲线,它由意大利数学家Peano于1890年首先提出,德国数学家Hilbert于1891年首先给出了构造这种空间填充曲线的几何过程,并提出了所构造的空间填充曲线“处处连续,但处处不可导”的著名假设,直到1994年,才由Sagan将之证明

[11]

1　空间排列基本特征

空间排列(Spatialordering),或称空间聚集(Spatialclustering),可以定义为连续整数或关键字值与空间实体集元素之间可逆的一一对应关系[3].由于这些关键字值可以决定目标的遍历次序或目标地址,故又可称为空间排列码.它们起初是作为栅格数据模型中的一种目标组织方式而提出的,但近年来,随着GIS技术的不断发展,空间排列码在目标空间索引中的应用研究也不断深入,如今空间索引的栅格化已经成为GIS数据结构重要的发展方向之一[10].

空间排列码可以通过将连续空间进行细致划分,并以栅格象元的联接进而构造规则曲线的方式来得到.空间目标的排列码即为空间目标所占据的象元在规则曲线中的排列次序,它与空间的细分程度密切相关.

基于空间排列的多维数据一维映射方法可分为如下两种基本类型[4]:

(1)非递归方法,如行(列)序排列、行(列)主序排列、螺旋排列等;

(2)递归方法,如Morton排列、Gray码排列、Hilbert排列、Sierpinsky排列等.

与空间数据处理相关的空间排列码可以用以下3种特征来描述[3]:

(1)连续性　指空间排列码相邻的目标在栅格格网中所占据的象元必须相邻;

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科一种基于空间层次分解的Hilbert码生成算法_陆锋(2)全文阅读和word下载服务。