nearest neighbor in 2D

Bengt Richter bokr at
Tue Nov 4 03:49:10 CET 2003

On Sun, 02 Nov 2003 22:12:47 -0600, John Hunter <jdhunter at> wrote:

>I have a list of two tuples containing x and y coord
> (x0, y0)
> (x1, y1)
> ...
> (xn, yn)
>Given a new point x,y, I would like to find the point in the list
>closest to x,y.  I have to do this a lot, in an inner loop, and then I
>add each new point x,y to the list.  I know the range of x and y in

Are you trying to find closest location to a mouse cursor as it moves,
and then adding a point when there's a click? I.e., your particular use case
might suggest a strategy that's different from, e.g., what you'd do if
each new point's coordinates where read from file or came from a generator,
and you had exactly one search leading to exactly one update of the set.
And also what you wanted to do with the completed set.

>One solution that comes to mind is to partition to space into
>quadrants and store the elements by quadrant.  When a new element
>comes in, identify it's quadrant and only search the appropriate
>quadrant for nearest neighbor.  This could be done recursively, a 2D
>binary search of sorts....

This might be a way of pruning, but you'd have to take into account that
nearest square doesn't guarantee nearest diagonal distance. Just blathering
off the top of my head, ... I think I would try dividing x and y into maybe a
16*16 grid of squares. A new point will fall into one of those, and then if
you find some existing points in that square, you could brute force find the
closest (remembering that comparing squared radial distances works as well as
comparing their square roots ;-) and then see if that shortest distance can
reach into any adjacent squares, and search those too if so, since there could be
a point just the other side of the border, or diagonally across an adjacent
corner that could be closer than your currently determined distance.

You could keep info about points in a square in lists or dicts (16*16 might
be sparsely populated, best in a dict of squares accessed by grid coordinates
(i.e., 4 bits apiece, maybe as tuple or combined as a single number (but then
you could use a list pre-populated with None's instead of a dict, so either way).

I guess in the extreme you could compute a complete table of nearest point
coordinates for every possible x,y point, so you'd have a raster map of voronoi
regions, with each region colored by the coordinates of its nearest point. The more
points you had, the less info would have to be updated for each new point.
I wonder when the crossover would occur ;-)
>Can anyone point me to some code or module that provides the
>appropriate data structures and algorithms to handle this task
>efficiently?  The size of the list will likely be in the range of
>10-1000 elements.
What are the ranges of x and y?

Bengt Richter

More information about the Python-list mailing list