[Numpy-discussion] finding close together points.

Anne Archibald peridot.faceted@gmail....
Fri Nov 13 15:39:02 CST 2009

2009/11/13 Christopher Barker <Chris.Barker@noaa.gov>:
> Anne Archibald wrote:
>>>> 2009/11/10 Christopher Barker <Chris.Barker@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 now implemented in SVN.
> Wow! great -- you sounded interested, but I had no idea you'd run out
> and do it! thanks! we'll check it out.

No problem, it was a fairly minor modification of the two-tree code.

>> I (tentatively?) used a set to store
>> the collection of pairs, because my tree traversal is not smart enough
>> to reliably uniquify the pairs without using sets. With more time and
>> energy, I'm sure the algorithm could be improved to avoid using sets
>> (both internally and on return), but I think that's something to save
>> for the Cython version.
> I agree -- what's wrong with using a set?

It should be possible to arrange the tree traversal algorithm so that
each pair of subtrees is automatically traversed only once - akin to
for i in range(n):
    for j in range(i):
This would avoid having to build and modify a set every time you
traverse the tree (sets are fairly cheap hash tables, so the cost is
probably minor compared to other python overhead), and it would also
naturally allow the result to be a list/inflatable array (which would
save memory, if nothing else). But it would also require carefully
thinking through the tree traversal algorithm.

> Thanks, we'll let you know how it works for us.

Good luck!


> -Chris
> --
> 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@noaa.gov
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion

More information about the NumPy-Discussion mailing list