PostGIS  2.3.7dev-r@@SVN_REVISION@@
lwtree.c
Go to the documentation of this file.
1 /**********************************************************************
2  *
3  * PostGIS - Spatial Types for PostgreSQL
4  * http://postgis.net
5  *
6  * PostGIS is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * PostGIS is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with PostGIS. If not, see <http://www.gnu.org/licenses/>.
18  *
19  **********************************************************************
20  *
21  * Copyright (C) 2009-2012 Paul Ramsey <pramsey@cleverelephant.ca>
22  *
23  **********************************************************************/
24 
25 #include "liblwgeom_internal.h"
26 #include "lwgeom_log.h"
27 #include "lwtree.h"
28 
29 
33 static int rect_node_is_leaf(const RECT_NODE *node)
34 {
35  return (node->p1 != NULL);
36 }
37 
43 {
44  if ( node->left_node )
45  {
47  node->left_node = 0;
48  }
49  if ( node->right_node )
50  {
52  node->right_node = 0;
53  }
54  lwfree(node);
55 }
56 
57 /* 0 => no containment */
58 int rect_tree_contains_point(const RECT_NODE *node, const POINT2D *pt, int *on_boundary)
59 {
60  if ( FP_CONTAINS_INCL(node->ymin, pt->y, node->ymax) )
61  {
62  if ( rect_node_is_leaf(node) )
63  {
64  double side = lw_segment_side(node->p1, node->p2, pt);
65  if ( side == 0 )
66  *on_boundary = LW_TRUE;
67  return (side < 0 ? -1 : 1 );
68  }
69  else
70  {
71  return rect_tree_contains_point(node->left_node, pt, on_boundary) +
72  rect_tree_contains_point(node->right_node, pt, on_boundary);
73  }
74  }
75  /* printf("NOT in measure range\n"); */
76  return 0;
77 }
78 
80 {
81  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);
82  /* There can only be an edge intersection if the rectangles overlap */
83  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) ) )
84  {
85  LWDEBUG(4," interaction found");
86  /* We can only test for a true intersection if the nodes are both leaf nodes */
87  if ( rect_node_is_leaf(n1) && rect_node_is_leaf(n2) )
88  {
89  LWDEBUG(4," leaf node test");
90  /* Check for true intersection */
91  if ( lw_segment_intersects(n1->p1, n1->p2, n2->p1, n2->p2) )
92  return LW_TRUE;
93  else
94  return LW_FALSE;
95  }
96  else
97  {
98  LWDEBUG(4," internal node found, recursing");
99  /* Recurse to children */
100  if ( rect_node_is_leaf(n1) )
101  {
103  return LW_TRUE;
104  else
105  return LW_FALSE;
106  }
107  else
108  {
110  return LW_TRUE;
111  else
112  return LW_FALSE;
113  }
114  }
115  }
116  else
117  {
118  LWDEBUG(4," no interaction found");
119  return LW_FALSE;
120  }
121 }
122 
123 
129 {
130  POINT2D *p1, *p2;
131  RECT_NODE *node;
132 
133  p1 = (POINT2D*)getPoint_internal(pa, i);
134  p2 = (POINT2D*)getPoint_internal(pa, i+1);
135 
136  /* Zero length edge, doesn't get a node */
137  if ( FP_EQUALS(p1->x, p2->x) && FP_EQUALS(p1->y, p2->y) )
138  return NULL;
139 
140  node = lwalloc(sizeof(RECT_NODE));
141  node->p1 = p1;
142  node->p2 = p2;
143  node->xmin = FP_MIN(p1->x,p2->x);
144  node->xmax = FP_MAX(p1->x,p2->x);
145  node->ymin = FP_MIN(p1->y,p2->y);
146  node->ymax = FP_MAX(p1->y,p2->y);
147  node->left_node = NULL;
148  node->right_node = NULL;
149  return node;
150 }
151 
157 {
158  RECT_NODE *node = lwalloc(sizeof(RECT_NODE));
159  node->p1 = NULL;
160  node->p2 = NULL;
161  node->xmin = FP_MIN(left_node->xmin, right_node->xmin);
162  node->xmax = FP_MAX(left_node->xmax, right_node->xmax);
163  node->ymin = FP_MIN(left_node->ymin, right_node->ymin);
164  node->ymax = FP_MAX(left_node->ymax, right_node->ymax);
165  node->left_node = left_node;
166  node->right_node = right_node;
167  return node;
168 }
169 
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 }
248 
struct rect_node * right_node
Definition: lwtree.h:32
void lwfree(void *mem)
Definition: lwutil.c:242
int npoints
Definition: liblwgeom.h:370
POINT2D * p1
Definition: lwtree.h:33
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
#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:175
POINT2D * p2
Definition: lwtree.h:34
double xmax
Definition: lwtree.h:28
static int rect_node_is_leaf(const RECT_NODE *node)
Internal nodes have their point references set to NULL.
Definition: lwtree.c:33
double x
Definition: liblwgeom.h:327
int rect_tree_contains_point(const RECT_NODE *node, const POINT2D *pt, int *on_boundary)
Definition: lwtree.c:58
#define LW_FALSE
Definition: liblwgeom.h:76
#define FP_GT(A, B)
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
uint8_t * getPoint_internal(const POINTARRAY *pa, int n)
Definition: ptarray.c:1706
double ymax
Definition: lwtree.h:30
double y
Definition: liblwgeom.h:327
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
double xmin
Definition: lwtree.h:27
double ymin
Definition: lwtree.h:29
int rect_tree_intersects_tree(const RECT_NODE *n1, const RECT_NODE *n2)
Definition: lwtree.c:79
#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:42
void * lwalloc(size_t size)
Definition: lwutil.c:227
int lw_segment_side(const POINT2D *p1, const POINT2D *p2, const POINT2D *q)
lw_segment_side()
Definition: lwalgorithm.c:64
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
struct rect_node * left_node
Definition: lwtree.h:31
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
#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:371