PostGIS  2.1.10dev-r@@SVN_REVISION@@
lwtree.c
Go to the documentation of this file.
1 #include "liblwgeom_internal.h"
2 #include "lwgeom_log.h"
3 #include "lwtree.h"
4 
5 
9 static int rect_node_is_leaf(const RECT_NODE *node)
10 {
11  return (node->p1 != NULL);
12 }
13 
19 {
20  if ( node->left_node )
21  {
23  node->left_node = 0;
24  }
25  if ( node->right_node )
26  {
28  node->right_node = 0;
29  }
30  lwfree(node);
31 }
32 
33 /* 0 => no containment */
34 int rect_tree_contains_point(const RECT_NODE *node, const POINT2D *pt, int *on_boundary)
35 {
36  if ( FP_CONTAINS_INCL(node->ymin, pt->y, node->ymax) )
37  {
38  if ( rect_node_is_leaf(node) )
39  {
40  double side = lw_segment_side(node->p1, node->p2, pt);
41  if ( side == 0 )
42  *on_boundary = LW_TRUE;
43  return (side < 0 ? -1 : 1 );
44  }
45  else
46  {
47  return rect_tree_contains_point(node->left_node, pt, on_boundary) +
48  rect_tree_contains_point(node->right_node, pt, on_boundary);
49  }
50  }
51  /* printf("NOT in measure range\n"); */
52  return 0;
53 }
54 
56 {
57  LWDEBUGF(4,"n1 (%.9g %.9g,%.9g %.9g) vs n2 (%.9g %.9g,%.9g %.9g)",n1->xmin,n1->ymin,n1->xmax,n1->ymax,n2->xmin,n2->ymin,n2->xmax,n2->ymax);
58  /* There can only be an edge intersection if the rectangles overlap */
59  if ( ! ( FP_GT(n1->xmin, n2->xmax) || FP_GT(n2->xmin, n1->xmax) || FP_GT(n1->ymin, n2->ymax) || FP_GT(n2->ymin, n1->ymax) ) )
60  {
61  LWDEBUG(4," interaction found");
62  /* We can only test for a true intersection if the nodes are both leaf nodes */
63  if ( rect_node_is_leaf(n1) && rect_node_is_leaf(n2) )
64  {
65  LWDEBUG(4," leaf node test");
66  /* Check for true intersection */
67  if ( lw_segment_intersects(n1->p1, n1->p2, n2->p1, n2->p2) )
68  return LW_TRUE;
69  else
70  return LW_FALSE;
71  }
72  else
73  {
74  LWDEBUG(4," internal node found, recursing");
75  /* Recurse to children */
76  if ( rect_node_is_leaf(n1) )
77  {
79  return LW_TRUE;
80  else
81  return LW_FALSE;
82  }
83  else
84  {
86  return LW_TRUE;
87  else
88  return LW_FALSE;
89  }
90  }
91  }
92  else
93  {
94  LWDEBUG(4," no interaction found");
95  return LW_FALSE;
96  }
97 }
98 
99 
105 {
106  POINT2D *p1, *p2;
107  RECT_NODE *node;
108 
109  p1 = (POINT2D*)getPoint_internal(pa, i);
110  p2 = (POINT2D*)getPoint_internal(pa, i+1);
111 
112  /* Zero length edge, doesn't get a node */
113  if ( FP_EQUALS(p1->x, p2->x) && FP_EQUALS(p1->y, p2->y) )
114  return NULL;
115 
116  node = lwalloc(sizeof(RECT_NODE));
117  node->p1 = p1;
118  node->p2 = p2;
119  node->xmin = FP_MIN(p1->x,p2->x);
120  node->xmax = FP_MAX(p1->x,p2->x);
121  node->ymin = FP_MIN(p1->y,p2->y);
122  node->ymax = FP_MAX(p1->y,p2->y);
123  node->left_node = NULL;
124  node->right_node = NULL;
125  return node;
126 }
127 
133 {
134  RECT_NODE *node = lwalloc(sizeof(RECT_NODE));
135  node->p1 = NULL;
136  node->p2 = NULL;
137  node->xmin = FP_MIN(left_node->xmin, right_node->xmin);
138  node->xmax = FP_MAX(left_node->xmax, right_node->xmax);
139  node->ymin = FP_MIN(left_node->ymin, right_node->ymin);
140  node->ymax = FP_MAX(left_node->ymax, right_node->ymax);
141  node->left_node = left_node;
142  node->right_node = right_node;
143  return node;
144 }
145 
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 }
224 
struct rect_node * right_node
Definition: lwtree.h:11
void lwfree(void *mem)
Definition: lwutil.c:190
int npoints
Definition: liblwgeom.h:327
POINT2D * p1
Definition: lwtree.h:12
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
#define FP_MIN(A, B)
#define FP_CONTAINS_INCL(A, X, B)
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 rang...
Definition: lwtree.c:151
POINT2D * p2
Definition: lwtree.h:13
double xmax
Definition: lwtree.h:7
static int rect_node_is_leaf(const RECT_NODE *node)
Internal nodes have their point references set to NULL.
Definition: lwtree.c:9
double x
Definition: liblwgeom.h:284
int rect_tree_contains_point(const RECT_NODE *node, const POINT2D *pt, int *on_boundary)
Definition: lwtree.c:34
#define LW_FALSE
Definition: liblwgeom.h:52
#define FP_GT(A, B)
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:51
uint8_t * getPoint_internal(const POINTARRAY *pa, int n)
Definition: ptarray.c:1645
double ymax
Definition: lwtree.h:9
double y
Definition: liblwgeom.h:284
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
double xmin
Definition: lwtree.h:6
double ymin
Definition: lwtree.h:8
int rect_tree_intersects_tree(const RECT_NODE *n1, const RECT_NODE *n2)
Definition: lwtree.c:55
#define FP_EQUALS(A, B)
void rect_tree_free(RECT_NODE *node)
Recurse from top of node tree and free all children.
Definition: lwtree.c:18
void * lwalloc(size_t size)
Definition: lwutil.c:175
int lw_segment_side(const POINT2D *p1, const POINT2D *p2, const POINT2D *q)
lw_segment_side()
Definition: lwalgorithm.c:62
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55
struct rect_node * left_node
Definition: lwtree.h:10
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
#define FP_MAX(A, B)
int lw_segment_intersects(const POINT2D *p1, const POINT2D *p2, const POINT2D *q1, const POINT2D *q2)
returns the kind of CG_SEGMENT_INTERSECTION_TYPE behavior of lineseg 1 (constructed from p1 and p2) a...
Definition: lwalgorithm.c:372