我正在实现一个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)
分别表示。欢迎提出任何其他建议。
谢谢。