Hi,
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.
This class of problems is usually solved by spreading out the cost of the calculation. If you can calcuate the distance when you create or add the pixels you won't have to do it all at once later.
This is called the nearest neighbor search. Donald Knuth called it the post-office problem.
There are a number of solutions: linear search, locality sensitive hashing, vector approximation files and space partitioning.
Googling those should help.
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.
Depending on how densely this graphic is filled with pixels, you might be better off just searching outward from your pixel of origin.
I programmed something like this for a graphic terminal emulation. What I ended up doing was programming a search pattern in the shape of a square-sided spiral that grew out from the center point, and I let it grow until it hit something. That was sufficiently fast for the purpose, even on an old CPU.
Another hint: The distance is always greater than or equal to each coordinate difference, and always less than or equal to their sum, i.e.
d >= dx, d >= dy, d <= dx + dy.
This might help you doing the sorting more efficiently.
what you are trying to do is construct a voronoi diagram this can be done in O(n log n) using a plane sweep
The construction of Voronoi Diagrams is a branch of Computational Geometry. The construction of Delaunay Triangulations involves similar considerations. You may be able to adapt one of the following Delaunay algorithms to suit your needs.
Put the points in a KD tree, after this it's very fast to find the nearest neighbor. See this article on wikipedia for details.