球面菱形網格遞歸剖分方法研究

張玉梅,陳維華,聶洪山,李鐵根,曾勝強,孫兆林

(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