| 4 | | A quadtree index for geospatial Python objects based on shapelib. |
|---|
| | 5 | Whether for PCL in-memory feature stores, Plone content, or whatever -- we need |
|---|
| | 6 | a simple spatial index to speed up retrieval of objects that intersect with a |
|---|
| | 7 | given bounding box. |
|---|
| | 8 | |
|---|
| | 9 | The simplest, most tried-and-true, open source spatial index is shapelib's |
|---|
| | 10 | (http://shapelib.maptools.org) quadtree. It's been improving the performance of |
|---|
| | 11 | MapServer applications for years. The quadtree itself is completely separable |
|---|
| | 12 | from any shapefile. We can use it with arbitrary Python object collections. |
|---|
| | 13 | |
|---|
| | 14 | Quadtree Protocol |
|---|
| | 15 | ----------------- |
|---|
| | 16 | |
|---|
| | 17 | In a nutshell: |
|---|
| | 18 | |
|---|
| | 19 | >>> index.add(id=id, bounds=[minx, miny, maxx, maxy]) |
|---|
| | 20 | >>> [n for n in index.likely_intersection(bounds=[minx, miny, maxx, maxy])] |
|---|
| | 21 | [id] |
|---|
| | 22 | |
|---|
| | 23 | This resembles a subset of the set protocol, and is all we need to begin. |
|---|
| | 24 | *add* indexes a new object by id, *likely_intersection* returns an iterator |
|---|
| | 25 | over ids where the node containing the id intersects with the specified |
|---|
| | 26 | bounding box. This method can produce false positives. It is up to the |
|---|
| | 27 | application to handle such false positive index hits and to map ids to objects. |
|---|
| | 28 | |
|---|
| | 29 | Performance |
|---|
| | 30 | ----------- |
|---|
| | 31 | |
|---|
| | 32 | Even with the false positives, Quadtree wins over brute force intersection |
|---|
| | 33 | evaluations implemented in Python once you have more than ~20 points. See the |
|---|
| | 34 | tests/benchmarks.py file for a comparison. |
|---|
