文章快速检索  
  高级检索
Hilbert曲线层级演进关系
曹雪峰1, 万刚1, 张宗佩2     
1. 信息工程大学地理空间信息学院, 郑州 450052;
2. 95989部队, 北京 100076
摘要:网格编码代数是当前全球空间网格研究中的难点,也是推动全球空间网格从数据组织管理框架发展成为新一代空间分析模型的理论基础。Hilbert曲线是设计全球空间网格单元编码的重要工具。本文以Hilbert曲线序列码作为八叉树立体网格单元的唯一编码,由Hilbert曲线数学性质推导得到网格单元Hilbert码的层级演进关系表,进而设计了用于网格编码代数运算的若干操作算子,为构建全球空间网格分析理论与方法提供参考。
关键词:Hilbert曲线    网格编码代数    全球空间网格    八叉树    
Hilbert Curve Hierarchical Evolution Relationship
CAO Xuefeng1, WAN Gang1, ZHANG Zongpei2     
1. Institute of Geospatial Information, Information Engineering University, Zhengzhou 450052, China;
2. Troops 95989, Beijing 100076, China
Foundation support: The National Natural Science Foundation of China (Nos. 41371384; 41491465)
First author: CAO Xuefeng (1983—), male, lecturer, majors in discrete global grid. E-mail: CAO_Xue_Feng@163.com
Abstract: Grid code algebra is the difficult of current global spatial grid research, and it is the theoretic basis for the development from data organization framework to the new generation of spatial analysis model. Hilbert curve has been an important tool in the global spatial grid code design. In this paper, the octree grid code is based on Hilbert curve, then Hilbert curve hierarchical evolution relationship table is presented, which is used to design some grid code algebra operator. This work provides a reference for the construction of global spatial grid analysis theory and methods.
Key words: Hilbert Curve     Grid Code Algebra     Global Spatial Grid     Octree    

全球空间网格将地球空间离散化为各个剖分等级的网格单元,为每一个网格单元建立全球唯一的网格编码,以网格单元为基础实现全球空间信息的统一组织,为全球范围的空间数据管理、空间信息分析、空间问题建模提供统一框架[1]。按照网格剖分对象,全球空间网格可分为球面网格和球体网格。常见的球面网格包括球面正多面体网格[2]、球面Voronoi网格[3]、混合式球面网格[4]等。常见的球体网格包括阴阳网格[5]、立方体网格[6]、球体退化八叉树网格[7]、圈层立体网格[8]等。

利用空间填充曲线的降维和聚簇性,设计高效的网格单元编码算法,是全球离散网格领域的一个重要研究方向[1]。文献[9]提出了基于Hilbert曲线的全球离散网格影像金字塔索引算法,文献[10]基于Z曲线设计了球体退化八叉树网格的编码算法,文献[8]提出基于Hilbert曲线的扩展八叉树剖分网格编码算法,文献[11]将Hilbert曲线扩展应用到地月一体圈层立体网格的编码算法中。Hilbert曲线编码的经典方法是由文献[12]针对二维空间构造提出的。该算法是基于Morton码的二进制位操作法,算法复杂度为O(n2)。文献[13]根据Hilbert曲线的空间层次分解特征,通过栅格空间层次分解与构造域状态转移向量,设计了二维空间中Hilbert码的递归生成算法,算法复杂度为O(max (n))。文献[14]设计了基于状态转移矩阵的Hilbert码快速生成算法,将Hilbert状态转移矩阵转换为C++中的数组运算, 减少了Hilbert码计算过程中的嵌套循环及迭代处理,将算法复杂度降为O(n)。上述编码方法都只是在二维空间中进行讨论的。文献[15]研究了n维Hilbert曲线的生成问题,提出基于静态演化规则、自底向上的生成算法,算法复杂度为O(nlog n)。文献[16]设计了任意维空间中具有线性复杂度的Hilbert码算法。上述Hilbert曲线研究工作主要集中在曲线生成与排列码计算方面,对全球离散网格数据索引设计与优化发挥重要作用。但是,以Hilbert码为基础的网格编码计算分析研究却鲜见报导。

随着网格剖分模型研究的深入,全球空间网格已经在地球系统模拟器、全球气候变化、公众地理信息服务等科学研究和经济社会的诸多领域得到应用。但是,全球空间网格不仅仅是一种空间数据组织管理框架,而且将发展成为新一代空间分析模型。网格编码代数是这一发展过程中重要的理论推动[17]。在网格编码上构建代数运算法则,将传统上复杂耗时的空间坐标计算转换为网格编码的代数运算,不仅给很多算法带来效率上的显著提升,还将为空间分析带来新的模型和方法。这一点已经在遥感图像处理[17]等领域出露端倪。

本文首先基于Hilbert曲线设计八叉树立体网格单元编码,然后研究Hilbert曲线层级演进关系的计算方法,最后给出用于网格编码代数运算的Hilbert曲线网格编码若干操作算子。

1 八叉树立体网格Hilbert编码

对于八叉树结构的立体网格,可采用“行向编号-列向编号-径向编号”结构设计网格单元编码,简称“行列高”(I, J, K) 码。若剖分层次为N,则八叉树立体网格的大小为2N×2N×2N,可对其中的每一个网格单元赋予3维N阶Hilbert编码作为唯一网格编码。图 1给出了3维1阶、2阶Hilbert编码与网格空间的对应关系。表 1所示为3维1阶Hilbert编码顺序及其对应二进制码与空间坐标 (I, J, K) 关系。

图 1 3维1阶、2阶Hilbert编码与对应网格空间关系 Fig. 1 3D 1 and 2 order Hilbert code and its corresponding grid space

表 1 3维1阶Hilbert曲线与 (I, J, K) 对应表 Tab. 1 3D 1 order Hilbert curve and its corresponding (I, J, K)
Hilbert序列码 二进制码 I J K
0 000 0 0 0
1 001 0 0 1
2 010 0 1 1
3 011 0 1 0
4 100 1 1 0
5 101 1 1 1
6 110 1 0 1
7 111 1 0 0

3维2阶Hilbert曲线是将3维1阶Hilbert曲线的节点网格空间进行再次细分得到的,如图 1(b)所示,其对应得编码等于“1阶编码+细分编码”。例如3维1阶Hilbert曲线序列码为3(011) 的网格被细分后获得对应3维2阶Hilbert编码如表 2所示。

表 2 部分3维2阶Hilbert曲线与 (I, J, K) 对应表 Tab. 2 3D 2 order Hilbert curve and its corresponding (I, J, K)
Hilbert序列码 二进制码 I J K
24 011000 1 2 1
25 011001 0 2 1
26 011010 0 3 1
27 011011 1 3 1
28 011100 1 3 0
29 011101 0 3 0
30 011110 0 2 0
31 011111 1 2 0

根据3维1阶、2阶Hilbert编码生成过程,可以从图形结构上发现Hilbert编码的两个层级之间的关系为

(1)

式中,HN+12表示3维N+1阶Hilbert编码的二进制形式;HN2表示3维N阶Hilbert编码的二进制形式;H12′表示该立体网格单元细分1次后的子单元Hilbert编码 (二进制形式)。因此,Hilbert曲线序列码随剖分层级的变化中包含了父级与子级网格单元之间的空间关系,为基于网格编码构建代数运算法则,进而实现网格空间分析提供了可能的途径。

2 Hilbert曲线的层级演进关系

下面在分析Hilbert曲线生成过程中,由Hilbert曲线数学性质推导分析N阶与N+1阶Hilbert曲线序列码之间的关系。

2.1 Hilbert曲线地址

编码空间限定为M(M≥2) 维欧拉空间RM,与其对应的是MN阶Hilbert曲线HNM

SaN, M表示一个M维超立方体,其中N为剖分等级,a表示该超立方体的地址。初始超立方体未进行剖分,则N=0,a=0,记为S00, M。在每个维度上对S00, M进行N次二等分,得到子超立方体集合{SaN, M}。设S00, M各个边长相等且均为单位长度1,则S00, MSaN, M的体积分别为1和 (1/2N)M,即是S00, M由2NMSaN, M组成。

考虑到M维欧拉空间RM与1维Hilbert曲线之间映射是一一映射,则有

(2)

Hilbert曲线具有自相似的层次结构,因此当把某一个SaN, M再细分1次时,得到2M个子单元,每个子单元的地址可由两部分二进制段衔接起来,第1部分是a,第2部分是第i个子单元在SaN, M中的相对位置,记为bi。可得

(3)

式中,b1, b2, …, b2M是一个M位二进制数,且满足当ijbibj

2.2 Hilbert曲线起点和终点

Hilbert曲线起点和终点必须经过“垂直”子超立方体。“垂直”子超立方体是指其中包含Sa0, M的任意一个顶点的子超立方体。集合{SaN, M}中有且仅有2M个“垂直”子超立方体,每个“垂直”子超立方体都可以作为Hilbert曲线的起始点。对于每一个起始点,存在M个对应的终点,且起点和终点是相互邻近的。因此,Hilbert曲线所有起始点和终点组合的数量是M×2M

“垂直”子超立方体可被分为AB两类。A类是指包含M个0的一组,其余为B类。由于Hilbert曲线的起点和终点是相互邻近的,若起点在A类中,则终点在B类中,反之亦然。例如,当M=3时,一条Hilbert曲线的起点和终点可以是A={000, 011, 110, 101},B={001, 010, 111, 100}。因此,在研究Hilbert编码层级关系过程中,只关心起点位于A类中的Hilbert曲线,故Hilbert曲线数量减少至M×2M-1

2.3 Hilbert曲线地址列表

为了标识不同起点终点的Hilbert曲线,使用φlN, M(h) 表示第l条Hilbert曲线序列码h对应的SaN, M的地址,其中l=1, 2, …, M×2M-1

M维空间第1条1阶Hilbert曲线上各个地址形成的列表φ11, M可以从式 (4) 所示的递推公式计算得到

(4)

式中,0φ11, M-1表示二进制“0”与φ11, M-1的连接,φ11, M-1表示对应的二进制位反转 (即0变为1, 1变为0)。例如,φ11, 3={000, 001, 011, 010, 110, 111, 101, 100}是3维1阶第1条Hilbert曲线对应的地址列表。

下面将分3步确定其他Hilbert曲线对应的地址码φl1, M(l=2, …, M2M-1) 列表。

(1) 确定起始点地址

Hilbert曲线集合φlN, M(h)(l=1, 2,…, M2M-1) 符合性质1;φl1, M(1) 和φl1, M(2M) 的汉明距离 (二进制位不同的个数) 等于1,且φl1, M(1) 和φl1, M(1)(ll′) 的汉明距离必然是偶数[18]

为了确定哪些φl1, M(l=2, …, M2M-1) 满足上述性质,将Hilbert曲线序列码H为奇数的φlN, M(h) 地址列表组成一个集合,例如φ11, M(1), φ11, M(3), …, φ11, M(2M-1)。由于它们之间的汉明距离是偶数,因此将其放到一起构成一个集合,即前面所说的类型A。考虑到一个Hilbert曲线起点对应的终点数量是M,可以使φ21, M(1), φ31, M(1), …, φM1, M(1) 表示与φ11, M(1) 具有相同起点。同样,φM(s-1)+11, M(1), φM(s-1)+21, M(1), …, φM(s-1)+M1, M(1) 具有与φ11, M(2s-1) 相同的起点,其中s=2, 3, …, 2M-1。这样就能确定所有Hilbert曲线的起始点地址。

(2) 确定终点地址

φ21, M(2M), …, φM1, M(2M), …, φM2M-11, M(2M) 的终点地址可以从各自的起点地址计算得到。对于每一个起始点地址φ11, M(1)=φ21, M(1)=…=φM1, M(1),其与相应的终点地址汉明距离等于1。例如,φ11, M(1)=000…0(M位二进制数,都是0),则对应的终点地址为100…0,010…0,001…0,…,000…1(M位二进制数,只有一位是1,其他均是0)。将这些终点地址分别指定给φ11, M(2M), φ21, M(2M), …, φM1, M(2M)。总之,可以通过对M位二进制数的一个二进制位进行置反计算对应的终点地址。定义该运算函数为InvertBit (a, m),其含义是将a对应的地址 (M位二进制数) 的第m位 (从高位到低位计数) 置反。因此,可将终点地址计算用如下函数表达

(5)

式中,s=1, 2, 3, …, 2M-1m=1, 2, …, M

(3) 确定起点和终点之间其他地址的顺序

起点地址集合{φl1, M(1)}和终点地址集合{φl1, M(2M)}中的对应元素分别作为第l条Hilbert曲线的起点和终点,则第l条Hilbert曲线剩余点的地址集合为{φl1, M(h)|h=2, 3, …, 2M-1}。

下面以2维和3维网格空间为例 (图 2),讨论给定Hilbert曲线起点和终点情况下剩余点的地址顺序集合。在2维网格空间中,若指定00和01分别是Hilbert曲线的起点和终点,则其对应的Hilbert曲线路径只有一条 (00, 10, 11, 01)。在3维网格空间中,若指定000和100分别是Hilbert曲线的起点和终点,则其对应的Hilbert曲线路径有4条,分别为 (000, 001, 011, 010, 110, 111, 101, 100)、(000, 001, 101, 111, 011, 010, 110, 100)、(000, 010, 011, 001, 101, 111, 110, 100) 和 (000, 010, 110, 111, 011, 001, 101, 100)。因此,针对每一组起点终点组合,需要选定一组地址顺序列表,并将其指定给{φl1, M(h)}。

图 2 2维和3维Hilbert曲线路径 Fig. 2 2D and 3D Hilbert curve path

基于φ11, M的地址顺序列表,可采用交换X1Xl(l=2, 3, …, M) 两个坐标轴的方法获得的φ11, M地址顺序列表。若定义位操作函数ExtractBit (φ, M) 是指提取二进制数a的第m位,则φl1, M地址顺序列表的生成操作可以表示为交换ExtractBit (φ11, M(h), 1) 和ExtractBit (φ11, M(h), l)。因此,生成φl1, M(l=2, 3, …, M) 地址顺序列表的公式为

(6)

式中,h=2, 3, …, 2M-1是指Hilbert曲线序列码;φ11, M(2M) 和φl1, M(2M) 是第1条和第l条Hilbert曲线的终点地址;⊕表示二进制异或运算符。

同样地,需要确定{φM+i1, M}(i=1, 2, 3, …, M) 的地址顺序列表,其可以根据Hilbert曲线如下的性质2,从{φi1, M}计算得到。

Hilbert曲线符合性质2[18]:给定一个地址顺序列表φi1, M和一个起点地址φi1, M(1)(φi1, M(1)≠φi1, M(1)),则新的地址顺序列表φi1, M将从φi1, M(h+1)=φi1, M(h)⊕(φi1, M(h)⊕φi1, M(h+1))(h=1, 2, …, 2M-1) 依次计算得到[18]

φi1, M为基础,可以计算φM+i1, M的地址顺序列表。重复该过程,可以根据φM(s-1)+i1, M计算φMs+i1, M(s=2, 3, …, 2M-1-1)。

2.4 Hilbert曲线初始条件表

在3维欧拉空间中,根据2.3节步骤 (1)、(2)、(3) 可以计算3维1阶Hilbert曲线的对应的地址顺序列表 (总共3×23-1=12条)。这12条Hilbert曲线是获取3维N阶Hilbert曲线经过网格点的地址顺序列表的初始条件,称为初始条件表。实际上,这12条Hilbert曲线就是构建3维N阶Hilbert曲线的基单元。

(7)

通过上面研究已经确定一个初始条件表,为了生成不同剖分等级N的Hilbert曲线,还需要研究两个相邻剖分等级之间的关系。

2.5 Hilbert曲线层级演进关系表

初始条件表确定地址顺序列表总体走向,而N阶和N+1阶之间的层级演进关系表可以确定子超立方体的分布情况,从而得到完整的Hilbert曲线地址顺序列表。N阶和N+1阶之间的层级演进关系是通过1阶和2阶之间的演进层级关系归纳总结而来。在M(M≥2) 维欧拉空间RM中,层级演进关系表也描述了两个邻近超立方体的地址φlN, M(h) 和φlN, M(h+1) 的连接关系。

在子超立方体SaN, M中,采用地址序列{Win, M}(n=1, 2, …, N-1 i=1, 2, …, N22N-1) 对应于第l条Hilbert曲线地址序列集合{φln, M}(l=1, 2, …, N2N-1)。地址序列Win, M包括起点和终点地址。N阶和N+1阶之间的演进层级关系可以使用Win, M来描述,即

(8)

式中,l′=(l-1)2M; l=1, 2, …, N2N-1。如果W为空 (n=0),则式 (8) 就等价于初始条件表。

{Win, M}具有如下的性质

(9)

根据上述性质,可将演进层级关系公式简化为

(10)

式中,l″=(l-1)(2M-1+1),l=1, 2, …, N2N-1。假定记演进层级关系表为TinductM[l],则

(11)

式中,induct (W) 表示输入地址序列W,输出其对应第几条Hilbert曲线。

以3维欧拉空间R3为例,则Tinduct3[1]=(3, 2, 2, 10, 10, 5, 5, 9),Tinduct3[3]=(1, 2, 2, 6, 6, 1, 1, 7)。根据Tinduct3[l]可以计算得到其完整演进层级关系表达式,即3维Hilbert曲线N阶和N+1阶之间关系为

(12)

从式 (12) 可得到演进层次表Tinduct3

(13)

由此,可以根据初始条件表和演进层次表计算3维欧拉空间R3任意一条可能的Hilbert曲线经过的坐标地址顺序列表。当然,其也可以拓展到更高的维度空间。

为了与表 2对应,3维1阶Hilbert曲线的走向选定为第2条Hilbert曲线,即φ21, 3为3维1阶Hilbert曲线对应的地址顺序列表,其中J对应X1I对应X2K对应X3。3维N阶Hilbert曲线是在第2条Hilbert曲线基础上依次按照Tinduct3得到的,其相应的地址顺序列表 (即Hilbert编码) 也可以计算得到。

3 基于Hilbert曲线层级演进关系的网格编码计算

全球立体网格可抽象为一个初始超立方体,记为S00, 3;按照八叉树剖分N次得到的立体网格单元可以抽象为子超立方体,记为SaN, 3φN, 3(h) 表示Hilbert编码为h的立体网格单元。若Hilbert编码以二进制形式表达,则记为h2;若以八进制形式表达,则记为h8

八叉树立体网格Hilbert编码是一种可用{0, 1, 2, …, 7}8个码元描述的立体网格单元“定位”系统。Hilbert编码h2的每3位对应于立体网格单元San, 3的一次“八分”,从最高的3位到最低3位依次对应Sa0, 3的第1级细分、第2级细分……直至第N级细分。

由于地球立体空间是一个连续的空间,因此可不断增加剖分等级N,减小立体网格单元的粒度,提高网格定位的精度。随着剖分等级N不断增加,八叉树立体网格Hilbert编码集合H将变成一个满足Hilbert曲线生成法则的无限空间集合。结合一般数学加法运算的性质,根据分析,Hilbert编码加法满足下面的性质:

(1) 封闭性:若hA2, hB2Hhnew2=hA2+hB2,则hnew2H

(2) 结合律:若hA2, hB2, hc2H,则满足 (hA2+hB2)+hc2=hA2+(hB2+hc2)。

(3) 交换律:若hA2, hB2H,则满足hA2+hB2=hB2+hA2

(4) 消去律:若hA2, hB2, hc2HhA2+hc2=hB2+hc2,则hA2=hB2

假定AB是两个同一剖分等级的立体网格单元,分别为SaN, 3SaN, 3。根据Hilbert编码生成算法和层级关系,可以得出Hilbert编码满足下列运算。

3.1 集合运算

(1) 若aa′,则SaN, 3SaN, 3SaN, 3SaN, 3=∅,即两个不同立体网格单元的Hilbert编码不同,地址也不同。

(2) SN+1, MabiSaN, 3经过一次剖分得到8个子单元。

3.2 位运算

(1) 异或运算。hA2hB2,表示AB两个立体网格单元的Hilbert编码逐位进行异或运算。异或运算可以应用于判断Hilbert编码在哪一个剖分等级开始与其直接父单元不再是同一个单元。

(2) 右移运算。hN+12≫3=hN2,即N+1级立体网格单元SN+1, 3abi(0≤i≤7) 的Hilbert编码右移3位得到其对应的N级单元SaN, 3的Hilbert编码。

(3) 左移运算。hN2≪3=hN+12,即N级立体网格单元SaN, 3的Hilbert编码左移3位得到N+1级单元SN+1, 3ab0(第1个子单元) 的Hilbert编码。

3.3 数学加法运算

hnew2=hA2+hB2hnew8=hA8+hB8,表示两个Hilbert码进行数学加法运算,其运算规则按照二进制或八进制加法进行。Hilbert编码 (h8) 的每1位表示立体网格单元在相应剖分层次上的8个子立方体中的哪一个。

具体运算过程 (以八进制为例):从低位开始逐位进行加法运算,若相应结果大于等于8,则向高位进位,其含义是在高一等级的剖分网格中沿Hilbert曲线走向前进了相应的子立方体数量;若最终结果增加了一位,则表明剖分等级增加一级。若想得到Hilbert编码对应的地址码φN, 3(h),只需依次从高位到低位获取数值,依据Hilbert编码层级关系计算得到。

例如:44+72=136,计算结果增加一位表明剖分等级增加一级,个位数“6”表示在最低剖分等级的8个子立方体的第7个中 (注意:编码是从0,1,…,7),同理依次可以得出10位数“3”对应于第4个子立方体,百位数“1”对应于第1个子立方体。按照层次关系,可得知不同剖分层次上对应的Hilbert曲线依次为φ23, 3φ12, 3φ21, 3,则可得出136(Hilbert码) 对应的地址码φ3, 3(136)=123,二进制形式为001010011。

3.4 数学减法运算

hnew2=|hA2-hB2|或hnew8=|hA8-hB8|,表示两个Hilbert编码进行数学减法运算,其运算规则按照二进制或八进制减法进行。

具体运算过程 (八进制为例):先比较两个Hilbert编码的大小,以较大的Hilbert编码减去较小的,从低位开始逐位进行减法运算,若不能进行减法运算,则向高位借位,其含义是在高一等级的剖分网格中沿Hilbert曲线走向后退一个子立方体;若最终结果减少了一位,则表明剖分等级减少一级。若想得到Hilbert编码对应的地址码φN, 3(h),只需依次从高位到低位获取数值,依据Hilbert编码层级关系计算得到。

4 结束语

建立以网格编码为基础的代数运算法则是推动全球空间网格从数据组织管理框架发展成为新一代空间分析模型的理论基础。本文基于Hilbert曲线设计了八叉树立体网格单元编码,分析推导出Hilbert曲线层级演进关系表,以此基础给出了用于网格编码代数运算的若干操作算子。Hilbert曲线层级演进关系的分析方法可以扩展到其他结构的全球空间网格模型中,从而为构建全球空间网格分析理论与方法提供参考。


参考文献
[1] 万刚, 曹雪峰, 李科, 等. 地理空间信息网格理论与技术[M]. 北京: 测绘出版社, 2016. WAN Gang, CAO Xuefeng, LI Ke, et al. Geospatial Information Grid Theory and Technology[M]. Beijing: Surveying and Mapping Press, 2016.
[2] SAHR K, WHITE D, KIMERLING A J. Geodesic Discrete Global Grid Systems[J]. Cartography and Geographic Information Science, 2003, 30(2): 121–134. DOI:10.1559/152304003100011090
[3] LUKATELA H. A Seamless Global Terrain Model in the Hipparchus System[EB/OL]. (2012-05-30). http://www.geodyssey.com/papers/ggterra.html.
[4] 韩阳, 万刚, 曹雪峰. 混合式全球网格划分方法及编码研究[J]. 测绘科学, 2009, 34(2): 136–138, 166. HAN Yang, WAN Gang, CAO Xuefeng. Research on A Mix Global Grid Data Structure and Encoding[J]. Science of Surveying and Mapping, 2009, 34(2): 136–138, 166.
[5] KAGEYAMA A, SATO T. The "Yin-Yang Grid":An Overset Grid in Spherical Geometry[J]. Geochemistry Geophysics Geosystems, 2004, 5(9).
[6] TSUBOI S, KOMATITSCH D. JI C, et al. Computations of global seismic wave propagation in three dimensional Earth mode[M]//LABARTA J, JOE K, SATO T. High-Performance Computing. Berlin Heidelberg:Springer, 2008:434-443.
[7] 吴立新, 余接情. 基于球体退化八叉树的全球三维网格与变形特征[J]. 地理与地理信息科学, 2009, 25(1): 1–4. WU Lixin, YU Jieqing. Global 3D-Grid Based on Sphere Degenerated Octree and Its Distortion Features[J]. Geography and Geo-Information Science, 2009, 25(1): 1–4.
[8] 曹雪峰. 地球圈层空间网格理论与算法研究[D]. 郑州: 解放军信息工程大学, 2012. CAO Xuefeng. Research on Earth Sphere Shell Space Grid Theory and Algorithms[D]. Zhengzhou:The PLA Information Engineering University, 2012.
[9] 程承旗, 张恩东, 万元嵬, 等. 遥感影像剖分金字塔研究[J]. 地理与地理信息科学, 2010, 26(1): 19–23. CHENG Chengqi, ZHANG Endong, WAN Yuanwei, et al. Research on Remote Sensing Image Subdivision Pyramid[J]. Geography and Geo-Information Science, 2010, 26(1): 19–23.
[10] 余接情, 吴立新. 适应性球体退化八叉树格网及其编码[J]. 地理与地理信息科学, 2012, 28(1): 14–18. YU Jieqing, WU Lixin. Adaptable Spheroid Degenerated-Octree Grid and Its Coding Method[J]. Geography and Geo-Information Science, 2012, 28(1): 14–18.
[11] 张宗佩. 地月圈层立体网格理论与应用研究[D]. 郑州: 信息工程大学, 2015. ZHANG Zongpei. Research on Earth-Lunar Sphere Shell Space Grid Theory and Application[D]. Zhengzhou:Information Engineering University, 2015.
[12] FALOUTSOS C, ROSEMAN S. Fractals for Secondary Key Retrieval[C]//Proceeding of the 8th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Philadelphia:ACM, 1989:247-252.
[13] 陆锋, 周成虎. 一种基于空间层次分解的Hilbert码生成算法[J]. 中国图象图形学报, 2001, 6A(5): 465–469. LU Feng, ZHOU Chenghu. An Algorithm for Hilbert Ordering Code Based on Spatial Hierarchical Decomposition[J]. Journal of Image and Graphics, 2001, 6A(5): 465–469.
[14] 李绍俊, 钟耳顺, 王少华, 等. 基于状态转移矩阵的Hilbert码快速生成算法[J]. 地球信息科学, 2014, 16(6): 846–851. LI Shaojun, ZHONG Ershun, WANG Shaohua, et al. An Algorithm for Hilbert Ordering Code Based on State-Transition Matrix[J]. Journal of Geo-Information Science, 2014, 16(6): 846–851.
[15] 李晨阳, 段雄文, 冯玉才. N维Hilbert曲线生成算法[J]. 中国图象图形学报, 2006, 11(8): 1068–1075. LI Chenyang, DUAN Xiongwen, FENG Yucai. Algorithm for Generating N-Dimensional Hilbert Curve[J]. Journal of Image and Graphics, 2006, 11(8): 1068–1075.
[16] 刘辉, 冷伟, 崔涛. 高维Hilbert曲线的编码与解码算法设计[J]. 数值计算与计算机应用, 2015, 36(1): 42–58. LIU Hui, LENG Wei, CUI Tao. Development of Encoding and Decoding Algorithms for High dimensional Hilbert Curves[J]. Journal on Numerical Methods and Computer Applications, 2015, 36(1): 42–58.
[17] 童晓冲, 贲进. 空间信息剖分组织的全球离散格网理论与方法[M]. 北京: 测绘出版社, 2016. TONG Xiaochong, BEN Jin. The Principles and Methods of Discrete Global Grid Systems for Geospatial Information Subdivision Organization[M]. Beijing: Surveying and Mapping Press, 2016.
[18] SAGAN H. Space-Filling Curve[M]. New York: Springer Verlag, 1994.
http://dx.doi.org/10.11947/j.AGCS.2016.F009
中国科学技术协会主管、中国测绘地理信息学会主办。
0

文章信息

曹雪峰,万刚,张宗佩
CAO Xuefeng, WAN Gang, ZHANG Zongpei
Hilbert曲线层级演进关系
Hilbert Curve Hierarchical Evolution Relationship
测绘学报,2016,45(S1): 77-84
Acta Geodaetica et Cartographica Sinica, 2016, 45(S1): 77-84
http://dx.doi.org/10.11947/j.AGCS.2016.F009

文章历史

收稿日期: 2016-08-20
修回日期: 2016-10-20

相关文章

工作空间