[Numpy-discussion] finding close together points.

Lou Pecora lou_boog2000@yahoo....
Wed Nov 11 07:35:52 CST 2009

----- Original Message ----
From: Christopher Barker <Chris.Barker@noaa.gov>
To: Discussion of Numerical Python <numpy-discussion@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.


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.


More information about the NumPy-Discussion mailing list