球面菱形网格递归剖分方法研究

张玉梅,陈维华,聂洪山,李铁根,曾胜强,孙兆林

(1.国防科技大学电子科学与工程学院,湖南长沙 410073;2.南京军区气象水文中心,江苏南京 210016）

球面菱形网格递归剖分方法研究

张玉梅1,陈维华2,聂洪山1,李铁根1,曾胜强1,孙兆林1

(1.国防科技大学电子科学与工程学院,湖南长沙 410073;2.南京军区气象水文中心,江苏南京 210016）

提出一种结合经纬线并且用正多面体逐级递归的思想对球面直接剖分的方法,该方法无需内接多面体和投影,剖分单元采用近似菱形,可以实现球面任意分辨率的无缝、无重叠剖分。每个剖分单元的顶点和中心点对应的地理坐标都容易求得,从而使剖分单元的编码与地理坐标之间的转换相对简单。

地球剖分;菱形剖分;剖分编码;经纬度;SRG

目前,GIS正面临着海量全球空间数据库、全球性问题研究以及位置相关信息社会化服务等方面的巨大挑战。传统的基于地图的空间信息表达、组织、管理和发布方式已不能满足全球空间信息管理的需要。随着航天遥感应用研究与理论探索的深入,尤其是在“数字地球(Digital Earth,DE）”[1]提出后, GIS所处理的不只是某一局部区域的信息,而是全球范围内连续的、多层次的、动态的环境资源和社会信息,传统平面数据模型逐渐暴露出投影复杂、缺乏多尺度数据集成管理等局限性,不能满足大范围甚至全球多分辨率海量数据管理的需要[2]。全球空间数据剖分系统(Global Geodata Partitioning System,G2PS）即在这一背景下提出,其研究如何将地球(或球面）剖分为等面积和等形状的层次状面片,并实现高效空间数据的表达和管理[3]。

1 球面网格剖分方法研究现状

目前根据剖分单元的形状特征将球面剖分系统分为规则剖分系统和不规则剖分系统,其中规则剖分系统包括基于地理坐标系的球面格网系统和基于正多面体剖分的球面格网系统[4]。

1.1 基于地理坐标系的球面网格

人们最早使用的球面网格为经纬网格(图 1）,基于大地坐标系统,将地球表面按相等经纬度增量划分成网格单元,所有的数据都与这些网格单元有关。它是适合人们认识地球习惯的一种模型,是现有大量空间数据集、处理算法以及软件的基础,也是目前GIS软件中处理算法的基础。但是这种格网存在面积变形、形状变形且由赤道向南北极递增,在南北两级网格退化成三角形而不是矩形,格网单元大小分布不均匀,不利于多分辨率、不同比例尺数据之间的转换[4],复杂的邻接关系不利于模拟应用。

图1 传统球面网格Fig.1 Traditional sphere grid

1.2 正多面体的球面网格剖分

20世纪80年代末以来,国内外学者对基于正多面体的球面网格剖分研究较多,其基本方法是以球体的内接正多面体在球面的投影为基础,对球面空间进行连续的递归剖分,包括正四面体、正六面体、正八面体、正十二面体和正二十面体以及14个半规则立体[5](图2）。以Dutton的基于八面体的四分三角形格网(Octahedral-Quaternary Triangular Mesh,OQTM）[6]和Fekete的基于正二十面体的球面四叉树(Sphere Quad Tree,SQ T）[7]为代表,其主要优点是对地球表面进行无缝、多级的格网划分,使全球空间数据能忽略投影的影响,在管理连续的、多层次和多分辨率的动态全球海量数据方面有着传统平面格网不具备的优势。

但是由球面的几何特性可知,区域剖分后产生的各个球面三角形在大小和形状上都不可避免地存在一定变形,各个球面三角形的上下方向不一致,边长和面积不全相等,即:没有一种剖分方法能使得球面各剖分单元具有完全相等的几何特征(如面积、边长、形状）,只能达到近似相等。特别是基于正多面体的剖分与地理坐标之间的转换比较复杂,不符合人们的一贯思维。

图2 正多面体球面网格剖分Fig.2 Sphere grid based on polyhedron

2 基于地理坐标的球面菱形网格递归剖分方法

2.1 SRG剖分思想的提出

评价网格系统优劣的指标主要有[2,8]:1）网格能以任意分辨率无缝、无重叠地覆盖全球;2）不同分辨率的网格能够形成一个高度一致的层次结构;3）网格系统对应一套有效的编码方案;4）网格系统与地理坐标之间的转换关系较简单;5）单元形状和结构完全一致。由于球面具有特殊的几何属性,因此任何一个网格系统都不能同时满足上述条件。而在实际应用中,对各种指标的要求也不一样,合格的网格系统应根据需要在各种标准之间取得平衡[9]。

基于地理坐标剖分产生的传统网格系统在理论和技术上起步较早,几乎所有的 GIS软件都采用了这种方式,因为地理坐标符合人们的思维习惯,计算简单、直观且与现有各类数据转换比较方便。基于多面体剖分产生的新型网格系统种类繁多,每种都针对不同的应用背景,绝大多数成果还仅限于学术研究,鲜有工程化;尽管在气候模拟、制图综合等分散领域有部分积累,但系统性和实用性不强,理论体系不够完善。

鉴于上述两种方法各有优缺点,并权衡以上5项评价指标,本文介绍一种新的剖分思路——基于地理坐标的球面菱形网格(Sphere Rhombus Grid, SRG）递归剖分方法。SRG结合两种格网系统的剖分方法,充分利用了经纬线,无需内接正多面体,无需投影,直接在球面用弧线连接进行递归菱形剖分,实现多分辨率层次性无缝、无重叠剖分。

2.2 SRG剖分过程

(1）0级剖分。首先用0°、90°、180°、270°经线把地球分成4等份,从0°开始自东向西分别编码为0、1、2、3(图3）

(2）1级剖分。以0号球面为例(图 4）,赤道将其等分为上下两部分,赤道以北的0°、90°经线是其上半部分的两条边,赤道以南的0°、90°经线是其下半部分的两条边。分别取各边的中点:北极点与赤道中间的纬线即北纬45°与上半部分的两条边交于两点A1、A2,恰好是上半部分两条边的中点;同样南极点与赤道中间的纬线即南纬45°与下半部分交于两点B 1、B2,恰是下半部分两条边的中点。0°、90°经线中间的45°经线与赤道的交点O1就是0号球面的中心点。

Fig.图3 3S RGSR 0-Glev 0el级 su剖bd分ivision

图4 SRG 1级剖分Fig.4 SRG first-level subdivision

用平滑弧线连接A1、O1,使之与赤道以北的90°经线平行;连接A2、O1,使之与赤道以北的0°经线平行;连接B1、O1,使之与赤道以南的90°经线平行;连接B2、O1,使之与赤道以南的0°经线平行。这样0号球面就被分为4个近似菱形球面,按照上下左右的顺序分别编码为00、01、02、03。其它球面类似,这样经过1级剖分,全球被分为4×4=16个菱形球面。

(3）2级剖分。对于00菱形球面,左右两个顶点A1、A2都在北纬45°纬线上,该纬线将其分为上下两部分。北纬45°纬线与上顶点所在纬线(即北极点）的中间纬线——北纬67.5°与其上边两条边交于两点,恰是这两条边的中点;同样北纬45°纬线与下顶点所在纬线(即赤道）的中间纬线——北纬22.5°与其下边两条边交于两点,恰是这两条边的中点。00四边形的中心点取其左右两个顶点连线(即北纬45°纬线的一部分）的中点:即北纬45°和东经45°交点(图5中点 P）。

00球面各边的中点与其中心点分别用弧线连接,4条弧线按照连接的方向或平行于A1O1或平行于A2O1。这样00球面就被近似等分为4个小菱形球面,按照上下左右的顺序编码为000、001、002、003 (图5）。其它菱形球面也可以按照上述方法进行2级剖分,01四边形被分为010、011、012、013 4个小的菱形球面……这样经过2级剖分,全球可分为4× 42=64个近似菱形球面。

(4）多级剖分。以此类推,逐层细分,每个菱形球面各边的中点都取其各边两个顶点所在两条纬线的中间纬线与这条边的交点,中心点都取其左右两个顶点的连线(属于某条纬线的一部分）的中点,中心点与各边中点分别连线,或平行于0°经线的一部分或平行于90°经线的一部分或平行于180°经线的一部分或平行于270°经线的一部分,经过 n级剖分,全球可分为4×4n个菱形球面(3级剖分见图6）。

图 5 SRG- 2级剖分Fig.5SRG secondlevel subdivision

图6 SRG 3级剖分Fig.6 SRG third-level subdivision

以上分析了剖分的具体方法,但对于全球而言,不同地区地形差异很大,而且不同地区的军事关注度差异也很大,因此,针对不同区域分辨率需求的不同,应采用不同级别的剖分。

3 SRG剖分编码

以上剖分过程中已进行了剖分编码,具体编码方法如下:n级剖分产生的菱形球面的编码长度为n +1,编码都是由0、1、2、3中的几位数字组合而成,各个剖分层次菱形球面编码按照从低级剖分到高级剖分顺序组织,不同级别之间有层次性。每个菱形球面都可分成4个小的菱形球面,4个小四边形按照上下左右的顺序分别对应0、1、2、3。编码的首位是几就代表该面片在几号球面上,以后的每一位都是在上一级菱形球面编码的基础上多编一位。假设第k层某个剖分面片的编码为a0a1a2…ak,其中 a1～ak是k层四分码,取值为0,1,2,3;a0由0级剖分产生,取值也是0,1,2,3。每个剖分面片都有唯一的编码与之对应,编码的长短反映了剖分的层次,剖分单元编码具有空间位置相关性。例如,1号球面经过2级剖分后产生的编码如图7所示。整个编码过程与DU TTON的Q TM编码[10]相似。

4 SRG的特点

(1）菱形剖分单元更合理。采用菱形剖分单元,是因为菱形结构类似于正方形格网,具有一致的方向性、径向对称性,并不依赖于从多面体表面到球体或椭球体表面的映射方法,可以直接利用基于平面四叉树的许多算法,因而在空间操作特别是邻近搜索方面更容易实现。另外,菱形格网还能和一个等面积格网或一个基于其他标准的、最优化的性能格网一起用[11]。

图7 SRG 2级剖分编码Fig.7 Codes of SRG second-level subdivision

(2）编码与地理坐标之间的转换较简单。SRG方法借鉴了传统基于地理坐标系的平面网格剖分方法,每个剖分单元的顶点和中心点都对应特定的地理坐标点,剖分过程与经纬度密切结合;菱形单元方向一致,中心点直接取左右两个顶点连线(某条纬线的一部分）的中点,计算方便;编码按照一定的规则,每个面片都有唯一的编码与之对应。

(3）剖分单元变形小。该方法结合了地理坐标,但汲取了正多面体逐级递归的剖分思路,每个面片都可以以任意分辨率剖分,采用了特定的弧线连接,剖分单元从赤道到两极都是相似的四边形,变形很小。

(4）无需投影,操作简单。该方法直接在球面操作,无需内接正多面体,无需投影,操作简单;能采用任意分辨率,基本实现了无缝、无重叠的全球剖分。

5 结语

传统的经纬度剖分和正多面体剖分都有其缺陷,本文采用了一种新的基于地理坐标的球面菱形网格递归剖分方法,剖分单元边界与经纬度紧密结合,使剖分单元的编码与地理坐标之间的转换相对容易;同时汲取了正多面体逐级递归剖分的思路,使剖分单元从赤道到两级的面积和形状变形减小,而且可以实现任意分辨率的剖分;另外SRG方法还具有操作简单的特点。

[1] GOODCH ILD M.Discrete Global Grids fo r Digital Earth[R]. International Conference on Discrete Global Grids.Califo rnia: Santa Barbara,2000.

[2] 赵学胜.基于QTM的球面Voronoi数据模型[M].北京:测绘出版社,2004.

[3] 程承旗,郭辉.全球地理信息系统(G2 IS）架构体系初探[J].地理信息世界,2007,5(6）:25-29.

[4] 宋树华,程承旗,关丽,等.全球空间数据剖分模型分析[J].地理与地理信息科学,2008,24(4）:11-15.

[5] WHITED,KIMERLINGA J,OVERTON W S.Cartographic and geometric componentsof a global sampling design for environmentalmonitoring[J].Cartography and Geographic Information Systems,1992,19(1）:5-22.

[6] DU TTON G.Imp roving locational specificity of map data——a multi-resolution,metadata-driven app roach and notation[J]. Geographical Information Systems,1996,10(3）:253-268.

[7] FEKETE G.Rendering and managing spherical data with sphere quadtrees[A].Proceedings of the First 1990 IEEE Conference on Visualization[C].I990.176-186.

[8] GOODCHILD M,YANG S.A hierarchical spatial data structure for global geographic information systems[J].Graphical Models and Image Processing,1992,54(1）:31-44.

[9] 张永生.地球空间信息球面离散网格——理论、算法及应用[M].北京:科学出版社,2007.

[10] DU TTON G.Universal Geospatial Data Exchange via Global Hierarchical Coordinates[C].International Conference on Discrete Global Grids,California:Santa Barbara,2000.

[11] WHITED,KIMERLINGA,SAHR K.Comparing area and shape distortion on polyhedral-based recursive partitions of the sphere [J].Geographical Information,Science,1998,12(8）:805-827.

Study on Sphere Rhombus Grid Recursive Subdivision

ZHANG Yu-mei1,CHEN Wei-hua2,N IE Hong-shan1,L I Tie-gen1,ZENG Sheng-qiang1,SUN Zhao-lin1
(1.College of Electronic Science and Engineering,N ational University of Defense Technology,Changsha 410073;
2.M eteorological and H y drologica l Center of N anjing M ilitary A rea Comm and,N anjing 210016,China）

In this paper,a new method of global subdivision is p roposed,w hich combines longitude and latitude and also the thinking of regular polyhedron′s recursive subdivision.It subdivides the earth directly on the sphere,with no internal polyhedron and no p rojection,using similar rhombus as subdivision units.The method can achieve a seam less sphere w ithout overlapping, w ith any resolution adop ted subdivision.As the co rresponding geographic coordinates of each unit′s vertexs and the focal point are easy to calculate,the conversion between subdivision unit′s coding and geographical coo rdinates is relatively simp le.

global subdivision;rhombus subdivision;subdivision coding;latitude and longitude;SRG

P208

A

1672-0504(2010）06-0034-04

2010-06-02;

2010-09-03

国家973计划项目(613990103）;国防科技大学科研计划项目(JC09-04-03）

张玉梅(1983-）,女,硕士,主要研究方向为嵌入式系统与固态存储。E-mail:zhangyumei1126@126.com