GIS空间数据库(27)Hilbert曲线

本文目录
  • 正文

与Z-排序类似,Hilbert曲线也是一种空间填充曲线,它利用一个线性序列来填充空间,其构造过程如图所示。

理想情况下,这种映射会带来更少的磁盘访问,但由于磁盘访问的次数依赖于很多因素,如磁盘页面容量、分割算法、插入顺序等,因此,对于不同的查询,其磁盘访问的次数会有很大的不同。通常,可将给定查询代表的子空间中每个网格点的散列单元平均数,来作为衡量磁盘访问效率的标准。

实验证明,Hi1bert曲线的方法比Z-排序好一些,因为它没有斜线。不过Hilbert曲线算法的计算量要比Z-排序复杂。

Hilbert曲线的算法如下(Faloutsos and Roseman,1989):

(1)读入x和y坐标的n比特二进制表示。

(2)隔行扫描二进制比特到一个字符串。

(3)将字符串自左至右分成2比特长的串si,其中i=1,...,n

(4)规定每个2比特长的串的十进制值di,例如“00”等于0,“01”等于1,“10”等于3,“11”等于2。

(5)对于数组中每个数字j,如果j=0把后面数组中出现的所有1变成3,并把所有出现的3变成1。j=3把后面数组中出现的所有0变成2,并把所有出现的2变成0。

(6)将数组中每个值按步骤5转换成二进制表示(2比特长的串),自左至右连接所有的串,并计算其十进制值。

如您有疑问,可在文末留言,或到QQ群提问。
本站QQ群:291616564 麻辣GIS
微信公众号:malagis,扫描二维码直接关注。

打赏¥1

作者:,GIS爱好者。
分享本文,请您带上本文链接
分享到:

发表评论