Swift算法俱乐部
本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Octree
八叉树（Octree）
八叉树是树，其中每个内部（非叶节点）节点有八个子节点。 例如，通常用于游戏中的碰撞检测。
问题
考虑以下问题：您需要在3D空间中存储多个对象（每个对象在某个位置使用X，Y和Z坐标表示）然后您需要回答哪些对象位于某个3D区域。 一个天真的解决方案是将点存储在一个数组中，然后迭代这些点并分别检查每个点。 该解决方案花费O(n)。
更好的方法
八叉树最常用于通过递归地将其细分为8个区域来划分三维空间。 让我们看看我们如何使用八叉树来存储一些值。
树中的每个节点代表一个类似盒子的区域。 叶节点在该区域中存储单个点，并为该点分配一组对象。
一旦添加了同一区域内（但在不同点）的对象，叶节点就会变成一个内部节点，并向它添加8个子节点（叶节点）。 先前包含在节点中的所有点都将传递给其对应的子节点并进行存储。 因此，只有叶子包含实际的点和值。
为了找到位于给定区域中的点，我们现在可以从上到下遍历树并从节点收集合适的点。
在最坏的情况下，添加点和搜索仍然可以占用O(n)，因为树不以任何方式平衡。 但是，平均而言，它的运行速度明显更快（与O(log n)相当）。
扩展阅读
作者：Jaap Wijnen
灵感来自于Timur Galimov和苹果公司的八叉树实现
翻译：Andy Ron
校对：Andy Ron
网友评论