孔径为4的六边形格网层次编码、运算与索引方法

摘要

本发明涉及孔径为4的六边形格网层次编码、运算与索引方法，索引方法采用孔径为4的剖分方法对六边形格网进行层次划分，用{0,1,2,3}进行层次编码，得到HBQT格点编码集合，并得到HBQT格网单元编码集合；定义HBQT格网编码的四则运算；根据HBQT格网编码四则运算的规则，建立标准笛卡尔坐标系与HBQT格网编码之间的相互转换，得到六边形格网层次结构的索引方法，包括同层次格网的检索和不同层格网的检索；本发明能够方便地进行格网的层次编码，简单地实现空间矢量的四则运算和六边形格网的层次索引，并能够与笛卡尔坐标系统快速进行转换，克服了现有方法难以建立方向一致的六边形层次结构、高效的编码与运算、快速的层次索引方法、以及难以扩展到封闭球面等问题。

说明书

技术领域

本发明属于空间信息技术领域，涉及一种用于全球离散格网构建或数字图像处理的孔径为4六边形层次采样格网结构的编码、运算与索引方法。

背景技术

在空间信息处理技术领域，经过研究发现，有且只有三种图形（三角形、四边形、六边形）能够规则化地对空间进行划分，其中，六边形格网是最紧凑的一种，它具有下面的特点：

（1）以最小的平均误差量化平面，具有最大的角分辨率；

（2）与矩形格网和和三角形格网不同，六边形格网单元拥有一致的邻域；

（3）六边形格网的6个离散的速度向量足以描述连续的各向同性的流体；

（4）在表达相同信息量的情况下，六边形格网比矩形格网要节省约14%的采样量。

正因为六边形格网具有上述独特的性质，使得它非常适合用作空间数据的建模和处理，并受到越来越多的重视。Rothman和Zaleski在流体元胞自动机的经典教材Lattice-Gas Cellular Automata中采用的完全是六边形格网，未提及其它类型的格网单元。Saff和Kuijlaars、Kimerling等经过研究得出结论：平面六边形格网的各种优点可以延续到全球格网系统上。随后，六边形格网被美国环保署用于全球取样，以及全球气候模拟、全球洋流分析等许多面向全球的空间处理与分析领域。在非全球格网数据处理方面，根据生理学的研究，人眼的视觉系统视网膜使用的就是六边形采样模式，并具有处理不同分辨率影像数据的能力，因此，多分辨率的六边形格网也被应用于数字图像信号获取与处理领域。

六边形的聚合、分解问题将影响它们的优势。由于六边形不具备自相似性，并不能像矩形或三角四叉树那样排列：即不可能将一个六边形分解为小一些的六边形（或将较小的六边形组合成一个大六边形），导致多分辨率六边形格网系统的应用却受到了限制。如何设计高效的多分辨率六边形格网的层次结构成为瓶颈所在。美国军方曾资助Laurie Gibson和Dean Lucas发明了一种优美的、在六边形图像处理中广泛应用的方案，这种用于表达空间数据的六边形数学系统允许在不同尺寸的影像上进行量测。该方案证明了通过索引和代数聚合六边形单元的方式能够将其扩展到多维，因此被称为“一般平衡三进制”（Generalized Balanced Ternary，GBT）。然而，GBT并不能很好地满足单元分解的需求，而且GBT单元在某一层次上是真正的六边形，而在其它层次上则变为7个六边形组成的星型玫瑰形状，这些形状随着单元层次不断旋转，导致GBT的相关应用比较复杂。

Middleton和Sivaswamy在GBT的基础上，提出了HIP（Hexagonal Image Processing）结构，将其系统地应用于数字图像处理的多个领域，在处理效果和效率等诸多方面取得了优于矩形格网的结果。但HIP产生的是非一致性（non-congruent）格网，且格网单元方向随格网的层次不断变化。尽管在平面上可以通过旋转、平移等操作保证层次结构的单元方向相同，但类似的方法在球面上却会导致单元之间出现重叠或裂缝。

加拿大PYXIS Innovation Inc的Peterson等设计了全球六边形离散格网的PYXIS索引结构，该结构利用ISEA3H格网系统（Icosahedral Snyder Equal Area Aperture 3 Hexagonal DGG），提供了一种孔径为3的非一致性的六边形聚合及分解方案。这种方案能够像GBT算术操作那样进行快速聚合或分解，同时又保留了地理坐标或投影坐标的格网地址，与传统坐标可实现无误差转换。但PYXIS采用的是孔径为3的的六边形层次格网，并且逐层之间的格网之间会发生旋转，在许多空间应用中存在较大困难。

发明内容

本发明的目的是提供一种孔径为4的六边形格网层次编码、运算与索引方法，以解决现有方法难以建立方向一致的六边形层次结构、高效的编码与运算、快速的层次索引方法、以及难以扩展到封闭球面的问题。

为实现上述目的，本发明的孔径为4的六边形格网层次编码方法步骤如下：

（1）采用孔径为4的剖分方法，对六边形格网进行层次划分，得到上下层对准的孔径为4的六边形网格层次剖分结构，其中每一个六边形格网称为格网单元；

（2）将四叉树三角形结构与六边形格网结构叠加表示，将整个四叉树三角形中心置于六边形格网结构的中心，四叉树三角形的顶点置于六边形单元的中心或交点处，形成一个具备四叉树结构的四元正三角形结构，该结构与六边形格网具有严格的对应关系，其中四元是指正三角形的中心点和三个顶点，各正三角形的四元共同构成HBQT格点系统，其中各构成点称为格点；

（3）利用{0,1,2,3}对四元三角形结构的HBQT格点系统中各格点进行四叉树编码，其中每一个三角形编码满足：三角形的中心用码元0表示，三角形的三个顶点分别用{1,2,3}进行表示，得到六边形平衡四叉树HBQT格点编码集合，删除没有位于格网单元中心的格点编码即得到对应六边形格网单元的HBQT格网编码集合；或利用下述公式得到格点系统第n层的格点编码集合                                                ：，其中， ， ， 表示集合间的点减运算，用编码0、1、2、3分别代替中的4个格网向量，则中任一格点均可用编码唯一描述，再排除没有位于格网单元中心的格点，即可得到格点系统第n层的格网单元编码集合，它是格点编码集合的子集，即。

进一步的，所述步骤（3）中三角形的三个顶点分别用{1,2,3}进行表示指：三角形朝上时编码的顺序为上顶点1，左下角顶点2，右下角顶点3；三角形朝下时编码的顺序为下顶点1，右上角顶点2，左上角顶点3。

本发明的孔径为4的六边形格网层次运算方法技术方案如下：该方法应用于对孔径为4的六边形剖分结构进行分层编码得到的HBQT格网单元编码，四则运算、、、中、运算遵循平行四边形法则，互为逆运算， 、运算遵循极坐标下向量的旋转与缩放，互为逆运算。

进一步的，设格点系统中两个格网单元编码， ，若是计算编码，步骤如下：

（1）判断两个格点编码的码串长度是否相同，若两个格点编码的码串长度不同，则将码串短的格点编码前补零，使两个格点编码变成相同长度的码串；

（2）按照格点编码的展开式，初始化和的符号标识矢量，初始化进位变量；

（3）利用列出的加法查找表从低位向高位逐位码元进行运算，并进行进位运算；

（4）逐位运算保证编码的每一位码元的符号符合编码展开式的符号约定即可。

进一步的，设两个格网单元编码， ，计算编码是利用运算的查找表，将的每一个码元，从低位到高位分别与的每一位进行运算，得到一系列编码序列，按照乘法规则， 的码元与进行运算得到的编码，末尾用码元补齐；然后将这一系列编码，使用运算进行相加，得到编码，保证编码的每一位码元的符号符合编码展开式的符号约定即可。

进一步的，格网单元系统中任一单元编码的展开式为：

，

其中，表示格网单元编码连续运算，函数、， 代表的是HBQT格网单元编码的码元。

孔径为4的六边形格网层次坐标转换方法，其特征在于，该方法包括从HBQT格点编码到标准笛卡尔坐标的转换和从标准笛卡尔坐标到HBQT格网单元编码的转换，所述HBQT编码是通过对孔径为4的六边形剖分结构进行分层编码得到的；

1）从HBQT格网单元编码到标准笛卡尔坐标的转换步骤如下：

（1）编码从HBQT格网单元编码到格点斜坐标系：

其中， 是对中进行规则化， ， 的结果是定值；

（2）从格点斜坐标到单元斜坐标系的转换：

；

（3）从单元斜坐标到标准笛卡尔坐标的转换：

；

2）从标准笛卡尔坐标到HBQT格网单元编码的转换步骤如下：

（1）从标准笛卡尔坐标到单元斜坐标的转换：

（2）从单元斜坐标到格点斜坐标的转换：

；

（3）从格点斜坐标到HBQT格网单元编码的转换：

；

上述运算遵循平行四边形法则， 运算遵循极坐标下向量的旋转与缩放。

本发明的孔径为4的六边形格网层次索引方法步骤如下：（1）采用孔径为4的剖分方法对六边形格网进行层次划分，用{0,1,2,3}四位数进行层次编码，得到六边形平衡四叉树HBQT格点编码集合，删除没有位于格网单元中心的格点编码即得到HBQT格网单元编码集合；（2）定义HBQT格网单元编码的四则运算：四则运算、、、中、运算遵循平行四边形法则，互为逆运算， 、运算遵循极坐标下向量的旋转与缩放，互为逆运算；（3）根据HBQT格网单元编码四则运算的规则，对基于六边形格网的单元斜坐标系建立标准笛卡尔坐标系与HBQT格网单元编码之间的相互转换；（4）采用HBQT格网单元编码的四则运算，得到六边形格网层次结构的索引方法，包括同层次格网的检索即邻近单元查找和不同层格网的检索即父单元查找、子单元查找。

进一步的，所述步骤（1）中得到的HBQT格点编码的步骤如下：(a)采用孔径为4的剖分方法，对六边形格网进行层次划分，得到上下层对准的孔径为4的六边形网格层次剖分结构，其中每一个六边形格网称为格网单元；

（b）将四叉树三角形结构与六边形格网结构叠加表示，将整个四叉树三角形中心置于六边形格网结构的中心，四叉树三角形的顶点置于六边形单元的中心或交点处，形成一个具备四叉树结构的四元正三角形结构，该结构与六边形格网具有严格的对应关系，其中四元是指正三角形的中心点和三个顶点，各正三角形的四元共同构成HBQT格点系统，其中各构成点称为格点；

（c）利用{0,1,2,3}对四元三角形结构的HBQT格点系统中各格点进行四叉树编码，其中每一个三角形编码满足：三角形的中心用码元0表示，三角形的三个顶点分别用{1,2,3}进行表示：三角形朝上时编码的顺序为上顶点1，左下角顶点2，右下角顶点3；三角形朝下时编码的顺序为下顶点1，右上角顶点2，左上角顶点3；得到六边形平衡四叉树HBQT格点编码集合，删除没有位于格网单元中心的格点编码即得到对应六边形格网单元的HBQT格网编码集合；或利用下述公式得到格点系统第n层的格点编码集合 ：，其中， ， ，表示集合间的点减运算，用编码0、1、2、3分别代替中的4个格网向量，则中任一格点均可用编码唯一描述，再排除没有位于格网单元中心的格点，即可得到格点系统第n层的格网单元编码集合，它是格点编码集合的子集，即。

进一步的，所述步骤（4）中得到六边形格网层次结构的索引方法具体为：

1）邻近关系查找

邻近关系的查找，又称作邻近单元的查找，设设孔径为4剖分的六边形格网第层的格网单元，6个方向上的邻近单元的编码分别为：

；

2）层次关系查找

（1）子单元的查找

设孔径为4剖分的六边形格网第层的格网单元，查找其在层的子单元：

子单元中与它对准的中心子单元编码为：；

周围的6个子单元分别为中心子单元的6个邻近单元：

；

（2）父单元的查找

孔径为4的六边形格网单元分成两类：一类是与其父单元对准的单元，称为中心继承单元，该类单元具有1个父单元；另一类是与其父单元不对准，称之为偏心继承单元，该类单元具有2个父单元；设层的单元，有：

如果码元满足条件，那该单元就是中心继承单元，其父单元为：

；

如果码元满足，则该单元为偏心继承单元，由于，设剩下可能的码元全集为，计算集合，则集合中必有两个码元元素，设它们分别为、，则的两个父单元分别为：

，

。

 本发明的孔径为4的六边形格网层次编码、运算与索引方法能够方便地进行格网的层次编码，简单地实现空间矢量的四则运算和六边形格网的层次索引，并能够与笛卡尔坐标系统快速进行转换，克服了现有方法难以建立方向一致的六边形层次结构、高效的编码与运算、快速的层次索引方法、以及难以扩展到封闭球面等问题。

本发明提出的孔径为4的六边形格网层次编码、运算与索引的方法，可以有效地解决孔径为4的六边形层次格网的应用问题，并可扩展到球面等任何封闭表面，与目前所知的唯一能够覆盖球面的六边形层次格网结构（孔径为3的六边形格网层次结构PYXIS的编码、运算与索引）相比，具有下面的优点：

（1）孔径为4的六边形格网层次结构的单元方向不随剖分层次变化，有利于空间定位；

（2）本方法提出的编码方案与四叉树结构等效，可用于开发高效的数据处理算法；

（3）本方法提出的编码方案只需要4个码元，2Bit（PYXIS要7个码元，3Bit），与四进制数对应，有利于减少数据量并提高编码运算的效率；

（4）本方法提出的运算方案的计算效率和索引效率都优于PYXIS结构，主要得益于算法使用的查找表规模（）仅是PYXIS方案（）的25%，且全部运算都是单码进位，计算速度更快；

（5）从目前的专利和文献的情况来看，定义在PYXIS编码空间上的运算只有运算，而本方法提出的编码空间上定义并实现了、、、四种空间运算，相比而言空间定义更加完整。

附图说明

图1是孔径为4的六边形格网层次剖分结构图；

图2是具备四叉树结构的格点系统图；

图3是四叉树结构的编码图；

图4是、对应的编码集合图；

图5是格网向量加法示意图；

图6是格网向量乘法示意图；

图7是与HBQT结构相关的四个坐标系统图，其中（a）格点编码坐标系、（b）格点斜坐标系、（c）单元斜坐标系、（d）标准笛卡尔坐标系；

图8 是格网层次时，每个六边形单元的HBQT编码图；

图9 是HBQT编码四则运算的图解式；

图10 是HBQT运算与索引的实验结果效率对比图；

图11是利用HBQT索引动态生成全球六边形离散格网的显示情况图，其中（a）是层次n=9的全球格网；（b）是层次n=10的全球格网；（c）是层次n=11的全球格网；

图12 是不同类型空间数据（栅格数据+矢量数据）利用HBQT索引方式在全球六边形离散格网上不同层次的显示情况与效率图，其中（a）对应的格网层次n=13；（b）对应的格网层次n=12；（c）对应的格网层次n=11；（d）对应的格网层次n=10。

具体实施方式

本发明的孔径为4的六边形格网层次编码、运算与索引方法中，编码、运算、坐标转换方法是索引方法所不可或缺的步骤，且四个方法中后续方法都依赖于前面方法才能实现，故以索引方法为例来具体说明各方法的具体实现，不再另举例分别赘述各方法的实现。本发明中孔径是指第k层和第k+1层格网单元的面积比。

本发明的孔径为4的六边形格网层次结构的编码、运算与索引方法，包括以下基本步骤：

1．编码方法

（1）采用孔径为4的剖分方法，对六边形格网进行层次划分，得到上下层对准的（即上一层单元的中心与下一层子单元的中心对准）孔径为4的六边形网格层次剖分结构如图1所示，其中每一个六边形格网称为格网单元；

（2）将四叉树三角形结构（即三角形中心作为四叉树父节点，三角形的三个顶点作为四叉树的子节点，三角形结构进行四叉树划分，每一层生成的四个小三角形的中心和顶点同样满足树状节点的对应关系）与六边形格网结构（即六边形的平面铺盖结构）叠加表示，将整个四叉树三角形中心置于六边形格网结构的中心，四叉树三角形的顶点置于六边形单元的中心或交点处，形成一个具备四叉树结构的四元正三角形结构，该结构与六边形格网具有严格的对应关系如图2所示，其中四元是指正三角形的中心点和三个顶点，各正三角形的四元共同构成HBQT格点系统，其中各构成点称为格点；

（3）利用{0,1,2,3}对四元三角形结构的HBQT格点系统中各格点进行四叉树编码如图3所示，其中每一个三角形编码满足：三角形的中心用码元0表示，三角形的三个顶点分别用{1,2,3}进行表示（表示方式为：三角形朝上时编码的顺序为上顶点1，左下角顶点2，右下角顶点3；三角形朝下时编码的顺序为下顶点1，右上角顶点2，左上角顶点3），得到六边形平衡四叉树HBQT格点编码集合，删除没有位于格网单元中心的格点编码即得到对应六边形格网单元的HBQT格网编码集合；或利用下述公式得到格点系统第n层的格点编码集合：，其中， ， ； 表示集合间的点减运算，用编码0、1、2、3分别代替中的4个格网向量，则中任一格点均可用编码唯一描述，再排除没有位于格网单元中心的格点，即可得到格点系统第n层的格网单元编码集合，它是格点编码集合的子集，即。、对应的格点编码集合如图4所示，如图8所示为格网层次n=5时，每个六边形单元的HBQT格网单元编码图。

点减运算：对于集合A、B，满足； ， 。

2．利用HBQT格网单元编码实现空间向量的四则运算

1）运算的定义

编码记录了单元的空间位置，在数学上可采用从原点指向单元中心的向量抽象表示，编码运算完全等效于这些格网向量的运算。

以HBQT结构的格网向量a、b为边作平行四边形，由原点作出的对角线定义为a、b通过加法得到的向量，记为。平行四边形法则，如图5所示，两个单元103和230向量用黑色的箭头表示，向量相加的结果单元33用虚线箭头表示，图中显示了向量相加的平行四边形法则。或者把两向量首尾相接，由始点到终点的连线定义为得到的向量（三角形法则）。HBQT编码集合与可用群表示，该群是一个Abelian群（交换群），具有如下性质：

封闭性——，；

交换律——，；

结合律——，；

存在幺元——，，使得，对于，；

存在逆元——，，使得，则是的逆元，记作，对于，。

减法是加法的逆运算，同样可以用平行四边形法则或三角形法则定义，用表示。

乘法的定义在极坐标系下给出，对于格网向量、，两者相乘所得向量的模为，向量的极角为两向量极角之和，记为，即：

，，，

。

乘法运算的本质是对单元的旋转和缩放，如图6所示。乘法运算定义的核心是旋转和缩放原始单元编码。建立极坐标系， ， ， 。运算的过程是通过初始单元向量旋转、缩放实现的。

除法的定义与乘法类似，同样表示单元的旋转与缩放，记为：

，，，

。

格网向量的乘法和除法互为逆运算，因此：

，

除法运算不具备封闭性，即不在格网单元中心。在实际应用中，可根据精度要求采用小数形式的HBQT编码表示。

2）运算的性质

因为HBQT格网单元编码集合是HBQT格点编码集合的子集，所以研究格网向量运算的性质必须在格点编码集合中讨论。由于HBQT格点的空间分布不均匀，格点编码集合对加、减、乘、除四则运算无法满足群的封闭性，存在“孔洞”。为了便于研究，首先需要填补这些孔洞。定义，，，，，，在此基础上有，即格网向量旋转180°，模不变，即。

HBQT格点编码集合中的四则运算具有以下性质：

，，；

，；

，

根据以上性质，，由此可知HBQT格点编码集合中任意元素都可以逐码元展开，这一结论对格网编码集合同样成立。

将HBQT格网系统中任意一个单元的编码进行展开。设函数、，其中代表的是HBQT格网单元编码的码元：

，

用下式展开：

3）运算的实现

建立一个查找表记录编码的加法运算规则，则格网向量的加法运算可通过查找表的查找高效实现，运算查找表如表1。由于格网向量的减法是加法的逆运算，实现思路与加法运算相同。

 

该表中每个码元对应的笛卡尔坐标为：

，，，，

，，

7个码元两两相加，可得到12个不同的格网向量，它们笛卡尔坐标为：

，，，，

，，，，

，，，

    建立一个查找表记录上述编码的加法运算规则，则格网向量的加法运算可通过查找表的查找高效实现。

设两个编码， ，计算编码，有下面步骤：

第一步：将两个格网单元编码变成相同长度的码串，若是两个单元编码的码串长度度不同，则将码串短的格点编码前补零，使两个编码变成相同长度的码串；

第二步：按照编码的展开式初始化和的符号标识矢量，初始化进位变量；

第三步：利用加法查找表从低位向高位逐位码元进行运算，并进行进位运算；

第四步：逐位运算保证编码的每一位码元的符号符合编码展开式的符号约定即可。

对于运算，利用极坐标构建运算的查找表，如表2。在极坐标系下，7个码元对应的坐标为：，，，，，，，7个码元两两相乘，其结果同样可用如下的表格记录下来，在实现时查找这个表即可。

 

设两个编码， ，计算编码，有下面步骤：

第一步：利用运算的查找表，将的每一个码元，从低位到高位分别与的每一位进行运算，得到一系列编码序列，按照乘法规则， 的码元与进行运算得到的编码，末尾用码元补齐；

第二步：将这一系列编码，使用运算进行相加，得到编码，保证编码的每一位码元的符号符合编码展开式的符号约定即可。

除法运算是乘法运算的逆运算，其关键是求，即的编码。由于，可能不是一个整数编码，必须对编码进行扩展。参照整数的除法运算，将扩展为，在除法运算过程中，不足的补即可。格网编码向量除法的实质是消去运算，通过乘法和减法运算，将除法运算的每一位消去，每次乘运算和减运算消去一位编码，并求余即可。

如图9所示分别说明HBQT、、、运算的具体过程：

HBQT运算的具体过程：

（图9（a））； （图9（b））； （图9（c））。

HBQT运算的具体过程：

由于运算和运算互为逆运算，有，例如： 

HBQT运算的具体过程： （图9（d））。

HBQT运算的具体过程，例如h=13，求（图9（e））：

第一步： ，上0，余1；

第二步： ，余3；

第三步： ，余2；

第四步： ，余1， 

上面的过程出现循环，得到， 求到有效的小数点后位数即可。如取小数点后3位，计算，规则化后再就得到的进似值，根据整数部分判断落在哪个单元内。例如有：

的结果落在编码为303的单元内。

3．HBQT编码与传统笛卡尔坐标系之间的相互转换方法。

整个转换过程中涉及到图7中四个坐标系统：（a）格点编码坐标系、（b）格点斜坐标系、（c）单元斜坐标系、（d）标准笛卡尔坐标系。由于HBQT单元编码是HBQT格点编码的子集，因此，HBQT单元编码坐标系与格点编码坐标系的坐标一致。

1）从HBQT格点编码到标准笛卡尔坐标的转换

（1）从HBQT格点编码到格点斜坐标

编码，转换为格点斜坐标系有：

，其中：对中进行规则化，， 的结果如表3。

 

（2）从格点斜坐标到单元斜坐标

从格点斜坐标系到单元斜坐标系转换过程如下：

；

（3）从单元斜坐标到标准笛卡尔坐标

从单元斜坐标系到标准笛卡尔坐标系的转换过程如下：

；

2）从标准笛卡尔坐标到HBQT格点编码的转换

（1）从标准笛卡尔坐标到单元斜坐标

；

（2）从单元斜坐标到格点斜坐标

；

（3）从格点斜坐标到HBQT格点编码

；

4．HBQT结构下的六边形格网层次索引方法。

HBQT结构及编码运算进行单元索引算法的设计，包括：邻近关系和层次关系的确定。

1）邻近关系查找

邻近关系的查找，又称作邻近单元的查找。设单元，6个方向上的邻近单元的编码分别为：。

比如邻近单元的查找：6个方向上邻近单元的编码分别为： 、、、、、。

2）层次关系查找

（1）子单元的查找

对于孔径为4剖分的六边形格网单元，必有7个子单元，其中1个与它本身是对准的，其余6个是对准子单元的邻近单元。设第层的单元，查找其在层的子单元：

子单元中与它对准的中心子单元编码为：

周围的6个子单元分别中心子单元的6个邻近单元：

。

比如子单元查找： 子单元中与它对准的中心子单元编码为，剩下的6个子单元分别为： 、、、、、。

（2）父单元的查找

孔径为4的六边形格网单元分成两类：一类是与其父单元对准的单元，称为中心继承单元，该类单元具有1个父单元；另一类是与其父单元不对准，称之为偏心继承单元，该类单元具有2个父单元。设层的单元，有：

如果码元满足条件，那该单元就是中心继承单元，其父单元为：

如果码元满足，则该单元为偏心继承单元，由于，设剩下可能的码元全集为，计算集合，则集合中必有两个码元元素，设它们分别为、，则的两个父单元分别为：

，

。

举例说明HBQT索引中父单元的查找具体过程：

例如，属于中心继承单元，其父单元。

例如，属于偏心继承单元， ，集合，有、，两个父单元分别为：

， 。

5，实验

A、用例子验证HBQT结构的效率，设计了下面的实验：

（1）测试从十进制数转换为HBQT单元编码的效率，从单元编码转换成十进制数的效率；

（2）测试采用HBQT结构的六边形单元编码与标准笛卡儿坐标系的转换效率，从标准笛卡尔坐标系坐标转换为单元编码的效率；

（3）测试采用HBQT结构的六边形单元进行邻近单元查找的效率，HBQT单元编码运算的效率（利用HBQT编码的平方测试运算）。

实验数据：针对全球剖分单元进行测试，剖分为6~15层的单元，其中6~12选择全球所有单元，13~15由于单元数目高达377487362、1509949442、6039797762个，比如邻近单元搜索运算时间操过3个小时，并且随着层次的增加，搜索时间还将继续变长，因此13层以上只计算部分单元，选择13~15层中94371842个单元进行计算，与第12层的单元数一致，实际需要测试的只是单位时间内运算的效率。

实验环境：ThinkPad T61，CPU Intel(R) Core(TM)2 Duo，0.98GB内存，5400转硬盘，WinXP操作系统，下同。

实验结果时间如表4，记录运算时间的单位是ms。根据不同类型实验的运算时间和单元数目，可以得到不同层次单元编码各类运算的运行效率，即单元数/ms，如图10，将十进制数转换成HBQT单元编码的效率约为200单元/ms；笛卡尔坐标转换成HBQT单元编码的效率450~600单元/ms；HBQT单元编码转换成十进制数的效率4500~7000单元/ms；HBQT单元编码转换成笛卡尔坐标的效率3500~7000单元/ms；单元的邻近搜索效率约为110单元/ms；编码平方运算的效率约为50~160单元/ms。

 

B、用例子验证HBQT结构在全球空间数据显示时的效率，设计下面的实验，选择下面数据集进行测试：

下面的实验测试了全球六边形格网动态生成的效率，格网生成的过程实际上分别是邻近单元查找和子单元查找的过程。以第10层格网为基础，分别生成第7、8、9、11、12、13六层格网的坐标数据。由于动态生成算法是层次算法，因此测试的顺序是分两个方向  和进行的，实验结果如表5所示，全球格网生成的效果如图11所示，其中（a）是层次n=9的全球格网；（b）是层次n=10的全球格网；（c）是层次n=11的全球格网。

 （2）为了测试HBQT索引支持下全球离散格网加载空间数据后的显示效率，选取了下面数据集进行测试（该组实验结果是表6，效果如图12）：

一、全球GTOPO30高程晕渲数据，采样点数43200×21600，采样间隔0.00833333度，数据量6.95GB；

二、黄河小浪底库区的多光谱融合图像数据和DEM数据，采样点数皆为10764×8812，采样间隔25米，数据量271MB（图像）+361MB（DEM）；

三、郑州市QuickBird卫星图像，全色波段，地面分辨率0.61米，采样点数33837×32272数据量8.14 GB；

四、全球大陆的矢量边界数据，数据量9.90 MB；

五、中国全国县一级行政区划矢量数据，数据量17.3 MB。

图12中是利用HBQT索引支持的六边形全球离散格网系统加载空间数据后的显示效率，其中（a）对应的格网层次n=13；（b）对应的格网层次n=12；（c）对应的格网层次n=11；（d）对应的格网层次n=10。表6统计的是不同层次全球离散格网上利用HBQT索引加载空间数据（遥感图像数据+矢量数据）显示时部分指标的比较。

最后所应说明的是：以上实施例仅用以说明而非限定本发明的技术方案，尽管参照上述实施例对本发明进行了详细说明，本领域的普通技术人员应当理解；依然可以对本发明进行修改或者等同替换，而不脱离本发明的精神和范围的任何修改或局部替换，其均应涵盖在本发明的权利要求范围当中。