rect_tree_new()

RECT_NODE* rect_tree_new

(

const POINTARRAY *

pa

)

Build a tree of nodes from a point array, one node per edge, and each with an associated measure range along a one-dimensional space.

We can then search that space as a range tree.

Definition at line 175 of file lwtree.c.

References lwalloc(), lwfree(), POINTARRAY::npoints, rect_node_internal_new(), and rect_node_leaf_new().

Referenced by test_rect_tree_contains_point(), and test_rect_tree_intersects_tree().

{
        int num_edges, num_children, num_parents;
        int i, j;
        RECT_NODE **nodes;
        RECT_NODE *node;
        RECT_NODE *tree;

        if ( pa->npoints < 2 )
        {
                return NULL;
        }

        /*
        ** First create a flat list of nodes, one per edge.
        ** For each vertex, transform into our one-dimensional measure.
        ** Hopefully, when projected, the points turn into a fairly
        ** uniformly distributed collection of measures.
        */
        num_edges = pa->npoints - 1;
        nodes = lwalloc(sizeof(RECT_NODE*) * pa->npoints);
        j = 0;
        for ( i = 0; i < num_edges; i++ )
        {
                node = rect_node_leaf_new(pa, i);
                if ( node ) /* Not zero length? */
                {
                        nodes[j] = node;
                        j++;
                }
        }

        /*
        ** If we sort the nodelist first, we'll get a more balanced tree
        ** in the end, but at the cost of sorting. For now, we just
        ** build the tree knowing that point arrays tend to have a
        ** reasonable amount of sorting already.
        */

        num_children = j;
        num_parents = num_children / 2;
        while ( num_parents > 0 )
        {
                j = 0;
                while ( j < num_parents )
                {
                        /*
                        ** Each new parent includes pointers to the children, so even though
                        ** we are over-writing their place in the list, we still have references
                        ** to them via the tree.
                        */
                        nodes[j] = rect_node_internal_new(nodes[2*j], nodes[(2*j)+1]);
                        j++;
                }
                /* Odd number of children, just copy the last node up a level */
                if ( num_children % 2 )
                {
                        nodes[j] = nodes[num_children - 1];
                        num_parents++;
                }
                num_children = num_parents;
                num_parents = num_children / 2;
        }

        /* Take a reference to the head of the tree*/
        tree = nodes[0];

        /* Free the old list structure, leaving the tree in place */
        lwfree(nodes);

        return tree;

}

Here is the call graph for this function:

Here is the caller graph for this function: