C++ 以有效的方式寻找最近点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4509798/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding nearest point in an efficient way
提问by Nikita Rybak
I've got a point in 2d plane for example (x0,y0) and a set of n points (x1,y1)...(xn,yn) and I want to find nearest point to (x0,y0) in a way better than trying all points. Any solutions?
我在二维平面中有一个点，例如 (x0,y0) 和一组 n 个点 (x1,y1)...(xn,yn)，我想在 a比尝试所有要点要好得多。任何解决方案？
I should also say that my points are sorted in this way:
我还应该说，我的观点是这样排序的：
bool less(point a,point b){
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
回答by VGE
Use a quad-tree for 2D http://en.wikipedia.org/wiki/Quadtree
将四叉树用于 2D http://en.wikipedia.org/wiki/Quadtree
回答by Nikita Rybak
Voronoi diagramis designed specifically for finding nearest point very fast. Although it's quite a pain to implement, you might find some existing library/implementation.
Voronoi 图专为快速查找最近点而设计。尽管实现起来非常痛苦，但您可能会发现一些现有的库/实现。
There's also an option to of repeatedly dividing plane in squares, thus building some kind of tree where each non-leaf node has 4 children (top-right square, bottom-right square, etc.). Then, of four squares you find the one your point is in and proceed with it recursively. Often this yields point close enough, so you may eliminate the need to check other squares.
But it's easy to create a 'counter-example' for this strategy which will result in linear time.
还可以选择在正方形中重复划分平面，从而构建某种树，其中每个非叶节点都有 4 个子节点（右上角的正方形、右下角的正方形等）。然后，在四个方格中找到你的点所在的方格并递归进行。通常这会产生足够接近的点，因此您可能无需检查其他方块。
但是很容易为这个策略创建一个“反例”，这将导致线性时间。
But there's not much you can do with your sorted array to speed up the process. You'll need a special data structure.
但是对于已排序的数组，您无能为力来加速该过程。您将需要一个特殊的数据结构。
edit
Second structure is called Quadtree, thanks to VGEfor providing the name.
编辑
第二个结构称为Quadtree，感谢VGE提供的名称。
回答by Gareth Rees
回答by Zac Howland
If you aren't using any sort of tree data structure to help limit the range of values you have to query, you are going to have to check each point in your range of potential "neighbors". One way to limit the comparisons would be to check the squared distance from your given point for the smallest value:
如果您不使用任何类型的树数据结构来帮助限制您必须查询的值的范围，您将不得不检查潜在“邻居”范围内的每个点。限制比较的一种方法是检查与给定点的平方距离以获得最小值：
Point myPoint = {x, y};
std::vector<Point> otherPoints; // given list of points to check
struct PointDistance
{
Point pt;
float dist;
};
std::vector<PointDistance> squaredDistances(otherPoints.size()); // will be filled in with squared distances
float CalculateDistance(const Point& pt1, const Point& pt2)
{
float deltaX = pt1.x - pt2.x;
float deltaY = pt1.y - pt2.y;
return (deltaX * deltaX) + (deltaY * deltaY);
}
// should be changed to use an algorithm, but for clarity done as a loop here
for (int i = 0; i < otherPoints.size(); ++i)
{
PointDistance pd;
pd.pt = otherPoints[i];
pd.dist = CalculateDistance(myPoint, pd.pt);
squaredDistances.push_back(pd);
}
bool DistanceLess(const PointDistance& lhs, const PointDistance& rhs)
{
return lhs.dist < rhs.dist;
}
std::sort(squaredDistances.begin(), squaredDistances.end(), DistanceLess);
// squaredDistances[0].pt will be your closest point.
回答by Daniel Lidstr?m
A particularly nice solution is ANN: A Library for Approximate Nearest Neighbor Searching.I've used it for point location in triangulations. You initialize a data structure with points, in my case I used the center points of my triangles. Then you can pass in another point and get back list of the approximate closest neighbour points. Even the number of points returned is selectable as a parameter. Anyway ANN was a great library for my purposes, I'd suggest you check it out.
一个特别好的解决方案是ANN：A Library for Approximate Nearest Neighbor Searching。我已将其用于三角剖分中的点位置。你用点初始化一个数据结构，在我的例子中，我使用了三角形的中心点。然后您可以传入另一个点并获取近似最近邻点的列表。甚至返回的点数也可以作为参数选择。无论如何，ANN 对我来说是一个很棒的图书馆，我建议你检查一下。
Good luck!
祝你好运！
回答by yasouser
If you are creating the set of N points then instead of just pushing them into a set, you can hash and map them based on their linear distance from the point under consideration . So points with same linear distance will be in the same bucket. Then fetching the point(s) based on distance will be a constant time operation.
如果您正在创建 N 个点的集合，那么您可以根据它们与所考虑的点的线性距离对它们进行散列和映射，而不是仅仅将它们推入一个集合中。所以具有相同线性距离的点将在同一个桶中。然后根据距离获取点将是一个恒定的时间操作。
