以有效的方式找到最近的点

Question

我在2d平面上有一个点,例如(x0,y0)和一组n个点(x1,y1)...(xn,yn),我想找到一个点(x0,y0)的最近点比尝试所有点更好的方式.有解决方案吗

我还应该说我的观点是这样排序的:

bool less(point a,point b){
  if(a.x!=b.x)
     return a.x<b.x;
  else
     return a.y<b.y;
 }

Answer 1

使用四叉树进行2D http://en.wikipedia.org/wiki/Quadtree

Answer 2

Voronoi图是专为快速找到最近点而设计的.虽然实现起来非常困难,但您可能会发现一些现有的库/实现.

还可以选择在正方形中重复划分平面,从而构建某种树,其中每个非叶节点有4个子节点(右上角正方形,右下角正方形等).然后,在四个方格中,你找到你的一个方位,并递归地继续它.通常这会产生足够接近的点,因此您可以省去检查其他方块的需要.
但是很容易为这种策略创建一个"反例",这将导致线性时间.

但是你可以用你的排序数组来加速这个过程.您需要一个特殊的数据结构.

编辑
第二个结构称为四叉树,感谢VGE提供名称.

Answer 3

为了有效的最近邻搜索,您需要使用空间分区方案,例如k d树.