nearest neighbor in 2D

John Hunter jdhunter at ace.bsd.uchicago.edu
Mon Nov 3 05:12:47 CET 2003


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

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

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.

Thanks,
John Hunter






More information about the Python-list mailing list