資料結構中的壓縮四叉樹和八叉樹

壓縮四叉樹

在儲存每個對應於細分單元的節點時，我們最終可能會儲存大量空節點。透過僅儲存其葉子具有有趣資料（即“重要子樹”）的子樹，可以減少此類稀疏樹的大小。我們實際上可以進一步減少大小。當我們只考慮重要的子樹時，修剪過程可能會避免樹中的長路徑，其中中間節點的度數為二（一個指向父節點的連結和一個指向子節點的連結）。事實證明，我們只需要儲存此路徑開始處的節點 U（並與其關聯一些元資料以表示已刪除的節點）並將以其結尾為根的子樹附加到 U。當給定“不良”輸入點時，這些壓縮樹仍然具有線性高度。

雖然我們在執行此壓縮時減少了大量樹，但仍然可以透過利用 Z 階曲線來實現對數時間插入、刪除和搜尋。Z 階曲線將完整四叉樹（以及壓縮四叉樹）的每個單元在 O(1) 時間內轉換為一維線（並在 O(1) 時間內將其轉換回來），從而在元素上構建一個總順序。現在，我們能夠將四叉樹儲存在有序集的資料結構中（其中我們儲存樹的節點）。現在，我們必須在繼續之前陳述一個合理的假設：我們假設給定兩個表示為二進位制的實數 α、β € [0,1]，我們可以在 O(1) 時間內計算出它們不同的第一個位的索引。我們還假設我們可以在 O(1) 時間內計算出四叉樹中兩個點/單元的最小公共祖先並確定它們的相對 Z 順序，並且我們可以在 O(1) 時間內計算出 floor 函式。有了這些假設，給定點 Q 的點定位（即查詢包含 Q 的單元格）、刪除和插入操作都可以以 O(n log n) 時間執行（即在底層有序集資料結構中執行搜尋所需的時間）。

要對 Q 執行點定位（即確定其在壓縮樹中的單元格）

  • 在壓縮樹中找到在 Z 順序中位於 Q 之前的現有單元格。將此單元格稱為 V。
  • 如果執行 Q€V，則返回 V。
  • 否則，找到在未壓縮四叉樹中點 Q 和單元格 V 的最小公共祖先。將此祖先單元格稱為 U。
  • 在壓縮樹中找到在 Z 順序中位於 U 之前的現有單元格並返回它。

在不深入具體細節的情況下，要執行插入和刪除操作，我們首先對要插入/刪除的內容執行點定位，然後插入/刪除它。必須注意根據需要重塑樹，根據需要構建和刪除節點。

八叉樹

八叉樹定義為一種樹形資料結構，其中每個內部節點都與恰好八個子節點相關聯。

八叉樹最常用於透過遞迴地將三維空間細分為八個卦限來對三維空間進行分割槽。

八叉樹被視為四叉樹的三維類似物。名稱由 oct + tree 組成，但請注意，它通常寫成“octree”，只有一個“t”。

八叉樹通常在 3D 圖形和 3D 遊戲引擎中實現。

用於空間表示

八叉樹中的每個節點負責將其表示的空間細分為八個卦限。在點區域 (PR)

八叉樹中，節點儲存一個顯式三維點，它是該節點細分的“中心”；該點

為八個子節點中的每一個指定一個角。在基於矩陣 (MX) 的八叉樹的情況下，細分點隱式地是節點表示的空間的中心。PR 八叉樹的根節點能夠表示無限空間；MX 八叉樹的根節點必須能夠表示有限的有界空間，以便隱式中心定義明確。

常見用途

  • 3D 計算機圖形中的細節層次渲染
  • 空間索引
  • 搜尋最近鄰
  • 三維空間中有效的碰撞檢測
  • 有限元分析
  • 稀疏體素八叉樹
  • 狀態估計
  • 集合估計

更新於： 2020年1月8日

1K+ 閱讀量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告