source: TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/README.txt @ 2194

Subversion URL: http://proj.badc.rl.ac.uk/svn/ndg/TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/README.txt@2194
Revision 2194, 2.2 KB checked in by lawrence, 13 years ago (diff)

Adding various specs and 3rd party code of interest for the CSML
services development.

Line 
1
2Quadtree: spatial index for Python GIS
3======================================
4
5Whether for Python in-memory feature stores, Plone content, or whatever -- we
6need a simple spatial index to speed up the search for objects that intersect
7with a given spatial bounding box.
8
9The 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
11MapServer applications for years. The quadtree itself is completely separable
12from any shapefile. We can use it with arbitrary Python object collections.
13
14
15Quadtree Protocol
16-----------------
17
18In a nutshell:
19
20  >>> index.add(id=id, bounds=(left, bottom, right, top))
21  >>> [n for n in index.likely_intersection((left, bottom, right, top))]
22  [id]
23
24This resembles a subset of the set protocol, and is all we need to begin.
25*add* indexes a new object by id, *likely_intersection* returns an iterator
26over ids where the node containing the id intersects with the specified
27bounding box. This method can produce false positives. It is up to the
28application to handle such false positive index hits and to map ids to objects.
29
30
31Installation
32------------
33
34$ python setup.py install
35
36This installs an egg. If you'd rather stick with the old-school distributions,
37use
38
39$ python setup.py install --root / --single-version-externally-managed
40
41
42Usage
43-----
44
45See tests/QuadTree.txt.
46
47
48Performance
49-----------
50
51Even with the false positives, Quadtree wins over brute force intersection
52evaluations implemented in Python once you have more than ~20 points. See the
53tests/benchmarks.py file for a comparison.
54
55
56Support
57-------
58
59For current information about this project, see
60
61http://icon.stoa.org/trac/pleiades/wiki/QuadTree
62
63If you have questions, please consider joining our software support list:
64
65http://icon.stoa.org/trac/pleiades/wiki/PleiadesSoftwareList
66
67
68About Pleiades
69--------------
70
71Pleiades is an international research network and associated web portal and
72content management system devoted to the study of ancient geography.
73
74See http://icon.stoa.org/trac/pleiades/wiki.
75
76Funding for the creation of this software was provided by a grant from the
77U.S. National Endowment for the Humanities (http://www.neh.gov).
78
Note: See TracBrowser for help on using the repository browser.