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

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

第5期陆　锋等:一种基于空间层次分解的Hilbert码生成算法467

空间填充曲线的排列次序及逐步细化过程如图1所示,其曲线所经过的包含空间目标点的栅格格网的次序,即称为空间目标点的Hilbert排列码,由于Hilbert排列码是递归的、连续的、非单调的,且它与四叉树兼容,故在行程编码中具有较高的效率

.

有较大的影响.

3　基于空间层次分解的Hilbert空间排列码生成算法　　经过对

Hilbert空间填充曲线特征的分析,提

出通过栅格空间的层次分解来生成Hilbert排列码,以降低算法的复杂度.该空间层次分解即是通过可迭代的规则方法来对空间进行逐步细化,并用规则栅格格网来铺满整个空间的过程,因而这种方法实质上是一种在构造Hilbert空间填充曲线过程的同时来生成Hilbert空间排列码的方法.

由于在层次空间分解过程中,每个格网尺寸完全一致,不存在栅格图象的线性四叉树生成中的重复检测问题(判断块内格网元素是否相同,以决定是否继续划分),从而为算法效率的提高奠定了基础.

此算法采用栅格空间层次分解与区域状态转移

图1　Hilbert空间填充曲线的排列次序及细化过程

向量相结合的方法,其中状态转移向量表明了空间层次分解中子曲线的旋转与反射.算法描述如下:

(1)设定初始状态向量,并判断目标所在象限,根据初始状态向量得到初始空间排列码;

(2)将目标所在象限等分为4个子象限,若子象限对应区域范围小于限定值,则返回;

(3)判断目标所在子象限,根据父象限空间排列码及状态转移向量,来决定子象限空间排列码,并重新设定状态转移向量;

(4)返回(2),对子象限进行递归分解.通过Hilbert空间填充曲线特征的分析可以看出,曲线共有4种子象限形态,其决定了状态转移向量共有4种取值方式,即{1,2,3,4}、{1,4,3,2}、{3,2,1,4}和{3,4,1,2},如图2所示.

经典的Hilbert码生成算法由Faloutsos和Roseman(1989)提出,由于这种算法是基于空间目标点所在的栅格格网行列数的二进制位操作,故其复杂度为O(n),其中ni为与空间目标点i所在最终栅格格网行列数中较大者所对应的二进制位数.算法描述如下:

(1)将索引栅格格网行列数采用二进制位交叉方法转化为对应Morton码;

(2)以两位为一个单位,由高位开始,对生成的Morton码中的10和11互换;

(3)由高位开始,设为ti,对后续各位作如下处理:若ti为00,则将后续各位中的11和01进行互换;否则,若ti为11,则将后续各位中的10和00进行互换;

(4)将结果按顺序排列,即为Hilbert空间排列码.如图1所示,Hilbert空间填充曲线虽可通过栅格空间的层次分解方法来构造,但上述Hilbert空间排列码算法并没有考虑Hilbert空间填充曲线的层次分解过程,而且它与Hilbert空间填充曲线的构造无关,它是完全在最终栅格层次上进行处理,因而是完全针对最终栅格空间状态,对空间目标点行列数所对应的二进制代码进行的代数运算.其中(2)、(3)两步形成一个ni×ni的二重循环,使得算法的时间复杂度为O(ni2).这样,当空间目标点距离栅[2,14]2i

图2　Hilbert空间填充曲线状态转移

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