问四叉树最近邻算法

EN

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

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