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).

Answer 3

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.

• Flip algorithms
• Incremental
• Divide and conquer
• Sweepline

Answer 4

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.

Answer 5

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.

Answer 6

what you are trying to do is construct a voronoi diagram this can be done in O(n log n) using a plane sweep

Answer 7

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.

Answer 8

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.