-
在全球离散格网系统中，格网单元编码的邻近搜索作为空间聚类、索引、查询等基本空间操作的基础，已广泛应用于全球大尺度空间数据的集成管理和应用分析[1, 2]。近年来，国内外学者对格网单元的邻近索引进行了深入的探讨，按不同剖分单元形状，可分为球面三角网的邻近搜索[3, 5]、球面菱形格网单元的邻近搜索[6]、孔径为2的四边形格网编码方案及对应的邻近搜索方法[7]、孔径为3的球面六边形格网编码与邻近索引[8, 9]、孔径为4的球面六边形格网编码运算与邻近索引[10, 11]等。以上方法均以格网编码代替传统的经纬度坐标进行运算，具有较高的搜索效率，已广泛应用于拓扑关系计算[12]、球面Voronoi图的生成[13, 14]和多源数据融合[15]等领域。
随着空间数据采集技术的飞速发展和全球经济一体化的不断深入，单一尺度的空间数据已无法满足日益增长的应用需求，许多应用领域如全球环境变化监测、灾害应急预警、资源可持续开发、国防安全乃至战争等等，越来越频繁地使用大范围(甚至全球)、多尺度(或多分辨率)空间数据进行综合集成分析，以获得单一尺度数据无法达到的、更高质量的决策结果[16, 17]。但是上述编码与索引成果大都局限于单个剖分层次(即单一尺度)，无法满足全球多尺度数据综合查询和集成操作的基本需求。设计与发展一种多层次格网单元的动态邻近搜索算法, 已成为进行全球多尺度空间数据综合查询及分析亟待解决的基本问题之一。
在目前众多的球面格网系统中，球面退化四叉树格网(degenerate quadtree grid，DQG)类似经纬度格网，不同的是涉及极点的格网退化为三角形，避免了经纬度格网的非均匀性和极点奇异性问题。与传统的四元三角网(quaternary triangular mesh，QTM)格网相比，基于DQG的格网单元具有几何结构简单、径向对称性、平移相和性和方向一致性的特点[18]，这使得其空间邻近索引更易实现。为此，本文基于DQG格网，利用视点相关技术建立层次细节(levels of detail, LOD)分层模型，并引入细分评价函数动态确定格网单元的邻近单元层次，最后设计实现了一种相邻格网单元层次差不超过1的动态多层次格网单元邻近搜索算法。
-
DQG的剖分原理为：以球面内接正八面体作为球面格网剖分基础，顶点选用球面主要点，包括南北两极，赤道和主子午线、90°子午线、180°子午线、270°子午线相交的点。经过首次剖分，球面被划分成8个等正球面三角形，亦称为初始八分体。然后，对每一个八分体的3个顶点按经纬度进行两两平分，在3边上得到3个新点，将球面三角形两腰上的点连接成一条纬线，再将该纬线的中点与球面三角形底边上的新点连成一条经线，这样就形成1个新的子三角形和2个子四边形。下一层次，对于子三角形按八分体中三角形剖分的方法进行剖分，对于子四边形按线性四叉树结构剖分(图 1(b))；按照同样的方法依次递归剖分(图 1(c))，直到满足相应的应用要求为止。DQG的地址码编码规则及行列号定义详见文献[19]。
图 1 基于DQG的八分体剖分原理
Figure 1. Partition Principle of Octant Based on DQG
-
本文采用视点相关的LOD分层技术，通过视点与球面形成的视野夹角以及格网单元中心与视线间的方向夹角来构建节点细分评价函数，利用细分评价函数[20]确定视野中格网单元的层次。
如图 2所示，α为视点P与球面形成的视野夹角，点T为球面上某一格网单元的中心点，点T与视线间的夹角为β，取两方面的评价标准：
$$ {f_1} = (90 - \alpha /2)/({d} \times {\lambda _1}) $$ (1) $$ {{f}_2} = \beta /({d} \times {\lambda _2}) $$ (2) 
图 2 视点对LOD层次的影响
Figure 2. The Influence of Viewpoint of LOD Level
式中，λ1、λ2为控制模型层次变化程度的系数，可通过实时交互的方式来进行设置; d为点下所在网格单元的纬度差。综合f1、f2，取f=f1×f2作为LOD模型的格网单元细分评价函数。当f < 1时，可以认为格网满足细分条件，必须细分得到下一层次格网，否则绘制当前层次的格网即可。通过此函数可以保证视野中心区域的格网层次最高，远离视点中心的区域层次较低，相邻格网单元间的层次差不超过1，并且随着视距的变化视野内的格网层次也随之变化。
-
由于采用了LOD分层技术，DQG格网单元与其邻近单元的剖分层次可能不一致，层次差可能为-1、0或1，而且随着视点的移动，邻近单元的层次也会发生变化。因此，DQG格网单元多层次邻近搜索的关键在于实时确定邻近单元的层次。
-
在DQG格网系统中，地址编码隐含了格网单元在球面上的位置，不同位置的格网单元有着不同的编码特征，并都包含具有公共边的边邻近格网单元与具有公共顶点的角邻近格网单元。每一个初始八分体单元的格网特征是类似的，以0单元初始八分体为例，按照格网单元的编码特征的不同，将格网单元分为极点三角形、“0”号四边形、“1”号四边形、“2”号四边形、“3”号四边形5类(图 3)。三角形类型为地址码编号都为0的球面三角形格网单元，其位置对应为极点区域；“0”号四边形、“1”号四边形、“2”号四边形和“3”号四边形分别为地址码末尾编号为0、1、2和3的球面四边形格网单元，对应了由父节点剖分得到的左上、右上、左下和右下子节点。依据上述编码特征的不同，邻近单元可能出现的剖分层次见表 1(假设本单元的层次为N)。
图 3 不同编码特征的格网单元分类
Figure 3. The Grid Classification of Different Encoding Features
表 1 不同格网类型的可能邻近单元层次
Table 1. Level of Adjacent Cell that May Occur of Different Grid Type
邻近关系 三角形 “0”号四边形 “1”号四边形 “2”号四边形 “3”号四边形 上边邻近 无 N-1或N或N+1 N-1或N或N+1 N或N+1 N或N+1 下边邻近 N或N+1 N或N+1 N或N+1 N-1或N或N+1 N-1或N或N+1 左边邻近 N-1或N或N+1 N-1或N或N+1 N或N+1 N-1或N或N+1 N或N+1 右边邻近 N-1或N或N+1 N或N+1 N-1或N或N+1 N或N+1 N-1或N或N+1 左上角邻近 无 N-1或N或N+1 无或N或N+1 无或N或N+1 N或N+1 右上角邻近 无 无或N或N+1 N-1或N或N+1 N或N+1 无或N或N+1 左下角邻近 无或N或N+1 无或N或N+1 N或N+1 N-1或N或N+1 无或N或N+1 右下角邻近 无或N或N+1 N或N+1 无或N或N+1 无或N或N+1 N-1或N或N+1 顶角邻近 N-1或N或N+1 无 无 无 无 确定邻近单元的层次的方法为：首先假设邻近单元的层次为可能出现的最低层次，并根据邻近关系搜索到其中心经纬度，然后根据中心经纬度求出邻近单元对应的细分评价函数值，若不满足继续细分条件，该最低层次即为邻近单元的层次；若满足继续细分条件，则对其进行细分之后再进行判断，直到不再满足继续细分条件为止。
-
由于视点的移动，视野内格网单元的层次及其邻近单元实时发生变化。因此，与单层次邻近搜索不同的是，DQG多层次邻近搜索是一个动态的过程，即格网单元的邻近搜索每一帧都要重新进行。算法的详细步骤如下。
输入 视野内某DQG格网P的地址码A1
1) 由A1计算P的剖分层次N0、Morton码(除首位外的地址码)和格网中心经纬度坐标(B，L)，计算方法可参见文献[21]；
2) 由Morton码计算对应单元的行列号I、J，计算方法可参见文献[6]；
3) 由N0、I计算格网纬度差B0、经度差L0；
4) 由(B，L)、B0、L0以及细分评价函数依据§2.1所述方法确定邻近单元的层次N1；
(1) 若N1= N0-1，则按表 2所述规则将I、J转换得到邻近单元的行列号；
(2) 若N1= N0，按文献[19]所述规则将I、J转换得到邻近单元的行列号；
(3) 若N1= N0+1，则按表 3所述规则将I、J转换得到邻近单元的行列号；
5) 由邻近单元的层次、行列号得到邻近单元的Morton码，是步骤2的逆过程，计算方法参见文献[6]；
6) 由邻近单元的Morton码及八分码合成得到邻近单元的地址码；
输出 邻近单元的地址码
需要注意的是，表 2和表 3只考虑了0单元初始八分体内部四边形的邻近单元行列号转换，而对于边缘四边形格网单元(包括左边缘、右边缘、左底角和右底角四边形格网)，由于其邻近搜索可能跨越了多个初始八分体，故其行列号转换需特殊考虑。
表 2 邻近单元层次比本单元低1时不同格网类型的行列号转换规则
Table 2. Transformation Rules of Row and Column in Different Types When Adjacent Cell in a Lower Level
邻近关系 三角形 “0”号四边形 “1”号四边形 “2”号四边形 “3”号四边形 上边邻近 无 (I/2-1, int(J/4))或
(I/2-1, J/2)(I/2-1, int(J/4))或
(I/2-1, int (J/2))- - 下边邻近 - - - (int (I/2)+1, J/2)
或(int (I/2)+1, J)(int (I/2)+1, int(J/2))
或(int (I/2)+1, J)左边邻近 (I, J) (I/2, J/2-1) - (int(I/2), J/2-1) - 右边邻近 (I, J) - (I/2, int(J/2)+1) - (int (I/2), int(J/2)+1) 左上角邻近 无 无或(I/2-1, J/4-1)或
(I/2-1, J/2-1)无 无 - 右上角邻近 无 无 无或(I/2-1, int(J/4)+1)或(I/2-1, int(J/2)+1) - 无 左下角邻近 无 无 - (int (I/2)+1, J/2-1)
或(int (I/2)+1, J-1)无或(int (I/2)+1,
J-1)右下角邻近 无 - 无 无或(int (I/2)+1,
J+1)(int (I/2)+1, int (J/2)
+1)或(int(I/2)+1, J+1)顶角邻近 (I, J) 无 无 无 无 注：“无”表示无此种邻近单元；“-”表示邻近单元层次不可能比本单元低1；int为取整运算 表 3 邻近单元层次比本单元高1时不同格网类型的行列号转换规则
Table 3. Transformation Rules of Row and Column in Different Types When Adjacent Cell Level one Level Higher
邻近关系 三角形 “0”号四边形 “1”号四边形 “2”号四边形 “3”号四边形 上边邻近 无 (2I-1, 2J);
(2I-1, 2J+1)或
(2I-1, J)(2I-1, 2J);
(2I-1, 2J+1)或
(2I-1, J)(2I-1, 2J);
(2I-1, 2J+1)(2I-1, 2J);
(2I-1, 2J+1)下边邻近 (I+2, J);
(I+2, J+1);
(I+2, J+2);
(I+2, J+3)(2I+2, 2J);
(2I+2, 2J+1)(2I+2, 2J);
(2I+2, 2J+1)(2I+2, 2J); (2I+2,
2J+1)或(2I+2, 4J);
(2I+2, 4J+1); (2I+2,
4J+2); (2I+2, 4J+3)(2I+2, 2J); (2I+2,
2J+1)或(2I+2, 4J);
(2I+2, 4J+1); (2I+2,
4J+2); (2I+2, 4J+3)左边邻近 (I, J);
(I+1, 1)(2I, 2J-1);
(2I+1, 2J-1)(2I, 2J-1);
(2I+1, 2J-1)(2I, 2J-1);
(2I+1, 2J-1)(2I, 2J);
(2I+1, 2J+1)右边邻近 (I, J);
(I+1, 0)(2I, 2J+2);
(2I+1, 2J+2)(2I, 2J+2);
(2I+1, 2J+2)(2I, 2J+2);
(2I+1, 2J+2)((2I, 2J+2);
(2I+1, 2J+2)左上角邻近 无 (2I-1, 2J-1)
或(2I-1, J-1)(2I-1, 2J-1)
或(2I-1, J-1)(2I-1, 2J-1) (2I-1, 2J-1)或
(2I-1, J-1)右上角邻近 无 (2I-1, 2J+2)
或(2I-1, J+1)(2I-1, 2J+2)
或(2I-1, J+1)(2I-1, 2J+2)或
(2I-1, J+1)(2I-1, 2J+2) 左下角邻近 (I+2, 3) (2I+2, 2J-1) (2I+2, 2J-1) (2I+2, 2J-1)或(2I+2, 4J-1) (2I+2, 2J-1)或(2I+2, 4J-1) 右下角邻近 (I+2, 0) (2I+2, 2J+2) (2I+2, 2J+2) (2I+2, 2J+2)或
(2I+2, 4J+4)(2I+2, 2J+2)或
(2I+2, 4J+4)顶角邻近 (I, J) 无 无 无 无 注：“无”表示无此种邻近单元 1) 左边缘四边形格网：搜索其左边、左上角和左下角邻近格网时，行号转换规则不变，列号转换为其所在行的最大列号。
2) 右边缘四边形格网：搜索其右边、右上角和右下角邻近格网时，行号转换规则不变，列号转换为0。
3) 左底角四边形格网：搜索其左边和左上角邻近格网时，行号转换规则不变，列号转换为其所在行的最大列号；搜索其左下角、下边和右下角邻近格网时，行号转换为其所在层次的最大行号，左下角邻近的列号转换为0，下边和右下角邻近的列号转换为所在行最大列号减去按表 2和表 3转换得到的列号。
4) 右底角四边形格网：搜索其右边和右上角邻近格网时，行号转换规则不变，列号转换为0；搜索其右下角、下边和左下角邻近格网时，行号转换为其所在层次的最大行号，右下角邻近的列号转换为所在行的最大列号，下边和左下角邻近的列号转换为所在行最大列号减去按表 2和表 3转换得到的列号。
-
为了验证算法的正确性和效率，作者将本文提出的算法与DQG单层次邻近搜索算法进行了对比实验，实验利用C#语言和DirectX三维图形接口构建系统平台。主要硬件环境配置为：CPU为英特尔Core P7450 2.13 GHz，内存2 GB，硬盘320 GB。
实验的基本原理为：固定视点位置，通过改变控制模型层次变化程度的系数λ1、λ2改变视野内的格网单元剖分层次。实验时，首先依据视点位置及细分评价函数确定视野中心格网，然后，从视野中心格网开始，分别用本文算法以及DQG单层次邻近搜索算法[19]搜索周围格网，直到搜索到的格网不再位于视野区域为止。图 4(a)为本文系统下全球远距离LOD格网视图(λ1=5，λ2=3)，表 4为对比实验的数据。由图 4(a)可以看出，本文系统视野中心格网层次最高，向外逐渐降低，比较符合人眼对视野中心具有更高关注度的视觉特点。从表 4可以看出，多层次模型大大简化了格网数据量(层次为11时，本文模型的格网简化效率接近80%)，所以，对同一区域进行格网单元的邻近搜索，多层次搜索的耗时成本约为单层次搜索的1/3。
图 4 基于DQG的全球多分辨率模型
Figure 4. The Global Multi-resolution Model Based on DQG
表 4 搜索效率对照表
Table 4. Comparison Table of Search Efficiency
λ1 λ2 最高层次 DQG多层次搜索 DQG单层次搜索 简化效率/(%) 格网数 耗时/ms 格网数 耗时/ms 3 3 5 142 7 378 13 62.43 5 5 6 464 24 1 431 64 67.58 8 6 7 1 735 107 5 547 283 68.72 9 8 8 5 921 406 21 888 1 303 72.95 13 13 9 21 227 1 652 86 897 4 993 75.57 15 15 10 81 086 7 029 346 371 20 104 76.59 18 18 11 314 964 27 562 1 377 794 80 089 77.14 在DQG多层次邻近搜索算法基础上，作者将本文模型用于全球多分辨率地形实时可视化表达。实验数据为美国地质测量局(USGS)于1996年发布的GTOPO30数据(分辨率为30 s，下载网站ftp://edcftp.cr.usgs.gov/data/gtopo30/global/)。由图 4可以看出，利用DirectX三维渲染引擎，采用本文提出的多分辨率模型并通过对格网加密(四边形格网按线性四叉树剖分方法加密，三角形格网按退化四叉树剖分方法加密)得到了较好的全球地形实时绘制效果。由图 4(b)、4(c)的地形格网视图可以看出，由于采用了LOD的绘制方法，相邻地形块之间可能存在裂缝，本文采用检测边界并改变格网构网方式的方法从根本上消除了裂缝，并且其平均刷新帧率达到了60帧/s。这进一步从另一方面证明了文中提出的邻近搜索算法能满足实时计算的需要。
-
本文以DQG格网为基础，针对全球大范围、多尺度空间数据索引及综合分析的需求，提出了一种格网单元的动态多层次邻近搜索算法。基于球面DQG，利用视点相关技术建立了LOD模型，引入细分评价函数动态确定格网单元的邻近单元层次，设计并实现了一种相邻格网单元层次差不超过1的动态多层次格网单元邻近搜索算法。
实验结果表明，本文提出的LOD模型大大简化了格网数据量，且对同一区域搜索时，本文算法的耗时成本约为单层次搜索算法的1/3；在该算法基础上，将本文算法用于全球多分辨率地形实时可视化表达，其平均刷新帧率达到了60帧/s，这从另一方面证明了该算法能满足实时计算的需要。
下一步的工作是矢量线所经过DQG格网单元的多层次定向搜索以及矢量数据与全球多分辨率地形动态无缝集成表达研究。
A Multi-level Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet
-
摘要: 格网单元的邻近搜索是聚类、索引、查询等空间操作的基础，但现有方法大都局限于单个剖分层次，无法直接满足全球多尺度数据集成查询和操作的应用需求。在球面退化四叉树格网（DQG）模型基础上，提出了一种基于多层次格网的邻近搜索算法。首先采用视点相关技术建立DQG格网的多层次模型，然后引入细分评价函数确定格网单元的邻近单元层次，设计并实现了一种相邻格网单元层次差不超过1的动态多层次格网单元邻近搜索算法，最后与单层次邻近搜索算法进行了对比实验。结果表明，搜索同一区域，该算法的耗时成本约为DQG单层次搜索算法的1/3（层次为11）；将该算法用于全球地形实时可视化表达，平均刷新帧率达到60帧/s。Abstract: The model of Global Discrete Grid is the base of Digital Earth and Spatial Information Grid. Adjacent search of grid cell is the basis of spatial operations, such as aggregation, index, and query, and has become one of the key problems in the global discrete grids researches. However, most existing methods are limited to single-level, cannot directly meet the application requirements of the global multi-scale data integration query and operation. A multi-level adjacent searching algorithm is proposed based on spherical DQG(degenerate quadtree grid) model in this paper. Firstly, the partition principle and encoding rules of the degenerate quadtree grid on sphere were analyzed, the multi-level DQG-based grid model is established by using view-dependent technique. Then, the segmentation evaluation function is introduced to determine the adjacent cell level of grid unit. A dynamic and multi-level adjacent searching algorithm is designed and implemented as level difference between adjacent grids is not more than 1. Finally, the contrast experiment with the single-level algorithm and the multi-level algorithm is done. The results show that the time consume of this algorithm is only about 1/3 to that of the DQG-based single-level algorithm (level 11) when searching for the same area, and the average frame refresh rate reaches 60 frames/s when this algorithm is used to real-time visualization of the global terrain. The new method not only eliminates the grids cracks between the same level or the different levels completely, but avoids the phenomenons of T connection and steep as well. In the end, the conclusions and future works are presented.
-
Key words:
- global discrete grid /
- DQG /
- multi-level adjacent search /
- address code /
- terrain visualization
-
表 1 不同格网类型的可能邻近单元层次
Table 1. Level of Adjacent Cell that May Occur of Different Grid Type
邻近关系 三角形 “0”号四边形 “1”号四边形 “2”号四边形 “3”号四边形 上边邻近 无 N-1或N或N+1 N-1或N或N+1 N或N+1 N或N+1 下边邻近 N或N+1 N或N+1 N或N+1 N-1或N或N+1 N-1或N或N+1 左边邻近 N-1或N或N+1 N-1或N或N+1 N或N+1 N-1或N或N+1 N或N+1 右边邻近 N-1或N或N+1 N或N+1 N-1或N或N+1 N或N+1 N-1或N或N+1 左上角邻近 无 N-1或N或N+1 无或N或N+1 无或N或N+1 N或N+1 右上角邻近 无 无或N或N+1 N-1或N或N+1 N或N+1 无或N或N+1 左下角邻近 无或N或N+1 无或N或N+1 N或N+1 N-1或N或N+1 无或N或N+1 右下角邻近 无或N或N+1 N或N+1 无或N或N+1 无或N或N+1 N-1或N或N+1 顶角邻近 N-1或N或N+1 无 无 无 无 
下载: 导出CSV
表 2 邻近单元层次比本单元低1时不同格网类型的行列号转换规则
Table 2. Transformation Rules of Row and Column in Different Types When Adjacent Cell in a Lower Level
邻近关系 三角形 “0”号四边形 “1”号四边形 “2”号四边形 “3”号四边形 上边邻近 无 (I/2-1, int(J/4))或
(I/2-1, J/2)(I/2-1, int(J/4))或
(I/2-1, int (J/2))- - 下边邻近 - - - (int (I/2)+1, J/2)
或(int (I/2)+1, J)(int (I/2)+1, int(J/2))
或(int (I/2)+1, J)左边邻近 (I, J) (I/2, J/2-1) - (int(I/2), J/2-1) - 右边邻近 (I, J) - (I/2, int(J/2)+1) - (int (I/2), int(J/2)+1) 左上角邻近 无 无或(I/2-1, J/4-1)或
(I/2-1, J/2-1)无 无 - 右上角邻近 无 无 无或(I/2-1, int(J/4)+1)或(I/2-1, int(J/2)+1) - 无 左下角邻近 无 无 - (int (I/2)+1, J/2-1)
或(int (I/2)+1, J-1)无或(int (I/2)+1,
J-1)右下角邻近 无 - 无 无或(int (I/2)+1,
J+1)(int (I/2)+1, int (J/2)
+1)或(int(I/2)+1, J+1)顶角邻近 (I, J) 无 无 无 无 注：“无”表示无此种邻近单元；“-”表示邻近单元层次不可能比本单元低1；int为取整运算
下载: 导出CSV
表 3 邻近单元层次比本单元高1时不同格网类型的行列号转换规则
Table 3. Transformation Rules of Row and Column in Different Types When Adjacent Cell Level one Level Higher
邻近关系 三角形 “0”号四边形 “1”号四边形 “2”号四边形 “3”号四边形 上边邻近 无 (2I-1, 2J);
(2I-1, 2J+1)或
(2I-1, J)(2I-1, 2J);
(2I-1, 2J+1)或
(2I-1, J)(2I-1, 2J);
(2I-1, 2J+1)(2I-1, 2J);
(2I-1, 2J+1)下边邻近 (I+2, J);
(I+2, J+1);
(I+2, J+2);
(I+2, J+3)(2I+2, 2J);
(2I+2, 2J+1)(2I+2, 2J);
(2I+2, 2J+1)(2I+2, 2J); (2I+2,
2J+1)或(2I+2, 4J);
(2I+2, 4J+1); (2I+2,
4J+2); (2I+2, 4J+3)(2I+2, 2J); (2I+2,
2J+1)或(2I+2, 4J);
(2I+2, 4J+1); (2I+2,
4J+2); (2I+2, 4J+3)左边邻近 (I, J);
(I+1, 1)(2I, 2J-1);
(2I+1, 2J-1)(2I, 2J-1);
(2I+1, 2J-1)(2I, 2J-1);
(2I+1, 2J-1)(2I, 2J);
(2I+1, 2J+1)右边邻近 (I, J);
(I+1, 0)(2I, 2J+2);
(2I+1, 2J+2)(2I, 2J+2);
(2I+1, 2J+2)(2I, 2J+2);
(2I+1, 2J+2)((2I, 2J+2);
(2I+1, 2J+2)左上角邻近 无 (2I-1, 2J-1)
或(2I-1, J-1)(2I-1, 2J-1)
或(2I-1, J-1)(2I-1, 2J-1) (2I-1, 2J-1)或
(2I-1, J-1)右上角邻近 无 (2I-1, 2J+2)
或(2I-1, J+1)(2I-1, 2J+2)
或(2I-1, J+1)(2I-1, 2J+2)或
(2I-1, J+1)(2I-1, 2J+2) 左下角邻近 (I+2, 3) (2I+2, 2J-1) (2I+2, 2J-1) (2I+2, 2J-1)或(2I+2, 4J-1) (2I+2, 2J-1)或(2I+2, 4J-1) 右下角邻近 (I+2, 0) (2I+2, 2J+2) (2I+2, 2J+2) (2I+2, 2J+2)或
(2I+2, 4J+4)(2I+2, 2J+2)或
(2I+2, 4J+4)顶角邻近 (I, J) 无 无 无 无 注：“无”表示无此种邻近单元
下载: 导出CSV
表 4 搜索效率对照表
Table 4. Comparison Table of Search Efficiency
λ1 λ2 最高层次 DQG多层次搜索 DQG单层次搜索 简化效率/(%) 格网数 耗时/ms 格网数 耗时/ms 3 3 5 142 7 378 13 62.43 5 5 6 464 24 1 431 64 67.58 8 6 7 1 735 107 5 547 283 68.72 9 8 8 5 921 406 21 888 1 303 72.95 13 13 9 21 227 1 652 86 897 4 993 75.57 15 15 10 81 086 7 029 346 371 20 104 76.59 18 18 11 314 964 27 562 1 377 794 80 089 77.14
下载: 导出CSV
-
[1] Vince A, Zheng X. Arithmetic and Fourier Transform for the PYXIS Multi-resolution Digital Earth Model[J]. International Journal of Digital Earth, 2009, 2(1):59-79 doi: 10.1080/17538940802657694 [2] Bernardin T, Cowgill E, Kreylos O, et al. Crusta:A New Virtual Globe for Real-Time Visualization of Sub-meter Digital Topography at Planetary Scales[J]. Computers & Geosciences, 2011, 37(1):75-85 https://www.sciencedirect.com/science/article/pii/S0098300410001251 [3] Goodchild M F, Yang S. A Hierarchical Spatial Data Structure for Global Geographic Information Systems[M]. New York:Academic Press Inc., 1992 [4] Bartholdi J, Goldsman P.Continuous Indexing of Hierarchical Subdivisions of the Globe[J].International Journal of Geographic Information Science, 2001, 15(6):489-522 doi: 10.1080/13658810110043603 [5] 孙文彬, 赵学胜.基于Quaternary编码的球面三角格网邻近搜索算法[J].武汉大学学报·信息科学版, 2007, 32(4):350-352 http://ch.whu.edu.cn/CN/abstract/abstract1865.shtml Sun Wenbin, Zhao Xuesheng. Algorithm of Neighbor Finding on Sphere Triangular Meshes with Quaternary Code[J]. Geomatics and Information Science of Wuhan University, 2007, 32(4):350-352 http://ch.whu.edu.cn/CN/abstract/abstract1865.shtml [6] 白建军, 赵学胜, 陈军.基于线性四叉树的全球离散格网索引[J].武汉大学学报·信息科学版, 2005, 30(9):805-808 http://ch.whu.edu.cn/CN/abstract/abstract2276.shtml Bai Jianjun, Zhao Xuesheng, Chen Jun. Indexing of Discrete Global Grids Using Linear Quadtree[J]. Geomatics and Information Science of Wuhan University, 2005, 30(9):805-808 http://ch.whu.edu.cn/CN/abstract/abstract2276.shtml [7] Amiri A M, Bhojani F, Samavati F. One-to-Two Digital Earth[M]//Bebis G, Boyle R, Parvin B, et al. Advances in Visual Computing. Berlin Springer Berlin Heidelberg, 2013: 681-692 [8] Sahr K. Icosahedral Modified Generalized Balanced Ternary and Aperture 3 Hexagon Tree: US 8229237[P]. 2012-7-24 [9] Peterson P. Close-Packed Uniformly Adjacent, Multi-resolutional Overlapping Spatial Data Ordering: US 8018458[P]. 2011-9-13 [10] Tong X, Ben J, Wang Y, et al. Efficient Encoding and Spatial Operation Scheme for Aperture 4 Hexagonal Discrete Global Grid System[J]. International Journal of Geographical Information Science, 2013, 27(5):898-921 doi: 10.1080/13658816.2012.725474 [11] 贲进, 童晓冲, 元朝鹏.孔径为4的全球六边形格网系统索引方法[J].测绘学报, 2011, 40(6):785-789 http://www.cnki.com.cn/Article/CJFDTotal-CHXB201106022.htm Ben Jin, Tong Xiaochong, Yuan Chaopeng. Indexing Schema of the Aperture 4 Hexagonal Discrete Global Grid System[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(6):785-789 http://www.cnki.com.cn/Article/CJFDTotal-CHXB201106022.htm [12] 侯妙乐, 邢华桥, 赵学胜, 等.球面四元三角网的复杂拓扑关系计算[J].武汉大学学报·信息科学版, 2012, 37(4):468-471 http://ch.whu.edu.cn/CN/abstract/abstract172.shtml Hou Miaole, Xing Huaqiao, Zhao Xuesheng, et al. Computing of Complicated Topological Relation in Spherical Surface Quaternary Triangular Mesh[J]. Geomatics and Information Science of Wuhan University, 2012, 37(4):468-471 http://ch.whu.edu.cn/CN/abstract/abstract172.shtml [13] Chen J, Zhao X, Li Z. An Algorithm for the Generation of Voronoi Diagrams on the Sphere Based on QTM[J].Photogrammetric Engineering & Remote Sensing, 2003, 69(1):79-89 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.3571 [14] 童晓冲, 贲进, 张永生.基于二十面体剖分格网的球面实体表达与Voronoi图生成[J].武汉大学学报·信息科学版, 2006, 31(11):966-970 http://ch.whu.edu.cn/CN/abstract/abstract2591.shtml Tong Xiaochong, Ben Jin, Zhang Yongsheng. Expression of Spherical Entities and Generation of Voronoi Diagram Based on Truncated Icosahedron DGG[J]. Geomatics and Information Science of Wuhan University, 2006, 31(11):966-970 http://ch.whu.edu.cn/CN/abstract/abstract2591.shtml [15] 王姣姣.矢量线与球面DQG地形集成的几何叠加算法[J].辽宁工程技术大学学报:自然科学版, 2013, 32(10):1399-1405 http://www.oalib.com/paper/5216563 Wang Jiaojiao. Geometric Overlay Algorithm for Egration of Vector Polyline and Dem Based on Spherical DQG[J]. Journal of Liaoning Technical University (Natural Science), 2013, 32(10):1399-1405 http://www.oalib.com/paper/5216563 [16] Chen H, Meer P. Robust Fusion of Uncertain Information[J]. Systems, Man, and Cybernetics, Part B:Cybernetics, IEEE Transactions on, 2005, 35(3):578-586 doi: 10.1109/TSMCB.2005.846659 [17] Dutton G. Modeling Locational Uncertainty via Hierarchical Tessellation[M]//Goodchild M, Gopal S. Accuracy of Spatial Databases. London: Taylor & Francis, 1989: 125-140 [18] 崔马军, 赵学胜.球面退化四叉树格网的剖分及变形分析[J].地理与地理信息科学, 2007, 23(6):23-25 http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_dlxygtyj200706005 Cui Majun, Zhao Xuesheng. Tessellation and Distortion Analysis Based on Spherical DQG[J].Geography and Geo-Information Science, 2007, 23(6):23-25 http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_dlxygtyj200706005 [19] 赵学胜, 崔马军, 李昂, 等.球面退化四叉树格网单元的邻近搜索算法[J].武汉大学学报·信息科学版, 2009, 34(4):479-482 http://ch.whu.edu.cn/CN/abstract/abstract1234.shtml Zhao Xuesheng, Cui Majun, Li Ang, et al. An Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet[J]. Geomatics and Information Science of Wuhan University, 2009, 34(4):479-482 http://ch.whu.edu.cn/CN/abstract/abstract1234.shtml [20] 许妙忠.大规模地形实时绘制的算法研究[J].武汉大学学报·信息科学版, 2005, 30(5):392-395 http://ch.whu.edu.cn/CN/abstract/abstract2179.shtml Xu Miaozhong. Research on Real-Time Rendering for Large Scale Terrain[J]. Geomatics and Information Science of Wuhan University, 2005, 30(5):392-395 http://ch.whu.edu.cn/CN/abstract/abstract2179.shtml [21] 崔马军, 高彦丽, 赵学胜.球面DQG地址码与经纬度坐标的快速转换算法[J].地理与地理信息科学, 2009, 25(3):42-44 http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_dlxygtyj200903010 Cui Majun, Gao Yanli, Zhao Xuesheng. A Fast Translating Algorithm Between DQG Code and Longitude/Latitude Coordinates[J]. Geography and Geo-Information Science, 2009, 25(3):42-44 http://industry.wanfangdata.com.cn/dl/Detail/Periodical?id=Periodical_dlxygtyj200903010 -
点击查看大图
图(4) / 表(4)
计量
- 文章访问数: 797
- HTML全文浏览量: 51
- PDF下载量: 296
- 被引次数: 0
