PostGIS  2.3.7dev-r@@SVN_REVISION@@
geography_measurement_trees.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^
22  *
23  **********************************************************************/
24 
26 
27 
28 /*
29 * Specific tree types include all the generic slots and
30 * their own slots for their trees. We put the implementation
31 * for the CircTreeGeomCache here because we can't shove
32 * the PgSQL specific bits of the code (fcinfo) back into
33 * liblwgeom, where most of the circtree logic lives.
34 */
35 typedef struct {
36  int type; // <GeomCache>
39  size_t geom1_size; //
40  size_t geom2_size; //
41  int32 argnum; // </GeomCache>
44 
45 
46 
50 static int
51 CircTreeBuilder(const LWGEOM* lwgeom, GeomCache* cache)
52 {
53  CircTreeGeomCache* circ_cache = (CircTreeGeomCache*)cache;
54  CIRC_NODE* tree = lwgeom_calculate_circ_tree(lwgeom);
55 
56  if ( circ_cache->index )
57  {
58  circ_tree_free(circ_cache->index);
59  circ_cache->index = 0;
60  }
61  if ( ! tree )
62  return LW_FAILURE;
63 
64  circ_cache->index = tree;
65  return LW_SUCCESS;
66 }
67 
68 static int
69 CircTreeFreer(GeomCache* cache)
70 {
71  CircTreeGeomCache* circ_cache = (CircTreeGeomCache*)cache;
72  if ( circ_cache->index )
73  {
74  circ_tree_free(circ_cache->index);
75  circ_cache->index = 0;
76  circ_cache->argnum = 0;
77  }
78  return LW_SUCCESS;
79 }
80 
81 static GeomCache*
83 {
84  CircTreeGeomCache* cache = palloc(sizeof(CircTreeGeomCache));
85  memset(cache, 0, sizeof(CircTreeGeomCache));
86  return (GeomCache*)cache;
87 }
88 
89 static GeomCacheMethods CircTreeCacheMethods =
90 {
91  CIRC_CACHE_ENTRY,
95 };
96 
97 static CircTreeGeomCache*
98 GetCircTreeGeomCache(FunctionCallInfoData* fcinfo, const GSERIALIZED* g1, const GSERIALIZED* g2)
99 {
100  return (CircTreeGeomCache*)GetGeomCache(fcinfo, &CircTreeCacheMethods, g1, g2);
101 }
102 
103 
104 static int
105 CircTreePIP(const CIRC_NODE* tree1, const GSERIALIZED* g1, const POINT4D* in_point)
106 {
107  int tree1_type = gserialized_get_type(g1);
108  GBOX gbox1;
109  GEOGRAPHIC_POINT in_gpoint;
110  POINT3D in_point3d;
111 
112  POSTGIS_DEBUGF(3, "tree1_type=%d", tree1_type);
113 
114  /* If the tree'ed argument is a polygon, do the P-i-P using the tree-based P-i-P */
115  if ( tree1_type == POLYGONTYPE || tree1_type == MULTIPOLYGONTYPE )
116  {
117  POSTGIS_DEBUG(3, "tree is a polygon, using tree PiP");
118  /* Need a gbox to calculate an outside point */
119  if ( LW_FAILURE == gserialized_get_gbox_p(g1, &gbox1) )
120  {
121  LWGEOM* lwgeom1 = lwgeom_from_gserialized(g1);
122  POSTGIS_DEBUG(3, "unable to read gbox from gserialized, calculating from scratch");
123  lwgeom_calculate_gbox_geodetic(lwgeom1, &gbox1);
124  lwgeom_free(lwgeom1);
125  }
126 
127  /* Flip the candidate point into geographics */
128  geographic_point_init(in_point->x, in_point->y, &in_gpoint);
129  geog2cart(&in_gpoint, &in_point3d);
130 
131  /* If the candidate isn't in the tree box, it's not in the tree area */
132  if ( ! gbox_contains_point3d(&gbox1, &in_point3d) )
133  {
134  POSTGIS_DEBUG(3, "in_point3d is not inside the tree gbox, CircTreePIP returning FALSE");
135  return LW_FALSE;
136  }
137  /* The candidate point is in the box, so it *might* be inside the tree */
138  else
139  {
140  POINT2D pt2d_outside; /* latlon */
141  POINT2D pt2d_inside;
142  pt2d_inside.x = in_point->x;
143  pt2d_inside.y = in_point->y;
144  /* Calculate a definitive outside point */
145  gbox_pt_outside(&gbox1, &pt2d_outside);
146  POSTGIS_DEBUGF(3, "p2d_inside=POINT(%g %g) p2d_outside=POINT(%g %g)", pt2d_inside.x, pt2d_inside.y, pt2d_outside.x, pt2d_outside.y);
147  /* Test the candidate point for strict containment */
148  POSTGIS_DEBUG(3, "calling circ_tree_contains_point for PiP test");
149  return circ_tree_contains_point(tree1, &pt2d_inside, &pt2d_outside, NULL);
150  }
151  }
152  else
153  {
154  POSTGIS_DEBUG(3, "tree1 not polygonal, so CircTreePIP returning FALSE");
155  return LW_FALSE;
156  }
157 }
158 
159 
160 static int
161 geography_distance_cache_tolerance(FunctionCallInfoData* fcinfo, const GSERIALIZED* g1, const GSERIALIZED* g2, const SPHEROID* s, double tolerance, double* distance)
162 {
163  CircTreeGeomCache* tree_cache = NULL;
164 
165  int type1 = gserialized_get_type(g1);
166  int type2 = gserialized_get_type(g2);
167 
168  Assert(distance);
169 
170  /* Two points? Get outa here... */
171  if ( type1 == POINTTYPE && type2 == POINTTYPE )
172  return LW_FAILURE;
173 
174  /* Fetch/build our cache, if appropriate, etc... */
175  tree_cache = GetCircTreeGeomCache(fcinfo, g1, g2);
176 
177  /* OK, we have an index at the ready! Use it for the one tree argument and */
178  /* fill in the other tree argument */
179  if ( tree_cache && tree_cache->argnum && tree_cache->index )
180  {
181  CIRC_NODE* circtree_cached = tree_cache->index;
182  CIRC_NODE* circtree = NULL;
183  const GSERIALIZED* g_cached;
184  const GSERIALIZED* g;
185  LWGEOM* lwgeom = NULL;
186  int geomtype_cached;
187  int geomtype;
188  POINT4D p4d;
189 
190  /* We need to dynamically build a tree for the uncached side of the function call */
191  if ( tree_cache->argnum == 1 )
192  {
193  g_cached = g1;
194  g = g2;
195  geomtype_cached = type1;
196  geomtype = type2;
197  }
198  else if ( tree_cache->argnum == 2 )
199  {
200  g_cached = g2;
201  g = g1;
202  geomtype_cached = type2;
203  geomtype = type1;
204  }
205  else
206  {
207  lwpgerror("geography_distance_cache this cannot happen!");
208  return LW_FAILURE;
209  }
210 
211  lwgeom = lwgeom_from_gserialized(g);
212  if ( geomtype_cached == POLYGONTYPE || geomtype_cached == MULTIPOLYGONTYPE )
213  {
214  lwgeom_startpoint(lwgeom, &p4d);
215  if ( CircTreePIP(circtree_cached, g_cached, &p4d) )
216  {
217  *distance = 0.0;
218  lwgeom_free(lwgeom);
219  return LW_SUCCESS;
220  }
221  }
222 
223  circtree = lwgeom_calculate_circ_tree(lwgeom);
224  if ( geomtype == POLYGONTYPE || geomtype == MULTIPOLYGONTYPE )
225  {
226  POINT2D p2d;
227  circ_tree_get_point(circtree_cached, &p2d);
228  p4d.x = p2d.x;
229  p4d.y = p2d.y;
230  if ( CircTreePIP(circtree, g, &p4d) )
231  {
232  *distance = 0.0;
233  circ_tree_free(circtree);
234  lwgeom_free(lwgeom);
235  return LW_SUCCESS;
236  }
237  }
238 
239  *distance = circ_tree_distance_tree(circtree_cached, circtree, s, tolerance);
240  circ_tree_free(circtree);
241  lwgeom_free(lwgeom);
242  return LW_SUCCESS;
243  }
244  else
245  {
246  return LW_FAILURE;
247  }
248 }
249 
250 
251 int
252 geography_distance_cache(FunctionCallInfoData* fcinfo, const GSERIALIZED* g1, const GSERIALIZED* g2, const SPHEROID* s, double* distance)
253 {
254  return geography_distance_cache_tolerance(fcinfo, g1, g2, s, FP_TOLERANCE, distance);
255 }
256 
257 int
258 geography_dwithin_cache(FunctionCallInfoData* fcinfo, const GSERIALIZED* g1, const GSERIALIZED* g2, const SPHEROID* s, double tolerance, int* dwithin)
259 {
260  double distance;
261  /* Ticket #2422, difference between sphere and spheroid distance can trip up the */
262  /* threshold shortcircuit (stopping a calculation before the spheroid distance is actually */
263  /* below the threshold. Lower in the code line, we actually reduce the threshold a little to */
264  /* avoid this. */
265  /* Correct fix: propogate the spheroid information all the way to the bottom of the calculation */
266  /* so the "right thing" can be done in all cases. */
267  if ( LW_SUCCESS == geography_distance_cache_tolerance(fcinfo, g1, g2, s, tolerance, &distance) )
268  {
269  *dwithin = (distance <= (tolerance + FP_TOLERANCE) ? LW_TRUE : LW_FALSE);
270  return LW_SUCCESS;
271  }
272  return LW_FAILURE;
273 }
274 
275 int
276 geography_tree_distance(const GSERIALIZED* g1, const GSERIALIZED* g2, const SPHEROID* s, double tolerance, double* distance)
277 {
278  CIRC_NODE* circ_tree1 = NULL;
279  CIRC_NODE* circ_tree2 = NULL;
280  LWGEOM* lwgeom1 = NULL;
281  LWGEOM* lwgeom2 = NULL;
282  POINT4D pt1, pt2;
283 
284  lwgeom1 = lwgeom_from_gserialized(g1);
285  lwgeom2 = lwgeom_from_gserialized(g2);
286  circ_tree1 = lwgeom_calculate_circ_tree(lwgeom1);
287  circ_tree2 = lwgeom_calculate_circ_tree(lwgeom2);
288  lwgeom_startpoint(lwgeom1, &pt1);
289  lwgeom_startpoint(lwgeom2, &pt2);
290 
291  if ( CircTreePIP(circ_tree1, g1, &pt2) || CircTreePIP(circ_tree2, g2, &pt1) )
292  {
293  *distance = 0.0;
294  }
295  else
296  {
297  /* Calculate tree/tree distance */
298  *distance = circ_tree_distance_tree(circ_tree1, circ_tree2, s, tolerance);
299  }
300 
301  circ_tree_free(circ_tree1);
302  circ_tree_free(circ_tree2);
303  lwgeom_free(lwgeom1);
304  lwgeom_free(lwgeom2);
305  return LW_SUCCESS;
306 }
int gserialized_get_gbox_p(const GSERIALIZED *g, GBOX *box)
Read the bounding box off a serialization and calculate one if it is not already there.
Definition: g_serialized.c:398
double x
Definition: liblwgeom.h:351
uint32_t gserialized_get_type(const GSERIALIZED *s)
Extract the geometry type from the serialized form (it hides in the anonymous data area...
Definition: g_serialized.c:69
int lwgeom_calculate_gbox_geodetic(const LWGEOM *geom, GBOX *gbox)
Calculate the geodetic bounding box for an LWGEOM.
Definition: lwgeodetic.c:2626
static int CircTreeFreer(GeomCache *cache)
unsigned int int32
Definition: shpopen.c:273
Note that p1 and p2 are pointers into an independent POINTARRAY, do not free them.
LWGEOM * lwgeom_from_gserialized(const GSERIALIZED *g)
Allocate a new LWGEOM from a GSERIALIZED.
int circ_tree_get_point(const CIRC_NODE *node, POINT2D *pt)
Returns a POINT2D that is a vertex of the input shape.
int lwgeom_startpoint(const LWGEOM *lwgeom, POINT4D *pt)
Definition: lwgeom.c:1850
#define POLYGONTYPE
Definition: liblwgeom.h:86
void lwgeom_free(LWGEOM *geom)
Definition: lwgeom.c:1063
static int geography_distance_cache_tolerance(FunctionCallInfoData *fcinfo, const GSERIALIZED *g1, const GSERIALIZED *g2, const SPHEROID *s, double tolerance, double *distance)
int gbox_contains_point3d(const GBOX *gbox, const POINT3D *pt)
Return true if the point is inside the gbox.
Definition: g_box.c:259
#define LW_SUCCESS
Definition: liblwgeom.h:79
static int CircTreeBuilder(const LWGEOM *lwgeom, GeomCache *cache)
Builder, freeer and public accessor for cached CIRC_NODE trees.
static GeomCache * CircTreeAllocator(void)
double circ_tree_distance_tree(const CIRC_NODE *n1, const CIRC_NODE *n2, const SPHEROID *spheroid, double threshold)
int geography_tree_distance(const GSERIALIZED *g1, const GSERIALIZED *g2, const SPHEROID *s, double tolerance, double *distance)
Point in spherical coordinates on the world.
Definition: lwgeodetic.h:47
CIRC_NODE * lwgeom_calculate_circ_tree(const LWGEOM *lwgeom)
static CircTreeGeomCache * GetCircTreeGeomCache(FunctionCallInfoData *fcinfo, const GSERIALIZED *g1, const GSERIALIZED *g2)
#define LW_FAILURE
Definition: liblwgeom.h:78
static int CircTreePIP(const CIRC_NODE *tree1, const GSERIALIZED *g1, const POINT4D *in_point)
double x
Definition: liblwgeom.h:327
#define LW_FALSE
Definition: liblwgeom.h:76
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
int circ_tree_contains_point(const CIRC_NODE *node, const POINT2D *pt, const POINT2D *pt_outside, int *on_boundary)
Walk the tree and count intersections between the stab line and the edges.
#define FP_TOLERANCE
Floating point comparators.
char * s
Definition: cu_in_wkt.c:23
double y
Definition: liblwgeom.h:327
Datum distance(PG_FUNCTION_ARGS)
void geog2cart(const GEOGRAPHIC_POINT *g, POINT3D *p)
Convert spherical coordinates to cartesion coordinates on unit sphere.
Definition: lwgeodetic.c:369
#define MULTIPOLYGONTYPE
Definition: liblwgeom.h:89
void circ_tree_free(CIRC_NODE *node)
Recurse from top of node tree and free all children.
void gbox_pt_outside(const GBOX *gbox, POINT2D *pt_outside)
Calculate a spherical point that falls outside the geocentric gbox.
Definition: lwgeodetic.c:1461
int geography_dwithin_cache(FunctionCallInfoData *fcinfo, const GSERIALIZED *g1, const GSERIALIZED *g2, const SPHEROID *s, double tolerance, int *dwithin)
void geographic_point_init(double lon, double lat, GEOGRAPHIC_POINT *g)
Initialize a geographic point.
Definition: lwgeodetic.c:171
#define POINTTYPE
LWTYPE numbers, used internally by PostGIS.
Definition: liblwgeom.h:84
int geography_distance_cache(FunctionCallInfoData *fcinfo, const GSERIALIZED *g1, const GSERIALIZED *g2, const SPHEROID *s, double *distance)
static GeomCacheMethods CircTreeCacheMethods
double y
Definition: liblwgeom.h:351