[Numpy-discussion] finding close together points.

[Lou Pecora]

----- Original Message ----
From: Christopher Barker <Chris.Barker at noaa.gov>
To: Discussion of Numerical Python <numpy-discussion at scipy.org>
Sent: Tue, November 10, 2009 7:07:32 PM
Subject: [Numpy-discussion] finding close together points.

Hi all,

I have a bunch of points in 2-d space, and I need to find out which 
pairs of points are within a certain distance of one-another (regular 
old Euclidean norm).

scipy.spatial.KDTree.query_ball_tree() seems like it's built for this.



----
Chris,

Maybe I'm missing something simple, but if your array of 2D points is static, a KD tree for 2D nearest neighbor seems like over kill.  You might want to try the simple approach of using boxes of points to narrow things down by sorting on the first component.  If your distances are, say, 10% of the variance, then you'll *roughly* decrease the remaining points to search by a factor of 10.  This can get more sophisticated and is useful in higher dimensions (see:  Sameer A. Nene and Shree K. Nayar, A Simple Algorithm for Nearest Neighbor Search in High Dimensions, IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 19 (9), 989 (1997).) where for a static data set it can match KD trees in speed, but is SO much easier to program.  
 -- Lou Pecora, my views are my own.