基于全球三維空間網(wǎng)格的時空地理數(shù)據(jù)組織方法

潘良波，趙曉晶，周文

(1.正元地理信息集團股份有限公司，北京 101300； 2.北京市智慧管網(wǎng)安全評價及運營監(jiān)管工程技術(shù)研究中心，北京 101300；3.山東正元地球物理信息技術(shù)有限公司，山東 濟南 250000)

1 引 言

當前，測繪、遙感、衛(wèi)星導航、對地觀測等時空地理信息數(shù)據(jù)獲取技術(shù)越來越成熟[1]，數(shù)據(jù)體量也越來越大。但是不同領(lǐng)域、不同區(qū)域的數(shù)據(jù)有其獨立的格式、標準，很難進行統(tǒng)一的組織存儲、融合與管理[2]，不利于數(shù)據(jù)的進一步開發(fā)利用。如何將這些海量、多源、異構(gòu)的時空地理信息數(shù)據(jù)進行統(tǒng)一管理[3]，深度分析挖掘數(shù)據(jù)之間的關(guān)系，研究其時空發(fā)展規(guī)律，成為充分利用新一代信息技術(shù)的基礎(chǔ)[4]。此外，隨著地球空間元素的多元化，時空地理信息數(shù)據(jù)范圍從地球表面擴展到了地上地下全空間，迫切需要在傳統(tǒng)二維空間數(shù)據(jù)組織編碼的基礎(chǔ)上進行立體空間的延展[5，6]，建立滿足地上地下全空間的三維空間數(shù)據(jù)組織編碼體系[7～9]，進而實現(xiàn)對地上地下全空間多源數(shù)據(jù)的組織管理。

基于此，本文設(shè)計一種基于Geohash算法的全球三維空間網(wǎng)格剖分方法和編碼方式，為多元、多尺度、多語義、多模態(tài)的時空地理信息進行數(shù)據(jù)組織融合提供方法與解決思路，并顯著提高時空地理信息數(shù)據(jù)的檢索查詢效率。

2 三維空間網(wǎng)格剖分與編碼

2.1 三維空間網(wǎng)格剖分

全球三維空間網(wǎng)格剖分實現(xiàn)步驟主要包括如下內(nèi)容：

(1)球面網(wǎng)格剖分

根據(jù)Geohash算法，將地球球面理解為一個基于經(jīng)緯線的坐標系，緯度范圍在[-90°，90°]，經(jīng)度范圍在[-180°，180°]。用平面遞歸的方式將地球球面分解成多個級別的子塊，即利用等分法將經(jīng)度范圍和緯度范圍分別劃分為多級、等分的不同區(qū)間段。

(2)高程區(qū)間段劃分

在高程維度上，按照三維空間的高程范圍由低到高的順序，將地球球面以下的地下空間以及地球球面以上的地上空間的高程范圍，利用等分法的原則將高程維度劃分為不同級別的多個高程區(qū)間段，同一級別包括多個相同高度的高程區(qū)間段，高程級別越高，高程區(qū)間段的高度越短，所表示的空間位置越精確。在確定的三維空間內(nèi)，對高程區(qū)間進行n等分，得到第1級的三維空間網(wǎng)格的高程區(qū)間段，然后再對第1級的高程區(qū)間段進行n等分得到第2級的高程區(qū)間段，以此類推將高程區(qū)間劃分至最高級別。其中，n為高程維度每級的等分數(shù)，取值為大于等于2的任意正整數(shù)，n的取值主要影響每級高程區(qū)間段的精度，在實際應(yīng)用時應(yīng)根據(jù)編碼的空間范圍和實際所需精度等各方面的條件自行選擇。例如，以12級為最高級，取n=5，在確定的三維空間范圍內(nèi)，將高程區(qū)間進行5等分，獲得第1級的高程區(qū)間段；然后將第1級的每一個高程區(qū)間段再進行5等分，獲得第2級高程區(qū)間段，以此類推，第12級的高程區(qū)間段將高程平均分為512= 244 140 625段。

(3)網(wǎng)格組合

將球面維度的網(wǎng)格與高程維度的高程區(qū)間段組合形成以地球球面為基準的全球三維空間網(wǎng)格(圖1)，同一級別的網(wǎng)格在三個維度上包括的區(qū)間段是相同的，球面維度的單位為“度”(°)，高程維度的單位為m。

圖1 全球三維空間網(wǎng)格示意圖

2.2 三維空間網(wǎng)格編碼

全球三維空間網(wǎng)格的編碼包括三個步驟，分別為單維度編碼、轉(zhuǎn)碼和組碼。

(1)單維度編碼

單維度編碼即對經(jīng)度、緯度和高程三個維度上每一級別的每一個區(qū)間段進行編碼。其中：

經(jīng)度和緯度維度參考Geohash的編碼方式，采用二進制編碼。

高程維度的編碼方式為：以0，1，2，…，n-1的編碼方式為每一級每一個高程區(qū)間段進行編碼。每一級n等分的高程區(qū)間段從小到大分別用0、1、2…(n-1)表示，即第1級的高程區(qū)間段從小到大分別為0、1、2…(n-1)，第2級的高程區(qū)間段從小到大分別為00、01、02…0(n-1)、10、11、12…1(n-1)…(n-1)1、(n-1)2、(n-1)3…(n-1)(n-1)，以此類推，得到第1級到最高級所有高程區(qū)間段的編碼。

(2)轉(zhuǎn)碼

根據(jù)實際應(yīng)用需求，采用base 32的編碼方式，即Geohash編碼，將經(jīng)度和緯度維度的二進制編碼組合為球面網(wǎng)格的二進制編碼，并轉(zhuǎn)換為相應(yīng)的數(shù)值編碼(如表1)。

base 32編碼方式 表1

高程維度上，將高程區(qū)間段的編碼轉(zhuǎn)換為相應(yīng)的數(shù)值編碼，其中一個編碼表示唯一的一個數(shù)值，用數(shù)值編碼表示每一級每一個高程區(qū)間段的數(shù)值，即為每一級別每一個高程段的高程編碼，當n小于等于32時，可采用與Geohash編碼規(guī)則相同的base 32編碼方法。

例如，當n為5時，將每一級的高程區(qū)間段平均5等分，然后采用base 32編碼方法，即第1級的高程編碼為0、1、2、3、4，第2級的高程編碼分別為00、01、02、03、04、10、11、12、13、14、20、21、22、23、24、30、31、32、33、34、40、41、42、43、44，第1級別的高程編碼有0-4共5個，第2級別有52(即5×5)=25個，以此類推，直至將最高級的高程區(qū)間段完成編碼。

當n大于32時，base 32的編碼便不能滿足需求，需要采用其他的編碼方式進行轉(zhuǎn)碼，可以考慮采用base 36、base 64等編碼方式。

(3)組碼

將球面網(wǎng)格的編碼和高程維度的編碼進行交叉重組，在球面網(wǎng)格編碼的基礎(chǔ)上加入上述高程區(qū)間段的編碼，構(gòu)建形成全球三維空間網(wǎng)格的唯一編碼。每一級的全球三維空間網(wǎng)格編碼都是由相應(yīng)級別的球面網(wǎng)格編碼和相應(yīng)級別的高程區(qū)間段編碼組成，球面網(wǎng)格編碼在前，高程區(qū)間段編碼在后；每一級別的全球三維空間網(wǎng)格編碼的前綴都是該位置的上一級別的全球三維空間網(wǎng)格編碼。

3 基于三維空間網(wǎng)格的立體空間索引方法

全球三維空間網(wǎng)格在編碼過程中采用類似Z曲線的編碼方式。采用遞歸思想，將每一個三維空間網(wǎng)格分解為更高一級的網(wǎng)格時，編碼的順序是自相似的，進而在三維空間中形成三維的皮亞諾曲線。利用三維的皮亞諾曲線將三維空間轉(zhuǎn)換成一維曲線，進而編碼相似的網(wǎng)格其距離也相近，在空間檢索過程中只需要搜索編碼相似網(wǎng)格中的對象。

例如，在三維空間范圍內(nèi)，搜索某POI點周圍固定范圍內(nèi)的其他已知POI點，可根據(jù)搜索范圍、各級網(wǎng)格精度確定該點所在三維空間網(wǎng)格應(yīng)編碼的級別，并根據(jù)該點的經(jīng)緯度以及高程值確定所在網(wǎng)格的全球三維空間網(wǎng)格編碼，然后查找其周圍的26個三維空間網(wǎng)格，最后確定在這27個三維空間網(wǎng)格(包括矢量點所在的三維空間網(wǎng)格)中與其相近的其他已知矢量點的位置，并通過實際距離計算找到符合要求的矢量點。

4 案例分析

將本文所述時空地理數(shù)據(jù)組織方法應(yīng)用到實際生活中，首先確定空間編碼范圍，在此基礎(chǔ)上將三維空間劃分為多級網(wǎng)格，并且對每一個網(wǎng)格進行唯一編碼，以此作為三維空間索引的基礎(chǔ)。

由于每一級的每個三維空間網(wǎng)格都有其對應(yīng)的唯一編碼，并且每級編碼與其對應(yīng)的上一級編碼的前綴相同，這就保證了相近位置上全球三維空間網(wǎng)格編碼具有相似性，進而為三維空間矢量數(shù)據(jù)的查詢提供了便捷方法，大幅度降低了三維空間數(shù)據(jù)組織管理的復雜程度，減少了三維空間數(shù)據(jù)查詢的時間。

理論上，為了對數(shù)據(jù)進行更好的組織管理，高程范圍內(nèi)應(yīng)該包含全部的數(shù)據(jù)。但是，如果選取的高程范圍過大，編碼空間過大，數(shù)據(jù)查詢時無效數(shù)據(jù)很多，就加大了編碼的工作量，也加大了對計算機的性能要求，延長了對數(shù)據(jù)的查詢時間，不利于對數(shù)據(jù)的有效組織管理。因此，在獲取編碼空間時，應(yīng)避免出現(xiàn)選取的編碼空間過大或過小的問題。同時，為統(tǒng)一高程值，高程基準選擇1985國家高程基準；編碼空間的高程范圍為(-6371，6371)，單位為km，以地球表面為中間面，此空間可以保證三維空間網(wǎng)格的精度，并且可以容納更多的數(shù)據(jù)。

編碼空間確定后，將選取的三維空間劃分為不同級別的三維空間網(wǎng)格，每一級三維空間網(wǎng)格的平面網(wǎng)格按Geohash劃分，編碼采用Geohash編碼體系；為了與Geohash編碼具有更好的匹配性，高程同樣劃分為12級，并對每一級別的高程5等分進行對比，如表2所示。

不同級別高程維度誤差對比表 表2

上一級的高程區(qū)間段包含5個下一級的高程區(qū)間段。對三維空間網(wǎng)格進行編碼時，將球面維度的Geohash編碼放在前面，高程編碼放在后面，這樣就組成了全球三維空間網(wǎng)格編碼。其中每一個三維空間網(wǎng)格的編碼從左至右的第一位至倒數(shù)第三位的編碼序列表示該三維空間網(wǎng)格所在處上一級的編碼。比如，一個高程區(qū)間段的編碼數(shù)值為143021，表示一個6級的三維空間網(wǎng)格，則其對應(yīng)的高程編碼就是143021。如果該三維空間網(wǎng)格球面維度的Geohash編碼為wkmxfb，則其三維空間編碼為w1k4m3x0f2b1，該三維空間網(wǎng)格所在位置的第5級三維空間編碼為w1k4m3x0f2。

利用以下步驟可確定空間中一點的各級編碼：

(1)已知編碼空間的高程范圍為(-6371，6371)，單位為km，高程基準采用1985國家高程基準，對每一級別高程進行5等分，高程分為12級。

(2)三維空間中一點的坐標為：東經(jīng)116.604980°，北緯39.603027°，高程 -3.526 km，高程基準采用1985國家高程基準，若已知點的高程基準與三維空間編碼采用的高程基準不同，應(yīng)將點的高程統(tǒng)一到三維空間編碼采用的高程基準下。

(3)已知高程范圍為(-6371，6371)，對其5等分，得到的高程段分別為：(-6371，-3822.6]、(-3822.6， -1274.2]、(-1274.2，1274.2]、(1274.2，3822.6]、(3822.6，6371)，其中-3.526落在(-1274.2，1274.2]高程段中，編碼數(shù)值記為2，所以-3.526所在三維空間網(wǎng)格的第1級高程編碼為2；然后對(-1274.2，1274.2]高程段5等分，得到的高程段分別為：(-1274.2， -764.52]、(-764.52，-254.84]、(-254.84，254.84]、(254.84，764.52]、(764.52，1274.2]，其中-3.526落在(-254.84，254.84]高程段中，因此編碼數(shù)值記為2，所以該點所在三維空間網(wǎng)格的第2級高程編碼為22，以此類推，該點所在三維空間網(wǎng)格的第12級高程編碼為：222213042003，具體計算方法如表3所示。

-3.526 km處所在網(wǎng)格高程編碼 表3

(4)確定該點經(jīng)緯度所在位置的Geohash編碼為wx4cm3t0kgqf。

(5)將Geohash編碼與高程編碼交叉重組得到該點的三維空間編碼為w2x242c2m133t004k2g0q0f3。

續(xù)表3

5 結(jié) 論

本文基于Geohash算法突破二維空間索引編碼的方式，加入高程維度的剖分，將地上地下全空間剖分為多層級、多尺度的立體網(wǎng)格，并為所有立體網(wǎng)格建立全球唯一的網(wǎng)格編碼，以立體網(wǎng)格單元為基礎(chǔ)，把地上地下全空間大數(shù)據(jù)映射到統(tǒng)一空間，構(gòu)建統(tǒng)一時空基準下的時空對象關(guān)聯(lián)關(guān)系，進而為地上地下全空間數(shù)據(jù)的可視化、快速查詢統(tǒng)計和空間分析提供基礎(chǔ)支撐，同時可將空間數(shù)據(jù)查詢檢索效率提升10倍以上。采用基于Geohash算法的全球三維空間網(wǎng)格剖分方法建立索引系統(tǒng)能夠降低數(shù)據(jù)管理的復雜程度，可減少空間矢量數(shù)據(jù)查詢的時間，避免數(shù)據(jù)在高度上的不匹配，出現(xiàn)重疊、交叉等現(xiàn)象。