Quadtree Nearest Neighbour Algorithm

Question

I have implemented a quadtree structure for n points as well as a method for returning an array of points within a given rectangle. I can't seem to find an algorithm to efficiently find the point that is closest to another given point. Am I missing something obvious? I assume a recursive solution is the correct approach?

Am working in Objective C but pseudo code would be fine. Additionally I am actually storing lat, long data and the distance between points is along a great circle.

EDIT: This is my tree insert and subdivide code

- (BOOL)insert:(id<PASQuadTreeDataPoint>)dataPoint {

    BOOL pointAdded = false;

    // If the point lies within the region
    if(CGRectContainsPoint(self.region, dataPoint.point)) {

        // If there are less than 4 points then add this point
        if(self.dataPoints.count < kMaxPointsPerNode) {
            [self.dataPoints addObject:dataPoint];
            pointAdded = true;
        }
        else {

            // Subdivide into 4 quadrants if not already subdivided
            if(northEast == nil) [self subdivide];

            // Attempt to add the point to one of the 4 subdivided quadrants
            if([northEast insert:dataPoint]) return true;
            if([southEast insert:dataPoint]) return true;
            if([southWest insert:dataPoint]) return true;
            if([northWest insert:dataPoint]) return true;
        }
    }

    return pointAdded;
}

- (void)subdivide {

    // Compute the half width and the origin
    CGFloat width = self.region.size.width * 0.5f;
    CGFloat height = self.region.size.height * 0.5f;
    CGFloat x = self.region.origin.x;
    CGFloat y = self.region.origin.y;

    // Create a new child quadtree with the region divided into quarters
    self.northEast = [PASQuadTree quadTreeWithRegion:CGRectMake(x + width, y, width, height)];
    self.southEast = [PASQuadTree quadTreeWithRegion:CGRectMake(x + width, y + height, width, height)];
    self.southWest = [PASQuadTree quadTreeWithRegion:CGRectMake(x, y + height, width, height)];
    self.northWest = [PASQuadTree quadTreeWithRegion:CGRectMake(x, y, width, height)];
}

EDIT: Have written this code to find the smallest node (leaf) that would contain the point:

-(PASQuadTree *)nodeThatWouldContainPoint:(CGPoint)point {

    PASQuadTree *node = nil;

    // If the point is within the region
    if (CGRectContainsPoint(self.region, point)) {

        // Set the node to this node
        node = self;

        // If the node has children
        if (self.northEast != nil) {

            // Recursively check each child to see if it would contain the point
            PASQuadTree *childNode = [self.northEast nodeThatWouldContainPoint:point];
            if (!childNode) childNode = [self.southEast nodeThatWouldContainPoint:point];
            if (!childNode) childNode = [self.southWest nodeThatWouldContainPoint:point];
            if (!childNode) childNode = [self.northWest nodeThatWouldContainPoint:point];
            if (childNode) node = childNode;
        }
    }

    return node;
}

Closer but no cigar!

Pursuance

Answer 1

Find the smallest square with your search point at the center and exactly one other point inside that rectangle (you need to do logn number of searches).

Let x be the distance to the other point.

Then find all the points within a square whose side is 2x and centered around your first point. For each point within this square, calculate the distance from search point and find the closest.

UPDATE: How to find one square centered around search point that contains exactly one other point?

Find a random point. Let the distance to that random point be x. Find all points within square of size x centered around search point. If there are non zero number of points within this square, then select a point at random and repeat. If there are no points, increase search square size to (2-0.5)*x (in next step (2-0.25)*x and so on.

Wesley

Thanks ElKamina, will give it a go and post my code in the question. The part I am not sure about is the fact that each node will have four points in it and will only be segmented into smaller rectangles when the capacity of the node is full. Could some of these points also be the closest point? – Pursuance

OK, have code to find the smallest region that would contain the point (see original question). Struggling to find the surrounding rectangles in an elegant way, plus need to take into account the 4 points contained within each node. Any pointers would be helpful. Cheers Dave. – Pursuance

@MagicBulletDave I am just using functionality of quadtree that it "returning an array of points within a given rectangle" efficiently. I am not using any other properties. I have updated my answer with more explaination. – Wesley

Thanks ElKamina, was being a bit thick :o) – Pursuance

Each child requires to have a pointer to its parent. with this simple change, you basically can traverse upward. When you find the smallest rectangle, if doesn't have enough point you can go upward and examine your search criteria against the parent. The other solution would be the leaf nodes get connected with a pointer to its sibling building a doubly LinkedList. You basically preprocess the quadtree, During search, you find the smallest grid in the quadtree, from there you go right and left in LinkedList to find the right grids with your search criteria. – Cactus