專輯論文| 林冰仙：正二十面體球面菱形離散格網的編碼模型及其映射方法

《測繪學報》

構建與學術的橋樑 拉近與權威的距離

林冰仙1,2

1, 盛業華1,2,3, 閭國年1,2,3, 周良辰1,2

1. 南京師範大學虛擬地理環境教育部重點試驗室, 江蘇 南京 210023;

2. 江蘇省地理信息資源開發與利用協同創新中心, 江蘇 南京 210023;

3. 江蘇省地理環境演化國家重點試驗室培育建設點, 江蘇 南京 210023

收稿日期：2016-08-20； 修回日期：2016-10-20

基金項目：國家自然科學基金（41571381；41271383）；江蘇高校優勢學科建設工程資助項目

第一作者簡介：林冰仙 (1984—),女, 博士, 講師, 主要研究方向為虛擬地理環境。

E-mail: [email protected]

摘要：全球離散格網為全球尺度的空間數據組織與管理提供了基礎環境，而全球離散格網的編碼體系，則可屏蔽不同坐標參考框架下的坐標轉換，減少空間分析的複雜度，有利於數據的多尺度表達和統一建模。相對於其他類型的全球離散格網，基於正二十面體所構建的球面菱形離散格網具有更均勻的幾何性質，有利於球面空間數據的集成與表達。但基於正二十面體的球面菱形離散格網的初始菱形邊線並不貼合經緯線，這導致相對於基於正八面體的球面菱形離散格網，其格網結構更為複雜。這對構建正二十面體球面菱形離散格網的層次編碼模型和建立其與地理坐標間的映射關係轉換帶來了新的挑戰。針對這一問題，本文基於Hilbert曲線構建了正二十面體球面菱形離散格網編碼模型，並在此基礎上設計了格網編碼與地理坐標的相互轉換方法。研究表明，利用球面菱形離散格網與平面規則格網的相似性，基於Hilbert曲線構建的正二十面體球面菱形離散格網編碼模型能夠隱式表達空間尺度與位置信息，且在地理坐標與格網編碼轉換方面兼具效率與精度，可以支持全球海量空間數據建模、集成管理以及各類空間分析。

關鍵詞：全球離散格網 菱形 正二十面體 編碼 希爾伯特曲線

Coding Model and Mapping Method of Spherical Diamond Discrete Grids Based on Icosahedron

LIN Bingxian1,2

, XU Depeng1, SHENG Yehua1,2,3, LÜ Guonian1,2,3, ZHOU Liangchen1,2

Abstract: Discrete Global Grid (DGG) provides a fundamental environment for global-scale spatial data's organization and management. DGG's encoding scheme, which blocks coordinate transformation between different coordination reference frames and reduces the complexity of spatial analysis, contributes a lot to the multi-scale expression and unified modeling of spatial data. Compared with other kinds of DGGs, Diamond Discrete Global Grid (DDGG) based on icosahedron is beneficial to the spherical spatial data's integration and expression for much better geometric properties. However, its structure seems more complicated than DDGG on octahedron due to its initial diamond's edges cannot fit meridian and parallel. New challenges are posed when it comes to the construction of hierarchical encoding system and mapping relationship with geographic coordinates. On this issue, this paper presents a DDGG's coding system based on the Hilbert curve and designs conversion methods between codes and geographical coordinates. The study results indicate that this encoding system based on the Hilbert curve can express space scale and location information implicitly with the similarity between DDG and planar grid put into practice, and balances efficiency and accuracy of conversion between codes and geographical coordinates in order to support global massive spatial data's modeling, integrated management and all kinds of spatial analysis.

Key words: Discrete Global Gird diamond icosahedron encoding Hilbert curve

為了有效管理全球多尺度海量空間數據，多位學者研究了基於正多面體剖分地球的方法，將地球表面剖分成面積、形狀近似相等，具有多解析度層次結構的格網單元[

]，稱為正多面體全球離散格網系統 (discrete global grid system，DGGS)。常見的正多面體全球離散格網系統包括基於正六面體的四邊形格網[

-

]、基於正八面體的三角形格網[

-

]、基於正八面體的菱形格網[

-

][

]和基於正二十面體的三角形格網[

-

]、基於正二十面體的菱形格網[

-

]與基於正二十面體的六邊形格網[

-

]。正多面體全球離散格網基於正多面體與球面的映射關係進行球面遞歸剖分[

]，在全球範圍內是無縫的、穩定的和近似均勻的，在空間數據表達[

-

]總的來說，基於幾種正多面體剖分球面各有千秋。正六面體的每個面均是正方形，可以生成類似於經緯格網的交錯格網，因而被應用於地球系統模式計算中[

]。正八面體的6個頂點可以定位在兩個極點和4個等分的赤道點上，任意的經緯度坐標能較容易地定位到其中一個面上[

]，鑒於該特性可以較容易地實現空間數據的表達，如經典的QTM模型[

][

]。相比較而言，二十面體是幾種正多面體中面最小，最接近球面的正多面體，在此基礎上剖分的全球離散格網變形相對較小，具有更均勻的幾何性質，有利於全球空間數據集成與地球系統模式計算，因此逐步引起相關學者的關注相關研究者基於正二十面體三角形格網、六邊形格網的剖分方法分別設計了其相應的格網編碼方案。Fekete利用正二十面體三角形格網建立了SQT編碼，並在此基礎上研究了球面空間上的鄰近分析和可視化[

]。袁文採用L型空間填充曲線設計了正二十面體三角形格網的面片編碼模型，並給出了面片節點的生成、訪問及定址演算法[

]。Sahr受到GBT結構的啟發，在球面上藉助與廣義平衡三進位類似的編碼運算，提出了正二十面體六邊形格網編碼和快速索引演算法[

]。童曉沖基於全球六邊形格網提出了具備層次性的金字塔結構編碼方案，採用遞歸方法設計並實現了編碼與地理坐標的轉換演算法[

][

-

]，但鮮有對其編碼模型的研究。全球離散格網通常使用格網編碼代替地理坐標進行各種空間操作，因此編碼模型是格網系統至關重要的組成部分。格網編碼既隱含了對應單元的位置信息，又表達了比例尺和精度[

]基於正二十面體的球面菱形離散格網，有別於結構簡單的正八面體，其初始菱形塊的邊線並不貼合經緯線，且幾何性質、拓撲性質上都更為複雜，這對構建正二十面體球面菱形離散格網的層次編碼模型和建立其與地理坐標間的映射關係轉換帶來了新的挑戰。但值得注意的是，球面菱形離散格網採用四叉樹剖分，在基礎菱形內，其幾何結構與平面柵格類似，適於現有的空間填充曲線的應用。目前應用最廣泛的空間填充曲線包括Z曲線、Gray曲線及Hilbert曲線，不同的空間填充曲線具有不同的空間聚集能力，因而使得索引效率存在差異[

]。其中，Hilbert曲線被證明能夠最好保持空間點的局部鄰接性[

]

因此，本文基於Hilbert曲線構建了正二十面體球面菱形離散格網的編碼模型，在此基礎上研究了格網單元編碼與地理坐標的相互轉化演算法，並設計了相關試驗，對轉換精度與效率進行了分析。

1 正二十面體球面菱形離散格網剖分方法

本文所採用的剖分方法以球體的內接正二十面體作為球面格網劃分的基礎，在兩個極點各放置一個頂點，其中一條通過北極的邊線投影和0°經線重合 (

)。經緯度坐標下南北極兩處存在極點奇異性，因而需將球面上的幾何位置轉為以球心為原點的三維直角坐標系 (

) 形式表達[

]。合併相鄰的南北向三角形形成10個球面菱形，在三維直角坐標系下對球面菱形進行細化，採用大圓弧平分法確定4條邊的中點，點連線的球面投影即把球面菱形分為4個小球面菱形，依次類推，完成對整個球面近似均勻的剖分 (

)。基於此方法所得到的格網整體分佈均勻，格網單元面積、角度形變小、排列緊緻

本文所提出的編碼模型包括區位碼和Hilbert碼兩部分組成，可以採用如下CODE的形式表示

式中，D表示區位碼，用於索引正二十面體球面菱形格網的十個初始菱形塊，採用二進位碼錶示，在計算機上佔2個位元組 (16位)。H為Hilbert碼，以每個初始菱形塊左頂點對應的格網單元為起始點建立Hilbert填充曲線，對某個基菱形上的格網單元進行索引，同樣以二進位表示，每層於末尾增加2位 (bit)，因而隱含了格網的剖分層級、父子單元的Hilbert碼。本文規定以正二十面體0號基菱形為例，由Hilbert碼便能定位格網單元在基菱形內的位置，如圖 5中第2層的菱形塊對應的格網編碼為00001101。

[

]。其中，Hilbert曲線分為4種子象限形態，這決定了存在4種形式的狀態轉移向量，即{1，2，3，4}，{1，4，3，2}，{3，2，1，4}和{3，4，1，2}(

)。球面菱形離散格網在初始菱形塊內可以看作是傾斜的平面柵格，通過旋轉平面柵格上的狀態可以得到球面菱形塊上Hilbert曲線的4種狀態轉移向量 (

)。在空間層次分解時，結合象限的Hilbert碼和狀態轉移向量可以推導齣子象限的Hilbert碼和狀態轉移向量，其中狀態轉移向量表明子象限中曲線的旋轉與反射。

本文借鑒Hilbert曲線的空間層次分解方法，設計了地理坐標與格網編碼相互轉換的演算法。

地理坐標到格網編碼的轉換實質是自由球面點在格網上確定其所屬格網單元的過程。本文首先根據待求點所在的地圖比例尺查找確定其所在的目標層次L，在判斷待求點是否在指定剖分層次的基礎上，通過平面方程判別法逐層求取待定點在下一剖分層次中所屬的子菱形Hilbert碼，最終得到地理坐標所屬的球面菱形格網單元的編碼。具體的步驟如下 (圖 8)。

(2) 判斷地理坐標的落點區域，即正二十面體菱形格網的初始菱形塊d，得到對應的二進位區位碼：D=d，並以該初始菱形塊為當前基菱形；

(3) 若當前菱形的剖分層次l為目標層次L，則當前菱形塊即為地理坐標在指定剖分層次上對應的格網單元，將二進位區位碼D與Hilbert碼H組合成編碼CODE並輸出，演算法結束；否則，進入下一步；

12103313133的法向量。根據法線方程可以直接給出平面

xN×

+yN×

+zN×

=0。此時問題便轉化為判斷點和平面的位置關係，據此即可判斷待定點

和平面

13(5) 採用的同樣的方法，再對另外一個方向上菱形邊界

010232

表 1 求解新狀態轉移向量與Hilbert碼增量Tab. 1 Seeking new state transition vector and Hilbert code's increment

從格網編碼到地理坐標的轉換實際上是一個格網單元的編碼到格網單元中心點的球面經緯坐標的轉換。本文中格網單元的中心點即為菱形單元短軸的中點。轉換的基本思想是根據編碼進行單元的逐層遞歸逼近，直至定位到編碼所對應的菱形單元，再求出中點即可 (圖 10)。具體過程如下：

(1) 根據正二十面體與球面的對應關係獲取格網編碼中區位碼D對應的初始菱形頂點坐標

012

(2) 設定初始狀態轉移向量V，初始化格網剖分計數：l=0，目標層次L為Hilbert碼M位數的二分之一；

(3) 若當前菱形的層次l為目標層次L，輸出菱形單元中點的經緯度坐標，演算法結束；否則，進入下一步；

(4) 取Hilbert碼中的第2l+1、2l+2位二進位碼組成Hilbert增量k，由增量k和狀態轉移向量V根據表 2確定單元在當前菱形塊下所屬的象限號，依據狀態轉移向量V與得到的象限號通過表 1獲得該象限內的新狀態轉移向量v，重新設定狀態轉移向量：V=v；

表 2 求解象限號Tab. 2 Seeking quadrant number

0123和剖分計數

：

=

+1。返回步驟 (3)。

4 試驗與分析

[

]。絕對精度指的是將地理坐標形式的點或球面編碼轉換為對應的格網編碼或地理坐標后，再將其轉換回輸入形式得到輸出結果，對比輸入和輸出的坐標點球面距離或者編碼值，如果二者在一個格網剖分單元內，則轉換演算法符合格網絕對精度的要求。為了分析本文提出的編碼轉換演算法效率與精度，選擇不同數量的 (2000、1萬、10萬、100萬) 隨機坐標點在不同層次下 (12、14、16、19、21層，對應比例尺分別為1:400萬、1:100萬、1:25萬、1:5萬、1:1萬) 進行編碼與地理坐標的相互轉換試驗，與White提出的Morton碼編碼方案[

]為編碼轉換精度評判標準。主要硬體配置環境為：CPU為Intel (R) Core (TM) i7-4770 3.10 GHz，8 GB內存，1 TB硬碟，採用VC++ 2013作為基礎開發平台。試驗結果如下 (

)。

表 3 不同點數不同剖分層級地理坐標和格網編碼的相互轉換效率與精度Tab. 3 Conversion efficiency and accuracy between geographical coordinates and codes on different subdivision level

從圖 11可以發現，地理坐標轉格網編碼后的絕對精度誤差隨著剖分層級的增加而迅速減小，綜合對應剖分層級 (12、14、16、19、21層) 下菱形單元的邊長表 4來看，轉換的絕對精度始終控制在一個格網單元內。從表 3可知，格網編碼轉地理坐標后格網編碼值保持不變，前後所表示的格網單元始終為同一個單元。綜上分析，本文提出的坐標編碼轉換演算法以遞歸逼近方法為基礎，相當於進行了一次格網單元局部的遞歸剖分，因而可以保證轉換演算法滿足絕對精度的要求。

剖分層次11121314151617菱形邊長/m50002000100061030515376對應比例尺1:1000萬1:500萬無1:100萬1:50萬1:25萬1:10萬剖分層次18192021222324菱形邊長/m3818105210.6對應比例尺1:5萬無1:1萬1:50001:25001:10001:500[

]進行地理坐標與格網編碼轉換的對比試驗。從

可以發現，隨著剖分層級的增加，基於兩種編碼模型的地理坐標與網格編碼的轉換效率均逐步下降，轉換耗時呈現線性增長，而兩者之間的效率表現幾近一致。由於格網的剖分中心、菱形塊的棱邊中點與球心構成兩個扇面，子菱形歸屬只需要與這兩個扇面進行2次位置判斷 (

)，因而均能夠在顧及轉換精度的前提下實現坐標向編碼的快速轉換。

值得注意的是，相比White在Z曲線基礎上提出的編碼方案，本文所提出的基於Hilbert曲線的編碼模型對於空間數據的局部鄰接性保持更好，因此在後續的空間數據索引、拓撲分析等方面具有明顯的優勢。

5 結論

本文在正二十面體球面菱形離散格網剖分方法的基礎上，考慮到在球面上難以直接構建全球連續的菱形格網編碼，利用基礎菱形內部與二維柵格的相似性，採用分區編碼與二進位的Hilbert曲線結合的方案，構建了一種具有層次結構的正二十面體球面菱形離散格網編碼模型。基於此，本文借鑒平面柵格上基於空間層次分解的Hilbert碼的生成演算法，採用迭代細化的規則方法構造球面Hilbert曲線的同時實現了經緯度向格網編碼的轉換，並進一步實現了對球面菱形離散格網編碼的反向解碼。研究表明，由於球面菱形離散格網在結構上與平面規則格網具有相似性，因此基於Hilbert曲線的編碼模型能夠在地理坐標與格網編碼轉換方面兼具效率與精度，可以支撐全球海量空間數據建模、集成管理以及各類空間分析。

【引文格式】林冰仙，許德朋，盛業華，等。 正二十面體球面菱形離散格網的編碼模型及其映射方法[J]. 測繪學報，2016，45(S1)：23-31. DOI: 10.11947/j.AGCS.2016.F003

圖片| 太空俯瞰地球，衛星視角下的農田竟如此壯觀！

權威 | 專業 | 學術 | 前沿

微信投稿郵箱 | [email protected]

歡迎加入《測繪學報》作者QQ群： 297834524

進群請備註：姓名+單位+稿件編號