algorithm - Closest point to a given point

Question

I have a set K of randomly selected pixels in a 2D image. For every other pixel in the image I need to find out which pixel in set K is closest to it (using the standard sqrt(dx^2 + dy^2) measure of distance). I am aware that there may be more than one solution for each pixel. Obviously it can be done by brute force against every pixel in the set, but I'd rather avoid this as it's not efficient. Any other good suggestions?

Cheers.

Answer 1

Don't forget that you don't need to bother with the square root.

If you just want to find the nearest one (and not it's actual distance) just use dx^2 + dy^2, which will give you the distance squared to the each item, which is just as useful.

If you have no data structure wrapping this list of pixels up, you will need to just test against them all.

If you have some flexibility, there are loads of good ways to reducing the workload. Make a Quadtree, or keep sorted list of the pixels (sorted by x and sorted by y) to narrow your search more quickly.