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

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

468中国图象图形学报第6卷(A版)

　　由于状态转移向量的不同取值决定了后续子象限中子曲线的形态,也就决定了目标点所在子象限对应空间排列码,因此,算法的关键在于决定层次分解中状态转移向量的取值.

算法伪码如下:

f=0;scan-order=3;

//决定初始排列码和初始扫描序,扫描序决定状态向量inthilbert(a,b,p,scan-order)

//a,b为父象限角点,p为目标点{

if(b.x-a.x≤xtol||b.y-a.y≤ytol)return(f);

//子象限小于最终格网尺寸容限值则返回fc1=f 2;fc2=fc1+1;fc3=fc1+2;fc4=fc1+3;

//决定区域状态转移向量

t1=(a.x+b.x)/2;t2=(a.y+b.y)/2;

quadrant=locate-quadrant(a,b,p);//决定目标点象限switch(quadrant)

//根据所在子象限,决定扫描序和子象限排列码{

　　case1:

a.x=t1;a.y=t2;switch(scan-order){

//决定本层次目标点排列码及扫描序…}break;

　　…}

hilbert(a,b,p,scan-order);

}

排列码算法的时间复杂度为O(max(ni)).

对于任何一个空间目标点,基于栅格空间层次分解的Hilbert排列码算法均具有一致的时间耗费,而前面所述的Faloutsos和Roseman算法,其时间耗费则与空间目标点位置密切相关,即其时间耗费将随着与栅格格网坐标原点距离的增大而增大.表1是基于二进制位操作的Hilbert空间排列码算法与基于层次分解的Hilbert空间排列码算法在不同格网细化规模下的效率比较.由表1可以看出,基于层次分解的Hilbert空间排列码算法,较之基于二进制位操作的Hilbert码算法效率有了显著的提高.

表1　Hilbert空间排列码算法效率比较

格网数位操作层次分解

512×512

31

768×768

74

(单位:s)

1024×10242048×2048

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