source: TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/quadtree/_treemodule.c @ 2194

Subversion URL: http://proj.badc.rl.ac.uk/svn/ndg/TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/quadtree/_treemodule.c@2194
Revision 2194, 7.1 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
2#include "Python.h"
3#include "shapefil.h"
4
5typedef struct {
6    PyObject_HEAD
7    SHPTree *tree;
8} Quadtree;
9
10staticforward PyTypeObject QuadtreeType;
11
12/* Alloc/dealloc */
13
14static void
15Quadtree_dealloc(Quadtree *self)
16{
17    if (self->tree)
18        SHPDestroyTree(self->tree);
19    self->tree = NULL;
20    self->ob_type->tp_free((PyObject*) self);
21}
22
23static int
24Quadtree_init(Quadtree *self, PyObject *args, PyObject *kwds)
25{
26    int d=16;
27    double min[2], max[2];
28       
29    if (!PyArg_ParseTuple(args, "(dddd)|i", &min[0], &min[1], &max[0], &max[1],
30                          &d)
31        )
32        return -1;
33    self->tree = SHPCreateTree(NULL, 2, d, min, max);
34    if (!self->tree) return -1;
35    return 0;
36}
37
38/* Methods */
39
40static PyObject *
41Quadtree_add(Quadtree *self, PyObject *args)
42{
43    int n, size;
44    PyObject *bounds=NULL;
45    double min[2], max[2];
46    SHPObject *s;
47
48    /* our shapes are boxes, single rings */
49    int part_start[1] = {0};
50    double x[5], y[5];
51   
52    if (!PyArg_ParseTuple(args, "iO", &n, &bounds))
53        return NULL;
54
55    /* Check length of the bounds argument */
56    if (!PySequence_Check(bounds))
57    {
58        PyErr_SetString(PyExc_TypeError, "Bounds must be a sequence");
59        return NULL;
60    }
61
62    size = (int) PySequence_Size(bounds);
63    if (size == 2)
64    {
65        min[0] = max[0] = PyFloat_AsDouble(PySequence_ITEM(bounds, 0));
66        min[1] = max[1] = PyFloat_AsDouble(PySequence_ITEM(bounds, 1));
67    }
68    else if (size == 4)
69    {
70        min[0] = PyFloat_AsDouble(PySequence_ITEM(bounds, 0));
71        min[1] = PyFloat_AsDouble(PySequence_ITEM(bounds, 1));
72        max[0] = PyFloat_AsDouble(PySequence_ITEM(bounds, 2));
73        max[1] = PyFloat_AsDouble(PySequence_ITEM(bounds, 3));
74    }
75    else
76    {
77        PyErr_Format(PyExc_TypeError,
78            "Bounds argument must be sequence of length 2 or 4, not %d",
79            size);
80        return NULL;
81    }
82   
83    /* make shape vertices */
84    x[0] = min[0];
85    x[1] = min[0];
86    x[2] = max[0];
87    x[3] = max[0];
88    x[4] = min[0];
89   
90    y[0] = min[1];
91    y[1] = max[1];
92    y[2] = max[1];
93    y[3] = min[1];
94    y[4] = min[1];
95   
96    s = (SHPObject *) SHPCreateObject(5, n, 1, part_start, NULL, 5,
97                                      x, y, NULL, NULL);
98    if (!SHPTreeAddShapeId(self->tree, s))
99    {
100        PyErr_SetString(PyExc_Exception, "Failed to index item");
101        return NULL;
102    }
103    SHPDestroyObject(s);
104   
105    Py_INCREF(Py_None);
106    return Py_None;
107}
108
109static PyObject *
110Quadtree_prune(Quadtree *self)
111{
112    SHPTreeTrimExtraNodes(self->tree);
113    Py_INCREF(Py_None);
114    return Py_None;
115}
116
117/* Tree structure */
118
119static void 
120QuadtreeNodeDump(SHPTreeNode *node, PyObject *nodelist)
121{
122    int i;
123    PyObject *g=NULL, *ids=NULL, *bounds=NULL, *children=NULL;
124
125    g = PyDict_New();
126   
127    /* Save bounds */
128    bounds = Py_BuildValue("(dddd)", 
129                node->adfBoundsMin[0], node->adfBoundsMin[1], 
130                node->adfBoundsMax[0], node->adfBoundsMax[1]); 
131    PyDict_SetItemString(g, "bounds", bounds);
132 
133    /* Save ids */
134    ids = PyList_New(0);
135    for (i=0; i<node->nShapeCount; i++)
136    {
137        PyList_Append(ids, Py_BuildValue("i", node->panShapeIds[i]));
138    }
139    PyDict_SetItemString(g, "ids", ids);
140
141    /* Child nodes */
142    children = PyList_New(0);
143    for (i=0; i<node->nSubNodes; i++)
144    {
145        if (node->apsSubNode[i] != NULL)
146            QuadtreeNodeDump(node->apsSubNode[i], children);
147    }
148    PyDict_SetItemString(g, "nodes", children);
149   
150    /* Add g to the node list */
151    PyList_Append(nodelist, g);
152}
153
154static PyObject *
155Quadtree_struct(Quadtree *self)
156{
157    PyObject *nodes=NULL;
158    nodes = PyList_New(0);
159    QuadtreeNodeDump(self->tree->psRoot, nodes);
160    return PyList_GetItem(nodes, 0);
161}
162
163static PyObject *
164Quadtree_intersection(Quadtree *self, PyObject *args)
165{
166    int *hits, count=0, i;
167    double min[2], max[2];
168    PyObject *list;
169
170    if (!PyArg_ParseTuple(args, "(dddd)", &min[0], &min[1], &max[0], &max[1]))
171        return NULL;
172
173    hits = SHPTreeFindLikelyShapes(self->tree, min, max, &count);
174    list = PyList_New((size_t)count);
175    for (i=0; i<count; i++)
176    {
177        PyList_SET_ITEM(list, (size_t)i, Py_BuildValue("i", hits[i]));
178    }
179   
180    return PySeqIter_New(list);
181}
182
183/* Define Methods */
184
185static PyMethodDef module_methods[] = {
186    {"add", (PyCFunction)Quadtree_add, METH_VARARGS, "Add an item to an index, specifying an integer id and a bounding box"},
187    {"prune", (PyCFunction)Quadtree_prune, METH_NOARGS, "Remove unused nodes from the tree"},
188    {"struct", (PyCFunction)Quadtree_struct, METH_NOARGS, "Return simple graph structure of the tree"},
189    {"likely_intersection", (PyCFunction)Quadtree_intersection, METH_VARARGS, "Return an iterator over integer ids of items that are likely to intersect with the specified bounding box."},
190    {NULL}
191};
192
193/* Define Type */
194
195static PyTypeObject QuadtreeType = {
196    PyObject_HEAD_INIT(NULL)
197    0,                              /*ob_size*/
198    "Quadtree",                     /*tp_name*/
199    sizeof(Quadtree),               /*tp_basicsize*/
200    0,                              /*tp_itemsize*/
201    (destructor)Quadtree_dealloc,   /*tp_dealloc*/
202    0,                              /*tp_print*/
203    0,                              /*tp_getattr*/
204    0,                              /*tp_setattr*/
205    0,                              /*tp_compare*/
206    0,                              /*tp_repr*/
207    0,                              /*tp_as_number*/
208    0,                              /*tp_as_sequence*/
209    0,                              /*tp_as_mapping*/
210    0,                              /*tp_hash */
211    0,                              /*tp_call*/
212    0,                              /*tp_str*/
213    0,                              /*tp_getattro*/
214    0,                              /*tp_setattro*/
215    0,                              /*tp_as_buffer*/
216    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
217    "Quadtree spatial index",       /* tp_doc */
218    0,                         /* tp_traverse */
219    0,                         /* tp_clear */
220    0,                         /* tp_richcompare */
221    0,                         /* tp_weaklistoffset */
222    0,                         /* tp_iter */
223    0,                         /* tp_iternext */
224    module_methods,             /* tp_methods */
225    0,                         /* tp_members */
226    0,                         /* tp_getset */
227    0,                         /* tp_base */
228    0,                         /* tp_dict */
229    0,                         /* tp_descr_get */
230    0,                         /* tp_descr_set */
231    0,                         /* tp_dictoffset */
232    (initproc)Quadtree_init,   /* tp_init */
233    0,                         /* tp_alloc */
234    PyType_GenericNew,         /* tp_new */
235};
236
237/* Initialization */
238
239#ifndef PyMODINIT_FUNC  /* declarations for DLL import/export */
240#define PyMODINIT_FUNC void
241#endif
242PyMODINIT_FUNC
243init_tree(void) 
244{
245    PyObject* m;
246    if (PyType_Ready(&QuadtreeType) < 0)
247        return;
248    m = Py_InitModule3("_tree", module_methods,
249                       "Quadtree spatial index.");
250    if (m == NULL)
251      return;
252
253    Py_INCREF(&QuadtreeType);
254    PyModule_AddObject(m, "Quadtree", (PyObject *)&QuadtreeType);
255
256}
257
Note: See TracBrowser for help on using the repository browser.