Changeset 410

Timestamp:

10/23/06 19:23:13 (2 years ago)

Author:

sgillies

Message:

add methods to prune empty nodes from trees and dump the tree out to a nested dict

Files:

• Quadtree/trunk/quadtree/_treemodule.c (modified) (4 diffs)
• Quadtree/trunk/tests/QuadTree.txt (modified) (2 diffs)
• Quadtree/trunk/tests/benchmarks.py (modified) (1 diff)
• Quadtree/trunk/tests/runtests (modified) (1 diff)

Quadtree/trunk/quadtree/_treemodule.c

@@ -41 +41 @@
-Quadtree_add(Quadtree *self, PyObject *args)
-{
-
+
+
-    double min[2], max[2];
-    SHPObject *s;
@@ -49 +50 @@
-    double x[5], y[5];
-    
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    /* make shape vertices */
-    x[0] = min[0];
@@ -79 +107 @@
-}
-
+static PyObject *
+Quadtree_prune(Quadtree *self)
+{
+    SHPTreeTrimExtraNodes(self->tree);
+    Py_INCREF(Py_None);
+    return Py_None;
+}
+
+/* Tree structure */
+
+static void 
+QuadtreeNodeDump(SHPTreeNode *node, PyObject *nodelist)
+{
+    int i;
+    PyObject *g=NULL, *ids=NULL, *bounds=NULL, *children=NULL;
+
+    g = PyDict_New();
+    
+    /* Save bounds */
+    bounds = Py_BuildValue("(dddd)", 
+                node->adfBoundsMin[0], node->adfBoundsMin[1], 
+                node->adfBoundsMax[0], node->adfBoundsMax[1]); 
+    PyDict_SetItemString(g, "bounds", bounds);
+ 
+    /* Save ids */
+    ids = PyList_New(0);
+    for (i=0; i<node->nShapeCount; i++)
+    {
+        PyList_Append(ids, Py_BuildValue("i", node->panShapeIds[i]));
+    }
+    PyDict_SetItemString(g, "ids", ids);
+
+    /* Child nodes */
+    children = PyList_New(0);
+    for (i=0; i<node->nSubNodes; i++)
+    {
+        if (node->apsSubNode[i] != NULL)
+            QuadtreeNodeDump(node->apsSubNode[i], children);
+    }
+    PyDict_SetItemString(g, "nodes", children);
+    
+    /* Add g to the node list */
+    PyList_Append(nodelist, g);
+}
+
+static PyObject *
+Quadtree_struct(Quadtree *self)
+{
+    PyObject *nodes=NULL;
+    nodes = PyList_New(0);
+    QuadtreeNodeDump(self->tree->psRoot, nodes);
+    return PyList_GetItem(nodes, 0);
+}
-
-static PyObject *
@@ -104 +185 @@
-static PyMethodDef module_methods[] = {
-    {"add", (PyCFunction)Quadtree_add, METH_VARARGS, "Add an item to an index, specifying an integer id and a bounding box"},
+    {"prune", (PyCFunction)Quadtree_prune, METH_NOARGS, "Remove unused nodes from the tree"},
+    {"struct", (PyCFunction)Quadtree_struct, METH_NOARGS, "Return simple graph structure of the tree"},
-    {"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."},
-    {NULL}

Quadtree/trunk/tests/QuadTree.txt

@@ -7 +7 @@
-    >>> index = Quadtree((-180, -90, 180, 90), maxdepth=16)
-
-3 items
+4 items, the last one a point
-
-    >>> index.add(0, [-106, 39, -105, 40])
-    >>> index.add(1, (-100, 25, -95, 30))
-    >>> index.add(2, (40, 50, 45, 55))
+    >>> index.add(3, (-105, 33))
+
+Prune
+
+    >>> index.prune()
-
-Find likely items
-
-    >>> [n for n in index.likely_intersection([-110, 30, -100, 45])]
-
+, 3
-    >>> [n for n in index.likely_intersection([10, 40, 40.05, 60])]
-    [2]
@@ -26 +31 @@
-    >>> [n for n in index.likely_intersection([-110, 35, -108, 45])]
-    [0]
+   
+Tree structure
+
+    >>> tree = index.struct()
-    
+Visualize
+
+    >>> from quadtree.viz import render_graph
+    >>> render_graph(tree, 'quadtree.png')
+    
+

Quadtree/trunk/tests/benchmarks.py

@@ -18 +18 @@
-
-# Scatter points randomly in a 1x1 box
-1
-[-180, -90, 180, 90]
+50
+(-180, -90, 180, 90)
-points = []
-index = Quadtree(index_extent)
-for i in xrange(count):
-random.random(
-random.random(
+360.0*(random.random()-0.5
+180.0*(random.random()-0.5
-    points.append(Point(x, y))
-[x, y, x, y]
+(x, y)
-
-[0.2, 0.3, 0.3, 0.4]
+(0.0, 50.0, 5.0, 55.0)
-
-print count, "points"

Quadtree/trunk/tests/runtests

@@ -1 +1 @@
-#!/bin/sh
-
+PCL-trunk/
-