自動平衡（或便宜平衡）的3D數據結構

Question

我正在研究一種需要3D「基於體素」引擎的工具。我的意思是它將涉及到從網格中添加和刪除多維數據集。爲了管理這些立方體，我需要一個允許快速插入和刪除的數據結構。我在k-d樹和八叉樹中看到的問題是，由於這些操作，他們似乎經常需要重新創建（或至少重新平衡）。

在我跳入之前，我想獲得有關這方面的最佳方法的意見。

更多的細節：

• 的x，y，z位置是在整數空間
• 需要是足夠有效的實時應用
• 沒有對數量沒有硬性限制將使用的立方體。 在所有的可能性的數量將最經常不合邏輯 低（< 100），但是我想有工具處理多達 立方體儘可能

我想最終的問題是什麼是最好的方式以一種可以處理頻繁插入和刪除的方式來管理本質上的3D點數據？

（不，我不是做的Minecraft）

Answer 1

Octrees是容易進行動態更新。典型地，該樹是基於每片葉子上/下計數人口精製：

1. 當新的項目被插入時，它被壓入項目列表包圍葉節點。如果超過了上限人口數，葉子就會被精製。

2. 當現有項目被刪除時，它將從封閉葉節點的項目列表中刪除。如果達到較低的人口數量，則掃描葉兄弟姐妹。如果所有兄弟姐妹都是葉節點，並且其累計物品數量少於上限人口數量，則會刪除同組的兄弟姐妹，並將物品推送到父級。

這兩個操作都是本地的，只遍歷樹的高度，對於分佈良好的點集，這個高度是O(log(n))。

另一方面，KD樹是而不是動態更新容易，因爲它們的結構是基於全點集的分佈。

還有一些支持動態更新的其他空間數據結構 - R-trees，Delaunay triangulations僅舉幾例，但尚不清楚它們是否會提供比八叉樹更好的性能。我並不知道任何支持動態查詢的空間結構都優於O(log(n))。

希望這會有所幫助。