nearest neighbor in 2D

[Ron Adam]

On Sun, 02 Nov 2003 22:12:47 -0600, John Hunter
<jdhunter at ace.bsd.uchicago.edu> 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
>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
>


This is how I would do it.  Maybe it's how you are already doing it?


import math
import random

n_points = 1000
max_x = 1000
max_y = 1000
closest_distance = 10000
closest_point = (max_x,max_y)

p = []
for i in xrange(n_points):
    x = round(max_x*random.random())
    y = round(max_y*random.random())
    p.append((x, y))

new_point = (round(max_x*random.random()), \
             round(max_y*random.random()))

for point in p:
    distance = math.sqrt((new_point[0]-point[0])**2 \
                         +(new_point[1]-point[1])**2)    
    if distance < closest_distance:
        closest_distance = distance
        closest_point = point
        
print 'new_point:', new_point
print 'closest_point:', closest_point,' \
        out of',n_points,'points.'


I really don't know how you can make this faster.  There might be a
library that has a distance between two points function that could
speed it up.

Ronald R. Adam
radam2 at tampabay.rr.com