四叉树的范围搜索效率

Question

我在c中实现了一个点四叉树和该树的范围研究。我的范围研究返回正确的结果，但当我通过valgrind运行它时，valgrind被杀死了。我用的是递归方法。我想使我的范围搜索更有效，但我的大多数尝试似乎过于复杂。

int qt_rangesearch(qt_node* root, double x, double y, double d){
  qt_node* temp = root;
  int count = 0;
  if (root == NULL){ return 0; }
  if (dist2(temp->x, temp->y, x, y) <= (d*d)){
    count = 1;
  }
  return (count + 
          qt_rangesearch(temp->ne, x, y, d) + 
          qt_rangesearch(temp->nw, x, y, d) + 
          qt_rangesearch(temp->se, x, y, d) + 
          qt_rangesearch(temp->sw, x, y, d) );
}

这是我的简单方法，缓慢但杀死Valgrind。我如何使它更有效率?我假设点x,y是当前节点的SW当前节点距离x,y大于d不继续搜索到当前节点的NE。

编辑:

My distance function:

double dist2(double x1, double y1, double x2, double y2) {
    return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
}

Answer 1

你似乎总是递归到节点的每个子节点，所以你总是访问四叉树的每个节点。如果出于某种原因，你总是要访问每个节点，为什么要用四叉树呢?为什么不保留一个节点向量呢?

通常四叉树是有用的因为你可以计算出你不需要递归到一些子节点。无论是根据四叉树的构建方式，还是通过在每个节点上保存某种记录信息，你都会知道，例如，这个节点以下的所有节点都在它的距离D内，你可以从中得出，在给定的子节点下面不可能有你感兴趣的节点，所以你不需要递归下去。

排除节点的一种方法是为该节点下的所有内容保留一个边界框，并计算出该边界框内的所有内容至少距离查询点d。

另一种方法是将三角形不等式d(a, c) <= d(a, b) + d(b, c)改写为d(a, b)>= |d(a, c) - d(b, c)|(您可能还需要假设d(x, y) = d(y, x))，并使用此方法计算出给定节点下方的所有内容从查询点开始必须>= d