我已经实现了 n 个点的四叉树结构以及返回给定矩形内的点数组的方法。我似乎无法找到一种算法来有效地找到最接近另一个给定点的点。我错过了一些明显的事情吗?我认为递归解决方案是正确的方法吗?
我正在使用 Objective C,但伪代码就可以了。此外,我实际上存储了经纬度数据,并且点之间的距离沿着一个大圆。
EDIT:这是我的树插入和细分代码
- (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:编写此代码来查找包含该点的最小节点(叶):
-(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;
}
更近了,但没有雪茄!