球面菱形網(wǎng)格遞歸剖分方法研究

張玉梅,陳維華,聶洪山,李鐵根,曾勝?gòu)?qiáng),孫兆林

(1.國(guó)防科技大學(xué)電子科學(xué)與工程學(xué)院,湖南長(zhǎng)沙 410073;2.南京軍區(qū)氣象水文中心,江蘇南京 210016）

球面菱形網(wǎng)格遞歸剖分方法研究

張玉梅1,陳維華2,聶洪山1,李鐵根1,曾勝?gòu)?qiáng)1,孫兆林1

(1.國(guó)防科技大學(xué)電子科學(xué)與工程學(xué)院,湖南長(zhǎng)沙 410073;2.南京軍區(qū)氣象水文中心,江蘇南京 210016）

提出一種結(jié)合經(jīng)緯線并且用正多面體逐級(jí)遞歸的思想對(duì)球面直接剖分的方法,該方法無(wú)需內(nèi)接多面體和投影,剖分單元采用近似菱形,可以實(shí)現(xiàn)球面任意分辨率的無(wú)縫、無(wú)重疊剖分。每個(gè)剖分單元的頂點(diǎn)和中心點(diǎn)對(duì)應(yīng)的地理坐標(biāo)都容易求得,從而使剖分單元的編碼與地理坐標(biāo)之間的轉(zhuǎn)換相對(duì)簡(jiǎn)單。

地球剖分;菱形剖分;剖分編碼;經(jīng)緯度;SRG

目前,GIS正面臨著海量全球空間數(shù)據(jù)庫(kù)、全球性問(wèn)題研究以及位置相關(guān)信息社會(huì)化服務(wù)等方面的巨大挑戰(zhàn)。傳統(tǒng)的基于地圖的空間信息表達(dá)、組織、管理和發(fā)布方式已不能滿足全球空間信息管理的需要。隨著航天遙感應(yīng)用研究與理論探索的深入,尤其是在“數(shù)字地球(Digital Earth,DE）”[1]提出后, GIS所處理的不只是某一局部區(qū)域的信息,而是全球范圍內(nèi)連續(xù)的、多層次的、動(dòng)態(tài)的環(huán)境資源和社會(huì)信息,傳統(tǒng)平面數(shù)據(jù)模型逐漸暴露出投影復(fù)雜、缺乏多尺度數(shù)據(jù)集成管理等局限性,不能滿足大范圍甚至全球多分辨率海量數(shù)據(jù)管理的需要[2]。全球空間數(shù)據(jù)剖分系統(tǒng)(Global Geodata Partitioning System,G2PS）即在這一背景下提出,其研究如何將地球(或球面）剖分為等面積和等形狀的層次狀面片,并實(shí)現(xiàn)高效空間數(shù)據(jù)的表達(dá)和管理[3]。

1 球面網(wǎng)格剖分方法研究現(xiàn)狀

目前根據(jù)剖分單元的形狀特征將球面剖分系統(tǒng)分為規(guī)則剖分系統(tǒng)和不規(guī)則剖分系統(tǒng),其中規(guī)則剖分系統(tǒng)包括基于地理坐標(biāo)系的球面格網(wǎng)系統(tǒng)和基于正多面體剖分的球面格網(wǎng)系統(tǒng)[4]。

1.1 基于地理坐標(biāo)系的球面網(wǎng)格

人們最早使用的球面網(wǎng)格為經(jīng)緯網(wǎng)格(圖 1）,基于大地坐標(biāo)系統(tǒng),將地球表面按相等經(jīng)緯度增量劃分成網(wǎng)格單元,所有的數(shù)據(jù)都與這些網(wǎng)格單元有關(guān)。它是適合人們認(rèn)識(shí)地球習(xí)慣的一種模型,是現(xiàn)有大量空間數(shù)據(jù)集、處理算法以及軟件的基礎(chǔ),也是目前GIS軟件中處理算法的基礎(chǔ)。但是這種格網(wǎng)存在面積變形、形狀變形且由赤道向南北極遞增,在南北兩級(jí)網(wǎng)格退化成三角形而不是矩形,格網(wǎng)單元大小分布不均勻,不利于多分辨率、不同比例尺數(shù)據(jù)之間的轉(zhuǎn)換[4],復(fù)雜的鄰接關(guān)系不利于模擬應(yīng)用。

圖1 傳統(tǒng)球面網(wǎng)格Fig.1 Traditional sphere grid

1.2 正多面體的球面網(wǎng)格剖分

20世紀(jì)80年代末以來(lái),國(guó)內(nèi)外學(xué)者對(duì)基于正多面體的球面網(wǎng)格剖分研究較多,其基本方法是以球體的內(nèi)接正多面體在球面的投影為基礎(chǔ),對(duì)球面空間進(jìn)行連續(xù)的遞歸剖分,包括正四面體、正六面體、正八面體、正十二面體和正二十面體以及14個(gè)半規(guī)則立體[5](圖2）。以Dutton的基于八面體的四分三角形格網(wǎng)(Octahedral-Quaternary Triangular Mesh,OQTM）[6]和Fekete的基于正二十面體的球面四叉樹(shù)(Sphere Quad Tree,SQ T）[7]為代表,其主要優(yōu)點(diǎn)是對(duì)地球表面進(jìn)行無(wú)縫、多級(jí)的格網(wǎng)劃分,使全球空間數(shù)據(jù)能忽略投影的影響,在管理連續(xù)的、多層次和多分辨率的動(dòng)態(tài)全球海量數(shù)據(jù)方面有著傳統(tǒng)平面格網(wǎng)不具備的優(yōu)勢(shì)。

但是由球面的幾何特性可知,區(qū)域剖分后產(chǎn)生的各個(gè)球面三角形在大小和形狀上都不可避免地存在一定變形,各個(gè)球面三角形的上下方向不一致,邊長(zhǎng)和面積不全相等,即:沒(méi)有一種剖分方法能使得球面各剖分單元具有完全相等的幾何特征(如面積、邊長(zhǎng)、形狀）,只能達(dá)到近似相等。特別是基于正多面體的剖分與地理坐標(biāo)之間的轉(zhuǎn)換比較復(fù)雜,不符合人們的一貫思維。

圖2 正多面體球面網(wǎng)格剖分Fig.2 Sphere grid based on polyhedron

2 基于地理坐標(biāo)的球面菱形網(wǎng)格遞歸剖分方法

2.1 SRG剖分思想的提出

評(píng)價(jià)網(wǎng)格系統(tǒng)優(yōu)劣的指標(biāo)主要有[2,8]:1）網(wǎng)格能以任意分辨率無(wú)縫、無(wú)重疊地覆蓋全球;2）不同分辨率的網(wǎng)格能夠形成一個(gè)高度一致的層次結(jié)構(gòu);3）網(wǎng)格系統(tǒng)對(duì)應(yīng)一套有效的編碼方案;4）網(wǎng)格系統(tǒng)與地理坐標(biāo)之間的轉(zhuǎn)換關(guān)系較簡(jiǎn)單;5）單元形狀和結(jié)構(gòu)完全一致。由于球面具有特殊的幾何屬性,因此任何一個(gè)網(wǎng)格系統(tǒng)都不能同時(shí)滿足上述條件。而在實(shí)際應(yīng)用中,對(duì)各種指標(biāo)的要求也不一樣,合格的網(wǎng)格系統(tǒng)應(yīng)根據(jù)需要在各種標(biāo)準(zhǔn)之間取得平衡[9]。

基于地理坐標(biāo)剖分產(chǎn)生的傳統(tǒng)網(wǎng)格系統(tǒng)在理論和技術(shù)上起步較早,幾乎所有的 GIS軟件都采用了這種方式,因?yàn)榈乩碜鴺?biāo)符合人們的思維習(xí)慣,計(jì)算簡(jiǎn)單、直觀且與現(xiàn)有各類數(shù)據(jù)轉(zhuǎn)換比較方便?；诙嗝骟w剖分產(chǎn)生的新型網(wǎng)格系統(tǒng)種類繁多,每種都針對(duì)不同的應(yīng)用背景,絕大多數(shù)成果還僅限于學(xué)術(shù)研究,鮮有工程化;盡管在氣候模擬、制圖綜合等分散領(lǐng)域有部分積累,但系統(tǒng)性和實(shí)用性不強(qiáng),理論體系不夠完善。

鑒于上述兩種方法各有優(yōu)缺點(diǎn),并權(quán)衡以上5項(xiàng)評(píng)價(jià)指標(biāo),本文介紹一種新的剖分思路——基于地理坐標(biāo)的球面菱形網(wǎng)格(Sphere Rhombus Grid, SRG）遞歸剖分方法。SRG結(jié)合兩種格網(wǎng)系統(tǒng)的剖分方法,充分利用了經(jīng)緯線,無(wú)需內(nèi)接正多面體,無(wú)需投影,直接在球面用弧線連接進(jìn)行遞歸菱形剖分,實(shí)現(xiàn)多分辨率層次性無(wú)縫、無(wú)重疊剖分。

2.2 SRG剖分過(guò)程

(1）0級(jí)剖分。首先用0°、90°、180°、270°經(jīng)線把地球分成4等份,從0°開(kāi)始自東向西分別編碼為0、1、2、3(圖3）

(2）1級(jí)剖分。以0號(hào)球面為例(圖 4）,赤道將其等分為上下兩部分,赤道以北的0°、90°經(jīng)線是其上半部分的兩條邊,赤道以南的0°、90°經(jīng)線是其下半部分的兩條邊。分別取各邊的中點(diǎn):北極點(diǎn)與赤道中間的緯線即北緯45°與上半部分的兩條邊交于兩點(diǎn)A1、A2,恰好是上半部分兩條邊的中點(diǎn);同樣南極點(diǎn)與赤道中間的緯線即南緯45°與下半部分交于兩點(diǎn)B 1、B2,恰是下半部分兩條邊的中點(diǎn)。0°、90°經(jīng)線中間的45°經(jīng)線與赤道的交點(diǎn)O1就是0號(hào)球面的中心點(diǎn)。

Fig.圖3 3S RGSR 0-Glev 0el級(jí) su剖bd分ivision

圖4 SRG 1級(jí)剖分Fig.4 SRG first-level subdivision

用平滑弧線連接A1、O1,使之與赤道以北的90°經(jīng)線平行;連接A2、O1,使之與赤道以北的0°經(jīng)線平行;連接B1、O1,使之與赤道以南的90°經(jīng)線平行;連接B2、O1,使之與赤道以南的0°經(jīng)線平行。這樣0號(hào)球面就被分為4個(gè)近似菱形球面,按照上下左右的順序分別編碼為00、01、02、03。其它球面類似,這樣經(jīng)過(guò)1級(jí)剖分,全球被分為4×4=16個(gè)菱形球面。

(3）2級(jí)剖分。對(duì)于00菱形球面,左右兩個(gè)頂點(diǎn)A1、A2都在北緯45°緯線上,該緯線將其分為上下兩部分。北緯45°緯線與上頂點(diǎn)所在緯線(即北極點(diǎn)）的中間緯線——北緯67.5°與其上邊兩條邊交于兩點(diǎn),恰是這兩條邊的中點(diǎn);同樣北緯45°緯線與下頂點(diǎn)所在緯線(即赤道）的中間緯線——北緯22.5°與其下邊兩條邊交于兩點(diǎn),恰是這兩條邊的中點(diǎn)。00四邊形的中心點(diǎn)取其左右兩個(gè)頂點(diǎn)連線(即北緯45°緯線的一部分）的中點(diǎn):即北緯45°和東經(jīng)45°交點(diǎn)(圖5中點(diǎn) P）。

00球面各邊的中點(diǎn)與其中心點(diǎn)分別用弧線連接,4條弧線按照連接的方向或平行于A1O1或平行于A2O1。這樣00球面就被近似等分為4個(gè)小菱形球面,按照上下左右的順序編碼為000、001、002、003 (圖5）。其它菱形球面也可以按照上述方法進(jìn)行2級(jí)剖分,01四邊形被分為010、011、012、013 4個(gè)小的菱形球面……這樣經(jīng)過(guò)2級(jí)剖分,全球可分為4× 42=64個(gè)近似菱形球面。

(4）多級(jí)剖分。以此類推,逐層細(xì)分,每個(gè)菱形球面各邊的中點(diǎn)都取其各邊兩個(gè)頂點(diǎn)所在兩條緯線的中間緯線與這條邊的交點(diǎn),中心點(diǎn)都取其左右兩個(gè)頂點(diǎn)的連線(屬于某條緯線的一部分）的中點(diǎn),中心點(diǎn)與各邊中點(diǎn)分別連線,或平行于0°經(jīng)線的一部分或平行于90°經(jīng)線的一部分或平行于180°經(jīng)線的一部分或平行于270°經(jīng)線的一部分,經(jīng)過(guò) n級(jí)剖分,全球可分為4×4n個(gè)菱形球面(3級(jí)剖分見(jiàn)圖6）。

圖 5 SRG- 2級(jí)剖分Fig.5SRG secondlevel subdivision

圖6 SRG 3級(jí)剖分Fig.6 SRG third-level subdivision

以上分析了剖分的具體方法,但對(duì)于全球而言,不同地區(qū)地形差異很大,而且不同地區(qū)的軍事關(guān)注度差異也很大,因此,針對(duì)不同區(qū)域分辨率需求的不同,應(yīng)采用不同級(jí)別的剖分。

3 SRG剖分編碼

以上剖分過(guò)程中已進(jìn)行了剖分編碼,具體編碼方法如下:n級(jí)剖分產(chǎn)生的菱形球面的編碼長(zhǎng)度為n +1,編碼都是由0、1、2、3中的幾位數(shù)字組合而成,各個(gè)剖分層次菱形球面編碼按照從低級(jí)剖分到高級(jí)剖分順序組織,不同級(jí)別之間有層次性。每個(gè)菱形球面都可分成4個(gè)小的菱形球面,4個(gè)小四邊形按照上下左右的順序分別對(duì)應(yīng)0、1、2、3。編碼的首位是幾就代表該面片在幾號(hào)球面上,以后的每一位都是在上一級(jí)菱形球面編碼的基礎(chǔ)上多編一位。假設(shè)第k層某個(gè)剖分面片的編碼為a0a1a2…ak,其中 a1～ak是k層四分碼,取值為0,1,2,3;a0由0級(jí)剖分產(chǎn)生,取值也是0,1,2,3。每個(gè)剖分面片都有唯一的編碼與之對(duì)應(yīng),編碼的長(zhǎng)短反映了剖分的層次,剖分單元編碼具有空間位置相關(guān)性。例如,1號(hào)球面經(jīng)過(guò)2級(jí)剖分后產(chǎn)生的編碼如圖7所示。整個(gè)編碼過(guò)程與DU TTON的Q TM編碼[10]相似。

4 SRG的特點(diǎn)

(1）菱形剖分單元更合理。采用菱形剖分單元,是因?yàn)榱庑谓Y(jié)構(gòu)類似于正方形格網(wǎng),具有一致的方向性、徑向?qū)ΨQ性,并不依賴于從多面體表面到球體或橢球體表面的映射方法,可以直接利用基于平面四叉樹(shù)的許多算法,因而在空間操作特別是鄰近搜索方面更容易實(shí)現(xiàn)。另外,菱形格網(wǎng)還能和一個(gè)等面積格網(wǎng)或一個(gè)基于其他標(biāo)準(zhǔn)的、最優(yōu)化的性能格網(wǎng)一起用[11]。

圖7 SRG 2級(jí)剖分編碼Fig.7 Codes of SRG second-level subdivision

(2）編碼與地理坐標(biāo)之間的轉(zhuǎn)換較簡(jiǎn)單。SRG方法借鑒了傳統(tǒng)基于地理坐標(biāo)系的平面網(wǎng)格剖分方法,每個(gè)剖分單元的頂點(diǎn)和中心點(diǎn)都對(duì)應(yīng)特定的地理坐標(biāo)點(diǎn),剖分過(guò)程與經(jīng)緯度密切結(jié)合;菱形單元方向一致,中心點(diǎn)直接取左右兩個(gè)頂點(diǎn)連線(某條緯線的一部分）的中點(diǎn),計(jì)算方便;編碼按照一定的規(guī)則,每個(gè)面片都有唯一的編碼與之對(duì)應(yīng)。

(3）剖分單元變形小。該方法結(jié)合了地理坐標(biāo),但汲取了正多面體逐級(jí)遞歸的剖分思路,每個(gè)面片都可以以任意分辨率剖分,采用了特定的弧線連接,剖分單元從赤道到兩極都是相似的四邊形,變形很小。

(4）無(wú)需投影,操作簡(jiǎn)單。該方法直接在球面操作,無(wú)需內(nèi)接正多面體,無(wú)需投影,操作簡(jiǎn)單;能采用任意分辨率,基本實(shí)現(xiàn)了無(wú)縫、無(wú)重疊的全球剖分。

5 結(jié)語(yǔ)

傳統(tǒng)的經(jīng)緯度剖分和正多面體剖分都有其缺陷,本文采用了一種新的基于地理坐標(biāo)的球面菱形網(wǎng)格遞歸剖分方法,剖分單元邊界與經(jīng)緯度緊密結(jié)合,使剖分單元的編碼與地理坐標(biāo)之間的轉(zhuǎn)換相對(duì)容易;同時(shí)汲取了正多面體逐級(jí)遞歸剖分的思路,使剖分單元從赤道到兩級(jí)的面積和形狀變形減小,而且可以實(shí)現(xiàn)任意分辨率的剖分;另外SRG方法還具有操作簡(jiǎn)單的特點(diǎn)。

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

[2] 趙學(xué)勝.基于QTM的球面Voronoi數(shù)據(jù)模型[M].北京:測(cè)繪出版社,2004.

[3] 程承旗,郭輝.全球地理信息系統(tǒng)(G2 IS）架構(gòu)體系初探[J].地理信息世界,2007,5(6）:25-29.

[4] 宋樹(shù)華,程承旗,關(guān)麗,等.全球空間數(shù)據(jù)剖分模型分析[J].地理與地理信息科學(xué),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] 張永生.地球空間信息球面離散網(wǎng)格——理論、算法及應(yīng)用[M].北京:科學(xué)出版社,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

國(guó)家973計(jì)劃項(xiàng)目(613990103）;國(guó)防科技大學(xué)科研計(jì)劃項(xiàng)目(JC09-04-03）

張玉梅(1983-）,女,碩士,主要研究方向?yàn)榍度胧较到y(tǒng)與固態(tài)存儲(chǔ)。E-mail:zhangyumei1126@126.com