   Compute K nearest neighbors?
  I have a std::vector containing possible hundreds of points in 2D or 3D.I am currently writing a function that based on a single input point should return the K nearest neighbors where K typically is in the range from 9-16.My first thought was to just compute the distance to all the elements, add them to a vector and sort them. I was also thinking of keeping the point vector sorted at all times.Are there any better ways to solve the above problem?   
  If you have no other information about the points, than a list of points in 3D that can be at any random position, then no, you must calculate the distance to each of them.The best way is probably to have a container with a maximum of K points sorted by distance, and go through the whole list of points, adding points to the sorted container as you go along, if their distance is close enough.   ;  How fast does this need to be? Brute force FTW.A more optimised method would be to use some form of spatial partitioning, taking only those partitions which are capable of containing points that meet the distance criteria.;  A spatial partioning structure, like a kd-tree is essentially perfect for k-nearest searches, depending on the nature of your problem a different structure may be more suited, such as whether your points are static or not, and how often the tree may need to be rebuilt or balanced.   ;  Keep in mind that you only have to calculate the squared distance to each point. No need to get the actual distance using sqrt which will be way slower.   ;  You could also use a simple uniform grid as a space partitioning structure. It may not be as efficient as a hierarchical structure like a kd-tree or an octree but it is simpler to implement and still far better than a brute force approach. For a few hundred points you may use brute force as well but a simple space partitioning scheme will make your program scalable and it's not a great effort, especially considering the fact that it's about points and not something more complex like triangles for example. It may be a nice learning exercise as well.   ;  Has quick select gone out of fashion or something?   ;  I'd like to make the following distinction:Problem 1:Input: Point p. A list of points N. k > 0.Output: Find k nearest neighbors of p from the list N.Problem 2:Input: A list of points P. A list of points N. k > 0.Output: For each p in P, find the k nearest neighbors of p from the list N.If you are trying to solve 1), there is no way to do any better than a linear search through the array (you have to look at each input point at least once). If you're trying to solve 2) however, you can accelerate the subsequent searches by building an acceleration structure of the points in N, as mentioned in a previous post.;  Problem is that I need to find the distance to eg 16 point for each pixel in a image. If I have an 128*128 pixels image i must then do:for (i=0; < 127; i++) {    for (j=0; j<127; j++) {// calc distance to 16 control points in image.    }}I have just tried adding this rutine to my function and it now goes from 18 seconds to approx. 200 seconds (on a 3Ghz Dual Core with 6 GB RAM)!So this is definitly not the way to do it.;Quote:Original post by mltI have just tried adding this rutine to my function and it now goes from 18 seconds to approx. 200 seconds (on a 3Ghz Dual Core with 6 GB RAM)!So this is definitly not the way to do it.Now you're doing something very wrong. I remember doing image matching using similar methods way back on 486, and it took seconds for larger images (384x240), so the numbers sound way off.What is the exact problem you are trying to solve.Quote:I need to find the distance to eg 16 point for each pixel in a imageWhat is distance? The distance in color space? The distance in pixel coordinates? Something else?Also, which language and which image API (if any)?   