R-Tree spatial index for Python GIS
Whether for in-memory feature stores, Plone content, or whatever – we need an index to speed up the search for objects that intersect with a spatial bounding box. R-trees provide excellent query performance and good incremental insert performance.
Rtree is a Python library that uses ctypes and an internally built C API to wrap libspatialindex and provide very flexible spatial indexing. Rtree has gone through a number of iterations, and at 0.5.0, it was completely refactored to use a new internal architecture (ctypes + a C API over libspatialindex). This refactoring has resulted in a number of new features and much more flexibility. See CHANGES.txt for more detail.
In a nutshell:
>>> from rtree import Rtree >>> idx = Rtree() >>> idx.add(id=id, bounds=(left, bottom, right, top)) >>> [n for n in idx.intersection((left, bottom, right, top))] [id]
The following finds the 1 nearest item to the given bounds. If multiple items are of equal distance to the bounds, both are returned:
>>> sorted(idx.nearest((left, bottom, right, top), 1)) [0L, 1L]
This resembles a subset of the set protocol. add indexes a new object by id, intersection returns an iterator over ids (or objects) where the node containing the id intersects with the specified bounding box. The intersection method is exact, with no false positives and no missed data. Ids can be ints or long ints; index queries return long ints.
Rtree also supports inserting pickleable objects into the index (called a clustered index in libspatialindex parlance). The following inserts the pickleable object 42 into the index with the given id:
>>> index.add(id=id, bounds=(left, bottom, right, top), obj=42)
You can then return a list of objects by giving the objects=True flag to intersection:
>>> [n.object for n in index.intersection((left, bottom, right, top), objects=True)] 42
As of Rtree version 0.5.0, you can create 3D (actually kD) R-trees. The following is a 3D index that is to be stored on disk. Persisted indexes are stored on disk using two files – an index file (.idx) and a data (.dat) file. You can modify the extensions these files use by altering the properties of the index at instantiation time. The following creates a 3D index that is stored on disk as the files 3d_index.data and 3d_index.index:
>>> from rtree import index >>> p = index.Property() >>> p.dimension = 3 >>> p.dat_extension = 'data' >>> p.idx_extension = 'index' >>> idx3d = index.Index('3d_index',properties=p) >>> idx3d.insert(1, (0, 0, 60, 60, 23.0, 42.0)) >>> idx3d.intersection( (-1, -1, 62, 62, 22, 43)) [1L]
First, download and install version 1.4.0 of the libspatialindex library from:
The library is a GNU-style build, so it is a matter of:
$ ./configure; make; make install
You may need to run the ldconfig command after installing the library to ensure that applications can find it at startup time.
At this point you can get Rtree 0.5.0 via easy_install:
$ easy_install Rtree
or by running the local setup.py:
$ python setup.py install
You can build and test in place like:
$ python setup.py test
See tests/index.txt for more detail on index usage and tests/properties.txt for index properties that can be set and manipulated. Refer to libspatialindex documentation or code for more detail on their meanings and usage.
See the tests/benchmarks.py file for a comparison.
For current information about this project, see the wiki.
If you have questions, please consider joining our community list:
Release history Release notifications | RSS feed
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, size||File type||Python version||Upload date||Hashes|
|Filename, size Rtree-0.5.0-py2.5-macosx-10.5-i386.egg (108.3 kB)||File type Egg||Python version 2.5||Upload date||Hashes View|
|Filename, size Rtree-0.5.0-py2.6-win32.egg (226.7 kB)||File type Egg||Python version 2.6||Upload date||Hashes View|
|Filename, size Rtree-0.5.0.tar.gz (56.9 kB)||File type Source||Python version None||Upload date||Hashes View|
|Filename, size Rtree-0.5.0.win32-py2.6.exe (288.4 kB)||File type Windows Installer||Python version 2.6||Upload date||Hashes View|
Hashes for Rtree-0.5.0-py2.5-macosx-10.5-i386.egg