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.

Answer 2

I will have to agree with jk and Ewan with making a Voronoi Diagram. This will partition the space in polygons. Every point in K will have a polygon describing all points that are closest to it. Now when you get a query of a point, you need to find in which polygon it lies. This problem is called Point Location and can be solved by constructing a Trapezoidal Map.

jk already linked to the creation of the Voronoi Diagram using Fortune's algorithm which takes O(n log n) computational steps and costs O(n) space. This website shows you how to make a trapezoidal map and how to query it. You can also find some bounds there:
Expected creation time: O(n log n)
Expected space complexity: O(n)

But most importantly, expected query time: O(log n). This is (theoretically) better than O(√n) of the kD-tree.

My source(other than the links above) is: Computational Geometry: algorithms and applications, chapters six and seven.

There you will find detailed information about the two data structures (including detailed proofs). The Google books version only has a part of what you need, but the other links should be sufficient for your purpose. Just buy the book if you are interested in that sort of thing (it's a good book).