Find the closest point from the point vector

Question

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

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

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

Answer 1

Sorting takes O(n*log(N)) , so it is not very efficient. You can do this in O(n) by simply repeating the elements and remembering the best match.

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

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

Answer 2

The main question is how often will you make queries against one set of points.

If you are going to find one closest point in the set once, then @Lucian is right: you can also leave the points unsorted and perform a linear search to find the desired point.

If you will make a relatively large number of requests against the same set of points, it is advisable to organize point data to increase the speed of the request. @izomorphius already mentioned the kd tree, and this is definitely a good suggestion. Another possibility (admittedly quite similar) is the oct-tree. Between them, I find oct-tree a little easier to understand. Theoretically, the kd tree should be a little more efficient (on average), but I never saw much difference - although perhaps with different data the difference would be significant.

Please note, however, that creating something like a kd tree or an oct tree is not very slow, so you don’t have to make a lot of queries against many points to justify building it. One request clearly does not justify it, and two probably will not, either, but contrary to what Lucian suggests, O (N log N) (for example,) is not very slow. Roughly speaking, log (N) is the number of digits in the number N, so O (N log N) is actually not much slower than O (N). This, in turn, means that you do not need a particularly large number of queries to justify the organization of data to speed up each of them.

Answer 3

You cannot go faster than a linear comparison if you only know that there are dots in the vector. However, if you have additional knowledge, much can be improved. For example, if you know that all points are ordered and lie on the same line, there is a logarithmic solution.

There are also more efficient data structures to solve your problem, such as kd tree . It is not part of the STL - you will have to implement it yourself, but it is the data structure that is used to solve the problem that you have.

Answer 4

you can try using Quadtree http://en.wikipedia.org/wiki/Quadtree

or something similar.