PostGIS  2.1.10dev-r@@SVN_REVISION@@
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 151 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().

152 {
153  int num_edges, num_children, num_parents;
154  int i, j;
155  RECT_NODE **nodes;
156  RECT_NODE *node;
157  RECT_NODE *tree;
158 
159  if ( pa->npoints < 2 )
160  {
161  return NULL;
162  }
163 
164  /*
165  ** First create a flat list of nodes, one per edge.
166  ** For each vertex, transform into our one-dimensional measure.
167  ** Hopefully, when projected, the points turn into a fairly
168  ** uniformly distributed collection of measures.
169  */
170  num_edges = pa->npoints - 1;
171  nodes = lwalloc(sizeof(RECT_NODE*) * pa->npoints);
172  j = 0;
173  for ( i = 0; i < num_edges; i++ )
174  {
175  node = rect_node_leaf_new(pa, i);
176  if ( node ) /* Not zero length? */
177  {
178  nodes[j] = node;
179  j++;
180  }
181  }
182 
183  /*
184  ** If we sort the nodelist first, we'll get a more balanced tree
185  ** in the end, but at the cost of sorting. For now, we just
186  ** build the tree knowing that point arrays tend to have a
187  ** reasonable amount of sorting already.
188  */
189 
190  num_children = j;
191  num_parents = num_children / 2;
192  while ( num_parents > 0 )
193  {
194  j = 0;
195  while ( j < num_parents )
196  {
197  /*
198  ** Each new parent includes pointers to the children, so even though
199  ** we are over-writing their place in the list, we still have references
200  ** to them via the tree.
201  */
202  nodes[j] = rect_node_internal_new(nodes[2*j], nodes[(2*j)+1]);
203  j++;
204  }
205  /* Odd number of children, just copy the last node up a level */
206  if ( num_children % 2 )
207  {
208  nodes[j] = nodes[num_children - 1];
209  num_parents++;
210  }
211  num_children = num_parents;
212  num_parents = num_children / 2;
213  }
214 
215  /* Take a reference to the head of the tree*/
216  tree = nodes[0];
217 
218  /* Free the old list structure, leaving the tree in place */
219  lwfree(nodes);
220 
221  return tree;
222 
223 }
void lwfree(void *mem)
Definition: lwutil.c:190
int npoints
Definition: liblwgeom.h:327
Note that p1 and p2 are pointers into an independent POINTARRAY, do not free them.
Definition: lwtree.h:4
RECT_NODE * rect_node_leaf_new(const POINTARRAY *pa, int i)
Create a new leaf node, calculating a measure value for each point on the edge and storing pointers b...
Definition: lwtree.c:104
void * lwalloc(size_t size)
Definition: lwutil.c:175
RECT_NODE * rect_node_internal_new(RECT_NODE *left_node, RECT_NODE *right_node)
Create a new internal node, calculating the new measure range for the node, and storing pointers to t...
Definition: lwtree.c:132

Here is the call graph for this function:

Here is the caller graph for this function: