最佳性能关键算法求解近邻 [英] Best Performance-Critical Algorithm for Solving Nearest Neighbor

问题描述

我们具有的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树已广泛成功应用于神经网络搜索:) - 另外，如果你愿意接受近似匹配，你可以使用的Fast图书馆近似最近Neigbor（FLANN）。该FLANN实现是present在 OpenCV的2.0 。

KD-trees have been widely used successfully for NN searches :) - Also, if you're willing to accept approximate matches, you can use Fast Library for Approximate Nearest Neigbor (FLANN). The FLANN implementation is present in OpenCV 2.0.

如果你不想近似答案你可以调整FLANN的参数来搜索整个树。

If you don't want approximate answers you can tweak the FLANN parameters to search the entire tree.

这篇关于最佳性能关键算法求解近邻的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！