# 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:

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.

## 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

• dustin says:

• dterza01 says: