11

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

6 Answers6

10

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.

Nikita Rybak
  • 67,365
  • 22
  • 157
  • 181
  • 3
    Although it may seem overkill, you spend O(n log n) operations building your Voronoi diagram, but afterwards, each nearest neighbor can be looked up in O(log n) time. Contrast this with O(n) for naive iteration. Also, I recommand using CGAL for computing the Voronoi diagram (by Delaunay triangulation). CGAL is complicated, but the Delaunay algorithm is very sensitive to roundoff errors and you should not implement it yourself: you need (among others) adaptative precision floating point numbers. – Alexandre C. Dec 22 '10 at 13:57
  • Only problem is to implement the data structure :-). Also, CGAL is quite an expensive library unless you are open-sourcing your own code. – Daniel Lidström Dec 22 '10 at 15:39
  • @Daniel: I did not know cgal was dual licensed. The data structure is in fact quite natural. The real problem lies in the unstable test of "being in a circumscribed circle of a triangle": if the triangle points are almost aligned, the computation is very unaccurate and yields the wrong triangulation. – Alexandre C. Dec 22 '10 at 18:09
  • @Alexandre Yes I am very well aware of this problem :-). I've spent months working on a triangulation algorithm trying to fix it. Of course I didn't succeed and the bad code is still used by unfortunate clients... – Daniel Lidström Dec 22 '10 at 18:52
  • @Daniel: I'm afraid you have to use adaptive floating point computations. There are a lot of ways to do this, I may have some papers handy if you're interested. – Alexandre C. Dec 22 '10 at 20:41
10

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

VGE
  • 4,171
  • 18
  • 17
7

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

Gareth Rees
  • 64,967
  • 9
  • 133
  • 163
3

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.
Sneftel
  • 40,271
  • 12
  • 71
  • 104
Zac Howland
  • 15,777
  • 1
  • 26
  • 42
  • 1
    `std::min_element()` provides the answer with less complexity (max(N-1,0) comparisons) than `std::sort()` (O(N·log(N))). Exempting error handling, this yields the closest point: `std::min_element(...)->pt`. – Martin Moene Sep 03 '15 at 09:09
  • @MartinMoene Yes, `std::min_element` is a good alternative to sorting the squared distances for just the minimum element. – Zac Howland Sep 03 '15 at 19:03
0

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.

yasouser
  • 5,113
  • 2
  • 27
  • 41
0

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!

Daniel Lidström
  • 9,930
  • 1
  • 27
  • 35