自动平衡(或便宜平衡)三维数据结构
自动平衡(或便宜平衡)三维数据结构
提问于 2013-08-01 09:21:38
我正在工作的工具，需要一个三维“体素基础”引擎。我的意思是，它将涉及从网格中添加和删除多维数据集。为了管理这些多维数据集，我需要一个允许快速插入和删除的数据结构。我在and树和octree中看到的问题是，由于这些操作，它们似乎经常需要重新创建(或者至少是重新平衡)。
在我加入之前，我想了解一下解决这一问题的最佳方法。
更多细节：
- x，y，z位置在整数空间中
- 需要对实时应用程序具有足够的效率。
- 使用的立方体数量没有硬性限制。在所有可能的情况下，这个数字通常会很低(<100)，但是我想让工具处理尽可能多的立方体。
我想最终的问题是，以一种能够处理频繁插入和删除的方式来管理本质上是3D点数据的最佳方法是什么？
(不，我不是在制作“我的世界”)
回答 1
Stack Overflow用户
回答已采纳
发布于 2013-08-01 12:11:24
八叉树易于动态更新。通常，树是根据每片叶子上/下的种群数进行细化的：
- 当插入一个新项时，它将被推入到包围叶节点的项目列表中。如果超过了上层种群数，叶子就会被细化。
- 当删除现有项时，它将从包围叶节点的项列表中删除。如果达到较低的种群数，则扫描叶兄弟姐妹。如果所有兄弟节点都是叶节点，并且它们的累积项计数小于上层总体计数，则删除兄弟姐妹的集合，并将项目推送到父节点上。
这两个操作都是局部的，只遍历树的高度，这是分布良好的点集的O(log(n))。
另一方面，KD-树不容易动态更新，因为它们的结构基于完整点集的分布。
还有其他一些支持动态更新的空间数据结构-- R-树、Delaunay三角等等，但还不清楚它们是否能提供比八叉树更好的性能。我不知道有任何空间结构比O(log(n))动态查询支持得更好。
希望这能有所帮助。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17990004
复制相关文章
相似问题
腾讯云开发者
