四叉树最近邻算法 [英] Quadtree Nearest Neighbour Algorithm
问题描述
我已经实施了四叉树结构的n个点，以及对于给定的矩形内返回点的阵列的方法。我似乎无法找到一个算法，有效地找到点最接近另一个指定点。我失去了一些东西明显？我假设一个递归的解决方案是正确的做法？
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?
上午在Objective C，但伪code工作就可以了。另外我实际存储纬度，长数据和点之间的距离是沿大圆。
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.
编辑： 这是我的树插入和细分code
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)];
}
编辑： 写这篇code，找到最小的节点（叶），将包含点：
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!
推荐答案
查找矩形（你需要做的搜索LOGN数）内最小的广场与你的搜索点为中心，准确的另外一点。
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).
设x是另一点的距离。
然后找到一个正方形的边是2倍，并在你的第一个点为中心内的所有点。对于这个广场内的每个点，计算出从搜索点的距离，找到最接近。
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?
找到一个随机点。让我们到任意点的距离为x。查找在周围搜索点为中心的大小为x的平方所有点。如果有非这个广场内零的点，然后选择一个点随机和重复。如果没有点，增加搜索平方大小（2-0.5）* X（在下一步骤（2-0.25）* x和等。
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.
这篇关于四叉树最近邻算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
