在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中搜索很慢

回答

相關問題