EN中文

地球信息科学学报 >

2015 , Vol. 17 >Issue 7: 789 - 797

DOI: https://doi.org/10.3724/SP.J.1047.2015.00789

正八面体的六边形离散格网系统生成算法

  • 贲进 , 1, 2, * ,
  • 童晓冲 1 ,
  • 周成虎 2 ,
  • 张凯欣 1
展开
  • 1. 信息工程大学地理空间信息学院,郑州 450052
  • 2. 中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室,北京 100101

作者简介：贲 进(1977-),男,博士,副教授,研究方向为空间数据模型、数字摄影测量。E-mail:

收稿日期: 2014-12-31

  要求修回日期: 2015-03-05

  网络出版日期: 2015-07-08

基金资助

国家自然科学基金项目(41271391、41201392)

中国博士后基金特别资助项目(2013T60161)

资源与环境信息系统国家重点实验室2013年度开放基金项目

收起

Construction Algorithm of Octahedron Based Hexagon Grid Systems

  • BEN Jin , 1, 2, * ,
  • TONG Xiaochong 1 ,
  • ZHOU Chenghu 2 ,
  • ZHANG Kaixin 1
Expand
  • 1. Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450001, China
  • 2. State Key Laboratory of Resource and Environmental Information System, Chinese Academy of Science, Beijing 100101, China
*Corresponding author: BEN Jin, E-mail:

Received date: 2014-12-31

  Request revised date: 2015-03-05

  Online published: 2015-07-08

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

全球离散格网系统是一种面向全球的新型多分辨率数据建模与表达解决方案。与三角形和四边形格网相比,六边形格网具有对称性好、采样效率高、一致相邻等特点,更利于地球空间信息的建模、整合与分析。本文提出一种能生成各种六边形格网系统的算法,将正八面体上的相邻三角面组合为“四边形逻辑结构”,建立三轴离散斜坐标系,描述不同六边形剖分产生的多分辨率格网。其采用面向对象的思想设计了软件模型,通过实验验证了算法的可行性,分析了算法的效率。结果表明,该算法采用统一的数学模型描述正八面体上各种类型六边形剖分产生的离散格网系统,对应的软件模型,将不同格网系统的共性特征和个性特征分离,便于维护和扩展,具有一定的灵活性。

关键词： 全球离散格网; 八面体; 六边形; 生成; 算法

本文引用格式

贲进 , 童晓冲 , 周成虎 , 张凯欣 . 正八面体的六边形离散格网系统生成算法[J]. 地球信息科学学报, 2015 , 17(7) : 789 -797 . DOI: 10.3724/SP.J.1047.2015.00789

Abstract

A Discrete Global Grid System (DGGS) is a set of related global grids at various scales which tessellate the earth into areal cells and associated cell points. As a promising global reference model it supports fast, seamless assimilation of numerous and disparate geo-data sources and sensor networks, regardless of scale, origin, datum, or projection. Compared with square and triangle grids, hexagon grids are uniform adjacency and they have better symmetry and more quantizing efficiency. These properties have made hexagon grids the potential data structure for massive geospatial modeling, integration and analysis. This paper presents a new octahedron-based construction algorithm which yields all types of hexagon DGGSs. It combines two adjacent triangle facets of an octahedron into a logical quad structure on which a three-axis coordinate system is established to describe the location of multi-resolution grid cells produced by different types of hexagon partitions. According to the characteristics of the algorithm, an object oriented software model is designed. Experiments are carried out to examine the feasibility, validity and efficiency of the model. The results indicate that the proposed algorithm employs a uniform mathematical model to describe all types of hexagon DGGSs. The corresponding software model separates the unique features of an individual DGGS from the commonness of all DGGSs, which makes the model extendable and flexible. The results also reveal that the efficiency of the algorithm remains stable regardless the increase of partition level. Two dominant factors are found to be responsible to the phenomenon. One is the maximum processing ability of the computer in which the experiments were carried out. The other is the I/O bottleneck of the computer which makes the CPU idle during the procedure of data export.

Key words： Discrete Global Grid System; octahedron; hexagon; construction; algorithm

1 引言

“全球离散格网系统”（Discrete Global Grid System,DGGS）是一种新型全球建模解决方案。它借助特定方法将地球均匀剖分,形成无缝无叠的多分辨率格网层次结构,采用单元地址编码,代替传统地理坐标参与数据操作。与以局部区域为研究对象的传统空间数据组织、应用模式相比,全球离散格网系统更适合解决大尺度的问题,且在结构上支持多分辨率数据的高效处理。
与三角形和四边形格网相比,六边形格网的拓扑关系一致,有利于邻近、连通等空间分析的实现[1];拓扑距离与欧氏空间直线距离的模式最匹配,有助于度量空间的建立[2];空间采样效率最高,有助于数据的可视化表达[2]。因此,作者认为六边形全球离散格网系统为海量空间数据的建模、整合与分析,提供了一种新颖的技术思路——融合多源空间信息,利用六边形格网的优异特性,在球面空间更方便地处理多分辨率数据,更准确地表达计算结果。
许多学者对正二十面体的六边形全球离散格网系统开展了深入研究,较具代表性的理论成果有：Sahr等在ISEA3H（Icosahedral Snyder Equal Area aperture 3 Hexagon）格网上建立的单元索引[3-4];Zheng、Vince等采用复平面向量组合设计的格网编码和傅里叶变换算法[5-6];贲进等设计的等积格网生成算法[7];童晓冲等设计的新型六边形层次索引结构[8-9]等。在工程实践方面,加拿大的PYXIS Innovation公司研发了基于ISEA3H格网的空间数据整合软件[10],欧空局（European Space Agency,ESA）在“土壤湿度和海洋盐分任务”（Soil Moisture and Ocean Salinity Mission,SMOS）中,采用ISEA4H格网采集和处理数据[11]。
部分学者也对正八面体的六边形全球离散格网系统开展了一些研究：Vince从理论上证明平衡三进制（Balanced Ternary,BT）可有效描述正八面体上孔径为3的六边形格网单元的层次关系[12];白建军和贲进等在此基础上,设计了4孔六边形格网索引算法,其因采用更适合计算机处理的二进制运算,故执行效率较高,约达到BT算法的600倍[13-14]。
目前,六边形全球离散格网系统的相关研究大多是用正二十面体,采用正八面体的研究较少。其主要原因是正八面体的全球离散格网系统,被认为比正二十面体的格网系统几何变形更大[15],有可能降低数据处理和表达的精度。作者认为,全球离散格网系统是多面体格网系统（即在多面体表面构建的多分辨率格网集合）在球面（参考椭球面）上的映射,多面体格网系统的几何、拓扑属性与平面多分辨率格网类似,其形状、大小完全一致,单元操作在理论上是严密的。变形发生在多面体表面到球面的映射过程中,可改进映射方法或提高剖分层次加以控制[16],使其满足应用的精度要求。因此,对全球离散格网系统的评价不仅要考虑几何变形,还要关注与之对应的多面体格网系统所具备的性质。
与二十面体相比,八面体与地球的相对位置关系更简单,坐标计算更简便[1];三角面总数更少,相邻面边界处单元的拼接更容易[3];有偶数个共顶点的三角面,更有利于建立格网量测体系（二十面体有奇数个共顶点的三角面,导致建立量测体系异常复杂）。上述特点使得正八面体的六边形离散格网系统,在矢量表达、空间分析等方面更具优势,开展相关研究具有重要意义。
本文详细分析了各类六边形递归剖分的特点,建立统一数学模型描述正八面体上的多分辨率六边形格网,并据此设计了格网生成算法。该算法不仅支持目前已发现的各类六边形格网系统,而且扩展后能生成新型格网系统,为不同格网系统之间的集成、比较和转换提供可行的技术方法。

2 递归剖分

在正八面体的三角面上可进行孔径为3、4的六边形层次递归剖分[1],根据其对偶的三角格网与三角面三边的关系,相同孔径的剖分（格网）又可进一步细分为I类（连线与边平行）、II类（连线与边垂直）和III类（连线与边既不平行也不垂直）[17]。对于相同孔径、相同剖分类型的格网系统,本文根据剖分频率的质因数[18]、初始剖分产生的六边形单元是否与三角面中心重合（对心、偏心）命名区分。
孔径为4的格网系统单元方向不随剖分层次变化,可能的情况有3种：频率质因子为2的I类偏心剖分（Aperture 4 Hexagon Class I eccentric,A4H-CI-2-ecc）、频率质因子为3的I类对心剖分A4H-CI-3-cc和频率质因子为3的II类对心剖分A4H-CII-3-cc,如图1（a）-（c）所示。
孔径为3的格网系统单元分辨率渐变较平滑,单元方向随剖分层次在I类和II类之间交替变化,如图1（d）所示。这类对心的格网系统目前只发现了一种,本文将其命名为A3H-CI/II-cc（Aperture 3 Hexagon Class I/II concentric）。
Fig. 1 Hexagonal recursive subdivision on a triangular face

图1 三角面上的六边形层次剖分

3 格网系统的数学模型

综上,正八面体上的六边形格网系统种类繁多,建立描述它们的统一数学模型,有助于不同格网系统之间的互操作,具有较好的理论意义和实用价值。
尽管三角面是构成正八面体的基本单位,但由于六边形格网系统中存在“跨面单元”,逐个三角面生成格网会导致不同三角面上单元数目不一致、格网坐标计算不便等问题,因此,本文将相邻三角面组合为“四边形逻辑结构”以简化算法。将正八面体的8个三角面合并为4个四边形逻辑结构,准确描述这些结构上的各种六边形层次递归剖分,便建立了六边形格网系统生成算法。
假设正八面体的中心位于三维笛卡尔坐标系原点,其顶点坐标分别为 V 0 0,0 , 1 2 , V 1 0 , 1 2 , 0 , 。生成算法需计算不同层次六边形单元中心及边界点（顶点）的位置。

3.1 离散格网坐标系的建立

在四边形逻辑结构上,采用行列、几何距离等二维坐标,足以描述某点在其表面的位置。而格网单元的空间位置,最终是在三维笛卡尔坐标系中计算和表示,因此,必须建立四边形逻辑结构上的局部坐标系和三维笛卡尔坐标系之间的联系。
由于四边形逻辑结构由2个不共面的三角面构成,故建立“离散格网坐标系”需准确、方便地计算格网单元的空间位置。该坐标系的原点位于四边形逻辑结构的角点（也是正八面体的顶点） V s ( 1 ≤ s ≤ 4 ) ,向量 V s V 5 → 、 V s V s + 1 → 、 V s V 0 → ,分别是I、K、J离散格网坐标轴。扩展到正八面体上,某一六边形格网单元中心可记为 H [ s , ( i , j ) ] ( i , j ∈ Z * ) ， 其中, Z * 是正整数集合,s是四边形逻辑结构的索引, ( i , j ) 是离散格网坐标（非负整数）,如图2所示。
Fig. 2 Discrete grid coordinate system

图2 离散格网坐标系

离散格网坐标系的参数（如坐标取值范围、坐标步长向量等）均与格网类型及剖分层次相关。假设格网系统的孔径为 a ( a = 3,4 ) ,剖分质因子为p,层次为 n ( n = 0,1 , 2,3 , ⋯ ) ,相关参数的计算公式如表1所示。
Tab. 1 Parameters of discrete grid coordinate system

表1 离散格网坐标系参数

参数 计算公式
边长等分数（频率） ν=3n+22 n=0,2,4,⋯2⋅3n+12 n=1,3,5,⋯∀a=3)ν=2n⋅p n=0,1,2,3,⋯(∀a=4)
I/J坐标取值范围 i,j∈[0,ν-1]
I/K/J坐标步长向量 vId=1νVsV5→, vIu=1νV0Vs+1→vK=1νVsVs+1→vJu=1νVsV0→, vJd=1νV5Vs+1→
表1中,步长向量是指在逻辑四边形结构上,某点沿I/K/J轴“向上”或“向下”移动一等分的距离,对应三维笛卡尔坐标的变化。

3.2 跨面单元的归属

虽然,相邻四边形逻辑结构公共边上的单元（如图2中单元B、C、F）理论上属于2个四边形,但是,这样会导致单元归属不唯一,不利于算法的设计。因此,本文规定I/J轴上的单元属于当前四边形结构。结合格网系统的几何特点,可推导出四边形逻辑结构上单元个数计算公式（表2）。
Tab. 2 Amount of cells on a logical quad structure

表2 四边形上的单元个数

格网系统 计算公式
A4H-CI-2-ecc nq=14ν2=4n
A4H-CI-3-cc nq=14ν2=9×4n-1 (n≠0)
A4H-CII-3-cc nq=13ν2=3×4n
A3H-CI/II-cc nq=13ν2=3×4n n=0,2,4,⋯14ν2=4n n=1,3,5,⋯

3.3 单元位置的计算

设某一六边形格网单元中心的离散格网坐标为 H [ s , ( i , j ) ] ,根据单元在四边形逻辑结构上的位置,其三维笛卡尔坐标可通过式（1）计算。
H [ s , ( i , j ) ] ≡ H ( x , y , z ) = V s + ( i - j ) ⋅ v I u + j ⋅ v K i > j V s + i ⋅ v K i = j V s + ( j - i ) ⋅ v J u + i ⋅ v K i < j （1）
式中,i、j的有效值与格网类型及剖分层次相关。

4 格网系统生成

在上述数学模型的基础上,结合各类六边形剖分的特点计算离散格网坐标系参数和单元位置,即可生成多分辨率格网。

4.1 A4H-CI-2-ecc格网系统

A4H-CI-2-ecc是由I类剖分产生的格网系统,相邻单元中心的连线与坐标轴平行,因此,I、J轴上的单元紧致（连续）排列,如图3所示。坐标取值范围可根据表1的公式计算,步长值 Δ i ( Δ j ) = 2 。单元中心位置确定后,可进一步讨论顶点的坐标。
（1）在 i > j 的情况下,单元中心位于下三角面。
若 j ≠ 0 ,则该单元的所有顶点都在下三角面内,如图3中 H 1 单元。根据几何关系,即可计算出单元顶点的坐标（式（2））。
v 0 = H 1 ( x , y , z ) + 2 3 ( v I d - v J d ) v 1 = H 1 ( x , y , z ) + 2 3 ( v I d + v K ) v 2 = H 1 ( x , y , z ) + 2 3 ( v K + v J d ) v 3 = H 1 ( x , y , z ) - 2 3 ( v I d - v J d ) v 4 = H 1 ( x , y , z ) - 2 3 ( v I d + v K ) v 5 = H 1 ( x , y , z ) - 2 3 ( v K + v J d ) （2）
若 j = 0 ,则该单元位于I坐标轴上,其顶点分布于2个四边形逻辑结构的下三角面内,如图3H2、O单元。对于中心不在正八面体顶点处的单元H2,有 j = 0 且 i ≠ 0 ,根据几何关系, v 1 、 v 2 、 v 3 的坐标与（2）式相同,其他顶点的坐标需重新计算（式（3））。
v 0 = H 1 ( x , y , z ) - 2 3 ( v K ' + v J d ′ ) v 4 = H 1 ( x , y , z ) - 2 3 ( v I d ′ - v J d ′ ) v 5 = H 1 ( x , y , z ) - 2 3 ( v I d ′ + v K ' ) （3）
对于中心位于正八面体顶点处的单元O,有 j = i = 0 ,其6个不共面的顶点坐标如式（4）所示。
v 0 = H 1 ( x , y , z ) + v I d v 1 = H 1 ( x , y , z ) + 2 3 ( v I d + v K ) v 2 = H 1 ( x , y , z ) + 2 3 ( v K + v J u ) v 3 = H 1 ( x , y , z ) + v J u v 4 = H 1 ( x , y , z ) - 2 3 ( v I u ′ + v K ' ) v 5 = H 1 ( x , y , z ) - 2 3 ( v K ' + v J d ′ ) （4）
式（3）-（4）中, v I d ′ 、 v J u ′ 、 v K ' 、 v J d ′ 、 v J u ′ 是相邻四边形逻辑结构上的步长向量。
（2）在 i = j 的情况下,单元中心位于三角面的公共边上,如图3中H3单元。根据几何关系,除位于下三角面上的顶点 v 0 、 v 1 和 v 5 的坐标与式（2）相同之外,顶点 v 2 、 v 3 和 v 4 的坐标如式（5）所示。
v 2 = H 3 ( x , y , z ) + 2 3 ( v K + v J u ) v 3 = H 3 ( x , y , z ) - 2 3 ( v I u - v J u ) v 4 = H 3 ( x , y , z ) - 2 3 ( v I u + v K ) （5）
（3）在 i < j 的情况下,单元中心位于上三角面,顶点坐标的计算与 i > j 的情况类似。
若 i ≠ 0 ,则该单元的所有顶点都在上三角面内,如图3中H4单元,顶点坐标计算如式（6）所示。
v 0 = H 4 ( x , y , z ) + 2 3 ( v I u - v J u ) v 1 = H 4 ( x , y , z ) + 2 3 ( v I u + v K ) v 2 = H 4 ( x , y , z ) + 2 3 ( v K + v J u ) v 3 = H 4 ( x , y , z ) - 2 3 ( v I u - v J u ) v 4 = H 4 ( x , y , z ) - 2 3 ( v I u + v K ) v 5 = H 4 ( x , y , z ) - 2 3 ( v K + v J u ) （6）
若 i = 0 ,则该单元位于 J 坐标轴上,其顶点分布于2个四边形逻辑结构的上三角面内,如图3中 H 5 单元。根据几何关系, v 0 、 v 1 、 v 2 的坐标与式（6）相同,其他顶点的坐标需要重新计算（式（7））。
v 3 = H 5 ( x , y , z ) - 2 3 ( v I u ′ + v K ' ) v 4 = H 5 ( x , y , z ) - 2 3 ( v K ' + v I u ′ ) v 5 = H 5 ( x , y , z ) + 2 3 ( v I u ′ - v J u ′ ) （7）
遍历正八面体的4个四边形逻辑结构,在每个四边形上按照 I ( J ) 优先的顺序遍历每个单元中心,按上述各种情况计算单元顶点,即可生成指定层次的格网。
Fig. 3 Construction of A4H-CI-2-ecc grid system

图3 A4H-CI-2-ecc格网系统生成

4.2 A4H-CI-3-cc格网系统

除剖分频率因子之外,A4H-CI-3-cc的形状和结构与A4H-CI-2-ecc相似,如图4所示。因此,其单元中心及顶点坐标的计算与上述基本一致,此处不再赘述。
Fig. 4 Construction of A4H-CI-3-cc grid system

图4 A4H-CI-3-cc格网系统生成

4.3 A4H-CII-3-cc格网系统

另一种孔径为4的II类对心剖分,会在正八面体顶点处产生四边形单元,如图5所示。单元中心坐标的取值范围根据表1公式计算,J方向的步长值 Δ j = 2 。随着I坐标的递增,J坐标的初始值js可根据式（8）计算。
j s = 0 i% 3 = 0 2 i% 3 = 1 1 i% 3 = 2 （8）
单元顶点坐标的计算与A4H-CII-3-ecc格网系统类似,不同的是单元位于正八面体顶点,即 i = j = 0 时,单元退化为四边形,如图5中单元O。顶点坐标如式（9）所示。
v 0 = H 1 ( x , y , z ) + v I d v 1 = H 1 ( x , y , z ) + v K v 2 = H 1 ( x , y , z ) + v J d v 4 = H 1 ( x , y , z ) - v K ' （9）
式中, v K ' 是相邻四边形逻辑结构上的步长向量。
Fig. 5 Construction of A4H-CII-3-cc grid system

图5 A4H-CII-3-cc格网系统生成

4.4 A3H-CI/II-cc格网系统

A3H-CI/II-cc格网系统是奇数、偶数层按照I类型、II类型交替剖分产生的格网系统,如图6所示。单元中心及顶点坐标的计算过程,可参照A4H-CI-2-ecc、A4H-CII-3-cc格网系统。
Fig. 6 Construction of A3H-CI/II-3-cc grid system

图6 A3H-CI/II-3-cc格网系统生成

5 算法实验与分析

通过上述算法分析可发现,构建不同格网系统的主要差别,在于四边形逻辑结构内部参数（如坐标范围、步长、相互关系等）的设置,其他步骤则基本类似。算法的这一特点非常有利于采用面向对象的设计思想,如图7所示的软件模型。采用C++语言,可将与格网类型密切相关的计算均设计为父类COctHexDS的纯虚函数,由不同类型的子格网类继承实现。
Fig. 7 Class relationships of the software model

图7 软件模型类结构

为了验证软件模型的可行性,作者在Windows 7 x64平台上,采用Visual C++2012开发了实验系统。取球半径为WGS-84参考椭球的平均半径[19],即R≈6 371 008.771 m。采用Fuller-Gray投影[20-21]建立球面和正八面体表面的对应关系,此时正八面体的边长为 L = 2 R ≈12 742 017.542 m,实验系统在正八面体表面和球面上生成的各种六边形离散格网系统（部分）见图8-10,格网层次 n = 3,4 , 5 。
Fig. 8 A4H-CI-3-cc discrete grid systems

图8 A4H-CI-3-cc离散格网系统

Fig. 9 A4H-CII-3-cc grid systems

图9 A4H-CII-3-cc离散格网系统

Fig. 10 A3H-C12-cc grid systems

图10 A3H-CI/II-cc离散格网系统

除了已知的4种六边形剖分,作者研究发现在正八面体上还可进行孔径为4、频率质因子为3的II类偏心剖分,记为A4H-CII-3-ecc。这种剖分在正八面体的顶点处产生半六边形单元,调整奇、偶数四边形面上的剖分方向,能得到一种完全由六边形单元覆盖的格网系统（图11）。这是目前为止具有这一性质的唯一一种格网系统。因为II类剖分产生的格网相邻单元中心的连线与坐标轴垂直,所以I、J轴上的单元非紧致（连续）排列。又因为相邻四边形面上的剖分方向随面编号、剖分层次交替变化,因此,随着坐标的递增,坐标的初始值也发生规律变化,具体计算公式如表3所示。J方向的步长值 Δ j = 2 ,单元顶点坐标与其他格网类似。
Fig. 11 A4H-CII-3-ecc subdivision

图11 A4H-CII-3-ecc剖分示意图

Tab. 3 Alternation rules of starting coordinate of J

表3 J坐标初始值的变化规律

面号 层次
奇数层 偶数层
Q0、Q2 js=1 i%3=00 i%3=12 i%3=2 js=2 i%3=01 i%3=10 i%3=2
Q1、Q3 js=2 i%3=01 i%3=10 i%3=2 js=1 i%3=00 i%3=12 i%3=2
为了生成A4H-CII-3-ecc格网系统,只需按照图7的类继承关系,在实验系统中派生新的子类,并根据表1-3中的公式,在对应的虚函数中调整四边形逻辑结构内部参数即可,无需改变软件模型本身。结果如图12所示,格网层次 n = 3,4 , 5 。
Fig. 12 A4H-CII-3-ecc grid systems

图12 A4H-CII-3-ecc离散格网系统

上述实验表明,本文提出的算法采用统一的数学模型描述正八面体上各种类型六边形剖分产生的离散格网系统。据此设计的软件模型将不同格网系统的共性特征和个性特征分离,不仅能生成目前已知的各类六边形格网系统,而且便于维护和扩展,具有一定的灵活性。
为了测试算法的效率,作者在ThinkPad W520（Intel Core i7-2720QM@2.2GHz,8G RAM,500G/7200rpm HD）的机器上,运行上述实验系统的Release版本,统计“计算并输出格网坐标”和“计算不输出格网坐标”2种情况下单位时间（ms）内处理单元的平均个数,结果如表4、5所示,绘制的曲线如图13所示。通过对图表的分析,可发现：
Tab. 4 Statistics of the executive time for ‘cell coordinates calculation and output’ case

表4 “计算并输出格网坐标”执行时间统计

层次 类型
A4H-CI-2-ecc A4H-CI-3-cc A4H-CII-3-cc A3H-CI/II-cc
单元总数（个） 执行时间（ms） 单元总数（个） 执行时间（ms） 单元总数（个） 执行时间（ms） 单元总数（个） 执行时间（ms）
3 66 16.000 146 18.585 194 27.217 110 15.789
4 258 15.584 578 25.682 770 59.149 326 29.406
5 1026 46.796 2306 102.462 3074 183.797 974 69.841
6 4098 190.198 9218 420.990 12 290 592.318 2918 163.602
7 16 386 755.080 36 866 1718.534 49 154 2301.864 8750 429.595
8 65 538 3004.401 147 458 6738.781 196 610 9044.530 26 246 1256.872
9 262 146 11 915.727 589 826 26 822.465 786 434 35 952.912 78 734 3669.043
10 1 048 578 47 541.621 2 359 298 107 450.836 3 145 730 144 432.048 236 198 10 835.268
Tab. 5 Statistics of the executive time for ‘cell coordinates calculation only’ case

表5 “计算不输出格网坐标”执行时间统计

层次 类型
A4H-CI-2-ecc A4H-CI-3-cc A4H-CII-3-cc A3H-CI/II-cc
单元总数（个） 执行时间（ms） 单元总数（个） 执行时间（ms） 单元总数（个） 执行时间（ms） 单元总数（个） 执行时间（ms）
3 66 15.000 146 16.000 194 15.319 110 16.000
4 258 15.483 578 16.000 770 36.028 326 17.715
5 1026 15.385 2306 33.489 3074 81.151 974 25.024
6 4098 61.452 9218 133.769 12 290 226.962 2918 96.053
7 16 386 239.961 36 866 539.189 49 154 761.228 8750 164.332
8 65 538 951.799 147 458 2143.378 196 610 2907.658 26 246 433.288
9 262 146 3800.154 589 826 8545.478 786 434 11 422.591 78 734 1216.758
10 1 048 578 15 209.788 2 359 298 34 110.661 3 145 730 45 598.220 236 198 3497.986
（1）随着剖分层次的深入,格网单元坐标的计算、输出效率逐渐到达实验计算机的极限,而与格网系统类型无关（图13）,这说明单机、单线程（进程）程序的格网处理效率有限;
（2）在计算并输出格网单元坐标的过程中,坐标计算仅用去约1/3的时间,其余约2/3的时间都用于坐标输出（图13）,这说明磁盘输出也是影响格网生成效率的主要因素。
Fig. 13 Efficiency curves of grid cell processing

图13 格网处理效率曲线

6 结语

本文将正八面体上的相邻三角面组合为“四边形逻辑结构”,并建立特殊坐标系描述不同六边形剖分产生的多分辨率格网,从而提出了一种支持现有各类六边形剖分的格网系统生成算法,且通过实验进行了验证。实验结果分析指出,对影响格网生成效率的主要因素,今后可采用多机、多线程并行计算技术进一步予以提高效率。
另外,本文只建立了各类六边形剖分与正八面体表面n:1的对应关系。为了实现数据在不同格网系统中的集成和相互转换,下一步还需研究各类六边形剖分之间n:n的对应关系。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Sahr K, White D, Kimerling J.Geodesic discrete global grid systems[J]. Cartography and Geographic Information Science, 2003,30(2):121-134.

[2]
Colin P, Sander P, Jonathan A.Rectangular and hexagonal grids used for observation, experiment and simulation in ecology[J]. Ecological Modelling, 2007,206:347-359.

[3]
Sahr K.Discrete global grid systems: A new class of geospatial data structures[D]. Oregon: University of Oregon, 2005.

[4]
Sahr K.Location coding on icosahedral aperture 3 hexagon discrete global grids[J]. Computers, Environment and Urban Systems, 2008,32(3):174-187.

[5]
Zheng X.Efficient Fourier transforms on hexagonal arrays[D]. Florida: University of Florida, 2007.

[6]
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.

[7]
贲进,童晓冲,张永生,等.球面等积网格系统生成算法与软件模型研究[J].测绘学报,2007,36(2):187-191.

[8]
童晓冲. 空间信息剖分组织的全球离散格网理论与方法[D].郑州:信息工程大学,2010.

[9]
Tong X C, Ben J, Wang Y, et al.Efficient encoding and spatial operation scheme for aperture4 hexagonal discrete global grid system[J]. International Journal of Geographical Information Science, 2013,27(5):898-921.

[10]
PYXIS Innovation. How PYXIS works-Pyxis public wiki[EB/OL]. 2014.

[11]
Europe Space Agency. SMOS mission overview[EB/OL]. 2014.

[12]
Vince A.Indexing the aperture 3 hexagonal discrete global grid[J]. Journal of Visual Communication & Image Representation, 2006, 17:1227-1236.

[13]
白建军. 基于正八面体的四孔六边形球面格网编码及索引[J].遥感学报,2011,15(6):1131-1137.

[14]
贲进,童晓冲,元朝鹏.孔径为4的全球六边形格网系统索引方法[J].测绘学报,2011,40(6):785-789.

[15]
White D, Kimerling J, Sahr K, et al.Comparing area and shape distortion on polyhedral-based recursive partitions of the sphere[J]. International Journal of Geographical Information Science, 1998,12(8):805-827.

[16]
童晓冲,贲进,汪滢.利用数值投影变换构建全球六边形离散格网[J].测绘学报,2013,42(2):268-276.

[17]
Kenner H.Geodesic math and how to use it[M]. California: California Press, 2003:32-35.

[18]
张永生,贲进,童晓冲,等.地球空间信息球面离散网格——理论、算法及应用[M].北京:科学出版社,2007:65-66.

[19]
吴忠性,杨启和.数学制图学原理[M].北京:测绘出版社,1989:87-89.

[20]
Gray R.Exact transformation equations for Fuller's world map[J]. Cartographica, 1995,32(3):17-25.

[21]
Crider J.Exact equations for Fuller's map projection and inverse[J]. Cartographica, 2004,43(1):67-72.

Options
文章导航

/

〈 〉