由网友(玩命不玩心)分享简介：我们具有的x，y对的列表。每对重presents在二维空间中的点。我想找到从这个名单的最近点，以一个特定的点XQ，YQ。什么是这个问题的最佳性能关键算法？点Lisp是不会改变的;这意味着我并不需要执行的插入和删除。我只想找到一个目标XQ的近邻，YQ点在此设。We have a list of x,y pairs. E...

我们具有的x，y对的列表。每对重presents在二维空间中的点。我想找到从这个名单的最近点，以一个特定的点XQ，YQ。什么是这个问题的最佳性能关键算法？点Lisp是不会改变的;这意味着我并不需要执行的插入和删除。我只想找到一个目标XQ的近邻，YQ点在此设。

We have a list of x,y pairs. Every pair represents a point on a 2D space. I want to find the closest point from this list, to a specific point xq,yq. What is the best performance-critical algorithm for this problem? Lisp of points is not going to change; which means I do not need to perform insertion and deletion. I want just to find the nearest neighbor of a target xq,yq point in this set.

编辑1：感谢所有！由于Stephan202已经猜中，我想重复做;像的功能。一个列表不一定排序（其实我不明白怎么能进行排序？像表2列和y的主键？有没有什么帮助，然后我会排序）。

Edit 1: Thanks to all! As Stephan202 has guessed correctly, I want to do this repeatedly; like a function. An the list is not necessarily sorted (In fact I do not understand how can it be sorted? Like a table with a primary key of 2 columns a and y? If that helps then I will sort it).

我将构建一个基于名单上一次的数据结构，然后我会用在这个函数生成的数据结构（如果这个过程本身是相关的）。

I will construct the data structure based on the list one time, and then I will use this generated data structure in the function (if this process itself is relevant).

感谢您雅各。看来，KD-Tree的数据结构是一个很好的候选人是答案（而且我觉得它是。当我得到一些相关的结果，我会更新）。

Thank you Jacob; It seems that KD-Tree data structure is a good candidate for being the answer (And I feel it is. I will update when I get some relevant results).

编辑2：我发现，这个问题被命名为近邻

Edit 2: I have found that, this problem is named "nearest neighbor"!

编辑3：第一个标题是在算法搜索（对空间，查询和空间索引）（最近邻）;我已经选择了一个新的头衔：最佳性能关键算法求解近邻。因为我不希望我的初始数据进行插入和删除操作，我想只是最近的一个，从他们到一个新的点（这是不会被插入），我选择了（目前）工作的KD树。感谢所有！

Edit 3: First title was "In Search of an Algorithm (for Spatial-Querying and Spatial-Indexing) (Nearest Neighbor)"; I have chose a new title: "Best Performance-Critical Algorithm for Solving Nearest Neighbor". Since I do not want to perform insertion and deletion operation on my initial data and I want just the nearest one from them to a new point (which is not going to be inserted), I chose to (currently) working on KD-Trees. Thanks to all!

推荐答案

由于Stephan202指出，如果你打算找到最接近的匹配超过一个点，你应该使用一棵树。

As Stephan202 noted, if you plan to find the closest-match for more than one point, you should use a tree.

我会建议KD树，它的实现可以在几个包像的OpenCV 2.0 很容易被发现。或者你可以自己实现一个！

I would recommend a KD-tree, whose implementation can be easily found in several packages like OpenCV 2.0. Or you could implement one yourself!

编辑：我曾问一个关于kd树实现这里 - 可能是有用的。

I had asked a question about kd-tree implementations here - might be useful.

编辑： KD树已广泛成功应用于神经网络搜索:) - 另外，如果你愿意接受近似匹配，你可以使用的