Build an R-Tree in Python for Fun and Profit

There might come a time when you will prefer to stylishly load spatial data into a memory-structure rather than clumsily integrating a database just to quickly answer a question over a finite amount of data. You can use an R-tree by way of the rtree Python package that wraps the libspatialindex native library.

It’s both Python 2 and 3 compatible.

Building libspatialindex:

  1. Download it (using either Github or an archive.
  2. Configure, build, and install it (the shared-library won’t be created unless you do the install):
$ ./configure
$ make
$ sudo make install
  1. Install the Python package:
$ sudo pip install rtree
  1. Run the example code, which is based on their example code:
import rtree.index

idx2 = rtree.index.Rtree()

locs = [
    (14, 10, 14, 10),
    (16, 10, 16, 10),
]

for i, (minx, miny, maxx, maxy) in enumerate(locs):
    idx2.add(i, (minx, miny, maxx, maxy), obj={'a': 42})

for distance in (1, 2):
    print("Within distance of: ({0})".format(distance))
    print('')

    r = [
        (i.id, i.object) 
        for i 
        in idx2.nearest((13, 10, 13, 10), distance, objects=True)
    ]

    print(r)
    print('')

Output:

Within distance of: (1)

[(0, {'a': 42})]

Within distance of: (2)

[(0, {'a': 42}), (1, {'a': 42})]

NOTE: You need to represent your points as bounding-boxes, which is the basic structure of an R-tree (polygons inside of polygons inside of polygons).

In this case, we assign arbitrary objects that are associated with each bounding box. When we do a search, we get the objects back, too.

Advertisements

3 thoughts on “Build an R-Tree in Python for Fun and Profit

  1. dterza01 says:

    Great article! Terrific way to get into spatial data and queries like ranges, nearest neighbor and k-NN.
    One note on building libspatialindex
    First run ./autogen.sh in order to generate the configure file.

    Like

Comments are closed.