虽然我们通常为每个四叉树定义容量,但我在网上找到的所有伪代码算法似乎都不太关心四叉树内视觉点数。
当四叉树被划分时,是否有必要将其包含的点重新分配给其子树?
我似乎无法正确实现这一点,维基百科四叉树的伪代码类别对此只有一条评论(但没有代码(:
如果我们希望只有最后一个节点保存数据,我们必须将包含在这个四元数组中的点/数据添加到新的四元数组
假设问题是关于点四叉树的,让我们复习一下。
当四叉树被分割时,是否有必要将其包含的点重新分配给其子树?
不,没有必要。
但是,它更好吗
当特定用例中的性能测量结果显示启用了Redistribution后代码运行速度更快时,重新分发通常只是你打开的东西。
感谢@Mik'Pomax'Kamermans的评论。
这取决于您如何使用四叉树。
记住,
-
您仍然可以为每个四叉树定义一个
capacity
,作为划分阈值。 -
它不会影响整体时间复杂性。
-
更多的四叉树将会出现。
父母不会持有任何观点。
-
在插入时支付价格。
当满足容量时,您必须重新分配点。
对查询的影响是什么?
- 超出范围点停止得更快
- 强力重击检查点可能会减少
- 选中的四叉树可能会增加
与其他模式相比,它执行得更快还是更慢,这实际上取决于环境;容量、递归堆栈开销和点分散。
但是,由于您在插入时付出了代价,它通常会更快地执行查询。