通過雷達、激光掃描、立體攝像機等三維測量設備獲取的點云數據，具有數據量大、分布不均勻等特點。作為三維領域中一個重要的數據來源，點云數據主要是表征目標表面的海量點集合，并不具備傳統網格數據的集合拓撲信息。所以點云數據處理中最為核心的問題就是建立離散點間的拓撲關系，實現基于鄰域關系的快速查找。

建立空間索引在點云數據處理中已被廣泛應用，常見空間索引一般是自頂向下逐級劃分空間的各種空間索引結構，比較有代表性的包括 BSP樹、 KD樹、 KDB樹、 R樹、 R+樹、 CELL樹、四叉樹和八叉樹等索引結構，而在這些結構中KD樹和八叉樹在3D點云數據組織中應用較為廣泛，PCL對上述兩者進行了實現。

1、八叉樹的描述

八叉樹結構是由 Hunter 博士于1978年首次提出的一種數據模型。八叉樹結構通過對三維空間的幾何實體進行體元剖分，每個體元具有相同的時間和空間復雜度，通過循環遞歸的劃分方法對大小為 (2n?2n?2n)(2n?2n?2n) 的三維空間的幾何對象進行剖分，從而構成一個具有根節點的方向圖。在八叉樹結構中如果被劃分的體元具有相同的屬性，則該體元構成一個葉節點；否則繼續對該體元剖分成8個子立方體，依次遞剖分，對于 (2n?2n?2n)(2n?2n?2n)大小的空間對象，最多剖分 nn 次，如下示意圖所示。

八叉樹結構示意圖

八叉樹(Octree)是一種用于描述三維空間的樹狀數據結構。八叉樹的每個節點表示一個正方體的體積元素，每個節點有八個子節點，這八個子節點所表示的體積元素加在一起就等于父節點的體積。一般中心點作為節點的分叉中心。八叉樹若不為空樹的話，樹中任一節點的子節點恰好只會有八個，或零個，也就是子節點不會有0與8以外的數目。

八叉樹葉子節點代表了分辨率最高的情況。例如分辨率設成0.01m，那么每個葉子就是一個1cm見方的小方塊。

那么，這要用來做什么？想象一個立方體，我們最少可以切成多少個相同等分的小立方體？答案就是8個。再想象我們有一個房間，房間里某個角落藏著一枚金幣，我們想很快的把金幣找出來，聰明的你會怎么做？我們可以把房間當成一個立方體，先切成八個小立方體，然后排除掉沒有放任何東西的小立方體，再把有可能藏金幣的小立方體繼續切八等份….如此下去，平均在Log8(房間內的所有物品數)的時間內就可找到金幣。因此，Octree就是用在3D空間中的場景管理，可以很快地知道物體在3D場景中的位置，或偵測與其它物體是否有碰撞以及是否在可視范圍內。

2、實現Octree的原理

(1). 設定最大遞歸深度

(2). 找出場景的最大尺寸，并以此尺寸建立第一個立方體

(3). 依序將單位元元素丟入能被包含且沒有子節點的立方體

(4). 若沒有達到最大遞歸深度，就進行細分八等份，再將該立方體所裝的單位元元素全部分擔給八個子立方體

(5). 若發現子立方體所分配到的單位元元素數量不為零且跟父立方體是一樣的，則該子立方體停止細分，因為跟據空間分割理論，細分的空間所得到的分配必定較少，若是一樣數目，則再怎么切數目還是一樣，會造成無窮切割的情形。

(6). 重復3，直到達到最大遞歸深度。

3、Octree的存儲結構

本例中Octree的存貯結構用一個有(若干+八)個字段的記錄來表示樹中的每個結點。其中若干字段用來描述該結點的特性(本例中的特性為：節點的值和節點坐標)，其余的八個字段用來作為存放指向其八個子結點的指針。此外，還有線性存儲和1托8式存儲。

4、BSP Tree和Octree對比

a) BSP Tree將場景分割為1個面，而Octree分割為3個面。

b) BSP Tree每個節點最多有2個子結點，而Octree最多有8個子結點

5、八叉樹和k-d樹比較

因此BSP Tree可以用在不論幾唯的場景中，而Octree則常用于三維場景

八叉樹算法的算法實現簡單，但大數據量點云數據下，其使用比較困難的是最小粒度(葉節點)的確定，粒度較大時，有的節點數據量可能仍比較大，后續查詢效率仍比較低，反之，粒度較小，八叉樹的深度增加，需要的內存空間也比較大(每個非葉子節點需要八個指針)，效率也降低。而等分的劃分依據，使得在數據重心有偏斜的情況下，受劃分深度限制，其效率不是太高。

k-d在鄰域查找上比較有優勢，但在大數據量的情況下，若劃分粒度較小時，建樹的開銷也較大，但比八叉樹靈活些。在小數據量的情況下，其搜索效率比較高，但在數據量增大的情況下，其效率會有一定的下降，一般是線性上升的規律。

也有將八叉樹和k-d樹結合起來的應用，應用八叉樹進行大粒度的劃分和查找，而后使用k-d樹進行細分，效率會有一定的提升，但其搜索效率變化也與數據量的變化有一個線性關系。

6、八叉樹的C++實現

https://my.oschina.net/u/4338729/blog/3399283

總結

以上是生活随笔為你收集整理的线性八叉树_octree八叉树数据结构原理与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。