nearest neighbor in 2D

[WEINHANDL Herbert]

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.  

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

The plotting-library dislin (http://www.dislin.com)
contains a really fast triangulation subroutine
(~1 hour for 700000 points on an 1.5 GHz Athlon).

For an example triangulation/nearest-neighbor-search see
the attached python-script.

Dislin is available for many platforms (Linux, Winxxx, ...)
and it can be used for free if you are using free languages like
Python, Perl, etc.

Happy pythoning

Herbert

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: nearest-n.py
URL: <http://mail.python.org/pipermail/python-list/attachments/20031105/d87f18c6/attachment.ksh>