Find the closest point out of a vector of points

Question

I have vector of pointers to a very simple Point class:

class Point{
public:
    float x;
    float y;
    float z;
};

How do I find the closest object to a referent point using STL?
Do I need first sort the vector first or is there a more efficient way?

Answer 1

Sorting takes O(n*log(N)), so it's not very efficient. You can do it in O(n) by just iterating through the elements and memorizing the best match.

Using for_each from <algorithm>, you can define a function that keeps track of the closest elements and completes in O(n).

Or, you can probably even use min_element, also from <algorithm>.

Answer 2

The basic question here is how often you'll be doing queries against a single set of points.

If you're going to find one nearest point in the set one time, then @Lucian is right: you might as well leave the points un-sorted, and do a linear search to find the right point.

If you'll do a relatively large number of queries against the same set of points, it's worthwhile to organize the point data to improve query speed. @izomorphius has already mentioned a k-d tree, and that's definitely a good suggestion. Another possibility (admittedly, quite similar) is an oct-tree. Between the two, I find an oct-tree quite a bit easier to understand. In theory, a k-d tree should be slightly more efficient (on average), but I've never seen much difference -- though perhaps with different data the difference would become significant.

Note, however, that building something like a k-d tree or oct-tree isn't terribly slow, so you don't need to do an awful lot of queries against a set of points to justify building one. One query clearly doesn't justify it, and two probably won't either -- but contrary to what Luchian implies, O(N log N) (just for example) isn't really very slow. Roughly speaking, log(N) is the number of digits in the number N, so O(N log N) isn't really a whole lot slower than O(N). That, in turn, means you don't need a particularly large number of queries to justify organizing the data to speed up each one.