PostGIS  2.2.7dev-r@@SVN_REVISION@@
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 204 of file lwgeom_rtree.c.

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

Referenced by RTreeBuilder().

205 {
206  RTREE_NODE* root;
207  RTREE_NODE** nodes = lwalloc(pointArray->npoints * sizeof(RTREE_NODE*));
208  int i, nodeCount;
209  int childNodes, parentNodes;
210 
211  POSTGIS_DEBUGF(2, "RTreeCreate called with pointarray %p", pointArray);
212 
213  nodeCount = pointArray->npoints - 1;
214 
215  POSTGIS_DEBUGF(3, "Total leaf nodes: %d", nodeCount);
216 
217  /*
218  * Create a leaf node for every line segment.
219  */
220  for (i = 0; i < nodeCount; i++)
221  {
222  nodes[i] = RTreeCreateLeafNode(pointArray, i);
223  }
224 
225  /*
226  * Next we group nodes by pairs. If there's an odd number of nodes,
227  * we bring the last node up a level as is. Continue until we have
228  * a single top node.
229  */
230  childNodes = nodeCount;
231  parentNodes = nodeCount / 2;
232  while (parentNodes > 0)
233  {
234  POSTGIS_DEBUGF(3, "Merging %d children into %d parents.", childNodes, parentNodes);
235 
236  i = 0;
237  while (i < parentNodes)
238  {
239  nodes[i] = RTreeCreateInteriorNode(nodes[i*2], nodes[i*2+1]);
240  i++;
241  }
242  /*
243  * Check for an odd numbered final node.
244  */
245  if (parentNodes * 2 < childNodes)
246  {
247  POSTGIS_DEBUGF(3, "Shuffling child %d to parent %d", childNodes - 1, i);
248 
249  nodes[i] = nodes[childNodes - 1];
250  parentNodes++;
251  }
252  childNodes = parentNodes;
253  parentNodes = parentNodes / 2;
254  }
255 
256  root = nodes[0];
257  lwfree(nodes);
258  POSTGIS_DEBUGF(3, "RTreeCreate returning %p", root);
259 
260  return root;
261 }
void lwfree(void *mem)
Definition: lwutil.c:214
int npoints
Definition: liblwgeom.h:355
The following struct and methods are used for a 1D RTree implementation, described at: http://lin-ear...
Definition: lwgeom_rtree.h:21
static RTREE_NODE * RTreeCreateInteriorNode(RTREE_NODE *left, RTREE_NODE *right)
Creates an interior node given the children.
Definition: lwgeom_rtree.c:134
static RTREE_NODE * RTreeCreateLeafNode(POINTARRAY *pa, int startPoint)
Creates a leaf node given the pointer to the start point of the segment.
Definition: lwgeom_rtree.c:155
void * lwalloc(size_t size)
Definition: lwutil.c:199

Here is the call graph for this function:

Here is the caller graph for this function: