[Numpy-discussion] finding close together points.

James Bergstra bergstrj@iro.umontreal...
Tue Nov 10 19:08:40 CST 2009

On Tue, Nov 10, 2009 at 7:07 PM, Christopher Barker
<Chris.Barker@noaa.gov> wrote:
> 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.

In some cases a brute-force approach is also good.
If r is a matrix of shape Nx2:

(r*r).sum(axis=1) -2 * numpy.dot(r, r.T) +
(r*r).sum(axis=1).reshape((r.shape[0], 1)) < thresh**2

It's brute force, but it takes advantage of fast matrix multiplication.


More information about the NumPy-Discussion mailing list