在C中移动对象后,如何更新QuadTree？

发布时间：2020-12-16 07:13:05 所属栏目：百科来源：网络整理

导读：最简单的方法是删除和插入对象,但可能有更快的方法. (如果我正在思考这个,我应该以简单的方式去做,请告诉我) 以下是关于我的QuadTree的一些注意事项正在移动的对象是AABB,可能比AABB大最小的QuadTree节点. 创建子QuadTrees时不会删除对象.那表示根QuadTre

最简单的方法是删除和插入对象,但可能有更快的方法. (如果我正在思考这个,我应该以简单的方式去做,请告诉我)

以下是关于我的QuadTree的一些注意事项

>正在移动的对象是AABB,可能比AABB大
最小的QuadTree节点.
>创建子QuadTrees时不会删除对象.那
表示根QuadTree有一个指向其中每个对象的指针
四叉树.
>对象作为指针存储在QuadTree外部的向量中.

到目前为止,每次对象移动时,它都会在根QuadTree上调用一个名为Update()的函数.它在参数中移动之前包含自身及其过去的边界框.我不知道如何制作这个功能.

将整个代码发布到我的QuadTree会使我的帖子很长,所以我创建了一个GitHub repository以便于阅读.

编辑：对于任何寻找答案的人来说,this似乎通过删除和删除对象来更新对象,并且通过他在评论中所做的测试来判断它是非常有效的.

解决方法

除了删除和重新插入之外,做起来真的很难,特别是在你的情况下,因为：

>删除似乎超级便宜(从相应节点的向量中删除指针)
>在查找要将对象移动到哪个节点时,您需要以与插入时完全相同的方式遍历树,之后：
>插入非常便宜

如果性能确实是一个问题,我唯一会尝试的是从叶子中插入某种东西.假设您的树非常大,并且对象通常会移动到紧邻的节点,您可以请求在父节点中插入,如果需要,可以将其传递给父节点.就像是：

void insert_from_leaf(object* o) {
  if (!is_in_this_subtree(o)) {
    parent->insert_from_leaf(o);
    return;
  }
  find_child_node_for_object(o)->insert(0);
}

基本上,从对象来自叶子走树比从总是从根开始可能更有效,因为相邻节点倾向于共享一个紧密的祖先.

在更糟糕的情况下,你最终会做两倍的工作,因为你会一直回到根.在最好的情况下,源和目标共享一个直接父级.

这有多好,这完全取决于特定树的布局,大小和一系列其他因素,因此您应该在实现这样的事情之前和之后测量代码的性能.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!