34

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.

8 Answers 8

43

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.

4
  • good thinking! for large datasets, this would reduce run-time tremendously. Dec 14, 2009 at 14:18
  • 2
    Since you are dealing with pixels, this also means you can drop down to integer maths, which is another huge speed bonus Dec 14, 2009 at 14:21
  • 11
    @rikh Even if you do need the distance, you could always do the sqrt once you know which point is nearest. Dec 14, 2009 at 14:22
  • Is it a good idea to generalize quadtrees to perform search on n-dimensional vectors?
    – Shashwat
    Jul 13, 2018 at 8:48
21

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

7

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.

7

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.

7

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

4

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.

3

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.

1
  • 1
    For a single point, my algorithm is "good enough". For a whole bunch, Voronoi sounds like a winner. I'd retract my answer except some future readers might have the single point requirement. Dec 14, 2009 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.