四叉树最近邻算法

Question

我已经实现了 n 个点的四叉树结构以及返回给定矩形内的点数组的方法。我似乎无法找到一种算法来有效地找到最接近另一个给定点的点。我错过了一些明显的东西吗？我认为递归解决方案是正确的方法吗？

我正在使用 Objective C，但伪代码就可以了。此外，我实际上存储了经纬度数据，并且点之间的距离沿着一个大圆。

编辑： 这是我的树插入和细分代码

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

更近了，但没有雪茄！

Answer 1

找到最小的正方形，其中您的搜索点位于中心，而另一个点正好位于该矩形内（您需要进行 logn 次搜索）。

设 x 为到另一点的距离。

然后找到边长为 2x 并以第一个点为中心的正方形内的所有点。对于该正方形内的每个点，计算距搜索点的距离并找到最近的点。

更新：如何找到一个以搜索点为中心且恰好包含另一个点的正方形？

找到一个随机点。设到该随机点的距离为 x。查找以搜索点为中心、大小为 x 的正方形内的所有点。如果该方格内的点数非零，则随机选择一个点并重复。如果没有点，请将搜索方块大小增加到 (2-0.5)*x（在下一步中为 (2-0.25)*x，依此类推。