在KD-tree中搜索很慢

我正在实现一个KD-tree来将一个地图分成几组。我一直在使用Wikipedia's KD-tree article作为参考。搜索返回正确的最近邻点，但它比我预期的要慢。这里是我的代码：在KD-tree中搜索很慢

- (FDRKDTree *)nnSearchForPoint:(id <MKAnnotation>)point best:(FDRKDTree *)best { 
// consider the current node 
distToPoint = [self distanceBetweenAnnotations:self.location and:point]; 
if (distToPoint < best.distToPoint) { 
    best = self; 
} 
// search near branch 
int axis = depth % 2; 
FDRKDTree *child = nil; 
if (axis) { 
    if (point.coordinate.latitude > location.coordinate.latitude) 
     child = rightChild; 
    else 
     child = leftChild; 
} else { 
    if (point.coordinate.longitude > location.coordinate.longitude) 
     child = rightChild; 
    else 
     child = leftChild; 
} 
if (child != nil) 
    best = [child nnSearchForPoint:point best:best]; 

child = nil; 
//search the away branch - maybe 
if (axis) { 
    if (fabs(point.coordinate.latitude - self.location.coordinate.latitude) < 
     best.distToPoint) { 
     if (point.coordinate.latitude > location.coordinate.latitude) 
      child = leftChild; 
     else 
      child = rightChild; 
    } 
} else { 
    if (fabs(point.coordinate.longitude - self.location.coordinate.longitude) < 
     best.distToPoint) { 
     if (point.coordinate.longitude > location.coordinate.longitude) 
      child = leftChild; 
     else 
      child = rightChild; 
    } 
} 


if (child != nil) { 
    best = [child nnSearchForPoint:point best:best]; 
} 

return best; 
}

我的问题是，如果我的“一个简单的对比解读，看看是否搜索点的分裂之间的差异协调和当前节点不到的距离（整体坐标）搜索指向当前最好的。“是正确的。我将此解释为：分别

if (fabs(point.coordinate.latitude - self.location.coordinate.latitude) < best.distToPoint)

和

if (fabs(point.coordinate.longitude - self.location.coordinate.longitude) < best.distToPoint)

。任何其他建议也是受欢迎的。

谢谢。

来源

2011-02-27 Kim Fiedler Vestergaard

你所做的事对我来说看起来相当不错，假设你的distToPoint是sqrt((x1-x0)**2+(y1-y0)**2)。我在Python中实现了该算法，这可能有助于交叉检查您的版本并阐明一些Wikipedia文章要点： https://gist.github.com/863301

来源

2011-03-10 03:30:34 Tom

在KD-tree中搜索很慢

回答

相关问题