四叉树最近邻算法

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

接近但不完美！

- Magic Bullet Dave

Answer 1

找到以你的搜索点为中心，正好有一个其他点在矩形内的最小正方形（你需要进行logn次搜索）。

设x为到其他点的距离。

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

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

找到一个随机点。将其距离设置为x。找到以搜索点为中心，边长为x的正方形内的所有点。如果此正方形内有非零数量的点，则随机选择一个并重复上述过程。如果没有点，则将搜索正方形的大小增加到（2-0.5）* x（下一步为（2-0.25）* x，以此类推）。

- ElKamina

---

谢谢ElKamina，我会尝试并在问题中发布我的代码。我不确定的部分是每个节点将有四个点，并且仅在节点的容量已满时才会被分割成更小的矩形。这些点中是否有一些也可以是最近的点？ - Magic Bullet Dave

好的，已经有代码来找到包含点（见原问题）的最小区域。正在努力以优雅的方式找到周围的矩形，并需要考虑每个节点内包含的4个点。任何指针都会很有帮助。谢谢，戴夫。 - Magic Bullet Dave

@MagicBulletDave 我只是利用四叉树的功能来高效地“返回给定矩形内的点数组”，并没有使用其他属性。我已经更新了我的答案，并提供了更详细的解释。 - ElKamina

谢谢ElKamina，我有点儿笨:o) - Magic Bullet Dave

每个子节点都需要有一个指向其父节点的指针。通过这个简单的改变，你基本上可以向上遍历。当你找到最小的矩形时，如果它没有足够的点，你可以向上走，并将你的搜索条件与父节点进行比较。另一种解决方案是将叶节点连接到其兄弟节点，构建一个双向链表。你基本上是预处理四叉树，在搜索时，找到四叉树中最小的网格，然后在链表中向左右查找符合你搜索条件的正确网格。 - Reza