PostGIS  2.5.2dev-r@@SVN_REVISION@@

◆ circ_tree_new()

CIRC_NODE* circ_tree_new ( const POINTARRAY pa)

Build a tree of nodes from a point array, one node per edge.

Definition at line 355 of file lwgeodetic_tree.c.

References circ_node_leaf_new(), circ_node_leaf_point_new(), circ_nodes_merge(), lwalloc(), lwfree(), and POINTARRAY::npoints.

Referenced by lwline_calculate_circ_tree(), lwpoint_calculate_circ_tree(), lwpoly_calculate_circ_tree(), test_tree_circ_create(), test_tree_circ_pip(), and test_tree_circ_pip2().

356 {
357  int num_edges;
358  int i, j;
359  CIRC_NODE **nodes;
360  CIRC_NODE *node;
361  CIRC_NODE *tree;
362 
363  /* Can't do anything with no points */
364  if ( pa->npoints < 1 )
365  return NULL;
366 
367  /* Special handling for a single point */
368  if ( pa->npoints == 1 )
369  return circ_node_leaf_point_new(pa);
370 
371  /* First create a flat list of nodes, one per edge. */
372  num_edges = pa->npoints - 1;
373  nodes = lwalloc(sizeof(CIRC_NODE*) * pa->npoints);
374  j = 0;
375  for ( i = 0; i < num_edges; i++ )
376  {
377  node = circ_node_leaf_new(pa, i);
378  if ( node ) /* Not zero length? */
379  nodes[j++] = node;
380  }
381 
382  /* Special case: only zero-length edges. Make a point node. */
383  if ( j == 0 ) {
384  lwfree(nodes);
385  return circ_node_leaf_point_new(pa);
386  }
387 
388  /* Merge the node list pairwise up into a tree */
389  tree = circ_nodes_merge(nodes, j);
390 
391  /* Free the old list structure, leaving the tree in place */
392  lwfree(nodes);
393 
394  return tree;
395 }
Note that p1 and p2 are pointers into an independent POINTARRAY, do not free them.
void lwfree(void *mem)
Definition: lwutil.c:244
static CIRC_NODE * circ_node_leaf_new(const POINTARRAY *pa, int i)
Create a new leaf node, storing pointers back to the end points for later.
static CIRC_NODE * circ_nodes_merge(CIRC_NODE **nodes, int num_nodes)
static CIRC_NODE * circ_node_leaf_point_new(const POINTARRAY *pa)
Return a point node (zero radius, referencing one point)
void * lwalloc(size_t size)
Definition: lwutil.c:229
CIRC_NODE * node
uint32_t npoints
Definition: liblwgeom.h:373
Here is the call graph for this function:
Here is the caller graph for this function: