Searching in KD-tree slow

I'm implementing a KD-tree to cluster points a map into groups. I've been using Wikipedia's KD-tree article as a reference. The search returns the correct nearest neighbor point, but it is slower than开发者_JAVA技巧 I expected. Here is my code:

- (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;
}

My question is if my interpretation of "a simple comparison to see whether the difference between the splitting coordinate of the search point and current node is less than the distance (overall coordinates) from the search point to the current best." is correct. What I interpret this as:

if (fabs(point.coordinate.latitude - self.location.coordinate.latitude) < best.distToPoint)

and

if (fabs(point.coordinate.longitude - self.location.coordinate.longitude) < best.distToPoint)

respectively. Any other advice is also welcome.

Thanks.

What you've done looks pretty good to me, assuming your distToPoint is sqrt((x1-x0)**2+(y1-y0)**2). I implemented the algorithm in Python which may help to cross-check your version and clarify some of the Wikipedia article points: https://gist.github.com/863301