Поиск в KD-дереве медленный - PullRequest
Новая
       46

Поиск в KD-дереве медленный

3 голосов
/ 27 февраля 2011

Я реализую KD-дерево, чтобы кластеризовать точки карты в группы. Я использую статью KD-дерева Википедии в качестве ссылки. Поиск возвращает правильную точку ближайшего соседа, но она медленнее, чем я ожидал. Вот мой код: 

- (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)

соответственно. Любой другой совет также приветствуется.

Спасибо.

1 Ответ

0 голосов
/ 10 марта 2011

То, что вы сделали, выглядит довольно хорошо для меня, если предположить, что ваш distToPoint равен sqrt((x1-x0)**2+(y1-y0)**2). Я реализовал алгоритм в Python, который может помочь перепроверить вашу версию и прояснить некоторые пункты статьи из Википедии: https://gist.github.com/863301

...