nearest neighbor in 2D

Noen not.available at na.no
Mon Nov 3 01:03:56 EST 2003


John Hunter 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
> 
> 
You could to a for loop, and inside that loop you will have a variable 
lessest_distance. I dont know much geometric mathematics, but Im pretty 
sure you can use pytagoras stuff to find the lenght from (Xn,Yn) to 
(X,Y) using sinus cosinus and such.

And when the function is finished, you should return lessest_distance

	





More information about the Python-list mailing list