2
私はクラスターにマップをグループにグループ化するKDツリーを実装しています。私は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)
。他のアドバイスも歓迎します。
ありがとうございました。