Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
OcTree.playground
README.md
README_en.md

README.md

八叉树(Octree)

八叉树是,其中每个内部(非叶节点)节点有八个子节点。 例如,通常用于游戏中的碰撞检测。

问题

考虑以下问题:您需要在3D空间中存储多个对象(每个对象在某个位置使用XYZ坐标表示)然后您需要回答哪些对象位于某个3D区域。 一个天真的解决方案是将点存储在一个数组中,然后迭代这些点并分别检查每个点。 该解决方案花费O(n)。

更好的方法

八叉树最常用于通过递归地将其细分为8个区域来划分三维空间。 让我们看看我们如何使用八叉树来存储一些值。

树中的每个节点代表一个类似盒子的区域。 叶节点在该区域中存储单个点,并为该点分配一组对象。

一旦添加了同一区域内(但在不同点)的对象,叶节点就会变成一个内部节点,并向它添加8个子节点(叶节点)。 先前包含在节点中的所有点都将传递给其对应的子节点并进行存储。 因此,只有叶子包含实际的点和值。

为了找到位于给定区域中的点,我们现在可以从上到下遍历树并从节点收集合适的点。

在最坏的情况下,添加点和搜索仍然可以占用O(n),因为树不以任何方式平衡。 但是,平均而言,它的运行速度明显更快(与O(log n)相当)。

扩展阅读

八叉树的维基百科
苹果公司的八叉树实现GKOctree

作者:Jaap Wijnen
灵感来自于Timur Galimov和苹果公司的八叉树实现
翻译:Andy Ron
校对:Andy Ron

You can’t perform that action at this time.