nearest neighbor in 2D

[Anthony Briggs]

At 10:12 PM -0600 2/11/03, 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 method that you can use is to narrow down the list of candidates 
by only considering those points within a box around your new point, 
eg xn-5 < x < xn+5, yn-5 < y < yn+5. You'll still need to test using 
trigonometric stuff after that, and also that there won't be a point 
outside the square that'll be closer, ie. that your closest point is 
< 5 away from the new point.

You might also consider sorting the list by distance from some other 
point (eg. 0,0), and keeping it sorted as you add new points - it'll 
take some time to do, but might make things faster overall when 
searching.

Hope that helps,

Anthony
-- 
----------------------------------------------------
HyPEraCtiVE? HeY, WhO aRE YoU cALliNg HypERaCtIve?!
aBRiGgS at wEStNeT.cOm.aU
----------------------------------------------------