[Numpy-discussion] finding close together points.

[Christopher Barker]

Anne Archibald wrote:
> 2009/11/10 Christopher Barker <Chris.Barker at noaa.gov>:

>> 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).
> 
> This is an eminently reasonable thing to want, and KDTree should
> support it. Unfortunately it doesn't.

darn.

> It's slow both because you're using the python implementation rather
> than the C,

I noticed that.

> The one good thing about using the python implementation rather than
> the Cython one is that you can subclass it, providing a new method.
> There's still a certain amount of boilerplate code to write, but it
> shouldn't be too bad.

Can you give me a hint as to where to start?  I have no idea how kd 
trees work.

> If this is still too slow, I have no problem incorporating additional
> code into cKDTree; the only reason none of the ball queries are in
> there is because ball queries must return variable-size results, so
> you lose a certain amount of speed because you're forced to manipulate
> python objects. But if there are relatively few result points, this
> need not be much of a slowdown.

And certainly in this case, there would not be very many results, and 
lists are pretty fast.

However, this does bring up the need for a growable numpy array. I've 
been working on one in Python, but it would be really nice to have one 
that could be accessed by C (or cython) code.

It wouldn't be that hard to do (for someone familiar with the numpy 
code, anyway), I don't think. It is mostly boiler plate in Python. I'm 
imagining it would only support contiguous arrays, and could only grow 
is the first dimension.




-- 
Christopher Barker, Ph.D.
Oceanographer

Emergency Response Division
NOAA/NOS/OR&R            (206) 526-6959   voice
7600 Sand Point Way NE   (206) 526-6329   fax
Seattle, WA  98115       (206) 526-6317   main reception

Chris.Barker at noaa.gov