Package quadtree-py25-0.1.2-1

Quadtree: Whether for PCL in-memory feature stores, Plone content, or whatever -- we need a simple spatial index to speed up retrieval of objects that intersect with a given bounding box. The simplest, most tried-and-true, open source spatial index is shapelib's (http://shapelib.maptools.org) quadtree. It's been improving the performance of MapServer applications for years. The quadtree itself is completely separable from any shapefile. We can use it with arbitrary Python object collections. Quadtree Protocol In a nutshell: >>> index.add(id=id, bounds=[minx, miny, maxx, maxy]) >>> [n for n in index.likely_intersection(bounds=[minx, miny, maxx, maxy])] [id] This resembles a subset of the set protocol, and is all we need to begin. *add* indexes a new object by id, *likely_intersection* returns an iterator over ids where the node containing the id intersects with the specified bounding box. This method can produce false positives. It is up to the application to handle such false positive index hits and to map ids to objects.