PostGIS  2.3.8dev-r@@SVN_REVISION@@

◆ 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().

176 {
177  int num_edges, num_children, num_parents;
178  int i, j;
179  RECT_NODE **nodes;
180  RECT_NODE *node;
181  RECT_NODE *tree;
182 
183  if ( pa->npoints < 2 )
184  {
185  return NULL;
186  }
187 
188  /*
189  ** First create a flat list of nodes, one per edge.
190  ** For each vertex, transform into our one-dimensional measure.
191  ** Hopefully, when projected, the points turn into a fairly
192  ** uniformly distributed collection of measures.
193  */
194  num_edges = pa->npoints - 1;
195  nodes = lwalloc(sizeof(RECT_NODE*) * pa->npoints);
196  j = 0;
197  for ( i = 0; i < num_edges; i++ )
198  {
199  node = rect_node_leaf_new(pa, i);
200  if ( node ) /* Not zero length? */
201  {
202  nodes[j] = node;
203  j++;
204  }
205  }
206 
207  /*
208  ** If we sort the nodelist first, we'll get a more balanced tree
209  ** in the end, but at the cost of sorting. For now, we just
210  ** build the tree knowing that point arrays tend to have a
211  ** reasonable amount of sorting already.
212  */
213 
214  num_children = j;
215  num_parents = num_children / 2;
216  while ( num_parents > 0 )
217  {
218  j = 0;
219  while ( j < num_parents )
220  {
221  /*
222  ** Each new parent includes pointers to the children, so even though
223  ** we are over-writing their place in the list, we still have references
224  ** to them via the tree.
225  */
226  nodes[j] = rect_node_internal_new(nodes[2*j], nodes[(2*j)+1]);
227  j++;
228  }
229  /* Odd number of children, just copy the last node up a level */
230  if ( num_children % 2 )
231  {
232  nodes[j] = nodes[num_children - 1];
233  num_parents++;
234  }
235  num_children = num_parents;
236  num_parents = num_children / 2;
237  }
238 
239  /* Take a reference to the head of the tree*/
240  tree = nodes[0];
241 
242  /* Free the old list structure, leaving the tree in place */
243  lwfree(nodes);
244 
245  return tree;
246 
247 }
void lwfree(void *mem)
Definition: lwutil.c:242
int npoints
Definition: liblwgeom.h:370
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:128
void * lwalloc(size_t size)
Definition: lwutil.c:227
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:156
Here is the call graph for this function:
Here is the caller graph for this function: