【文章內(nèi)容簡(jiǎn)介】 下地進(jìn)行全自動(dòng)的步進(jìn)掃描測(cè)量，隨著兩個(gè)同步反射鏡地旋轉(zhuǎn)，窄束激光脈沖從激光脈沖發(fā)射體發(fā)出依次掃過(guò)目標(biāo)區(qū)域，測(cè)量出從發(fā)出到返回儀器的每個(gè)激光脈沖所經(jīng)過(guò)的時(shí)間（或者相位差），由此計(jì)算出距離值，同時(shí)獲取掃描控制模塊的控制，測(cè)量出每個(gè)脈沖激光角度值。即獲得的原始數(shù)據(jù)有：兩個(gè)反射鏡的角度值，在下圖中為水平角值和垂直角值；通過(guò)計(jì)算得到的儀器到掃描點(diǎn)之間的斜距S，掃描點(diǎn)反射強(qiáng)度。前三個(gè)數(shù)據(jù)是用來(lái)計(jì)算掃描點(diǎn)的三維坐標(biāo)值的；掃描點(diǎn)反射強(qiáng)度則可以用于給反射點(diǎn)匹配顏色。圖8 掃描系統(tǒng)示意圖如圖所示，以地面LiDAR測(cè)量的儀器中心為坐標(biāo)原點(diǎn)，Y軸是儀器的固定方向，是儀器初始化時(shí)激光掃描的方向，Z軸為豎直向上方向，X軸通過(guò)右手坐標(biāo)系來(lái)確定。由下面公式就可以計(jì)算出被掃描的點(diǎn)的三維空間坐標(biāo)數(shù)據(jù)。 (23)地面LiDAR技術(shù)跟全站儀測(cè)量技術(shù)的定位原理是相同的，都是將儀器自身中心作為坐標(biāo)原點(diǎn)，測(cè)出距離值和角度值，進(jìn)行解算得出目標(biāo)的三維坐標(biāo)。兩者之間不同的地方是地面LiDAR技術(shù)是全自動(dòng)地獲取面數(shù)據(jù)，而且密度很高，數(shù)據(jù)信息也更加豐富。地面LiDAR系統(tǒng),顧名思義,是選擇激光作為能源進(jìn)行掃描測(cè)量的系統(tǒng)。該系統(tǒng)具有如下特點(diǎn)[4][12]：（1）快速性：激光掃描測(cè)量獲取到大面積目標(biāo)的空間信息的速度很快。將激光掃描技術(shù)用于目標(biāo)空間數(shù)據(jù)信息采集，能夠及時(shí)地測(cè)定出目標(biāo)表面的三維信息，所以能夠在自動(dòng)監(jiān)控行業(yè)內(nèi)應(yīng)用。（2）非接觸性：地面LiDAR系統(tǒng)可以不需要接觸目標(biāo)而完成掃描測(cè)量，獲取真實(shí)世界實(shí)體的三維坐標(biāo)數(shù)據(jù)，能夠一次性完成從目標(biāo)實(shí)體到三維點(diǎn)云數(shù)據(jù)的轉(zhuǎn)換，真正地做到了快速重構(gòu)原型。由于非接觸性的特點(diǎn)柔性目標(biāo)測(cè)量、危險(xiǎn)領(lǐng)域測(cè)量、人員不可到達(dá)位置的測(cè)量以及需要保護(hù)對(duì)象的測(cè)量的問(wèn)題也得到了解決。（3）激光具有穿透性：激光具有穿透的特性，這使得獲取到的采樣點(diǎn)能夠描述出目標(biāo)表面在不同層面上的幾何空間信息。（4）實(shí)時(shí)、動(dòng)態(tài)與主動(dòng)性：地面LiDAR系統(tǒng)是一個(gè)主動(dòng)式的掃描系統(tǒng)，利用的是探測(cè)自身發(fā)射的激光脈沖，由回射的信號(hào)通過(guò)處理來(lái)描述目標(biāo)信息，這給予了系統(tǒng)測(cè)量不會(huì)因時(shí)間和空間而受到影響的特點(diǎn)。系統(tǒng)發(fā)射的激光束可以近似看作平行光，不需要去擔(dān)心常規(guī)的光學(xué)照相測(cè)量中存在的光學(xué)變形誤差。這會(huì)更加完整地描述真是世界的場(chǎng)景和實(shí)體的空間形態(tài)及結(jié)構(gòu)屬性，采集到的三維數(shù)據(jù)也會(huì)更加具有實(shí)效、準(zhǔn)確。（5）密度高、精度高：激光掃描能夠獲取目標(biāo)的表面特征密度、精度都很高。有精密的傳感工藝支持，能自動(dòng)立體地采集目標(biāo)的立體結(jié)構(gòu)和表面結(jié)構(gòu)的數(shù)據(jù)。獲取的點(diǎn)云數(shù)據(jù)是由點(diǎn)的位置的三維坐標(biāo)數(shù)據(jù)構(gòu)成，降低了傳統(tǒng)手段中由于人工的計(jì)算或推導(dǎo)帶來(lái)的不確定性?？梢酝ㄟ^(guò)點(diǎn)陣和一定密度的格網(wǎng)去描述實(shí)體的信息，采樣點(diǎn)之間的點(diǎn)距間隔可以設(shè)置。（6）自動(dòng)化、數(shù)字化：系統(tǒng)掃描獲取的是數(shù)字距離信號(hào)，有這個(gè)全數(shù)字的特征，便更容易自動(dòng)化地去顯示和輸出，可靠性也更好。在進(jìn)行數(shù)據(jù)采集時(shí)，掃描系統(tǒng)采集和管理數(shù)據(jù)的軟件通過(guò)TCP/PI或平行連線接口及相應(yīng)的驅(qū)動(dòng)程序來(lái)控制掃描儀，處理軟件會(huì)對(duì)自動(dòng)選擇目標(biāo)的始點(diǎn)和終點(diǎn)，具有很好的建模處理、點(diǎn)云處理能力，其它的專(zhuān)業(yè)軟件還可以通過(guò)軟件開(kāi)放的接口格式調(diào)用掃描的三維信息，與其它軟件也能兼容和互相操作。（7）地面LiDAR掃描系統(tǒng)能夠通過(guò)同步變化視距使得激光自動(dòng)聚焦，改良了實(shí)際測(cè)量時(shí)的精度，在不同測(cè)距的散焦效應(yīng)也提高了，更好地逼近實(shí)體原形。（8）系統(tǒng)配置的數(shù)碼相機(jī)能夠協(xié)助掃描工作，同步地進(jìn)行遙控、監(jiān)測(cè)、拍照、選位、立體編輯等一系列的操作，易于現(xiàn)場(chǎng)目標(biāo)的選擇、優(yōu)化，在復(fù)雜空間或不友好環(huán)境下也能更好地工作。在后期數(shù)據(jù)處理階段，利用圖片信息還能夠?qū)?shù)據(jù)進(jìn)行調(diào)整、編輯、貼圖等操作。除此之外，軟件還能夠?qū)?shù)碼相機(jī)進(jìn)行定向、參數(shù)校準(zhǔn)和控制照片的采集等功能。這讓系統(tǒng)能夠帶色彩地去顯示云點(diǎn)數(shù)據(jù)。提供現(xiàn)場(chǎng)操作進(jìn)行過(guò)攝像校準(zhǔn)的功能，能夠及時(shí)解決現(xiàn)場(chǎng)發(fā)現(xiàn)的問(wèn)題，降低了之后處理工作的不確定性，減少了返工的可能。（9）系統(tǒng)很少依賴(lài)目標(biāo)環(huán)境和工作環(huán)境，具有抵御輻射、震動(dòng)、潮濕的性質(zhì)，適應(yīng)各種場(chǎng)景或野外的操作環(huán)境。系統(tǒng)提供了不同分辨率的掃描方式，可以重復(fù)地對(duì)物體進(jìn)行掃描，用戶(hù)也就能夠自己選在掃描的精度。對(duì)全景空間采集的內(nèi)容的量及后期的處理中數(shù)據(jù)拼接的次數(shù)由掃描的次數(shù)來(lái)決定，用戶(hù)能夠自由控制工作量的大小。根據(jù)需要，用戶(hù)控制掃描的次數(shù)，可以改善因?yàn)槠唇狱c(diǎn)云次數(shù)過(guò)多引起的空間變形以及拼接時(shí)差生的接縫誤差。（10）新型的掃描系統(tǒng)還裝備了GPS接收機(jī)或者其他的高精度定位裝置，在軟件平臺(tái)的內(nèi)部可以進(jìn)行坐標(biāo)轉(zhuǎn)換，將點(diǎn)云數(shù)據(jù)直接轉(zhuǎn)換成為大地坐標(biāo)系下的坐標(biāo)，更加方便使用。激光掃描儀掃描獲取的數(shù)據(jù)經(jīng)過(guò)格式轉(zhuǎn)換后，得到的點(diǎn)云數(shù)據(jù)格式如下：X（m）Y(m)H(m)………………………………這是最基礎(chǔ)的三維空間坐標(biāo)數(shù)據(jù)，即點(diǎn)云數(shù)據(jù)。除了三維坐標(biāo)屬性外還能夠加入其它的屬性數(shù)據(jù)，比如反射強(qiáng)度等等。所謂的點(diǎn)云，就是在相同的空間參考系下的一系列的表達(dá)目標(biāo)空間分布和表面光譜特性的點(diǎn)集合。點(diǎn)云數(shù)據(jù)有很多自身的特點(diǎn)。第一，點(diǎn)云數(shù)據(jù)的內(nèi)容是分布在目標(biāo)表面的大量三維點(diǎn)的坐標(biāo)。所以點(diǎn)云反映的是目標(biāo)表面的信息，并沒(méi)有內(nèi)部的信息。第二，點(diǎn)云數(shù)據(jù)的點(diǎn)呈現(xiàn)出離散分布的特點(diǎn)。點(diǎn)的位置和相互之間的間隔并沒(méi)有一定的分布規(guī)則，更加容易表達(dá)出目標(biāo)物體的細(xì)節(jié)信息。第三，點(diǎn)云數(shù)據(jù)能夠直接獲取測(cè)量數(shù)據(jù)，比如三維坐標(biāo)、距離等，還可以通過(guò)計(jì)算得到目標(biāo)的表面積、體積等。第四，點(diǎn)云數(shù)據(jù)分布不均勻。不論是機(jī)載的LiDAR還是地面LiDAR，掃描出來(lái)的數(shù)據(jù)的分布都是不均勻的，原因有很多。機(jī)載LiDAR采用圓錐掃描時(shí)，掃描帶中間數(shù)據(jù)密度大，兩側(cè)數(shù)據(jù)密度小，對(duì)于其它的掃描方式也會(huì)不同程度的出現(xiàn)點(diǎn)云數(shù)據(jù)分布不均勻，同時(shí)由于地面目標(biāo)地物的不同，也會(huì)造成數(shù)據(jù)分布不均勻。地面LiDAR也會(huì)由于目標(biāo)的不同出現(xiàn)數(shù)據(jù)分布不均勻的情況。本章節(jié)介紹了點(diǎn)云數(shù)據(jù)的結(jié)構(gòu)以及特點(diǎn)，在研究點(diǎn)云數(shù)據(jù)的索引方式的時(shí)候需要考慮到數(shù)據(jù)的結(jié)構(gòu)和特點(diǎn)，據(jù)此來(lái)分析各種索引可能從哪些特點(diǎn)提高檢索效率。3 基于KD樹(shù)的LiDAR點(diǎn)云數(shù)據(jù)組織與管理KD樹(shù)索引是由Bentley在1975年提出的，主要用來(lái)對(duì)多屬性的數(shù)據(jù)或者多維的點(diǎn)數(shù)據(jù)進(jìn)行檢索。KD樹(shù)是K（K2）維的二叉索引樹(shù)，但與二叉索引樹(shù)不同，它的每個(gè)結(jié)點(diǎn)表示的都是一個(gè)K維空間中的一個(gè)點(diǎn)。KD樹(shù)的每一層都需要一個(gè)分辨器，根據(jù)這個(gè)分辨器作出該層的分支決策，對(duì)于一棵KD樹(shù)，它的第i層的分辨器就是i mod k（根節(jié)點(diǎn)為0層，接下來(lái)依次遞增）。一棵非空的KD樹(shù)的性質(zhì)如下：（1）如果它的左子樹(shù)不是空樹(shù)，則左子樹(shù)上的所有結(jié)點(diǎn)的第d維的值都小于它的父結(jié)點(diǎn)第d維的值，右子樹(shù)是同理。（2）它的左右子樹(shù)也都是KD樹(shù)。圖 9 KD樹(shù)示意圖上圖是二維KD樹(shù)示意圖，根節(jié)點(diǎn)所在點(diǎn)為0層，分辨器是0 mod 2=0，即用x軸的值作為分支根據(jù)，A的左子樹(shù)B上所有點(diǎn)的x值都小于A的x值；A的右子樹(shù)C上所有點(diǎn)的x值都大于A的x值。接下來(lái)的其它層都依次類(lèi)推。KD樹(shù)索引是二叉樹(shù)索引在多維空間的擴(kuò)展，在具備為多維空間進(jìn)行索引，進(jìn)行精確點(diǎn)查找的同時(shí)，也繼承了二叉樹(shù)索引的優(yōu)點(diǎn)，平均查找長(zhǎng)度為1+4logn。根據(jù)點(diǎn)云數(shù)據(jù)不規(guī)則分布的特點(diǎn)，KD樹(shù)索引是一種非常適合管理點(diǎn)云數(shù)據(jù)的索引方法。為了降低KD樹(shù)刪除的代價(jià)，中間點(diǎn)不存儲(chǔ)數(shù)據(jù)點(diǎn)，所有的數(shù)據(jù)點(diǎn)都存放在葉結(jié)點(diǎn)中。分割方式采用的是取最長(zhǎng)軸中位數(shù)方法進(jìn)行分割。KD樹(shù)的每個(gè)中間結(jié)點(diǎn)都需要有將這個(gè)結(jié)點(diǎn)所代表的子空間分割平面，分割平面會(huì)把這個(gè)空間分割成兩個(gè)字空間，結(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)就代表了這兩個(gè)子空間，空間中所有的點(diǎn)也會(huì)分配到兩個(gè)子空間中。每次進(jìn)行分割時(shí)，首先應(yīng)該選定分割平面的法方向，然后選擇在哪個(gè)位置作為分割平面的位置，這會(huì)影響到兩個(gè)子空間占空間的比例，根據(jù)二叉樹(shù)索引的理想情況，分割完畢后應(yīng)該會(huì)建立一個(gè)滿(mǎn)二叉樹(shù)索引，就是說(shuō)在每次分割后，兩結(jié)點(diǎn)包含的點(diǎn)云數(shù)據(jù)的數(shù)量應(yīng)該相等，所以在選取分割位置時(shí)，需要根據(jù)該層的分辨器，確定中位數(shù)，取中位數(shù)的位置作為分割面的位置。索引建立算法的步驟如下：1）設(shè)定閾值，確定葉結(jié)點(diǎn)所代表的空間中允許存在的點(diǎn)數(shù)量的最大值；2）建立根結(jié)點(diǎn)，存儲(chǔ)原點(diǎn)云點(diǎn)數(shù)量，計(jì)算點(diǎn)云數(shù)據(jù)在三個(gè)維度方向的方差值，取方差最大的維度方向作為根結(jié)點(diǎn)的分割面的法方向即初始的分辨器，接下來(lái)各層的分辨器隨層數(shù)增加而增加；3）判斷結(jié)點(diǎn)所代表的空間中包含的點(diǎn)數(shù)量是否小于閾值，若小于閾值，則將所有點(diǎn)數(shù)據(jù)存儲(chǔ)在結(jié)點(diǎn)中，否則進(jìn)行4）；4）根據(jù)結(jié)點(diǎn)所在層的分辨器，確定中位數(shù)，即分割面的位置，將空間分割成兩個(gè)字空間，建立兩個(gè)新的結(jié)點(diǎn)表示對(duì)應(yīng)的兩個(gè)子空間，依次對(duì)兩個(gè)結(jié)點(diǎn)進(jìn)行3）；5)所有子空間所包含的點(diǎn)數(shù)量小于閾值后，建立索引成功。在根據(jù)算法進(jìn)行編程實(shí)現(xiàn)的過(guò)程中，考慮到數(shù)據(jù)量非常大的情況，避免出現(xiàn)內(nèi)存不夠?qū)е碌某绦蜻\(yùn)行失敗，建立索引的過(guò)程中并不移動(dòng)數(shù)據(jù)，僅僅依據(jù)數(shù)據(jù)建立索引，在完成索引建立后，才將對(duì)應(yīng)的數(shù)據(jù)存儲(chǔ)到相應(yīng)的也葉子結(jié)點(diǎn)中。 K鄰近查找K鄰近查找在不同的索引中查找原理也都不相同?；贙D樹(shù)索引的特點(diǎn)，在進(jìn)行K鄰近查找時(shí)，記錄下查找經(jīng)過(guò)的路徑，按路徑上每個(gè)結(jié)點(diǎn)所代表的子空間的分割面到查找點(diǎn)的距離進(jìn)行排序，在找到目標(biāo)區(qū)域后先對(duì)目標(biāo)區(qū)域所包含的點(diǎn)進(jìn)行計(jì)算，若查找的結(jié)果并不滿(mǎn)足一定的要求，則按排序后的結(jié)點(diǎn)進(jìn)行查找，指導(dǎo)查找到的所有結(jié)果滿(mǎn)足查找的要求。K鄰近查找的步驟：1）確定所查找點(diǎn)的坐標(biāo)及查找的鄰近點(diǎn)個(gè)數(shù)K；2）根據(jù)查找點(diǎn)坐標(biāo)確定點(diǎn)所在的葉子結(jié)點(diǎn)所代表的子空間R，記錄查詢(xún)路徑，同時(shí)記錄查詢(xún)路徑上中間點(diǎn)所代表子空間的分割面到查找點(diǎn)的距離，并按從小到大排序Z；3）計(jì)算R中包含的點(diǎn)到查找點(diǎn)的距離，同時(shí)進(jìn)行排序，取最近的K個(gè)點(diǎn)，若點(diǎn)的數(shù)量足夠K個(gè)點(diǎn)而且最遠(yuǎn)的點(diǎn)的距離小于查詢(xún)路徑上最近的分割面的距離，則完成查詢(xún)，否則根據(jù)查詢(xún)路徑排序Z對(duì)相應(yīng)的空間進(jìn)行查找，對(duì)查找過(guò)的空間標(biāo)號(hào)，若查找到的K個(gè)點(diǎn)滿(mǎn)足要求或者整個(gè)空間都查詢(xún)完成，這結(jié)束查詢(xún)。 算法測(cè)試算法測(cè)試的將數(shù)據(jù)按照數(shù)據(jù)量進(jìn)行等級(jí)劃分，在沒(méi)給數(shù)量等級(jí)對(duì)若干個(gè)不同的點(diǎn)進(jìn)行K鄰近查找，查找同一個(gè)點(diǎn)的時(shí)候，改變K值得出各種查詢(xún)方式的效率。本次驗(yàn)證的數(shù)據(jù)選取了3組點(diǎn)云數(shù)據(jù)，3組數(shù)據(jù)都是由Riegl VZ1000三維激光掃描儀掃描學(xué)校建筑獲取的點(diǎn)云數(shù)據(jù)。測(cè)試數(shù)據(jù)1的數(shù)據(jù)量為541527個(gè)數(shù)據(jù)點(diǎn)；測(cè)試數(shù)據(jù)2的數(shù)據(jù)量為1002406個(gè)數(shù)據(jù)點(diǎn)；測(cè)試數(shù)據(jù)3的數(shù)據(jù)量為1531046個(gè)數(shù)據(jù)點(diǎn)算法測(cè)試運(yùn)行環(huán)境是ASUS K43SV筆記本，處理器為Interl174。 Core? i52430M ，內(nèi)存為4G。在后面的集中算法的測(cè)試中也是在相同的環(huán)境下按同樣的測(cè)試方式進(jìn)行算法測(cè)試。下面是KD樹(shù)索引測(cè)試結(jié)果（最佳查找耗時(shí)是在多次測(cè)試，設(shè)定不同的閾值的情況下得出的耗時(shí)最少的情況）。程序某次次查詢(xún)結(jié)果及耗時(shí)運(yùn)行圖：KD樹(shù)索引測(cè)試結(jié)果：表2 KD樹(shù)算法測(cè)試最佳耗時(shí)表點(diǎn)數(shù)據(jù)量54152710024061531046K鄰近查找最佳耗時(shí)（s）10004000800012000就KD樹(shù)索引測(cè)試過(guò)程中獲得的完整數(shù)據(jù)來(lái)說(shuō)，有以下幾條規(guī)律：1）數(shù)據(jù)量相同的情況下，閾值越大，索引建立時(shí)間越少；2）閾值相同的情況下，數(shù)據(jù)量越大，索引建立時(shí)間越長(zhǎng)；3）閾值相同的情況下，查詢(xún)的數(shù)據(jù)量越大，查詢(xún)時(shí)間越長(zhǎng)；4）查詢(xún)數(shù)據(jù)相同的情況下，閾值越大，查詢(xún)時(shí)間越長(zhǎng)；5）閾值確定，在查詢(xún)數(shù)據(jù)量大于閾值耗時(shí)相比查詢(xún)數(shù)據(jù)量小于閾值會(huì)突然增長(zhǎng)很多。本章節(jié)介紹了KD樹(shù)索引的原理以及基于KD樹(shù)索引對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行組織的方法，還介紹了索引建立和檢驗(yàn)查找效率的K鄰近查找算法。進(jìn)行了算法測(cè)試，得出了一些規(guī)律，也發(fā)現(xiàn)了KD樹(shù)索引在組織管理海量的數(shù)據(jù)時(shí)消耗的時(shí)間會(huì)大大增加，影響到查詢(xún)的效率。本章節(jié)所有的實(shí)現(xiàn)代碼已經(jīng)附在附錄中。4 基于八叉樹(shù)的LiDAR點(diǎn)云數(shù)據(jù)組織與管理Hunter在1978年首次提出了八叉樹(shù)索引結(jié)構(gòu)，這是由四叉樹(shù)向三維空間發(fā)展而發(fā)展出來(lái)的索引結(jié)構(gòu)。通過(guò)對(duì)三維空間的實(shí)體進(jìn)行分割后，每個(gè)分割出來(lái)的子空間都具有相同的大小，通過(guò)循環(huán)遞歸地去劃分空間，將整個(gè)目標(biāo)三維空間劃分為個(gè)相同大小的子空間，n為分割的次數(shù)。在八叉樹(shù)索引中，若是一棵非空的八叉樹(shù)，它必定包含八個(gè)子樹(shù)，而且每個(gè)子樹(shù)都是八叉樹(shù)。圖10 八叉樹(shù)示意圖八叉樹(shù)結(jié)構(gòu)是將包含點(diǎn)云數(shù)據(jù)的外包六面體按照八叉樹(shù)劃分的規(guī)則進(jìn)行劃分（劃分的深度由設(shè)定的閾值決定），每次劃分通過(guò)點(diǎn)坐標(biāo)同空間中心坐標(biāo)的對(duì)比，分配到不同的子空間中，隨著遞歸劃分的深入，在子空間中的點(diǎn)數(shù)量小于閾值的時(shí)候，將被該子空間包含的點(diǎn)的數(shù)據(jù)存儲(chǔ)到葉結(jié)點(diǎn)中，劃分中途的“中間點(diǎn)”并不存儲(chǔ)點(diǎn)云數(shù)據(jù)。最后點(diǎn)云數(shù)據(jù)被分配到一定數(shù)量的子空間中。索引建立的算法步驟如下：1）設(shè)定索引的閾值，確定葉結(jié)點(diǎn)所代表的空間中允許存在的點(diǎn)數(shù)量的最大值；2）建立根結(jié)點(diǎn)R，計(jì)算原始點(diǎn)云的外包六面體邊長(zhǎng)、中心點(diǎn)和包含的點(diǎn)云點(diǎn)數(shù)據(jù)數(shù)量并存儲(chǔ)在根結(jié)點(diǎn)中；3）若結(jié)點(diǎn)R代表的六面體空間包含的點(diǎn)數(shù)據(jù)數(shù)量小于閾值，則將該部分點(diǎn)云數(shù)據(jù)存儲(chǔ)在該結(jié)點(diǎn)中，否則進(jìn)行4）；4）建立結(jié)點(diǎn)R的八個(gè)子結(jié)點(diǎn)，根據(jù)點(diǎn)云數(shù)據(jù)點(diǎn)相對(duì)于結(jié)點(diǎn)R中心點(diǎn)位置，將點(diǎn)云數(shù)據(jù)分配到八個(gè)子結(jié)點(diǎn)中，并存儲(chǔ)每個(gè)結(jié)點(diǎn)所代表的子空間的變長(zhǎng)、中心點(diǎn)和數(shù)據(jù)點(diǎn)數(shù)量等信息，依次對(duì)每個(gè)子結(jié)點(diǎn)執(zhí)行3）；5）在所有點(diǎn)分配完畢后結(jié)束索引建立。與KD樹(shù)索引建立相似，八叉樹(shù)索引建立時(shí)，同樣不在建立過(guò)程中移動(dòng)數(shù)據(jù)，只在最后完成索引建立后，才將數(shù)據(jù)存儲(chǔ)進(jìn)相應(yīng)的也葉子節(jié)點(diǎn)中。在編程實(shí)現(xiàn)八叉樹(shù)索引建立的過(guò)程中，為了便于進(jìn)行K鄰近查找，對(duì)那些并不存在點(diǎn)數(shù)據(jù)的子空間也建立了結(jié)點(diǎn)去表示，防止因?yàn)椴檎业狞c(diǎn)在原點(diǎn)云數(shù)據(jù)中的位置區(qū)域沒(méi)有結(jié)點(diǎn)表示而阻礙了K鄰近查找。 K鄰近查找八叉樹(shù)的K鄰近查找與KD樹(shù)不同，根據(jù)八叉樹(shù)索引的特點(diǎn)，并不需要記錄查找點(diǎn)目標(biāo)區(qū)域的路徑，只需要在查找