3

マップ ポイントをグループにクラスター化する KD ツリーを実装しています。Wikipedia の 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)

それぞれ。その他アドバイスも大歓迎です。

ありがとう。

4

1 に答える 1

0

あなたがしたことは、私にはかなり良さそうに見えdistToPointますsqrt((x1-x0)**2+(y1-y0)**2)。Python でアルゴリズムを実装しました。これは、バージョンをクロスチェックし、ウィキペディアの記事のポイントの一部を明確にするのに役立つ場合があります: https://gist.github.com/863301

于 2011-03-10T03:30:34.193 に答える