以有效的方式找到最近的点 [英] Finding nearest point in an efficient way

问题描述

我在二维平面上有一个点，例如 (x0,y0) 和一组 n 个点 (x1,y1)...(xn,yn) 我想找到离 (x0,y0) 最近的点) 比尝试所有点更好.有什么解决办法吗?

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?

我也应该说我的积分是这样排列的:

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;
 }

推荐答案

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

这篇关于以有效的方式找到最近的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！