In Rtree news

>>> from rtree import Rtree
>>> help(Rtree)

class BaseIndex(object):
    """Base class for indexes

    Deals in GeoJSON-like dicts we will call ``items``, like:

      {'id': 'db441f41-ec34-40fb-9f62-28b5a9f2f0e5',    # required
       'bbox': (0.0, 0.0, 1.0, 1.0),                    # recommended
       'geometry':                                      # required
         {'type': 'LineString', 'coordinates': ((0.0, 0.0), (1.0, 1.0))},
       'properties': { ... }                            # optional
       ... }

    """
    def intid(self, item):
        """Return a unique integer id for the item"""
        raise NotImplementedError
    def bbox(self, item):
        """Return a (minx, miny, maxx, maxy) tuple for the item"""
        return bbox(item)
    def intersection(self, bbox):
        """Return an iterator over items that intersect with the bbox"""
        raise NotImplementedError
    def nearest(self, bbox, limit=0):
        """Return an iterator over the nearest N=limit items to the bbox"""
        raise NotImplementedError
    def index_item(self, itemid, bbox, item):
        """Index item using unique integer itemid and bbox as key"""
        raise NotImplementedError
    def unindex_item(self, itemid, bbox):
        """Unindex the item with (itemid, bbox) as key"""
        raise NotImplementedError

class VRtreeIndex(BaseIndex):
    """An index with an R-tree as the forward mapping and a B-tree as the
    backward mapping

    Modeled after the example at http://docs.zope.org/zope.catalog/index.html.
    """

    def clear(self):
        self.fwd = Rtree()
        self.bwd = OOBTree.OOBTree()
    def __init__(self):
        self.clear()
    def intid(self, item):
        """Rtree requires unsigned long ids. Python's hash() yields signed
        ints, so we add 2**32 to hashed values for the former."""
        return hash(item['id']) + OFFSET
    def intersection(self, bbox):
        """Return an iterator over Items that intersect with the bbox"""
        for hit in self.fwd.intersection(bbox, True):
            yield self.bwd[(hit.id, tuple(hit.bbox))]
    def nearest(self, bbox, limit=1):
        """Return an iterator over the nearest N=limit Items to the bbox"""
        for hit in self.fwd.nearest(bbox, limit, True):
            yield self.bwd[(hit.id, tuple(hit.bbox))]
    def index_item(self, itemid, bbox, item):
        """Add an Item to the index"""
        if (itemid, bbox) in self.bwd:
            self.unindex_item(itemid, bbox)
        self.fwd.add(itemid, bbox)
        self.bwd[(itemid, bbox)] = item
    def unindex_item(self, itemid, bbox):
        """Remove an Item from the index"""
        value = self.bwd.get((itemid, bbox))
        if value is None:
            return
        del self.bwd[(itemid, bbox)]
        self.fwd.delete(itemid, bbox)