[Numpy-discussion] finding close together points.

[James Bergstra]

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.

-- 
http://www-etud.iro.umontreal.ca/~bergstrj