Finding nearest point in an efficient way

Question

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

Answer 1

For efficient nearest neighbour search you need to use a spatial partitioning scheme, for example a kd-tree.

Answer 2

If you aren't using any sort of tree data structure to help limit the range of values you have to query, you are going to have to check each point in your range of potential "neighbors". One way to limit the comparisons would be to check the squared distance from your given point for the smallest value:

Point myPoint = {x, y};
std::vector<Point> otherPoints; // given list of points to check

struct PointDistance
{
    Point pt;
    float dist;
};

std::vector<PointDistance> squaredDistances(otherPoints.size()); // will be filled in with squared distances

float CalculateDistance(const Point& pt1, const Point& pt2)
{
    float deltaX = pt1.x - pt2.x;
    float deltaY = pt1.y - pt2.y;
    return (deltaX * deltaX) + (deltaY * deltaY);
}

// should be changed to use an algorithm, but for clarity done as a loop here
for (int i = 0; i < otherPoints.size(); ++i)
{
    PointDistance pd;
    pd.pt = otherPoints[i];
    pd.dist = CalculateDistance(myPoint, pd.pt);
    squaredDistances.push_back(pd);
}

bool DistanceLess(const PointDistance& lhs, const PointDistance& rhs)
{
    return lhs.dist < rhs.dist;
}

std::sort(squaredDistances.begin(), squaredDistances.end(), DistanceLess);

// squaredDistances[0].pt will be your closest point.

Answer 3

A particularly nice solution is ANN: A Library for Approximate Nearest Neighbor Searching. I've used it for point location in triangulations. You initialize a data structure with points, in my case I used the center points of my triangles. Then you can pass in another point and get back list of the approximate closest neighbour points. Even the number of points returned is selectable as a parameter. Anyway ANN was a great library for my purposes, I'd suggest you check it out.

Good luck!

Answer 4

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

Answer 5

If you are creating the set of N points then instead of just pushing them into a set, you can hash and map them based on their linear distance from the point under consideration . So points with same linear distance will be in the same bucket. Then fetching the point(s) based on distance will be a constant time operation.

Answer 6

Voronoi diagram is designed specifically for finding nearest point very fast. Although it's quite a pain to implement, you might find some existing library/implementation.

There's also an option to of repeatedly dividing plane in squares, thus building some kind of tree where each non-leaf node has 4 children (top-right square, bottom-right square, etc.). Then, of four squares you find the one your point is in and proceed with it recursively. Often this yields point close enough, so you may eliminate the need to check other squares.
But it's easy to create a 'counter-example' for this strategy which will result in linear time.

But there's not much you can do with your sorted array to speed up the process. You'll need a special data structure.

edit
Second structure is called Quadtree, thanks to VGE for providing the name.