Kav*_*ian 6 algorithm machine-learning spatial spatial-query spatial-index
我们有一个x,y对的列表.每对代表2D空间上的一个点.我想找到这个列表中最接近的点,到特定点xq,yq.针对此问题的最佳性能关键算法是什么？点的Lisp不会改变; 这意味着我不需要执行插入和删除.我想在这个集合中找到目标xq,yq点的最近邻居.
编辑1:谢谢大家!正如Stephan202猜对了,我想反复这样做; 像一个功能.列表不一定排序(实际上我不明白它是如何排序的？就像一个主键为2列a和y的表？如果有帮助那么我会对它进行排序).
我将基于列表构建一次数据结构,然后我将在函数中使用此生成的数据结构(如果此过程本身是相关的).
谢谢Jacob; 似乎KD-Tree数据结构是一个很好的候选者(我觉得它是.我会在得到一些相关结果时更新).
编辑2:我发现,这个问题被命名为"最近邻居"!
编辑3:第一个标题是"寻找算法(用于空间查询和空间索引)(最近邻)"; 我选择了一个新标题:"解决最近邻居的最佳性能关键算法".因为我不想对我的初始数据执行插入和删除操作,并且我只想从它们中最近的一个到新点(不会被插入),所以我选择(当前)处理KD-Trees.谢谢大家!
Jac*_*cob 10
正如Stephan202所指出的,如果你打算找到一个以上点的最接近匹配,你应该使用一棵树.
我推荐一个KD树,它的实现可以很容易地在几个包中找到,比如OpenCV 2.0.或者你可以自己实现一个!
编辑:我在这里问了一个关于kd-tree实现的问题 - 可能有用.
编辑: KD树已成功广泛用于NN搜索:) - 此外,如果您愿意接受近似匹配,您可以使用快速库近似最近邻居(FLANN).FLANN实现存在于OpenCV 2.0中.
如果您不想要近似答案,可以调整FLANN参数以搜索整个树.
如果查询点(xq,yq)发生变化而列表没有变化,则需要计算点列表的Voronoi图.这将为您提供一组多边形或"单元格"(其中一些是无限的); 每个多边形对应于原始列表中的一个点,称为该单元格的"站点".完全位于一个多边形内的任何点都比该原始列表上的其他站点更接近该多边形的位置.两个多边形之间边界上的任何点距离每个站点都相同.
一旦你到达那么远,你需要一个简单的方法来找出你所在的多边形.这就是所谓的点位置问题.
对于这类事情,一本非常非常好的书是计算几何:算法和应用.他们详细讨论了Voronoi图计算和点位置的梯形板法.
如果您不想自己编写代码,而不应该编写代码,那么请尝试使用像CGAL这样的库来完成大部分工作.这可能也适用于KD树的答案,但我不知道.