RTreeCreate()

static RTREE_NODE* RTreeCreate ( POINTARRAY *  pointArray )

static

Creates an rtree given a pointer to the point array.

Must copy the point array.

Definition at line 218 of file lwgeom_rtree.c.

References lwalloc(), lwfree(), POINTARRAY::npoints, RTreeCreateInteriorNode(), and RTreeCreateLeafNode().

Referenced by RTreeBuilder().

{
        RTREE_NODE* root;
        RTREE_NODE** nodes = lwalloc(pointArray->npoints * sizeof(RTREE_NODE*));
        int i, nodeCount;
        int childNodes, parentNodes;

        POSTGIS_DEBUGF(2, "RTreeCreate called with pointarray %p", pointArray);

        nodeCount = pointArray->npoints - 1;

        POSTGIS_DEBUGF(3, "Total leaf nodes: %d", nodeCount);

        /*
         * Create a leaf node for every line segment.
         */
        for (i = 0; i < nodeCount; i++)
        {
                nodes[i] = RTreeCreateLeafNode(pointArray, i);
        }

        /*
         * Next we group nodes by pairs.  If there's an odd number of nodes,
         * we bring the last node up a level as is.      Continue until we have
         * a single top node.
         */
        childNodes = nodeCount;
        parentNodes = nodeCount / 2;
        while (parentNodes > 0)
        {
                POSTGIS_DEBUGF(3, "Merging %d children into %d parents.", childNodes, parentNodes);

                i = 0;
                while (i < parentNodes)
                {
                        nodes[i] = RTreeCreateInteriorNode(nodes[i*2], nodes[i*2+1]);
                        i++;
                }
                /*
                 * Check for an odd numbered final node.
                 */
                if (parentNodes * 2 < childNodes)
                {
                        POSTGIS_DEBUGF(3, "Shuffling child %d to parent %d", childNodes - 1, i);

                        nodes[i] = nodes[childNodes - 1];
                        parentNodes++;
                }
                childNodes = parentNodes;
                parentNodes = parentNodes / 2;
        }

        root = nodes[0];
        lwfree(nodes);
        POSTGIS_DEBUGF(3, "RTreeCreate returning %p", root);

        return root;
}

Here is the call graph for this function:

Here is the caller graph for this function: