基于八叉樹的三維室內(nèi)地圖數(shù)據(jù)快速檢索方法

呂宏武 付俊強(qiáng) 王慧強(qiáng) 李冰洋 袁泉 陳詩軍 陳大偉

摘 要：針對(duì)室內(nèi)三維地圖中數(shù)據(jù)檢索效率不高的問題，提出了一種基于八叉樹的室內(nèi)三維地圖數(shù)據(jù)檢索方法。首先，根據(jù)八叉樹的場景分割方法對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ);然后，對(duì)數(shù)據(jù)進(jìn)行編碼以方便尋址;其次，為數(shù)據(jù)添加房間隔斷約束條件對(duì)檢索數(shù)據(jù)進(jìn)行篩選;最后，對(duì)室內(nèi)地圖數(shù)據(jù)進(jìn)行檢索。與不具有約束條件的搜索方法相比，搜索代價(jià)平均降低了25個(gè)百分點(diǎn)，且搜索時(shí)間更加穩(wěn)定。所提方法可以顯著地提高室內(nèi)三維地圖數(shù)據(jù)的應(yīng)用效率。

關(guān)鍵詞：三維室內(nèi)地圖;地圖數(shù)據(jù);八叉樹;鄰居搜索;封閉性約束

中圖分類號(hào)： TP391

文獻(xiàn)標(biāo)志碼：A

Abstract： To solve the low efficiency problem of data retrieval in indoor three-dimensional （3D） maps， an indoor 3D map data retrieval method based on octree was proposed. Firstly， the data was stored according to the octree segmentation method. Secondly， the data was encoded to facilitate addressing. Thirdly， the search data was filtered by adding a room interval constraint to the data. Finally， the indoor map data was retrieved. Compared with the search method without constraints， the search cost of the proposed method was reduced by 25 percentage points on average， and the search time was more stable. Therefore， the proposed method can significantly improve the application efficiency of indoor 3D map data.

Key words： 3D indoor map; map data; octree; neighbor search; closedness constraint

0 引言

現(xiàn)如今，人們?nèi)粘Ｉ钪械暮芏喾矫娑夹枰貓D的支持，這些地圖的形式有紙質(zhì)地圖、電子地圖以及三維地圖等，無論是哪種形式的地圖，其使用效率一直是用戶所關(guān)心的問題。地圖數(shù)據(jù)的檢索在地圖數(shù)據(jù)更新、定位、導(dǎo)航呈現(xiàn)、動(dòng)態(tài)路徑規(guī)劃與網(wǎng)元布局等地圖技術(shù)基礎(chǔ)領(lǐng)域具有不可或缺的作用。張永玉等[1]指出傳統(tǒng)的數(shù)據(jù)搜索方法，只是將數(shù)據(jù)進(jìn)行簡單的存儲(chǔ)，并沒有使用任何數(shù)據(jù)結(jié)構(gòu)，這樣造成的結(jié)果就是無論在搜索時(shí)間上還是搜索穩(wěn)定性上都不是很理想，而室內(nèi)環(huán)境具有數(shù)據(jù)多變、物體繁多且體積較小的特點(diǎn)，在此環(huán)境下，傳統(tǒng)搜索方法的缺點(diǎn)無疑被再一次放大，因此，如何對(duì)三維室內(nèi)地圖數(shù)據(jù)進(jìn)行快速的檢索是一個(gè)十分有價(jià)值的研究課題。

在室外環(huán)境下，為了提高地圖數(shù)據(jù)的檢索效率，常常采用圖幅分幅的方式，其將地圖想象成一個(gè)俯視圖平面，然后對(duì)此平面進(jìn)行網(wǎng)格劃分，但對(duì)于三維室內(nèi)地圖來說，分幅方法無法解決以下兩個(gè)問題：一是室內(nèi)數(shù)據(jù)過于密集且分布不均，使用分幅方法不容易規(guī)定分幅比例，且會(huì)出現(xiàn)全部數(shù)據(jù)擠在一個(gè)圖幅中而其他圖幅空閑這種極端情況;二是分幅方式無法體現(xiàn)三維地圖的多樓層問題，而對(duì)每一個(gè)樓層都進(jìn)行一次分幅又顯得過于繁瑣，因此室外地圖的分幅方法在室內(nèi)環(huán)境下的表現(xiàn)并不是很好。

由于以上原因，本文提出了一種新的檢索方法，其采用由Meagher[2-3]提出的在三維模型處理中常常被使用到的八叉樹的概念，對(duì)三維室內(nèi)場景進(jìn)行規(guī)則的劃分，并利用八叉樹的規(guī)則劃分特點(diǎn)，采用鄰居搜索的方法提高數(shù)據(jù)的檢索效率;同時(shí)由于室內(nèi)環(huán)境隔斷較多，各個(gè)房間相互封閉的特點(diǎn)，本文對(duì)Aizawa等[4]所提出的方法進(jìn)行改進(jìn)，使其在搜索代價(jià)上有所改進(jìn)。本文所提出的方法，與傳統(tǒng)的方法相比具有時(shí)間效率和檢索穩(wěn)定性方面的優(yōu)勢，同時(shí)也對(duì)八叉樹鄰居檢索的效率進(jìn)行了提高。

1 地圖場景劃分

八叉樹作為一種空間數(shù)據(jù)結(jié)構(gòu)，由Meather[2-3]在1982年首次提出，是二維空間中的四叉樹結(jié)構(gòu)在三維立體空間中的擴(kuò)展，其作用主要是對(duì)三維環(huán)境與物體進(jìn)行存儲(chǔ)。Vo等[5]指出，八叉樹將三維室內(nèi)地圖的整體場景作為樹模型的根節(jié)點(diǎn)，每次將場景劃分為8份或0份，節(jié)點(diǎn)有三種顏色：白色代表該節(jié)點(diǎn)區(qū)域沒有數(shù)據(jù);灰色代表該區(qū)域包含至少兩個(gè)物體數(shù)據(jù);黑色代表該區(qū)域有一個(gè)或兩個(gè)物體數(shù)據(jù)，其中白色與黑色可以作為葉子節(jié)點(diǎn)，灰色代表要進(jìn)行進(jìn)一步劃分。Vespa等[6]指出這種劃分是一個(gè)遞歸的過程，其停止條件是所有節(jié)點(diǎn)都是葉子節(jié)點(diǎn)或達(dá)到規(guī)定的劃分層數(shù)。圖1對(duì)一個(gè)2層樹進(jìn)行了表示，其中圖1（a）從三維立方體的角度展示，圖1（b）從樹型結(jié)構(gòu)的角度展示，白色圓圈代表物體，在46中有兩個(gè)物體。

Wang等[7]指出，在八叉樹結(jié)構(gòu)中，一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)最多有26個(gè)鄰居節(jié)點(diǎn)，共分為三種情況：面鄰居、邊鄰居與點(diǎn)鄰居，如圖2所示。圖3對(duì)點(diǎn)q在每個(gè)方向上的鄰居節(jié)點(diǎn)進(jìn)行了分類展示，其中a代表面鄰居共有6個(gè)，b代表邊鄰居共有12個(gè)，c代表點(diǎn)鄰居共有8個(gè)[8]。

尋址編碼使用一個(gè)7元組，對(duì)劃分出的8個(gè)子節(jié)點(diǎn)進(jìn)行標(biāo)記。其中編碼的位數(shù)與所在層數(shù)n相同，記錄此節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑，利用“push back”的方法，通過不斷向編碼后7元組編碼的方式來實(shí)現(xiàn)，圖1對(duì)應(yīng)的尋址編碼的一部分為Pavez與Gómez-Pau提出的概念[9-10]：

2 存儲(chǔ)結(jié)構(gòu)的創(chuàng)建

2.1 近似表達(dá)

Ummenhofer等[11]指出由于三維場景與三維對(duì)象較為復(fù)雜且不規(guī)則，所以在將一個(gè)三維地圖數(shù)據(jù)存儲(chǔ)在八叉樹結(jié)構(gòu)中時(shí)，需要對(duì)三維數(shù)據(jù)進(jìn)行近似表達(dá)，這種近似表達(dá)的效果可以通過包裝盒來實(shí)現(xiàn)。Steinbrücker等[12]將包裝盒分為包裝球（bounding sphere）、軸對(duì)齊包裝盒（Axis Aligned Bounding Box，AABB）與定向包裝盒（Optimized or oriented Bounding Box，OBB）。由于室內(nèi)地圖場景的模型方形的較多，所以本文不采取包裝球的近似表達(dá)方法。另一點(diǎn)，Wang等[13]指出OBB實(shí)施起來很復(fù)雜，且執(zhí)行速度慢，其主要應(yīng)用于光線追蹤與碰撞檢測方面;而AABB實(shí)施簡單，精確度高，主要應(yīng)用于游戲場景的物體近似表達(dá)，所以，綜合比較場景特性與實(shí)施代價(jià)，本文選取AABB進(jìn)行室內(nèi)地圖中三維物體對(duì)象的近似表達(dá)。如圖4所示，本文以一個(gè)電腦椅為例，利用AABB進(jìn)行包圍，具有如下數(shù)據(jù)與結(jié)論：

1）A點(diǎn)坐標(biāo)（2，3，2）;

2）B點(diǎn)坐標(biāo)（10，10，18）;

3）A與B可以看成AABB的最小點(diǎn)與最大點(diǎn)，兩者可以包裹成一個(gè)范圍，則根據(jù)A，B的坐標(biāo)可以得出，{點(diǎn)在AABB包裝盒內(nèi)|2≤x≤10，3≤y≤10，2≤z≤18};

4）采用A、B兩點(diǎn)即可對(duì)包裝盒進(jìn)行表示。

當(dāng)進(jìn)行八叉樹分割時(shí)，有可能將物體進(jìn)行分割，本文將這種情況下物體嘗試存儲(chǔ)在其父節(jié)點(diǎn)中，所以本文中的結(jié)構(gòu)，不僅僅在葉子節(jié)點(diǎn)中有數(shù)據(jù)存在。

2.2 存儲(chǔ)模型結(jié)構(gòu)

在方法1中詳細(xì)介紹了3個(gè)用來表示八叉樹存儲(chǔ)模型的結(jié)構(gòu)體，它們功能各不相同，但是之間又具有聯(lián)系，同時(shí)八叉樹的構(gòu)建偽代碼如方法2所示。

Tree_Node表示八叉樹的節(jié)點(diǎn)，主要為坐標(biāo)、位置編碼與包含的物體;Room表示各個(gè)房間的信息，主要為房間號(hào)和房間范圍坐標(biāo);Object表示各個(gè)物體的信息，主要為物體號(hào)、AABB與所在房間號(hào);聯(lián)系表示TreeNode與Object通過objectID相聯(lián)系，Object與Room通過roomId相聯(lián)系。

3 搜索方法

三維室內(nèi)地圖的數(shù)據(jù)具有更新頻繁、數(shù)據(jù)量大的特點(diǎn)。當(dāng)進(jìn)行地圖數(shù)據(jù)更新，對(duì)室內(nèi)的一個(gè)物體進(jìn)行移動(dòng)、更換與刪除等操作時(shí)，其周圍的一些物體通常也會(huì)因此而發(fā)生變化，并且發(fā)生變化的多數(shù)只是同一個(gè)房間內(nèi)的物體;當(dāng)進(jìn)行導(dǎo)航呈現(xiàn)時(shí)，對(duì)于一個(gè)數(shù)據(jù)的呈現(xiàn)同時(shí)，也會(huì)將其周圍的地圖數(shù)據(jù)呈現(xiàn)出來，這種情況在室外導(dǎo)航地圖很常見，而對(duì)于室內(nèi)地圖來說同樣具有這種情況，不過是在此基礎(chǔ)上呈現(xiàn)的是同一房間內(nèi)的地圖數(shù)據(jù)。不僅僅是這兩種應(yīng)用，對(duì)于地圖的很多必要功能比如網(wǎng)元布局與路徑規(guī)劃等，都具有這種“搜一點(diǎn)，遍及周圍”的情況存在。

根據(jù)以上情況的特點(diǎn)，本文提出利用鄰居搜索的方式，當(dāng)搜索地圖數(shù)據(jù)時(shí)，利用八叉樹規(guī)則劃分的特點(diǎn)，直接進(jìn)行鄰居節(jié)點(diǎn)的計(jì)算，得到鄰居節(jié)點(diǎn)后進(jìn)行計(jì)算得到節(jié)點(diǎn)中的地圖數(shù)據(jù)，從而得到目標(biāo)數(shù)據(jù)周圍的數(shù)據(jù)，這些數(shù)據(jù)是真實(shí)有用的，可以減少反復(fù)搜索的次數(shù)，從而達(dá)到優(yōu)化地圖數(shù)據(jù)的目的。Schrack[14]在1992提出了一種計(jì)算四叉樹與八叉樹鄰居的方法，但其只能計(jì)算處于同一樹深度的鄰居;Aizawa等[4]在此基礎(chǔ)上進(jìn)行了改進(jìn)，不再受樹深度的影響;Namdari等[15]提出了在構(gòu)建樹結(jié)構(gòu)的同時(shí)將鄰居信息進(jìn)行搜索，這一過程并不會(huì)對(duì)樹結(jié)構(gòu)的構(gòu)建增添任何復(fù)雜性。本文在此基礎(chǔ)上，根據(jù)室內(nèi)地圖數(shù)據(jù)搜索的特點(diǎn)，提出了房間隔斷的約束，使其在進(jìn)行鄰居搜索時(shí)，對(duì)于處于不是同一封閉地圖數(shù)據(jù)，不再進(jìn)行顯示，這使得搜索在代價(jià)上有所提高。下面通過一個(gè)具體例子來說明這一搜索過程。

例1 本文以圖1（a）為例子，其中劃分層數(shù)為2。

步驟1 本文假設(shè)根節(jié)點(diǎn)為root，利用方法1中的算法，完成了八叉樹的構(gòu)建與地圖場景的劃分，這時(shí)需要在樹的構(gòu)建過程中確定節(jié)點(diǎn)45的鄰居。

步驟2 利用圖7與圖8中的算法對(duì)應(yīng)表1和表2，計(jì)算45與46，得到：利用式（1）與式（2）對(duì)應(yīng)表1和表2，計(jì)算45、46與47得到：

圖名在正文中，要依照編號(hào)的先后順序引用，不能跳躍式引用。此處建議改為別的語句描述，或?qū)懩硞€(gè)具體的名稱。另外，文中也沒有圖8

計(jì)算八叉樹的八個(gè)子節(jié)點(diǎn)的計(jì)算如式（3），設(shè)父節(jié)點(diǎn)坐標(biāo)為（x（f），y（f），z（f）），則子節(jié)點(diǎn)坐標(biāo)為：

z（c）∈{z（f），z（f）+length，z（f）-length}}（3）這個(gè)公式這樣排正確嗎？是否符合表達(dá)，原來的表達(dá)感覺不符合規(guī)范?；貜?fù)：正確

其中：x（c）為所求子節(jié)點(diǎn)的x坐標(biāo)，x（f）為父節(jié)點(diǎn)的x坐標(biāo)，y坐標(biāo)與z坐標(biāo)同理，length為子立方體的尺寸。

步驟4 查看45，46，47中物體所在房間號(hào)是否相同，得出，45與46中的物體所在房間號(hào)相同，則46為45的鄰居，47則不是，將46中的該物體放到45的鄰居物體表中。

步驟5 查看45的父節(jié)點(diǎn)以及45的鄰居46的父節(jié)點(diǎn)，它們中的物體所在的房間號(hào)，得出46的父節(jié)點(diǎn)中的物體f也在房間3中，所以物體f也放到45的鄰居物體表中。

對(duì)于鄰居節(jié)點(diǎn)的判定如式（4）～（6）所示，本文以判斷編碼為a和b的節(jié)點(diǎn)為例。

若a和b滿足式（4）中6種情況中的一種，則兩者為面鄰居：

同理a與b在y或z上差length的情況類似，共6種情況。

若a和b滿足式（5）中12種情況中的一種，則兩者為邊鄰居：

同理a與b在yz或xz上同時(shí)差length的情況類似，共12種情況。

若a和b滿足式（6）中8種情況中的一種，則兩者為點(diǎn)鄰居：

4 實(shí)驗(yàn)與分析

本文以SketchUp與ArcGIS文件作為實(shí)驗(yàn)的數(shù)據(jù)，如圖5所示，物體A與物體B為三維室內(nèi)地圖，具體細(xì)節(jié)參見表3所示。根據(jù)Namdari等[15]和王永志等[16]的分析得出，當(dāng)不采用任何數(shù)據(jù)結(jié)構(gòu)與搜索方法對(duì)三維室內(nèi)地圖進(jìn)行搜索時(shí)，搜索的時(shí)間復(fù)雜度是O（np），其中n為數(shù)據(jù)的個(gè)數(shù)，p為目標(biāo)數(shù)據(jù)周圍有用數(shù)據(jù)的個(gè)數(shù)。付仲良等[17]指出當(dāng)僅采用八叉樹劃分法對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)劃分，而不采用任何搜索方法，由于經(jīng)典八叉樹無法找到鄰居地址，所以此時(shí)搜索的時(shí)間復(fù)雜度是O（23（L-1）），其中L為樹的深度。肖怡等[18]指出當(dāng)采用八叉樹劃分，并采用Schrack[14]提出的搜索算法時(shí)，搜索的時(shí)間復(fù)雜度為O（L）。當(dāng)采用八叉樹數(shù)據(jù)結(jié)構(gòu)進(jìn)行劃分，并采用Aizawa等[4]所提出的鄰居搜索算法進(jìn)行搜索，由于其利用八叉樹劃分的規(guī)則性特點(diǎn)，可以通過公式計(jì)算出目標(biāo)數(shù)據(jù)周圍最多26個(gè)鄰居地圖數(shù)據(jù)，這能夠滿足地圖應(yīng)用中，對(duì)于目標(biāo)地圖數(shù)據(jù)的周圍數(shù)據(jù)進(jìn)行呈現(xiàn)的需求，即“搜一點(diǎn)，遍及周圍”的情況，這會(huì)減少對(duì)于地圖數(shù)據(jù)的搜索次數(shù)，這種應(yīng)用背景下的搜索時(shí)間復(fù)雜度會(huì)保持在O（1）。同理若采用本文提出的帶房間約束條件的鄰居搜索方式進(jìn)行物體的搜索，則搜索的時(shí)間復(fù)雜度也是O（1），因此采用八叉樹結(jié)構(gòu)的鄰居搜索方式對(duì)室內(nèi)地圖數(shù)據(jù)搜索進(jìn)行改善，在時(shí)間復(fù)雜度上有所降低，且不會(huì)隨著樹的深度的增加而變得更復(fù)雜。

Aizawa等[4]所提出的方法在時(shí)間效率上已經(jīng)達(dá)到了很好的效果，但是對(duì)于室內(nèi)地圖這種獨(dú)立封閉性空間較多的三維場景來說，在每次搜索代價(jià)上就顯得有些笨重，而本文提出的房間隔斷約束條件，可以很好地改善這一點(diǎn)，實(shí)驗(yàn)結(jié)果如圖6所示，結(jié)果表明此方法實(shí)際可行，且在房間約束條件下，多數(shù)情況下的搜索代價(jià)都有所改善。

由于本文提出的方法，在搜索代價(jià)方面有所改善，所以結(jié)合對(duì)于搜索結(jié)果的分析成本，總體來說時(shí)間上也有所降低，如圖7所示。

5 結(jié)語

本文提出了一種應(yīng)用于三維室內(nèi)地圖場景的數(shù)據(jù)搜索方法，主要目的是解決室內(nèi)地圖數(shù)據(jù)的存儲(chǔ)效率較低與檢索速度較慢的問題。其原理為利用八叉樹結(jié)構(gòu)對(duì)場景進(jìn)行劃分，這與傳統(tǒng)分幅存儲(chǔ)方法相比具有更高的檢索效率;同時(shí)根據(jù)室內(nèi)地圖應(yīng)用中普遍存在的“搜一點(diǎn)，遍及周圍”的這種區(qū)域需求的情況，提出鄰居搜索模型，并結(jié)合室內(nèi)環(huán)境相對(duì)封閉的特點(diǎn)，添加了封閉性約束條件從而對(duì)鄰居搜索模型進(jìn)行改進(jìn)。實(shí)驗(yàn)結(jié)果表明，本文提出的搜索方法，可以將時(shí)間復(fù)雜度保持在O（1），具有良好的穩(wěn)定性，不會(huì)因?yàn)閿?shù)據(jù)的增多、劃分層數(shù)的增加而出現(xiàn)波動(dòng);在搜索代價(jià)方面，受封閉性約束條件的限制，相比Aizawa等[4]提出的算法也得到了改善。

下一步工作中將在設(shè)計(jì)節(jié)點(diǎn)結(jié)構(gòu)時(shí)考慮更為復(fù)雜的場景，使其適用更多的更復(fù)雜的室內(nèi)環(huán)境。

參考文獻(xiàn) （References）

[1] 張永玉，馬勁松.3DGIS中線性八叉樹空間索引的建立與查詢算法研究[J].計(jì)算機(jī)工程與科學(xué)，2009，31（2）：61-63.（ZHANG Y Y， MA J S. Research on establishment and query algorithm of linear octal tree spatial index in 3DGIS[J]. Computer Engineering and Science， 2009， 31（2）： 61-63.）

[2] MEAGHER D. Geometric modeling using octree encoding[J]. Computer Graphics and Image Processing， 1982， 19（2）： 129-147.

[3] MEAGHER D. The octree encoding method for efficient solid modeling[D]. Troy， NY： Rensselaer Polytechnic Institute， 1982.

[4] AIZAWA K， TANAKA S. A constant-time algorithm for finding neighbors in quadtrees[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（7）： 1178-1183.

[5] VO A V， TRUONG-HONG L， LAEFER D F， et al. Octree-based region growing for point cloud segmentation[J]. ISPRS Journal of Photogrammetry and Remote Sensing， 2015， 104： 88-100.

[6] VESPA E， NIKOLOV N， GRIMM M， et al. Efficient octree-based volumetric SLAM supporting signed-distance and occupancy mapping[J]. IEEE Robotics and Automation Letters， 2018， 3（2）： 1144-1151.

[7] WANG K， FU H， PENG S， et al. A RDF data compress model based on octree structure[C]// Proceedings of the 2017 12th IEEE Conference on Industrial Electronics and Applications. Piscataway， NJ： IEEE， 2017： 990-994.

[8] WONG H T T， HUANG Y， TSANG S C， et al. Real-time model slicing in arbitrary direction using octree[C]// Proceedings of the ACM 44th International Conference on Computer Graphics and Interactive Technique. New York： ACM， 2017： Article No. 9.

[9] PAVEZ E， CHOU P A. Dynamic polygon cloud compression[C]// Proceedings of the 2017 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway， NJ： IEEE， 2017： 2936-2940.

[10] GMEZ-PAU ， BALADO L， FIGUERAS J. Detectability of structural defects using octree encoding[C]// Proceedings of the 2017 32nd Conference on I/Design of Circuits and Integrated Systems. Piscataway， NJ： IEEE， 2017： 1-6.

[11] UMMENHOFER B， BROX T. Global， dense multiscale recon-struction for a billion points[C]// Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway， NJ： IEEE， 2015： 1341-1349.

[12] STEINBRCKER F， STURM J， CREMERS D. Volumetric 3D mapping in real-time on a CPU[C]// Proceedings of the 2014 IEEE International Conference on Robotics and Automation. Piscataway， NJ： IEEE， 2014： 2021-2028.

[13] WANG P S， LIU Y， GUO Y X， et al. O-CNN： octree-based convolutional neural networks for 3D shape analysis[J]. ACM Transactions on Graphics， 2017， 36（4）： 72.

[14] SCHRACK G. Finding neighbors of equal size in linear quadtrees and octrees in constant time[J]. CVGIP： Image Understanding， 1992， 55（3）： 221-230.

[15] NAMDARI M H， HEJAZI S R， PALHANG M. MCPN， octree neighbor finding during tree model construction using parental neighboring rule[J]. 3D Research， 2015， 6（3）： 29.

[16] 王永志，楊路生，廖麗霞，等.八叉樹與三維R樹集成的激光點(diǎn)云數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)[J].地球信息科學(xué)學(xué)報(bào)，2017，19（5）：587-594.（WANG Y Z， YANG L S， LIAO L X， et al. Laser point cloud data storage structure integrated with octree and 3D R-tree[J]. Journal of Earth Information Science， 2017， 19（5）： 587-594.）

[17] 付仲良，劉思遠(yuǎn)，田宗舜，等.基于多級(jí)R-tree的分布式空間索引及其查詢驗(yàn)證方法研究[J].測繪通報(bào)，2012（11）：42-46.（FU Z L， LIU S Y， TIAN Z S， et al. Research on distributed spatial index and its query verification method based on multi-level R-tree[J]. Bulletin of Surveying and Mapping， 2012（11）： 42-46.）

[18] 肖怡，李佳田，張文靖，等.一種自然鄰近關(guān)系查詢的空間索引結(jié)構(gòu)[J].地理信息世界，2018，25（1）：32-38.（XIAO Y， LI J T， ZHANG W J， et al. A spatial index structure of natural neighbor relational query[J]. Geomatics World， 2018， 25（1）： 32-38.）