PostGIS  2.5.0dev-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 218 of file lwgeom_rtree.c.

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

Referenced by RTreeBuilder().

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

Here is the call graph for this function:

Here is the caller graph for this function: