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

问题描述

我有在2D平面上的点，例如（X0，Y0）和一组n个点（X1，Y1）...（XN，YN），我想找到最近点（X0，Y0 ）在某种程度上比尝试所有的好点。任何解决办法？

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

 布尔少（A点，B点）{
  如果（a.x！= b.x）
     返回a.x＆LT; b.x;
  其他
     返回a.y＆LT; b.y;
 }
 

解决方案

使用一个四叉树为2D http://en.wikipedia.org/wiki/Quadtree

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

解决方案

Use a quad-tree for 2D http://en.wikipedia.org/wiki/Quadtree

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