[SciPy-User] Scipy.spatial: Interval data structure?

[James Anderson]

Thanks,
	I may have found a solution with "rtree" on Gohlke's site.  It allows searching for ranges in 2D and 3D.  The downside is not having a Python 3 build.  However it has the exact functionality I needed.  I'm testing it out now.

	

-----Original Message-----
From: scipy-user-bounces at scipy.org [mailto:scipy-user-bounces at scipy.org] On Behalf Of Nathaniel Smith
Sent: Friday, December 13, 2013 11:24 AM
To: SciPy Users List
Subject: Re: [SciPy-User] Scipy.spatial: Interval data structure?

On Fri, Dec 13, 2013 at 10:47 AM, James Anderson <James.R.Anderson at utah.edu> wrote:
> I’m looking for a reasonably fast interval tree structure in Python 
> and Scipy.Spatial seems like the right place for this structure to 
> live.  I need the basic queries of “All intervals intersecting a 
> point” and “All intervals intersecting an interval”
>
> The only other interval tree I’ve found is in Banyan, but that 
> requires compilation and most of my users are on Windows so I try to 
> restrict my dependencies to the ones they can easily download from Gohlke’s site.
>
> Right now I’m thinking of coding my own interval tree in pure Python, 
> but before I do that is there an existing way of doing this with Scipy 
> I am missing?

I don't know of any implementation in scipy.

bx-python has an interval tree implementation, that I think has a pure-Python version.

For a hack implementing an interval-tree-like structure using the stdlib sqlite module, there's also this trick:
  http://www.logarithmic.net/pfh/blog/01235197474
which is what rERPy uses:
  https://github.com/rerpy/rerpy/blob/master/rerpy/events.py
But not sure this is the most useful approach unless you need some of the other advantages of sqlite.

Before spending a lot of effort on writing new code you might see if cgohlke would be willing to add banyan to his list, or if the banyan developers are interested in distributing .whl's for windows...

-n
_______________________________________________
SciPy-User mailing list
SciPy-User at scipy.org
http://mail.scipy.org/mailman/listinfo/scipy-user