PostGIS  2.5.7dev-r@@SVN_REVISION@@
gserialized_gist_2d.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 2009 Paul Ramsey <pramsey@cleverelephant.ca>
22  * Copyright 2017 Darafei Praliaskouski <me@komzpa.net>
23  *
24  **********************************************************************/
25 
26 
27 /*
28 ** R-Tree Bibliography
29 **
30 ** [1] A. Guttman. R-tree: a dynamic index structure for spatial searching.
31 ** Proceedings of the ACM SIGMOD Conference, pp 47-57, June 1984.
32 ** [2] C.-H. Ang and T. C. Tan. New linear node splitting algorithm for
33 ** R-Trees. Advances in Spatial Databases - 5th International Symposium,
34 ** 1997
35 ** [3] N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger. The R*tree: an
36 ** efficient and robust access method for points and rectangles.
37 ** Proceedings of the ACM SIGMOD Conference. June 1990.
38 ** [4] A. Korotkov, "A new double sorting-based node splitting algorithm for R-tree",
39 ** http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
40 */
41 
42 #include "postgres.h"
43 #include "access/gist.h" /* For GiST */
44 #include "access/itup.h"
45 #include "access/skey.h"
46 
47 #include "../postgis_config.h"
48 
49 #include "liblwgeom.h" /* For standard geometry types. */
50 #include "lwgeom_pg.h" /* For debugging macros. */
51 #include "gserialized_gist.h" /* For utility functions. */
52 
53 /* Fall back to older finite() if necessary */
54 #ifndef HAVE_ISFINITE
55 # ifdef HAVE_GNU_ISFINITE
56 # define _GNU_SOURCE
57 # else
58 # define isfinite finite
59 # endif
60 #endif
61 
62 #include <float.h> /* For FLT_MAX */
63 
64 /*
65 ** When is a node split not so good? If more than 90% of the entries
66 ** end up in one of the children.
67 */
68 #define LIMIT_RATIO 0.1
69 
70 /*
71 ** 0 == don't use it
72 ** 1 == use it
73 */
74 #define KOROTKOV_SPLIT 1
75 
76 /*
77 ** For debugging
78 */
79 #if POSTGIS_DEBUG_LEVEL > 0
80 static int g2d_counter_leaf = 0;
81 static int g2d_counter_internal = 0;
82 #endif
83 
84 /*
85 ** GiST 2D key stubs
86 */
87 Datum box2df_out(PG_FUNCTION_ARGS);
88 Datum box2df_in(PG_FUNCTION_ARGS);
89 
90 /*
91 ** GiST 2D index function prototypes
92 */
93 Datum gserialized_gist_consistent_2d(PG_FUNCTION_ARGS);
94 Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS);
95 Datum gserialized_gist_decompress_2d(PG_FUNCTION_ARGS);
96 Datum gserialized_gist_penalty_2d(PG_FUNCTION_ARGS);
97 Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS);
98 Datum gserialized_gist_union_2d(PG_FUNCTION_ARGS);
99 Datum gserialized_gist_same_2d(PG_FUNCTION_ARGS);
100 Datum gserialized_gist_distance_2d(PG_FUNCTION_ARGS);
101 
102 /*
103 ** GiST 2D operator prototypes
104 */
105 Datum gserialized_same_2d(PG_FUNCTION_ARGS);
106 Datum gserialized_within_2d(PG_FUNCTION_ARGS);
107 Datum gserialized_contains_2d(PG_FUNCTION_ARGS);
108 Datum gserialized_overlaps_2d(PG_FUNCTION_ARGS);
109 Datum gserialized_left_2d(PG_FUNCTION_ARGS);
110 Datum gserialized_right_2d(PG_FUNCTION_ARGS);
111 Datum gserialized_above_2d(PG_FUNCTION_ARGS);
112 Datum gserialized_below_2d(PG_FUNCTION_ARGS);
113 Datum gserialized_overleft_2d(PG_FUNCTION_ARGS);
114 Datum gserialized_overright_2d(PG_FUNCTION_ARGS);
115 Datum gserialized_overabove_2d(PG_FUNCTION_ARGS);
116 Datum gserialized_overbelow_2d(PG_FUNCTION_ARGS);
117 Datum gserialized_distance_box_2d(PG_FUNCTION_ARGS);
118 Datum gserialized_distance_centroid_2d(PG_FUNCTION_ARGS);
119 
120 #if POSTGIS_PGSQL_VERSION > 94
121 Datum gserialized_contains_box2df_geom_2d(PG_FUNCTION_ARGS);
122 Datum gserialized_contains_box2df_box2df_2d(PG_FUNCTION_ARGS);
123 Datum gserialized_within_box2df_geom_2d(PG_FUNCTION_ARGS);
124 Datum gserialized_within_box2df_box2df_2d(PG_FUNCTION_ARGS);
125 Datum gserialized_overlaps_box2df_geom_2d(PG_FUNCTION_ARGS);
126 Datum gserialized_overlaps_box2df_box2df_2d(PG_FUNCTION_ARGS);
127 #endif
128 
129 /*
130 ** true/false test function type
131 */
132 typedef bool (*box2df_predicate)(const BOX2DF *a, const BOX2DF *b);
133 
134 
135 static char* box2df_to_string(const BOX2DF *a)
136 {
137  char *rv = NULL;
138 
139  if ( a == NULL )
140  return pstrdup("<NULLPTR>");
141 
142  rv = palloc(128);
143  sprintf(rv, "BOX2DF(%.12g %.12g, %.12g %.12g)", a->xmin, a->ymin, a->xmax, a->ymax);
144  return rv;
145 }
146 
147 /* Allocate a new copy of BOX2DF */
148 BOX2DF* box2df_copy(BOX2DF *b)
149 {
150  BOX2DF *c = (BOX2DF*)palloc(sizeof(BOX2DF));
151  memcpy((void*)c, (void*)b, sizeof(BOX2DF));
152  POSTGIS_DEBUGF(5, "copied box2df (%p) to box2df (%p)", b, c);
153  return c;
154 }
155 
156 inline bool box2df_is_empty(const BOX2DF *a)
157 {
158  if (isnan(a->xmin))
159  return true;
160  else
161  return false;
162 }
163 
164 inline void box2df_set_empty(BOX2DF *a)
165 {
166  a->xmin = a->xmax = a->ymin = a->ymax = NAN;
167  return;
168 }
169 
170 inline void box2df_set_finite(BOX2DF *a)
171 {
172  if ( ! isfinite(a->xmax) )
173  a->xmax = FLT_MAX;
174  if ( ! isfinite(a->ymax) )
175  a->ymax = FLT_MAX;
176  if ( ! isfinite(a->ymin) )
177  a->ymin = -1*FLT_MAX;
178  if ( ! isfinite(a->xmin) )
179  a->xmin = -1*FLT_MAX;
180  return;
181 }
182 
183 /* Enlarge b_union to contain b_new. If b_new contains more
184  dimensions than b_union, expand b_union to contain those dimensions. */
185 void box2df_merge(BOX2DF *b_union, BOX2DF *b_new)
186 {
187 
188  POSTGIS_DEBUGF(5, "merging %s with %s", box2df_to_string(b_union), box2df_to_string(b_new));
189  /* Adjust minimums */
190  if (b_union->xmin > b_new->xmin || isnan(b_union->xmin))
191  b_union->xmin = b_new->xmin;
192  if (b_union->ymin > b_new->ymin || isnan(b_union->ymin))
193  b_union->ymin = b_new->ymin;
194  /* Adjust maximums */
195  if (b_union->xmax < b_new->xmax || isnan(b_union->xmax))
196  b_union->xmax = b_new->xmax;
197  if (b_union->ymax < b_new->ymax || isnan(b_union->ymax))
198  b_union->ymax = b_new->ymax;
199 
200  POSTGIS_DEBUGF(5, "merge complete %s", box2df_to_string(b_union));
201  return;
202 }
203 
204 #if KOROTKOV_SPLIT < 1
205 static bool box2df_intersection(const BOX2DF *a, const BOX2DF *b, BOX2DF *n)
206 {
207  POSTGIS_DEBUGF(5, "calculating intersection of %s with %s", box2df_to_string(a), box2df_to_string(b));
208 
209  if( a == NULL || b == NULL || n == NULL )
210  return false;
211 
212  n->xmax = Min(a->xmax, b->xmax);
213  n->ymax = Min(a->ymax, b->ymax);
214  n->xmin = Max(a->xmin, b->xmin);
215  n->ymin = Max(a->ymin, b->ymin);
216 
217  POSTGIS_DEBUGF(5, "intersection is %s", box2df_to_string(n));
218 
219  if ( (n->xmax < n->xmin) || (n->ymax < n->ymin) )
220  return false;
221 
222  return true;
223 }
224 #endif
225 
226 static float box2df_size(const BOX2DF *a)
227 {
228  float result;
229 
230  if ( a == NULL || box2df_is_empty(a) )
231  return (float)0.0;
232 
233  if ( (a->xmax <= a->xmin) || (a->ymax <= a->ymin) )
234  {
235  result = (float) 0.0;
236  }
237  else
238  {
239  result = (((double) a->xmax)-((double) a->xmin)) * (((double) a->ymax)-((double) a->ymin));
240  }
241 
242  return result;
243 }
244 
245 static float box2df_edge(const BOX2DF *a)
246 {
247  if ( a == NULL || box2df_is_empty(a) )
248  return (float)0.0;
249 
250  return ((a->xmax) - (a->xmin)) + ((a->ymax) - (a->ymin));
251 }
252 
253 static float box2df_union_size(const BOX2DF *a, const BOX2DF *b)
254 {
255  float result;
256 
257  POSTGIS_DEBUG(5,"entered function");
258 
259  if ( a == NULL && b == NULL )
260  {
261  elog(ERROR, "box2df_union_size received two null arguments");
262  return 0.0;
263  }
264 
265  if ( a == NULL || box2df_is_empty(a) )
266  return box2df_size(b);
267 
268  if ( b == NULL || box2df_is_empty(b) )
269  return box2df_size(a);
270 
271  result = ((double)Max(a->xmax,b->xmax) - (double)Min(a->xmin,b->xmin)) *
272  ((double)Max(a->ymax,b->ymax) - (double)Min(a->ymin,b->ymin));
273 
274  POSTGIS_DEBUGF(5, "union size of %s and %s is %.8g", box2df_to_string(a), box2df_to_string(b), result);
275 
276  return result;
277 }
278 
279 
280 static float box2df_union_edge(const BOX2DF *a, const BOX2DF *b)
281 {
282  float result;
283 
284  POSTGIS_DEBUG(5,"entered function");
285 
286  if ( a == NULL && b == NULL )
287  {
288  elog(ERROR, "box2df_union_edge received two null arguments");
289  return 0.0;
290  }
291 
292  if ( a == NULL || box2df_is_empty(a) )
293  return box2df_edge(b);
294 
295  if ( b == NULL || box2df_is_empty(b) )
296  return box2df_edge(a);
297 
298  result = (Max(a->xmax,b->xmax) - Min(a->xmin,b->xmin)) +
299  (Max(a->ymax,b->ymax) - Min(a->ymin,b->ymin));
300 
301  POSTGIS_DEBUGF(5, "union edge of %s and %s is %.8g", box2df_to_string(a), box2df_to_string(b), result);
302 
303  return result;
304 }
305 
306 /* Convert a double-based GBOX into a float-based BOX2DF,
307  ensuring the float box is larger than the double box */
308 static inline int box2df_from_gbox_p(GBOX *box, BOX2DF *a)
309 {
310  a->xmin = next_float_down(box->xmin);
311  a->xmax = next_float_up(box->xmax);
312  a->ymin = next_float_down(box->ymin);
313  a->ymax = next_float_up(box->ymax);
314  return LW_SUCCESS;
315 }
316 
317 int box2df_to_gbox_p(BOX2DF *a, GBOX *box)
318 {
319  memset(box, 0, sizeof(GBOX));
320  box->xmin = a->xmin;
321  box->xmax = a->xmax;
322  box->ymin = a->ymin;
323  box->ymax = a->ymax;
324  return LW_SUCCESS;
325 }
326 
327 /***********************************************************************
328 ** BOX3DF tests for 2D index operators.
329 */
330 
331 /* Ensure all minimums are below maximums. */
332 inline void box2df_validate(BOX2DF *b)
333 {
334  float tmp;
335  POSTGIS_DEBUGF(5,"validating box2df (%s)", box2df_to_string(b));
336 
337  if ( box2df_is_empty(b) )
338  return;
339 
340  if ( b->xmax < b->xmin )
341  {
342  tmp = b->xmin;
343  b->xmin = b->xmax;
344  b->xmax = tmp;
345  }
346  if ( b->ymax < b->ymin )
347  {
348  tmp = b->ymin;
349  b->ymin = b->ymax;
350  b->ymax = tmp;
351  }
352  return;
353 }
354 
355 bool box2df_overlaps(const BOX2DF *a, const BOX2DF *b)
356 {
357  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
358  return false;
359 
360  if ( (a->xmin > b->xmax) || (b->xmin > a->xmax) ||
361  (a->ymin > b->ymax) || (b->ymin > a->ymax) )
362  {
363  return false;
364  }
365 
366  return true;
367 }
368 
369 bool box2df_contains(const BOX2DF *a, const BOX2DF *b)
370 {
371  if ( !a || !b )
372  return false;
373 
374  /* All things can contain EMPTY (except EMPTY) */
375  if ( box2df_is_empty(b) && ! box2df_is_empty(a) )
376  return true;
377 
378  if ( (a->xmin > b->xmin) || (a->xmax < b->xmax) ||
379  (a->ymin > b->ymin) || (a->ymax < b->ymax) )
380  {
381  return false;
382  }
383 
384  return true;
385 }
386 
387 static bool box2df_within(const BOX2DF *a, const BOX2DF *b)
388 {
389  if ( !a || !b )
390  return false;
391 
392  /* EMPTY is within all other things (except EMPTY) */
393  if ( box2df_is_empty(a) && ! box2df_is_empty(b) )
394  return true;
395 
396  POSTGIS_DEBUG(5, "entered function");
397  return box2df_contains(b,a);
398 }
399 
400 bool box2df_equals(const BOX2DF *a, const BOX2DF *b)
401 {
402  if ( !a && !b )
403  return true;
404  else if ( !a || !b )
405  return false;
406  else if ( box2df_is_empty(a) && box2df_is_empty(b) )
407  return true;
408  else if ( box2df_is_empty(a) || box2df_is_empty(b) )
409  return false;
410  else if ((a->xmin == b->xmin) && (a->xmax == b->xmax) && (a->ymin == b->ymin) && (a->ymax == b->ymax))
411  return true;
412  else
413  return false;
414 }
415 
416 bool box2df_overleft(const BOX2DF *a, const BOX2DF *b)
417 {
418  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
419  return false;
420 
421  /* a.xmax <= b.xmax */
422  return a->xmax <= b->xmax;
423 }
424 
425 bool box2df_left(const BOX2DF *a, const BOX2DF *b)
426 {
427  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
428  return false;
429 
430  /* a.xmax < b.xmin */
431  return a->xmax < b->xmin;
432 }
433 
434 bool box2df_right(const BOX2DF *a, const BOX2DF *b)
435 {
436  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
437  return false;
438 
439  /* a.xmin > b.xmax */
440  return a->xmin > b->xmax;
441 }
442 
443 bool box2df_overright(const BOX2DF *a, const BOX2DF *b)
444 {
445  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
446  return false;
447 
448  /* a.xmin >= b.xmin */
449  return a->xmin >= b->xmin;
450 }
451 
452 bool box2df_overbelow(const BOX2DF *a, const BOX2DF *b)
453 {
454  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
455  return false;
456 
457  /* a.ymax <= b.ymax */
458  return a->ymax <= b->ymax;
459 }
460 
461 bool box2df_below(const BOX2DF *a, const BOX2DF *b)
462 {
463  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
464  return false;
465 
466  /* a.ymax < b.ymin */
467  return a->ymax < b->ymin;
468 }
469 
470 bool box2df_above(const BOX2DF *a, const BOX2DF *b)
471 {
472  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
473  return false;
474 
475  /* a.ymin > b.ymax */
476  return a->ymin > b->ymax;
477 }
478 
479 bool box2df_overabove(const BOX2DF *a, const BOX2DF *b)
480 {
481  if ( !a || !b || box2df_is_empty(a) || box2df_is_empty(b) )
482  return false;
483 
484  /* a.ymin >= b.ymin */
485  return a->ymin >= b->ymin;
486 }
487 
491 static double box2df_distance_leaf_centroid(const BOX2DF *a, const BOX2DF *b)
492 {
493  /* The centroid->centroid distance between the boxes */
494  double a_x = (a->xmax + a->xmin) / 2.0;
495  double a_y = (a->ymax + a->ymin) / 2.0;
496  double b_x = (b->xmax + b->xmin) / 2.0;
497  double b_y = (b->ymax + b->ymin) / 2.0;
498 
499  /* This "distance" is only used for comparisons, */
500  return sqrt((a_x - b_x) * (a_x - b_x) + (a_y - b_y) * (a_y - b_y));
501 }
502 
503 #if POSTGIS_PGSQL_VERSION < 95
508 static double box2df_distance_node_centroid(const BOX2DF *node, const BOX2DF *query)
509 {
510  BOX2DF q;
511  double qx, qy;
512  double d = 0.0;
513 
514  /* Turn query into point */
515  q.xmin = q.xmax = (query->xmin + query->xmax) / 2.0;
516  q.ymin = q.ymax = (query->ymin + query->ymax) / 2.0;
517  qx = q.xmin;
518  qy = q.ymin;
519 
520  /* Check for overlap */
521  if ( box2df_overlaps(node, &q) == LW_TRUE )
522  return 0.0;
523 
524  /* Above or below */
525  if ( qx >= node->xmin && qx <= node->xmax )
526  {
527  if( qy > node->ymax )
528  d = qy - node->ymax;
529  else if ( qy < node->ymin )
530  d = node->ymin - qy;
531  return d;
532  }
533  /* Left or right */
534  else if ( qy >= node->ymin && qy <= node->ymax )
535  {
536  if ( qx > node->xmax )
537  d = qx - node->xmax;
538  else if ( qx < node->xmin )
539  d = node->xmin - qx;
540  return d;
541  }
542  /* Corner quadrants */
543  else
544  {
545  /* below/left of xmin/ymin */
546  if ( qx < node->xmin && qy < node->ymin )
547  {
548  d = (node->xmin - qx) * (node->xmin - qx) +
549  (node->ymin - qy) * (node->ymin - qy);
550  }
551  /* above/left of xmin/ymax */
552  else if ( qx < node->xmin && qy > node->ymax )
553  {
554  d = (node->xmin - qx) * (node->xmin - qx) +
555  (node->ymax - qy) * (node->ymax - qy);
556  }
557  /* above/right of xmax/ymax */
558  else if ( qx > node->xmax && qy > node->ymax )
559  {
560  d = (node->xmax - qx) * (node->xmax - qx) +
561  (node->ymax - qy) * (node->ymax - qy);
562  }
563  /* below/right of xmax/ymin */
564  else if ( qx > node->xmin && qy < node->ymin )
565  {
566  d = (node->xmax - qx) * (node->xmax - qx) +
567  (node->ymin - qy) * (node->ymin - qy);
568  }
569  else
570  {
571  /*ERROR*/
572  elog(ERROR, "%s: reached unreachable code", __func__);
573  }
574  }
575 
576  return sqrt(d);
577 }
578 #endif
579 
580 /* Quick distance function */
581 static inline double pt_distance(double ax, double ay, double bx, double by)
582 {
583  return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
584 }
585 
589 static double box2df_distance(const BOX2DF *a, const BOX2DF *b)
590 {
591  /* Check for overlap */
592  if ( box2df_overlaps(a, b) )
593  return 0.0;
594 
595  if ( box2df_left(a, b) )
596  {
597  if ( box2df_above(a, b) )
598  return pt_distance(a->xmax, a->ymin, b->xmin, b->ymax);
599  if ( box2df_below(a, b) )
600  return pt_distance(a->xmax, a->ymax, b->xmin, b->ymin);
601  else
602  return (double)b->xmin - (double)a->xmax;
603  }
604  if ( box2df_right(a, b) )
605  {
606  if ( box2df_above(a, b) )
607  return pt_distance(a->xmin, a->ymin, b->xmax, b->ymax);
608  if ( box2df_below(a, b) )
609  return pt_distance(a->xmin, a->ymax, b->xmax, b->ymin);
610  else
611  return (double)a->xmin - (double)b->xmax;
612  }
613  if ( box2df_above(a, b) )
614  {
615  if ( box2df_left(a, b) )
616  return pt_distance(a->xmax, a->ymin, b->xmin, b->ymax);
617  if ( box2df_right(a, b) )
618  return pt_distance(a->xmin, a->ymin, b->xmax, b->ymax);
619  else
620  return (double)a->ymin - (double)b->ymax;
621  }
622  if ( box2df_below(a, b) )
623  {
624  if ( box2df_left(a, b) )
625  return pt_distance(a->xmax, a->ymax, b->xmin, b->ymin);
626  if ( box2df_right(a, b) )
627  return pt_distance(a->xmin, a->ymax, b->xmax, b->ymin);
628  else
629  return (double)b->ymin - (double)a->ymax;
630  }
631 
632  return FLT_MAX;
633 }
634 
635 
642 int
643 gserialized_datum_get_box2df_p(Datum gsdatum, BOX2DF *box2df)
644 {
645  GSERIALIZED *gpart;
646  uint8_t flags;
647  int result = LW_SUCCESS;
648 
649  POSTGIS_DEBUG(4, "entered function");
650 
651  /*
652  ** The most info we need is the 8 bytes of serialized header plus the
653  ** of floats necessary to hold the bounding box.
654  */
655  if (VARATT_IS_EXTENDED(gsdatum))
656  {
657  gpart = (GSERIALIZED*)PG_DETOAST_DATUM_SLICE(gsdatum, 0, 8 + sizeof(BOX2DF));
658  }
659  else
660  {
661  gpart = (GSERIALIZED*)PG_DETOAST_DATUM(gsdatum);
662  }
663 
664  flags = gpart->flags;
665 
666  POSTGIS_DEBUGF(4, "got flags %d", gpart->flags);
667 
668  /* Do we even have a serialized bounding box? */
669  if ( FLAGS_GET_BBOX(flags) )
670  {
671  /* Yes! Copy it out into the box! */
672  POSTGIS_DEBUG(4, "copying box out of serialization");
673  memcpy(box2df, gpart->data, sizeof(BOX2DF));
674  result = LW_SUCCESS;
675  }
676  else
677  {
678  /* No, we need to calculate it from the full object. */
679  GBOX gbox;
680  GSERIALIZED *g = (GSERIALIZED*)PG_DETOAST_DATUM(gsdatum);
681 
682  gbox_init(&gbox);
683 
684  if (gserialized_get_gbox_p(g, &gbox) == LW_FAILURE)
685  {
686  POSTGIS_DEBUG(4, "could not calculate bbox, returning failure");
687  POSTGIS_FREE_IF_COPY_P(gpart, gsdatum);
688  POSTGIS_FREE_IF_COPY_P(g, gsdatum);
689  return LW_FAILURE;
690  }
691  POSTGIS_FREE_IF_COPY_P(g, gsdatum);
692  result = box2df_from_gbox_p(&gbox, box2df);
693  }
694 
695  POSTGIS_FREE_IF_COPY_P(gpart, gsdatum);
696 
697  if ( result == LW_SUCCESS )
698  {
699  POSTGIS_DEBUGF(4, "got box2df %s", box2df_to_string(box2df));
700  }
701 
702  return result;
703 }
704 
705 
710 static int
711 gserialized_datum_predicate_2d(Datum gs1, Datum gs2, box2df_predicate predicate)
712 {
713  BOX2DF b1, b2, *br1=NULL, *br2=NULL;
714  POSTGIS_DEBUG(3, "entered function");
715 
716  if (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) br1 = &b1;
717  if (gserialized_datum_get_box2df_p(gs2, &b2) == LW_SUCCESS) br2 = &b2;
718 
719  if ( predicate(br1, br2) )
720  {
721  POSTGIS_DEBUGF(3, "got boxes %s and %s", br1 ? box2df_to_string(&b1) : "(null)", br2 ? box2df_to_string(&b2) : "(null)");
722  return LW_TRUE;
723  }
724  return LW_FALSE;
725 }
726 
727 #if POSTGIS_PGSQL_VERSION > 94
728 static int
729 gserialized_datum_predicate_box2df_geom_2d(const BOX2DF *br1, Datum gs2, box2df_predicate predicate)
730 {
731  BOX2DF b2, *br2=NULL;
732  POSTGIS_DEBUG(3, "entered function");
733 
734  if (gserialized_datum_get_box2df_p(gs2, &b2) == LW_SUCCESS) br2 = &b2;
735 
736  if ( predicate(br1, br2) )
737  {
738  POSTGIS_DEBUGF(3, "got boxes %s", br2 ? box2df_to_string(&b2) : "(null)");
739  return LW_TRUE;
740  }
741  return LW_FALSE;
742 }
743 
744 /***********************************************************************
745 * BRIN 2-D Index Operator Functions
746 */
747 
749 Datum gserialized_contains_box2df_geom_2d(PG_FUNCTION_ARGS)
750 {
751  POSTGIS_DEBUG(3, "entered function");
752  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_contains) == LW_TRUE )
753  PG_RETURN_BOOL(true);
754 
755  PG_RETURN_BOOL(false);
756 }
757 
760 {
761  if ( box2df_contains((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
762  PG_RETURN_BOOL(true);
763 
764  PG_RETURN_BOOL(false);
765 }
766 
768 Datum gserialized_within_box2df_geom_2d(PG_FUNCTION_ARGS)
769 {
770  POSTGIS_DEBUG(3, "entered function");
771  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_within) == LW_TRUE )
772  PG_RETURN_BOOL(true);
773 
774  PG_RETURN_BOOL(false);
775 }
776 
778 Datum gserialized_within_box2df_box2df_2d(PG_FUNCTION_ARGS)
779 {
780  if ( box2df_within((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
781  PG_RETURN_BOOL(true);
782 
783  PG_RETURN_BOOL(false);
784 }
785 
787 Datum gserialized_overlaps_box2df_geom_2d(PG_FUNCTION_ARGS)
788 {
789  POSTGIS_DEBUG(3, "entered function");
790  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_overlaps) == LW_TRUE )
791  PG_RETURN_BOOL(true);
792 
793  PG_RETURN_BOOL(false);
794 }
795 
798 {
799  if ( box2df_overlaps((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
800  PG_RETURN_BOOL(true);
801 
802  PG_RETURN_BOOL(false);
803 }
804 #endif
805 
806 /***********************************************************************
807 * GiST 2-D Index Operator Functions
808 */
809 
811 Datum gserialized_distance_centroid_2d(PG_FUNCTION_ARGS)
812 {
813  BOX2DF b1, b2;
814  Datum gs1 = PG_GETARG_DATUM(0);
815  Datum gs2 = PG_GETARG_DATUM(1);
816 
817  POSTGIS_DEBUG(3, "entered function");
818 
819  /* Must be able to build box for each argument (ie, not empty geometry). */
820  if ( (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) &&
822  {
823  double distance = box2df_distance_leaf_centroid(&b1, &b2);
824  POSTGIS_DEBUGF(3, "got boxes %s and %s", box2df_to_string(&b1), box2df_to_string(&b2));
825  PG_RETURN_FLOAT8(distance);
826  }
827  PG_RETURN_FLOAT8(FLT_MAX);
828 }
829 
831 Datum gserialized_distance_box_2d(PG_FUNCTION_ARGS)
832 {
833  BOX2DF b1, b2;
834  Datum gs1 = PG_GETARG_DATUM(0);
835  Datum gs2 = PG_GETARG_DATUM(1);
836 
837  POSTGIS_DEBUG(3, "entered function");
838 
839  /* Must be able to build box for each argument (ie, not empty geometry). */
840  if ( (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) &&
842  {
843  double distance = box2df_distance(&b1, &b2);
844  POSTGIS_DEBUGF(3, "got boxes %s and %s", box2df_to_string(&b1), box2df_to_string(&b2));
845  PG_RETURN_FLOAT8(distance);
846  }
847  PG_RETURN_FLOAT8(FLT_MAX);
848 }
849 
851 Datum gserialized_same_2d(PG_FUNCTION_ARGS)
852 {
853  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_equals) == LW_TRUE )
854  PG_RETURN_BOOL(true);
855 
856  PG_RETURN_BOOL(false);
857 }
858 
860 Datum gserialized_within_2d(PG_FUNCTION_ARGS)
861 {
862  POSTGIS_DEBUG(3, "entered function");
863  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_within) == LW_TRUE )
864  PG_RETURN_BOOL(true);
865 
866  PG_RETURN_BOOL(false);
867 }
868 
870 Datum gserialized_contains_2d(PG_FUNCTION_ARGS)
871 {
872  POSTGIS_DEBUG(3, "entered function");
873  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_contains) == LW_TRUE )
874  PG_RETURN_BOOL(true);
875 
876  PG_RETURN_BOOL(false);
877 }
878 
880 Datum gserialized_overlaps_2d(PG_FUNCTION_ARGS)
881 {
882  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overlaps) == LW_TRUE )
883  PG_RETURN_BOOL(true);
884 
885  PG_RETURN_BOOL(false);
886 }
887 
889 Datum gserialized_left_2d(PG_FUNCTION_ARGS)
890 {
891  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_left) == LW_TRUE )
892  PG_RETURN_BOOL(true);
893 
894  PG_RETURN_BOOL(false);
895 }
896 
898 Datum gserialized_right_2d(PG_FUNCTION_ARGS)
899 {
900  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_right) == LW_TRUE )
901  PG_RETURN_BOOL(true);
902 
903  PG_RETURN_BOOL(false);
904 }
905 
907 Datum gserialized_above_2d(PG_FUNCTION_ARGS)
908 {
909  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_above) == LW_TRUE )
910  PG_RETURN_BOOL(true);
911 
912  PG_RETURN_BOOL(false);
913 }
914 
916 Datum gserialized_below_2d(PG_FUNCTION_ARGS)
917 {
918  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_below) == LW_TRUE )
919  PG_RETURN_BOOL(true);
920 
921  PG_RETURN_BOOL(false);
922 }
923 
925 Datum gserialized_overleft_2d(PG_FUNCTION_ARGS)
926 {
927  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overleft) == LW_TRUE )
928  PG_RETURN_BOOL(true);
929 
930  PG_RETURN_BOOL(false);
931 }
932 
934 Datum gserialized_overright_2d(PG_FUNCTION_ARGS)
935 {
936  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overright) == LW_TRUE )
937  PG_RETURN_BOOL(true);
938 
939  PG_RETURN_BOOL(false);
940 }
941 
943 Datum gserialized_overabove_2d(PG_FUNCTION_ARGS)
944 {
945  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overabove) == LW_TRUE )
946  PG_RETURN_BOOL(true);
947 
948  PG_RETURN_BOOL(false);
949 }
950 
952 Datum gserialized_overbelow_2d(PG_FUNCTION_ARGS)
953 {
954  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overbelow) == LW_TRUE )
955  PG_RETURN_BOOL(true);
956 
957  PG_RETURN_BOOL(false);
958 }
959 
960 
961 /***********************************************************************
962 * GiST Index Support Functions
963 */
964 
965 /*
966 ** GiST support function. Given a geography, return a "compressed"
967 ** version. In this case, we convert the geography into a geocentric
968 ** bounding box. If the geography already has the box embedded in it
969 ** we pull that out and hand it back.
970 */
972 Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS)
973 {
974  GISTENTRY *entry_in = (GISTENTRY*)PG_GETARG_POINTER(0);
975  GISTENTRY *entry_out = NULL;
976  BOX2DF bbox_out;
977  int result = LW_SUCCESS;
978 
979  POSTGIS_DEBUG(4, "[GIST] 'compress' function called");
980 
981  /*
982  ** Not a leaf key? There's nothing to do.
983  ** Return the input unchanged.
984  */
985  if ( ! entry_in->leafkey )
986  {
987  POSTGIS_DEBUG(4, "[GIST] non-leafkey entry, returning input unaltered");
988  PG_RETURN_POINTER(entry_in);
989  }
990 
991  POSTGIS_DEBUG(4, "[GIST] processing leafkey input");
992  entry_out = palloc(sizeof(GISTENTRY));
993 
994  /*
995  ** Null key? Make a copy of the input entry and
996  ** return.
997  */
998  if ( DatumGetPointer(entry_in->key) == NULL )
999  {
1000  POSTGIS_DEBUG(4, "[GIST] leafkey is null");
1001  gistentryinit(*entry_out, (Datum) 0, entry_in->rel,
1002  entry_in->page, entry_in->offset, false);
1003  POSTGIS_DEBUG(4, "[GIST] returning copy of input");
1004  PG_RETURN_POINTER(entry_out);
1005  }
1006 
1007  /* Extract our index key from the GiST entry. */
1008  result = gserialized_datum_get_box2df_p(entry_in->key, &bbox_out);
1009 
1010  /* Is the bounding box valid (non-empty, non-infinite)? If not, return input uncompressed. */
1011  if ( result == LW_FAILURE )
1012  {
1013  box2df_set_empty(&bbox_out);
1014  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
1015  entry_in->rel, entry_in->page, entry_in->offset, false);
1016 
1017  POSTGIS_DEBUG(4, "[GIST] empty geometry!");
1018  PG_RETURN_POINTER(entry_out);
1019  }
1020 
1021  POSTGIS_DEBUGF(4, "[GIST] got entry_in->key: %s", box2df_to_string(&bbox_out));
1022 
1023  /* Check all the dimensions for finite values */
1024  if ( ! isfinite(bbox_out.xmax) || ! isfinite(bbox_out.xmin) ||
1025  ! isfinite(bbox_out.ymax) || ! isfinite(bbox_out.ymin) )
1026  {
1027  box2df_set_finite(&bbox_out);
1028  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
1029  entry_in->rel, entry_in->page, entry_in->offset, false);
1030 
1031  POSTGIS_DEBUG(4, "[GIST] infinite geometry!");
1032  PG_RETURN_POINTER(entry_out);
1033  }
1034 
1035  /* Enure bounding box has minimums below maximums. */
1036  box2df_validate(&bbox_out);
1037 
1038  /* Prepare GISTENTRY for return. */
1039  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
1040  entry_in->rel, entry_in->page, entry_in->offset, false);
1041 
1042  /* Return GISTENTRY. */
1043  POSTGIS_DEBUG(4, "[GIST] 'compress' function complete");
1044  PG_RETURN_POINTER(entry_out);
1045 }
1046 
1047 
1048 /*
1049 ** GiST support function.
1050 ** Decompress an entry. Unused for geography, so we return.
1051 */
1053 Datum gserialized_gist_decompress_2d(PG_FUNCTION_ARGS)
1054 {
1055  POSTGIS_DEBUG(5, "[GIST] 'decompress' function called");
1056  /* We don't decompress. Just return the input. */
1057  PG_RETURN_POINTER(PG_GETARG_POINTER(0));
1058 }
1059 
1060 
1061 
1062 /*
1063 ** GiST support function. Called from gserialized_gist_consistent below.
1064 */
1065 static inline bool gserialized_gist_consistent_leaf_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
1066 {
1067  bool retval;
1068 
1069  POSTGIS_DEBUGF(4, "[GIST] leaf consistent, strategy [%d], count[%i]",
1070  strategy, g2d_counter_leaf++);
1071 
1072  switch (strategy)
1073  {
1074 
1075  /* Basic overlaps */
1076  case RTOverlapStrategyNumber:
1077  retval = (bool) box2df_overlaps(key, query);
1078  break;
1079  case RTSameStrategyNumber:
1080  retval = (bool) box2df_equals(key, query);
1081  break;
1082  case RTContainsStrategyNumber:
1083  case RTOldContainsStrategyNumber:
1084  retval = (bool) box2df_contains(key, query);
1085  break;
1086  case RTContainedByStrategyNumber:
1087  case RTOldContainedByStrategyNumber:
1088  retval = (bool) box2df_contains(query, key);
1089  break;
1090 
1091  /* To one side */
1092  case RTAboveStrategyNumber:
1093  retval = (bool) box2df_above(key, query);
1094  break;
1095  case RTBelowStrategyNumber:
1096  retval = (bool) box2df_below(key, query);
1097  break;
1098  case RTRightStrategyNumber:
1099  retval = (bool) box2df_right(key, query);
1100  break;
1101  case RTLeftStrategyNumber:
1102  retval = (bool) box2df_left(key, query);
1103  break;
1104 
1105  /* Overlapping to one side */
1106  case RTOverAboveStrategyNumber:
1107  retval = (bool) box2df_overabove(key, query);
1108  break;
1109  case RTOverBelowStrategyNumber:
1110  retval = (bool) box2df_overbelow(key, query);
1111  break;
1112  case RTOverRightStrategyNumber:
1113  retval = (bool) box2df_overright(key, query);
1114  break;
1115  case RTOverLeftStrategyNumber:
1116  retval = (bool) box2df_overleft(key, query);
1117  break;
1118 
1119  default:
1120  retval = false;
1121  }
1122 
1123  return (retval);
1124 }
1125 
1126 /*
1127 ** GiST support function. Called from gserialized_gist_consistent below.
1128 */
1129 static inline bool gserialized_gist_consistent_internal_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
1130 {
1131  bool retval;
1132 
1133  POSTGIS_DEBUGF(4, "[GIST] internal consistent, strategy [%d], count[%i], query[%s], key[%s]",
1134  strategy, g2d_counter_internal++, box2df_to_string(query), box2df_to_string(key) );
1135 
1136  switch (strategy)
1137  {
1138 
1139  /* Basic overlaps */
1140  case RTOverlapStrategyNumber:
1141  retval = (bool) box2df_overlaps(key, query);
1142  break;
1143  case RTSameStrategyNumber:
1144  case RTContainsStrategyNumber:
1145  case RTOldContainsStrategyNumber:
1146  retval = (bool) box2df_contains(key, query);
1147  break;
1148  case RTContainedByStrategyNumber:
1149  case RTOldContainedByStrategyNumber:
1150  retval = (bool) box2df_overlaps(key, query);
1151  break;
1152 
1153  /* To one side */
1154  case RTAboveStrategyNumber:
1155  retval = (bool)(!box2df_overbelow(key, query));
1156  break;
1157  case RTBelowStrategyNumber:
1158  retval = (bool)(!box2df_overabove(key, query));
1159  break;
1160  case RTRightStrategyNumber:
1161  retval = (bool)(!box2df_overleft(key, query));
1162  break;
1163  case RTLeftStrategyNumber:
1164  retval = (bool)(!box2df_overright(key, query));
1165  break;
1166 
1167  /* Overlapping to one side */
1168  case RTOverAboveStrategyNumber:
1169  retval = (bool)(!box2df_below(key, query));
1170  break;
1171  case RTOverBelowStrategyNumber:
1172  retval = (bool)(!box2df_above(key, query));
1173  break;
1174  case RTOverRightStrategyNumber:
1175  retval = (bool)(!box2df_left(key, query));
1176  break;
1177  case RTOverLeftStrategyNumber:
1178  retval = (bool)(!box2df_right(key, query));
1179  break;
1180 
1181  default:
1182  retval = false;
1183  }
1184 
1185  return (retval);
1186 }
1187 
1188 /*
1189 ** GiST support function. Take in a query and an entry and see what the
1190 ** relationship is, based on the query strategy.
1191 */
1193 Datum gserialized_gist_consistent_2d(PG_FUNCTION_ARGS)
1194 {
1195  GISTENTRY *entry = (GISTENTRY*) PG_GETARG_POINTER(0);
1196  StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1197  bool result;
1198  BOX2DF query_gbox_index;
1199 
1200  /* PostgreSQL 8.4 and later require the RECHECK flag to be set here,
1201  rather than being supplied as part of the operator class definition */
1202  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1203 
1204  /* We set recheck to false to avoid repeatedly pulling every "possibly matched" geometry
1205  out during index scans. For cases when the geometries are large, rechecking
1206  can make things twice as slow. */
1207  *recheck = false;
1208 
1209  POSTGIS_DEBUG(4, "[GIST] 'consistent' function called");
1210 
1211  /* Quick sanity check on query argument. */
1212  if ( DatumGetPointer(PG_GETARG_DATUM(1)) == NULL )
1213  {
1214  POSTGIS_DEBUG(4, "[GIST] null query pointer (!?!), returning false");
1215  PG_RETURN_BOOL(false); /* NULL query! This is screwy! */
1216  }
1217 
1218  /* Quick sanity check on entry key. */
1219  if ( DatumGetPointer(entry->key) == NULL )
1220  {
1221  POSTGIS_DEBUG(4, "[GIST] null index entry, returning false");
1222  PG_RETURN_BOOL(false); /* NULL entry! */
1223  }
1224 
1225  /* Null box should never make this far. */
1226  if ( gserialized_datum_get_box2df_p(PG_GETARG_DATUM(1), &query_gbox_index) == LW_FAILURE )
1227  {
1228  POSTGIS_DEBUG(4, "[GIST] null query_gbox_index!");
1229  PG_RETURN_BOOL(false);
1230  }
1231 
1232  /* Treat leaf node tests different from internal nodes */
1233  if (GIST_LEAF(entry))
1234  {
1236  (BOX2DF*)DatumGetPointer(entry->key),
1237  &query_gbox_index, strategy);
1238  }
1239  else
1240  {
1242  (BOX2DF*)DatumGetPointer(entry->key),
1243  &query_gbox_index, strategy);
1244  }
1245 
1246  PG_RETURN_BOOL(result);
1247 }
1248 
1249 
1250 /*
1251 ** GiST support function. Take in a query and an entry and return the "distance"
1252 ** between them.
1253 **
1254 ** Given an index entry p and a query value q, this function determines the
1255 ** index entry's "distance" from the query value. This function must be
1256 ** supplied if the operator class contains any ordering operators. A query
1257 ** using the ordering operator will be implemented by returning index entries
1258 ** with the smallest "distance" values first, so the results must be consistent
1259 ** with the operator's semantics. For a leaf index entry the result just
1260 ** represents the distance to the index entry; for an internal tree node, the
1261 ** result must be the smallest distance that any child entry could have.
1262 **
1263 ** Strategy 13 = true distance tests <->
1264 ** Strategy 14 = box-based distance tests <#>
1265 */
1267 Datum gserialized_gist_distance_2d(PG_FUNCTION_ARGS)
1268 {
1269  GISTENTRY *entry = (GISTENTRY*) PG_GETARG_POINTER(0);
1270  BOX2DF query_box;
1271  BOX2DF *entry_box;
1272  StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1273  double distance;
1274 #if POSTGIS_PGSQL_VERSION >= 95
1275  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1276 #endif
1277 
1278  POSTGIS_DEBUG(4, "[GIST] 'distance' function called");
1279 
1280  /* We are using '13' as the gist true-distance <-> strategy number
1281  * and '14' as the gist distance-between-boxes <#> strategy number */
1282  if ( strategy != 13 && strategy != 14 ) {
1283  elog(ERROR, "unrecognized strategy number: %d", strategy);
1284  PG_RETURN_FLOAT8(FLT_MAX);
1285  }
1286 
1287  /* Null box should never make this far. */
1288  if ( gserialized_datum_get_box2df_p(PG_GETARG_DATUM(1), &query_box) == LW_FAILURE )
1289  {
1290  POSTGIS_DEBUG(4, "[GIST] null query_gbox_index!");
1291  PG_RETURN_FLOAT8(FLT_MAX);
1292  }
1293 
1294  /* Get the entry box */
1295  entry_box = (BOX2DF*)DatumGetPointer(entry->key);
1296 
1297 #if POSTGIS_PGSQL_VERSION >= 95
1298 
1299  /* Box-style distance test */
1300  if ( strategy == 14 ) /* operator <#> */
1301  {
1302  distance = box2df_distance(entry_box, &query_box);
1303  }
1304  /* True distance test (formerly centroid distance) */
1305  else if ( strategy == 13 ) /* operator <-> */
1306  {
1307  /* In all cases, since we only have keys (boxes) we'll return */
1308  /* the minimum possible distance, which is the box2df_distance */
1309  /* and let the recheck sort things out in the case of leaves */
1310  distance = box2df_distance(entry_box, &query_box);
1311 
1312  if (GIST_LEAF(entry))
1313  *recheck = true;
1314  }
1315  else
1316  {
1317  elog(ERROR, "%s: reached unreachable code", __func__);
1318  PG_RETURN_NULL();
1319  }
1320 #else
1321  /* Box-style distance test */
1322  if ( strategy == 14 )
1323  {
1324  distance = (double)box2df_distance(entry_box, &query_box);
1325  PG_RETURN_FLOAT8(distance);
1326  }
1327 
1328  /* Treat leaf node tests different from internal nodes */
1329  if (GIST_LEAF(entry))
1330  {
1331  /* Calculate distance to leaves */
1332  distance = (double)box2df_distance_leaf_centroid(entry_box, &query_box);
1333  }
1334  else
1335  {
1336  /* Calculate distance for internal nodes */
1337  distance = (double)box2df_distance_node_centroid(entry_box, &query_box);
1338  }
1339 #endif
1340 
1341  PG_RETURN_FLOAT8(distance);
1342 }
1343 
1344 /*
1345 ** Function to pack floats of different realms
1346 ** This function serves to pack bit flags inside float type
1347 ** Resulted value represent can be from four different "realms"
1348 ** Every value from realm 3 is greater than any value from realms 2, 1 and 0.
1349 ** Every value from realm 2 is less than every value from realm 3 and greater
1350 ** than any value from realm 1 and 0, and so on. Values from the same realm
1351 ** loose two bits of precision. This technique is possible due to floating
1352 ** point numbers specification according to IEEE 754: exponent bits are highest
1353 ** (excluding sign bits, but here penalty is always positive). If float a is
1354 ** greater than float b, integer A with same bit representation as a is greater
1355 ** than integer B with same bits as b.
1356 */
1357 static float pack_float(const float value, const int realm)
1358 {
1359  union {
1360  float f;
1361  struct { unsigned value:31, sign:1; } vbits;
1362  struct { unsigned value:29, realm:2, sign:1; } rbits;
1363  } a;
1364 
1365  a.f = value;
1366  a.rbits.value = a.vbits.value >> 2;
1367  a.rbits.realm = realm;
1368 
1369  return a.f;
1370 }
1371 
1372 /*
1373 ** GiST support function. Calculate the "penalty" cost of adding this entry into an existing entry.
1374 ** Calculate the change in volume of the old entry once the new entry is added.
1375 */
1377 Datum gserialized_gist_penalty_2d(PG_FUNCTION_ARGS)
1378 {
1379  GISTENTRY *origentry = (GISTENTRY*) PG_GETARG_POINTER(0);
1380  GISTENTRY *newentry = (GISTENTRY*) PG_GETARG_POINTER(1);
1381  float *result = (float*) PG_GETARG_POINTER(2);
1382  BOX2DF *gbox_index_orig, *gbox_index_new;
1383  float size_union, size_orig, edge_union, edge_orig;
1384 
1385  POSTGIS_DEBUG(4, "[GIST] 'penalty' function called");
1386 
1387  gbox_index_orig = (BOX2DF*)DatumGetPointer(origentry->key);
1388  gbox_index_new = (BOX2DF*)DatumGetPointer(newentry->key);
1389 
1390  /* Drop out if we're dealing with null inputs. Shouldn't happen. */
1391  if ( (gbox_index_orig == NULL) && (gbox_index_new == NULL) )
1392  {
1393  POSTGIS_DEBUG(4, "[GIST] both inputs NULL! returning penalty of zero");
1394  *result = 0.0;
1395  PG_RETURN_FLOAT8(*result);
1396  }
1397 
1398  /* Calculate the size difference of the boxes. */
1399  size_union = box2df_union_size(gbox_index_orig, gbox_index_new);
1400  size_orig = box2df_size(gbox_index_orig);
1401  *result = size_union - size_orig;
1402 
1403  /* REALM 0: No extension is required, volume is zero, return edge */
1404  /* REALM 1: No extension is required, return nonzero area */
1405  /* REALM 2: Area extension is zero, return nonzero edge extension */
1406  /* REALM 3: Area extension is nonzero, return it */
1407 
1408  if( *result == 0 )
1409  {
1410  if (size_orig > 0)
1411  {
1412  *result = pack_float(size_orig, 1); /* REALM 1 */
1413  }
1414  else
1415  {
1416  edge_union = box2df_union_edge(gbox_index_orig, gbox_index_new);
1417  edge_orig = box2df_edge(gbox_index_orig);
1418  *result = edge_union - edge_orig;
1419  if( *result == 0 )
1420  {
1421  *result = pack_float(edge_orig, 0); /* REALM 0 */
1422  }
1423  else
1424  {
1425  *result = pack_float(*result, 2); /* REALM 2 */
1426  }
1427  }
1428  }
1429  else
1430  {
1431  *result = pack_float(*result, 3); /* REALM 3 */
1432  }
1433 
1434  POSTGIS_DEBUGF(4, "[GIST] 'penalty', union size (%.12f), original size (%.12f), penalty (%.12f)", size_union, size_orig, *result);
1435 
1436  PG_RETURN_POINTER(result);
1437 }
1438 
1439 /*
1440 ** GiST support function. Merge all the boxes in a page into one master box.
1441 */
1443 Datum gserialized_gist_union_2d(PG_FUNCTION_ARGS)
1444 {
1445  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1446  int *sizep = (int *) PG_GETARG_POINTER(1); /* Size of the return value */
1447  int numranges, i;
1448  BOX2DF *box_cur, *box_union;
1449 
1450  POSTGIS_DEBUG(4, "[GIST] 'union' function called");
1451 
1452  numranges = entryvec->n;
1453 
1454  box_cur = (BOX2DF*) DatumGetPointer(entryvec->vector[0].key);
1455 
1456  box_union = box2df_copy(box_cur);
1457 
1458  for ( i = 1; i < numranges; i++ )
1459  {
1460  box_cur = (BOX2DF*) DatumGetPointer(entryvec->vector[i].key);
1461  box2df_merge(box_union, box_cur);
1462  }
1463 
1464  *sizep = sizeof(BOX2DF);
1465 
1466  POSTGIS_DEBUGF(4, "[GIST] 'union', numranges(%i), pageunion %s", numranges, box2df_to_string(box_union));
1467 
1468  PG_RETURN_POINTER(box_union);
1469 
1470 }
1471 
1472 /*
1473 ** GiST support function. Test equality of keys.
1474 */
1476 Datum gserialized_gist_same_2d(PG_FUNCTION_ARGS)
1477 {
1478  BOX2DF *b1 = (BOX2DF*)PG_GETARG_POINTER(0);
1479  BOX2DF *b2 = (BOX2DF*)PG_GETARG_POINTER(1);
1480  bool *result = (bool*)PG_GETARG_POINTER(2);
1481 
1482  POSTGIS_DEBUG(4, "[GIST] 'same' function called");
1483 
1484  *result = box2df_equals(b1, b2);
1485 
1486  PG_RETURN_POINTER(result);
1487 }
1488 
1489 #if KOROTKOV_SPLIT > 0
1490 /*
1491  * Adjust BOX2DF b boundaries with insertion of addon.
1492  */
1493 static void
1494 adjustBox(BOX2DF *b, BOX2DF *addon)
1495 {
1496  if (b->xmax < addon->xmax || isnan(b->xmax))
1497  b->xmax = addon->xmax;
1498  if (b->xmin > addon->xmin || isnan(b->xmin))
1499  b->xmin = addon->xmin;
1500  if (b->ymax < addon->ymax || isnan(b->ymax))
1501  b->ymax = addon->ymax;
1502  if (b->ymin > addon->ymin || isnan(b->ymin))
1503  b->ymin = addon->ymin;
1504 }
1505 
1506 /*
1507  * Trivial split: half of entries will be placed on one page
1508  * and another half - to another
1509  */
1510 static void
1511 fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
1512 {
1513  OffsetNumber i,
1514  maxoff;
1515  BOX2DF *unionL = NULL,
1516  *unionR = NULL;
1517  int nbytes;
1518 
1519  maxoff = entryvec->n - 1;
1520 
1521  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
1522  v->spl_left = (OffsetNumber *) palloc(nbytes);
1523  v->spl_right = (OffsetNumber *) palloc(nbytes);
1524  v->spl_nleft = v->spl_nright = 0;
1525 
1526  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1527  {
1528  BOX2DF *cur = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1529 
1530  if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
1531  {
1532  v->spl_left[v->spl_nleft] = i;
1533  if (unionL == NULL)
1534  {
1535  unionL = (BOX2DF *) palloc(sizeof(BOX2DF));
1536  *unionL = *cur;
1537  }
1538  else
1539  adjustBox(unionL, cur);
1540 
1541  v->spl_nleft++;
1542  }
1543  else
1544  {
1545  v->spl_right[v->spl_nright] = i;
1546  if (unionR == NULL)
1547  {
1548  unionR = (BOX2DF *) palloc(sizeof(BOX2DF));
1549  *unionR = *cur;
1550  }
1551  else
1552  adjustBox(unionR, cur);
1553 
1554  v->spl_nright++;
1555  }
1556  }
1557 
1558  if (v->spl_ldatum_exists)
1559  adjustBox(unionL, (BOX2DF *) DatumGetPointer(v->spl_ldatum));
1560  v->spl_ldatum = BoxPGetDatum(unionL);
1561 
1562  if (v->spl_rdatum_exists)
1563  adjustBox(unionR, (BOX2DF *) DatumGetPointer(v->spl_rdatum));
1564  v->spl_rdatum = BoxPGetDatum(unionR);
1565 
1566  v->spl_ldatum_exists = v->spl_rdatum_exists = false;
1567 }
1568 
1569 /*
1570  * Represents information about an entry that can be placed to either group
1571  * without affecting overlap over selected axis ("common entry").
1572  */
1573 typedef struct
1574 {
1575  /* Index of entry in the initial array */
1576  int index;
1577  /* Delta between penalties of entry insertion into different groups */
1578  float delta;
1579 } CommonEntry;
1580 
1581 /*
1582  * Context for g_box_consider_split. Contains information about currently
1583  * selected split and some general information.
1584  */
1585 typedef struct
1586 {
1587  int entriesCount; /* total number of entries being split */
1588  BOX2DF boundingBox; /* minimum bounding box across all entries */
1589 
1590  /* Information about currently selected split follows */
1591 
1592  bool first; /* true if no split was selected yet */
1593 
1594  float leftUpper; /* upper bound of left interval */
1595  float rightLower; /* lower bound of right interval */
1596 
1597  float4 ratio;
1598  float4 overlap;
1599  int dim; /* axis of this split */
1600  float range; /* width of general MBR projection to the
1601  * selected axis */
1603 
1604 /*
1605  * Interval represents projection of box to axis.
1606  */
1607 typedef struct
1608 {
1609  float lower,
1611 } SplitInterval;
1612 
1613 /*
1614  * Interval comparison function by lower bound of the interval;
1615  */
1616 static int
1617 interval_cmp_lower(const void *i1, const void *i2)
1618 {
1619  float lower1 = ((const SplitInterval *) i1)->lower,
1620  lower2 = ((const SplitInterval *) i2)->lower;
1621 
1622  if (isnan(lower1))
1623  {
1624  if (isnan(lower2))
1625  return 0;
1626  else
1627  return 1;
1628  }
1629  else if (isnan(lower2))
1630  {
1631  return -1;
1632  }
1633  else
1634  {
1635  if (lower1 < lower2)
1636  return -1;
1637  else if (lower1 > lower2)
1638  return 1;
1639  else
1640  return 0;
1641  }
1642 }
1643 
1644 
1645 /*
1646  * Interval comparison function by upper bound of the interval;
1647  */
1648 static int
1649 interval_cmp_upper(const void *i1, const void *i2)
1650 {
1651  float upper1 = ((const SplitInterval *) i1)->upper,
1652  upper2 = ((const SplitInterval *) i2)->upper;
1653 
1654  if (isnan(upper1))
1655  {
1656  if (isnan(upper2))
1657  return 0;
1658  else
1659  return -1;
1660  }
1661  else if (isnan(upper2))
1662  {
1663  return 1;
1664  }
1665  else
1666  {
1667  if (upper1 < upper2)
1668  return -1;
1669  else if (upper1 > upper2)
1670  return 1;
1671  else
1672  return 0;
1673  }
1674 }
1675 
1676 /*
1677  * Replace negative value with zero.
1678  */
1679 static inline float
1680 non_negative(float val)
1681 {
1682  if (val >= 0.0f)
1683  return val;
1684  else
1685  return 0.0f;
1686 }
1687 
1688 /*
1689  * Consider replacement of currently selected split with the better one.
1690  */
1691 static inline void
1693  float rightLower, int minLeftCount,
1694  float leftUpper, int maxLeftCount)
1695 {
1696  int leftCount,
1697  rightCount;
1698  float4 ratio,
1699  overlap;
1700  float range;
1701 
1702  POSTGIS_DEBUGF(5, "consider split: dimNum = %d, rightLower = %f, "
1703  "minLeftCount = %d, leftUpper = %f, maxLeftCount = %d ",
1704  dimNum, rightLower, minLeftCount, leftUpper, maxLeftCount);
1705 
1706  /*
1707  * Calculate entries distribution ratio assuming most uniform distribution
1708  * of common entries.
1709  */
1710  if (minLeftCount >= (context->entriesCount + 1) / 2)
1711  {
1712  leftCount = minLeftCount;
1713  }
1714  else
1715  {
1716  if (maxLeftCount <= context->entriesCount / 2)
1717  leftCount = maxLeftCount;
1718  else
1719  leftCount = context->entriesCount / 2;
1720  }
1721  rightCount = context->entriesCount - leftCount;
1722 
1723  /*
1724  * Ratio of split - quotient between size of lesser group and total
1725  * entries count.
1726  */
1727  ratio = ((float4) Min(leftCount, rightCount)) /
1728  ((float4) context->entriesCount);
1729 
1730  if (ratio > LIMIT_RATIO)
1731  {
1732  bool selectthis = false;
1733 
1734  /*
1735  * The ratio is acceptable, so compare current split with previously
1736  * selected one. Between splits of one dimension we search for minimal
1737  * overlap (allowing negative values) and minimal ration (between same
1738  * overlaps. We switch dimension if find less overlap (non-negative)
1739  * or less range with same overlap.
1740  */
1741  if (dimNum == 0)
1742  range = context->boundingBox.xmax - context->boundingBox.xmin;
1743  else
1744  range = context->boundingBox.ymax - context->boundingBox.ymin;
1745 
1746  overlap = (leftUpper - rightLower) / range;
1747 
1748  /* If there is no previous selection, select this */
1749  if (context->first)
1750  selectthis = true;
1751  else if (context->dim == dimNum)
1752  {
1753  /*
1754  * Within the same dimension, choose the new split if it has a
1755  * smaller overlap, or same overlap but better ratio.
1756  */
1757  if (overlap < context->overlap ||
1758  (overlap == context->overlap && ratio > context->ratio))
1759  selectthis = true;
1760  }
1761  else
1762  {
1763  /*
1764  * Across dimensions, choose the new split if it has a smaller
1765  * *non-negative* overlap, or same *non-negative* overlap but
1766  * bigger range. This condition differs from the one described in
1767  * the article. On the datasets where leaf MBRs don't overlap
1768  * themselves, non-overlapping splits (i.e. splits which have zero
1769  * *non-negative* overlap) are frequently possible. In this case
1770  * splits tends to be along one dimension, because most distant
1771  * non-overlapping splits (i.e. having lowest negative overlap)
1772  * appears to be in the same dimension as in the previous split.
1773  * Therefore MBRs appear to be very prolonged along another
1774  * dimension, which leads to bad search performance. Using range
1775  * as the second split criteria makes MBRs more quadratic. Using
1776  * *non-negative* overlap instead of overlap as the first split
1777  * criteria gives to range criteria a chance to matter, because
1778  * non-overlapping splits are equivalent in this criteria.
1779  */
1780  if (non_negative(overlap) < non_negative(context->overlap) ||
1781  (range > context->range &&
1782  non_negative(overlap) <= non_negative(context->overlap)))
1783  selectthis = true;
1784  }
1785 
1786  if (selectthis)
1787  {
1788  /* save information about selected split */
1789  context->first = false;
1790  context->ratio = ratio;
1791  context->range = range;
1792  context->overlap = overlap;
1793  context->rightLower = rightLower;
1794  context->leftUpper = leftUpper;
1795  context->dim = dimNum;
1796  POSTGIS_DEBUG(5, "split selected");
1797  }
1798  }
1799 }
1800 
1801 /*
1802  * Return increase of original BOX2DF area by new BOX2DF area insertion.
1803  */
1804 static float
1805 box_penalty(BOX2DF *original, BOX2DF *new)
1806 {
1807  float union_width,
1808  union_height;
1809 
1810  union_width = Max(original->xmax, new->xmax) -
1811  Min(original->xmin, new->xmin);
1812  union_height = Max(original->ymax, new->ymax) -
1813  Min(original->ymin, new->ymin);
1814  return union_width * union_height - (original->xmax - original->xmin) *
1815  (original->ymax - original->ymin);
1816 }
1817 
1818 /*
1819  * Compare common entries by their deltas.
1820  */
1821 static int
1822 common_entry_cmp(const void *i1, const void *i2)
1823 {
1824  float delta1 = ((const CommonEntry *) i1)->delta,
1825  delta2 = ((const CommonEntry *) i2)->delta;
1826 
1827  if (delta1 < delta2)
1828  return -1;
1829  else if (delta1 > delta2)
1830  return 1;
1831  else
1832  return 0;
1833 }
1834 
1835 /*
1836  * --------------------------------------------------------------------------
1837  * Double sorting split algorithm. This is used for both boxes and points.
1838  *
1839  * The algorithm finds split of boxes by considering splits along each axis.
1840  * Each entry is first projected as an interval on the X-axis, and different
1841  * ways to split the intervals into two groups are considered, trying to
1842  * minimize the overlap of the groups. Then the same is repeated for the
1843  * Y-axis, and the overall best split is chosen. The quality of a split is
1844  * determined by overlap along that axis and some other criteria (see
1845  * g_box_consider_split).
1846  *
1847  * After that, all the entries are divided into three groups:
1848  *
1849  * 1) Entries which should be placed to the left group
1850  * 2) Entries which should be placed to the right group
1851  * 3) "Common entries" which can be placed to any of groups without affecting
1852  * of overlap along selected axis.
1853  *
1854  * The common entries are distributed by minimizing penalty.
1855  *
1856  * For details see:
1857  * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
1858  * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
1859  * --------------------------------------------------------------------------
1860  */
1862 Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS)
1863 {
1864  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1865  GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
1866  OffsetNumber i,
1867  maxoff;
1868  ConsiderSplitContext context;
1869  BOX2DF *box,
1870  *leftBox,
1871  *rightBox;
1872  int dim,
1873  commonEntriesCount;
1874  SplitInterval *intervalsLower,
1875  *intervalsUpper;
1876  CommonEntry *commonEntries;
1877  int nentries;
1878 
1879  POSTGIS_DEBUG(3, "[GIST] 'picksplit' entered");
1880 
1881  memset(&context, 0, sizeof(ConsiderSplitContext));
1882 
1883  maxoff = entryvec->n - 1;
1884  nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
1885 
1886  /* Allocate arrays for intervals along axes */
1887  intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1888  intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1889 
1890  /*
1891  * Calculate the overall minimum bounding box over all the entries.
1892  */
1893  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1894  {
1895  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1896  if (i == FirstOffsetNumber)
1897  context.boundingBox = *box;
1898  else
1899  adjustBox(&context.boundingBox, box);
1900  }
1901 
1902  POSTGIS_DEBUGF(4, "boundingBox is %s", box2df_to_string(
1903  &context.boundingBox));
1904 
1905  /*
1906  * Iterate over axes for optimal split searching.
1907  */
1908  context.first = true; /* nothing selected yet */
1909  for (dim = 0; dim < 2; dim++)
1910  {
1911  float leftUpper,
1912  rightLower;
1913  int i1,
1914  i2;
1915 
1916  /* Project each entry as an interval on the selected axis. */
1917  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1918  {
1919  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1920  if (dim == 0)
1921  {
1922  intervalsLower[i - FirstOffsetNumber].lower = box->xmin;
1923  intervalsLower[i - FirstOffsetNumber].upper = box->xmax;
1924  }
1925  else
1926  {
1927  intervalsLower[i - FirstOffsetNumber].lower = box->ymin;
1928  intervalsLower[i - FirstOffsetNumber].upper = box->ymax;
1929  }
1930  }
1931 
1932  /*
1933  * Make two arrays of intervals: one sorted by lower bound and another
1934  * sorted by upper bound.
1935  */
1936  memcpy(intervalsUpper, intervalsLower,
1937  sizeof(SplitInterval) * nentries);
1938  qsort(intervalsLower, nentries, sizeof(SplitInterval),
1940  qsort(intervalsUpper, nentries, sizeof(SplitInterval),
1942 
1943  /*----
1944  * The goal is to form a left and right interval, so that every entry
1945  * interval is contained by either left or right interval (or both).
1946  *
1947  * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
1948  *
1949  * 0 1 2 3 4
1950  * +-+
1951  * +---+
1952  * +-+
1953  * +---+
1954  *
1955  * The left and right intervals are of the form (0,a) and (b,4).
1956  * We first consider splits where b is the lower bound of an entry.
1957  * We iterate through all entries, and for each b, calculate the
1958  * smallest possible a. Then we consider splits where a is the
1959  * upper bound of an entry, and for each a, calculate the greatest
1960  * possible b.
1961  *
1962  * In the above example, the first loop would consider splits:
1963  * b=0: (0,1)-(0,4)
1964  * b=1: (0,1)-(1,4)
1965  * b=2: (0,3)-(2,4)
1966  *
1967  * And the second loop:
1968  * a=1: (0,1)-(1,4)
1969  * a=3: (0,3)-(2,4)
1970  * a=4: (0,4)-(2,4)
1971  */
1972 
1973  /*
1974  * Iterate over lower bound of right group, finding smallest possible
1975  * upper bound of left group.
1976  */
1977  i1 = 0;
1978  i2 = 0;
1979  rightLower = intervalsLower[i1].lower;
1980  leftUpper = intervalsUpper[i2].lower;
1981  while (true)
1982  {
1983  /*
1984  * Find next lower bound of right group.
1985  */
1986  while (i1 < nentries && (rightLower == intervalsLower[i1].lower ||
1987  isnan(intervalsLower[i1].lower)))
1988  {
1989  leftUpper = Max(leftUpper, intervalsLower[i1].upper);
1990  i1++;
1991  }
1992  if (i1 >= nentries)
1993  break;
1994  rightLower = intervalsLower[i1].lower;
1995 
1996  /*
1997  * Find count of intervals which anyway should be placed to the
1998  * left group.
1999  */
2000  while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
2001  i2++;
2002 
2003  /*
2004  * Consider found split.
2005  */
2006  g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
2007  }
2008 
2009  /*
2010  * Iterate over upper bound of left group finding greatest possible
2011  * lower bound of right group.
2012  */
2013  i1 = nentries - 1;
2014  i2 = nentries - 1;
2015  rightLower = intervalsLower[i1].upper;
2016  leftUpper = intervalsUpper[i2].upper;
2017  while (true)
2018  {
2019  /*
2020  * Find next upper bound of left group.
2021  */
2022  while (i2 >= 0 && (leftUpper == intervalsUpper[i2].upper ||
2023  isnan(intervalsUpper[i2].upper)))
2024  {
2025  rightLower = Min(rightLower, intervalsUpper[i2].lower);
2026  i2--;
2027  }
2028  if (i2 < 0)
2029  break;
2030  leftUpper = intervalsUpper[i2].upper;
2031 
2032  /*
2033  * Find count of intervals which anyway should be placed to the
2034  * right group.
2035  */
2036  while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
2037  i1--;
2038 
2039  /*
2040  * Consider found split.
2041  */
2042  g_box_consider_split(&context, dim,
2043  rightLower, i1 + 1, leftUpper, i2 + 1);
2044  }
2045  }
2046 
2047  /*
2048  * If we failed to find any acceptable splits, use trivial split.
2049  */
2050  if (context.first)
2051  {
2052  POSTGIS_DEBUG(4, "no acceptable splits, trivial split");
2053  fallbackSplit(entryvec, v);
2054  PG_RETURN_POINTER(v);
2055  }
2056 
2057  /*
2058  * Ok, we have now selected the split across one axis.
2059  *
2060  * While considering the splits, we already determined that there will be
2061  * enough entries in both groups to reach the desired ratio, but we did
2062  * not memorize which entries go to which group. So determine that now.
2063  */
2064 
2065  POSTGIS_DEBUGF(4, "split direction: %d", context.dim);
2066 
2067  /* Allocate vectors for results */
2068  v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
2069  v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
2070  v->spl_nleft = 0;
2071  v->spl_nright = 0;
2072 
2073  /* Allocate bounding boxes of left and right groups */
2074  leftBox = palloc0(sizeof(BOX2DF));
2075  rightBox = palloc0(sizeof(BOX2DF));
2076 
2077  /*
2078  * Allocate an array for "common entries" - entries which can be placed to
2079  * either group without affecting overlap along selected axis.
2080  */
2081  commonEntriesCount = 0;
2082  commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
2083 
2084  /* Helper macros to place an entry in the left or right group */
2085 #define PLACE_LEFT(box, off) \
2086  do { \
2087  if (v->spl_nleft > 0) \
2088  adjustBox(leftBox, box); \
2089  else \
2090  *leftBox = *(box); \
2091  v->spl_left[v->spl_nleft++] = off; \
2092  } while(0)
2093 
2094 #define PLACE_RIGHT(box, off) \
2095  do { \
2096  if (v->spl_nright > 0) \
2097  adjustBox(rightBox, box); \
2098  else \
2099  *rightBox = *(box); \
2100  v->spl_right[v->spl_nright++] = off; \
2101  } while(0)
2102 
2103  /*
2104  * Distribute entries which can be distributed unambiguously, and collect
2105  * common entries.
2106  */
2107  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2108  {
2109  float lower,
2110  upper;
2111 
2112  /*
2113  * Get upper and lower bounds along selected axis.
2114  */
2115  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
2116  if (context.dim == 0)
2117  {
2118  lower = box->xmin;
2119  upper = box->xmax;
2120  }
2121  else
2122  {
2123  lower = box->ymin;
2124  upper = box->ymax;
2125  }
2126 
2127  if (upper <= context.leftUpper || isnan(upper))
2128  {
2129  /* Fits to the left group */
2130  if (lower >= context.rightLower || isnan(lower))
2131  {
2132  /* Fits also to the right group, so "common entry" */
2133  commonEntries[commonEntriesCount++].index = i;
2134  }
2135  else
2136  {
2137  /* Doesn't fit to the right group, so join to the left group */
2138  PLACE_LEFT(box, i);
2139  }
2140  }
2141  else
2142  {
2143  /*
2144  * Each entry should fit on either left or right group. Since this
2145  * entry didn't fit on the left group, it better fit in the right
2146  * group.
2147  */
2148  Assert(lower >= context.rightLower);
2149 
2150  /* Doesn't fit to the left group, so join to the right group */
2151  PLACE_RIGHT(box, i);
2152  }
2153  }
2154 
2155  POSTGIS_DEBUGF(4, "leftBox is %s", box2df_to_string(leftBox));
2156  POSTGIS_DEBUGF(4, "rightBox is %s", box2df_to_string(rightBox));
2157 
2158  /*
2159  * Distribute "common entries", if any.
2160  */
2161  if (commonEntriesCount > 0)
2162  {
2163  /*
2164  * Calculate minimum number of entries that must be placed in both
2165  * groups, to reach LIMIT_RATIO.
2166  */
2167  int m = ceil(LIMIT_RATIO * (double) nentries);
2168 
2169  /*
2170  * Calculate delta between penalties of join "common entries" to
2171  * different groups.
2172  */
2173  for (i = 0; i < commonEntriesCount; i++)
2174  {
2175  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
2176  commonEntries[i].index].key);
2177  commonEntries[i].delta = Abs(box_penalty(leftBox, box) -
2178  box_penalty(rightBox, box));
2179  }
2180 
2181  /*
2182  * Sort "common entries" by calculated deltas in order to distribute
2183  * the most ambiguous entries first.
2184  */
2185  qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
2186 
2187  /*
2188  * Distribute "common entries" between groups.
2189  */
2190  for (i = 0; i < commonEntriesCount; i++)
2191  {
2192  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
2193  commonEntries[i].index].key);
2194 
2195  /*
2196  * Check if we have to place this entry in either group to achieve
2197  * LIMIT_RATIO.
2198  */
2199  if (v->spl_nleft + (commonEntriesCount - i) <= m)
2200  PLACE_LEFT(box, commonEntries[i].index);
2201  else if (v->spl_nright + (commonEntriesCount - i) <= m)
2202  PLACE_RIGHT(box, commonEntries[i].index);
2203  else
2204  {
2205  /* Otherwise select the group by minimal penalty */
2206  if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
2207  PLACE_LEFT(box, commonEntries[i].index);
2208  else
2209  PLACE_RIGHT(box, commonEntries[i].index);
2210  }
2211  }
2212  }
2213  v->spl_ldatum = PointerGetDatum(leftBox);
2214  v->spl_rdatum = PointerGetDatum(rightBox);
2215 
2216  POSTGIS_DEBUG(4, "[GIST] 'picksplit' completed");
2217 
2218  PG_RETURN_POINTER(v);
2219 }
2220 
2221 #else /* !KOROTOV_SPLIT */
2222 
2223 typedef struct
2224 {
2225  BOX2DF *key;
2226  int pos;
2227 }
2228 KBsort;
2229 
2230 static int
2231 compare_KB(const void* a, const void* b)
2232 {
2233  BOX2DF *abox = ((KBsort*)a)->key;
2234  BOX2DF *bbox = ((KBsort*)b)->key;
2235  float sa = (abox->xmax - abox->xmin) * (abox->ymax - abox->ymin);
2236  float sb = (bbox->xmax - bbox->xmin) * (bbox->ymax - bbox->ymin);
2237 
2238  if ( sa==sb ) return 0;
2239  return ( sa>sb ) ? 1 : -1;
2240 }
2241 
2248 Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS)
2249 {
2250  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
2251 
2252  GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
2253  OffsetNumber i;
2254  OffsetNumber *listL, *listR, *listB, *listT;
2255  BOX2DF *unionL, *unionR, *unionB, *unionT;
2256  int posL, posR, posB, posT;
2257  BOX2DF pageunion;
2258  BOX2DF *cur;
2259  char direction = ' ';
2260  bool allisequal = true;
2261  OffsetNumber maxoff;
2262  int nbytes;
2263 
2264  POSTGIS_DEBUG(3, "[GIST] 'picksplit' entered");
2265 
2266  posL = posR = posB = posT = 0;
2267 
2268  maxoff = entryvec->n - 1;
2269  cur = (BOX2DF*) DatumGetPointer(entryvec->vector[FirstOffsetNumber].key);
2270 
2271  memcpy((void *) &pageunion, (void *) cur, sizeof(BOX2DF));
2272 
2273  /* find MBR */
2274  for (i = OffsetNumberNext(FirstOffsetNumber); i <= maxoff; i = OffsetNumberNext(i))
2275  {
2276  cur = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
2277 
2278  if ( allisequal == true && (
2279  pageunion.xmax != cur->xmax ||
2280  pageunion.ymax != cur->ymax ||
2281  pageunion.xmin != cur->xmin ||
2282  pageunion.ymin != cur->ymin
2283  ) )
2284  allisequal = false;
2285 
2286  if (pageunion.xmax < cur->xmax)
2287  pageunion.xmax = cur->xmax;
2288  if (pageunion.xmin > cur->xmin)
2289  pageunion.xmin = cur->xmin;
2290  if (pageunion.ymax < cur->ymax)
2291  pageunion.ymax = cur->ymax;
2292  if (pageunion.ymin > cur->ymin)
2293  pageunion.ymin = cur->ymin;
2294  }
2295 
2296  POSTGIS_DEBUGF(4, "pageunion is %s", box2df_to_string(&pageunion));
2297 
2298  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
2299  listL = (OffsetNumber *) palloc(nbytes);
2300  listR = (OffsetNumber *) palloc(nbytes);
2301  unionL = (BOX2DF *) palloc(sizeof(BOX2DF));
2302  unionR = (BOX2DF *) palloc(sizeof(BOX2DF));
2303 
2304  if (allisequal)
2305  {
2306  POSTGIS_DEBUG(4, " AllIsEqual!");
2307 
2308  cur = (BOX2DF*) DatumGetPointer(entryvec->vector[OffsetNumberNext(FirstOffsetNumber)].key);
2309 
2310 
2311  if (memcmp((void *) cur, (void *) &pageunion, sizeof(BOX2DF)) == 0)
2312  {
2313  v->spl_left = listL;
2314  v->spl_right = listR;
2315  v->spl_nleft = v->spl_nright = 0;
2316  memcpy((void *) unionL, (void *) &pageunion, sizeof(BOX2DF));
2317  memcpy((void *) unionR, (void *) &pageunion, sizeof(BOX2DF));
2318 
2319  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2320  {
2321  if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
2322  {
2323  v->spl_left[v->spl_nleft] = i;
2324  v->spl_nleft++;
2325  }
2326  else
2327  {
2328  v->spl_right[v->spl_nright] = i;
2329  v->spl_nright++;
2330  }
2331  }
2332  v->spl_ldatum = PointerGetDatum(unionL);
2333  v->spl_rdatum = PointerGetDatum(unionR);
2334 
2335  PG_RETURN_POINTER(v);
2336  }
2337  }
2338 
2339  listB = (OffsetNumber *) palloc(nbytes);
2340  listT = (OffsetNumber *) palloc(nbytes);
2341  unionB = (BOX2DF *) palloc(sizeof(BOX2DF));
2342  unionT = (BOX2DF *) palloc(sizeof(BOX2DF));
2343 
2344 #define ADDLIST( list, unionD, pos, num ) do { \
2345  if ( pos ) { \
2346  if ( unionD->xmax < cur->xmax ) unionD->xmax = cur->xmax; \
2347  if ( unionD->xmin > cur->xmin ) unionD->xmin = cur->xmin; \
2348  if ( unionD->ymax < cur->ymax ) unionD->ymax = cur->ymax; \
2349  if ( unionD->ymin > cur->ymin ) unionD->ymin = cur->ymin; \
2350  } else { \
2351  memcpy( (void*)unionD, (void*) cur, sizeof( BOX2DF ) ); \
2352  } \
2353  list[pos] = num; \
2354  (pos)++; \
2355 } while(0)
2356 
2357  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2358  {
2359  cur = (BOX2DF*) DatumGetPointer(entryvec->vector[i].key);
2360 
2361  if (cur->xmin - pageunion.xmin < pageunion.xmax - cur->xmax)
2362  ADDLIST(listL, unionL, posL,i);
2363  else
2364  ADDLIST(listR, unionR, posR,i);
2365  if (cur->ymin - pageunion.ymin < pageunion.ymax - cur->ymax)
2366  ADDLIST(listB, unionB, posB,i);
2367  else
2368  ADDLIST(listT, unionT, posT,i);
2369  }
2370 
2371  POSTGIS_DEBUGF(4, "unionL is %s", box2df_to_string(unionL));
2372  POSTGIS_DEBUGF(4, "unionR is %s", box2df_to_string(unionR));
2373  POSTGIS_DEBUGF(4, "unionT is %s", box2df_to_string(unionT));
2374  POSTGIS_DEBUGF(4, "unionB is %s", box2df_to_string(unionB));
2375 
2376  /* bad disposition, sort by ascending and resplit */
2377  if ( (posR==0 || posL==0) && (posT==0 || posB==0) )
2378  {
2379  KBsort *arr = (KBsort*)palloc( sizeof(KBsort) * maxoff );
2380  posL = posR = posB = posT = 0;
2381  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2382  {
2383  arr[i-1].key = (BOX2DF*) DatumGetPointer(entryvec->vector[i].key);
2384  arr[i-1].pos = i;
2385  }
2386  qsort( arr, maxoff, sizeof(KBsort), compare_KB );
2387  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2388  {
2389  cur = arr[i-1].key;
2390  if (cur->xmin - pageunion.xmin < pageunion.xmax - cur->xmax)
2391  ADDLIST(listL, unionL, posL,arr[i-1].pos);
2392  else if ( cur->xmin - pageunion.xmin == pageunion.xmax - cur->xmax )
2393  {
2394  if ( posL>posR )
2395  ADDLIST(listR, unionR, posR,arr[i-1].pos);
2396  else
2397  ADDLIST(listL, unionL, posL,arr[i-1].pos);
2398  }
2399  else
2400  ADDLIST(listR, unionR, posR,arr[i-1].pos);
2401 
2402  if (cur->ymin - pageunion.ymin < pageunion.ymax - cur->ymax)
2403  ADDLIST(listB, unionB, posB,arr[i-1].pos);
2404  else if ( cur->ymin - pageunion.ymin == pageunion.ymax - cur->ymax )
2405  {
2406  if ( posB>posT )
2407  ADDLIST(listT, unionT, posT,arr[i-1].pos);
2408  else
2409  ADDLIST(listB, unionB, posB,arr[i-1].pos);
2410  }
2411  else
2412  ADDLIST(listT, unionT, posT,arr[i-1].pos);
2413  }
2414  pfree(arr);
2415  }
2416 
2417  /* which split more optimal? */
2418  if (Max(posL, posR) < Max(posB, posT))
2419  direction = 'x';
2420  else if (Max(posL, posR) > Max(posB, posT))
2421  direction = 'y';
2422  else
2423  {
2424  float sizeLR, sizeBT;
2425  BOX2DF interLR, interBT;
2426 
2427  if ( box2df_intersection(unionL, unionR, &interLR) == false )
2428  sizeLR = 0.0;
2429  else
2430  sizeLR = box2df_size(&interLR);
2431 
2432  if ( box2df_intersection(unionB, unionT, &interBT) == false )
2433  sizeBT = 0.0;
2434  else
2435  sizeBT = box2df_size(&interBT);
2436 
2437  if (sizeLR < sizeBT)
2438  direction = 'x';
2439  else
2440  direction = 'y';
2441  }
2442 
2443  POSTGIS_DEBUGF(4, "split direction '%c'", direction);
2444 
2445  if (direction == 'x')
2446  {
2447  pfree(unionB);
2448  pfree(listB);
2449  pfree(unionT);
2450  pfree(listT);
2451 
2452  v->spl_left = listL;
2453  v->spl_right = listR;
2454  v->spl_nleft = posL;
2455  v->spl_nright = posR;
2456  v->spl_ldatum = PointerGetDatum(unionL);
2457  v->spl_rdatum = PointerGetDatum(unionR);
2458  }
2459  else
2460  {
2461  pfree(unionR);
2462  pfree(listR);
2463  pfree(unionL);
2464  pfree(listL);
2465 
2466  v->spl_left = listB;
2467  v->spl_right = listT;
2468  v->spl_nleft = posB;
2469  v->spl_nright = posT;
2470  v->spl_ldatum = PointerGetDatum(unionB);
2471  v->spl_rdatum = PointerGetDatum(unionT);
2472  }
2473 
2474  POSTGIS_DEBUG(4, "[GIST] 'picksplit' completed");
2475 
2476  PG_RETURN_POINTER(v);
2477 }
2478 
2479 #endif
2480 
2481 
2482 /*
2483 ** The BOX32DF key must be defined as a PostgreSQL type, even though it is only
2484 ** ever used internally. These no-op stubs are used to bind the type.
2485 */
2487 Datum box2df_in(PG_FUNCTION_ARGS)
2488 {
2489  ereport(ERROR,(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2490  errmsg("function box2df_in not implemented")));
2491  PG_RETURN_POINTER(NULL);
2492 }
2493 
2495 Datum box2df_out(PG_FUNCTION_ARGS)
2496 {
2497  BOX2DF *box = (BOX2DF *) PG_GETARG_POINTER(0);
2498  char *result = box2df_to_string(box);
2499  PG_RETURN_CSTRING(result);
2500 }
void gbox_init(GBOX *gbox)
Zero out all the entries in the GBOX.
Definition: g_box.c:47
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:640
bool box2df_left(const BOX2DF *a, const BOX2DF *b)
static char * box2df_to_string(const BOX2DF *a)
void box2df_merge(BOX2DF *b_union, BOX2DF *b_new)
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
static float box2df_size(const BOX2DF *a)
Datum gserialized_overbelow_2d(PG_FUNCTION_ARGS)
void box2df_set_empty(BOX2DF *a)
Datum gserialized_gist_same_2d(PG_FUNCTION_ARGS)
static float box2df_union_size(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_contains_box2df_geom_2d(PG_FUNCTION_ARGS)
bool box2df_is_empty(const BOX2DF *a)
static float pack_float(const float value, const int realm)
static int gserialized_datum_predicate_2d(Datum gs1, Datum gs2, box2df_predicate predicate)
Support function.
Datum gserialized_within_2d(PG_FUNCTION_ARGS)
PG_FUNCTION_INFO_V1(gserialized_contains_box2df_geom_2d)
Datum box2df_out(PG_FUNCTION_ARGS)
Datum gserialized_within_box2df_geom_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_penalty_2d(PG_FUNCTION_ARGS)
Datum gserialized_left_2d(PG_FUNCTION_ARGS)
Datum gserialized_contains_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_consistent_2d(PG_FUNCTION_ARGS)
static int interval_cmp_upper(const void *i1, const void *i2)
Datum gserialized_distance_box_2d(PG_FUNCTION_ARGS)
bool box2df_equals(const BOX2DF *a, const BOX2DF *b)
#define LIMIT_RATIO
bool box2df_contains(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_gist_union_2d(PG_FUNCTION_ARGS)
#define PLACE_RIGHT(box, off)
Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS)
Datum gserialized_distance_centroid_2d(PG_FUNCTION_ARGS)
Datum gserialized_contains_box2df_box2df_2d(PG_FUNCTION_ARGS)
static float box2df_union_edge(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_overlaps_2d(PG_FUNCTION_ARGS)
Datum gserialized_overlaps_box2df_geom_2d(PG_FUNCTION_ARGS)
Datum gserialized_within_box2df_box2df_2d(PG_FUNCTION_ARGS)
bool box2df_right(const BOX2DF *a, const BOX2DF *b)
bool box2df_overlaps(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_overleft_2d(PG_FUNCTION_ARGS)
void box2df_set_finite(BOX2DF *a)
static float box_penalty(BOX2DF *original, BOX2DF *new)
static bool gserialized_gist_consistent_internal_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
Datum gserialized_overlaps_box2df_box2df_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_distance_2d(PG_FUNCTION_ARGS)
Datum gserialized_overright_2d(PG_FUNCTION_ARGS)
static bool box2df_within(const BOX2DF *a, const BOX2DF *b)
bool box2df_above(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_right_2d(PG_FUNCTION_ARGS)
bool box2df_overbelow(const BOX2DF *a, const BOX2DF *b)
bool(* box2df_predicate)(const BOX2DF *a, const BOX2DF *b)
static double box2df_distance(const BOX2DF *a, const BOX2DF *b)
Calculate the box->box distance.
static double box2df_distance_leaf_centroid(const BOX2DF *a, const BOX2DF *b)
Calculate the centroid->centroid distance between the boxes.
Datum gserialized_below_2d(PG_FUNCTION_ARGS)
Datum gserialized_overabove_2d(PG_FUNCTION_ARGS)
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, float rightLower, int minLeftCount, float leftUpper, int maxLeftCount)
static float box2df_edge(const BOX2DF *a)
int box2df_to_gbox_p(BOX2DF *a, GBOX *box)
static int interval_cmp_lower(const void *i1, const void *i2)
bool box2df_overright(const BOX2DF *a, const BOX2DF *b)
static double pt_distance(double ax, double ay, double bx, double by)
static int common_entry_cmp(const void *i1, const void *i2)
Datum gserialized_gist_decompress_2d(PG_FUNCTION_ARGS)
int gserialized_datum_get_box2df_p(Datum gsdatum, BOX2DF *box2df)
Peak into a GSERIALIZED datum to find the bounding box.
static int box2df_from_gbox_p(GBOX *box, BOX2DF *a)
bool box2df_overabove(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS)
#define PLACE_LEFT(box, off)
void box2df_validate(BOX2DF *b)
bool box2df_below(const BOX2DF *a, const BOX2DF *b)
static bool gserialized_gist_consistent_leaf_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
bool box2df_overleft(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_above_2d(PG_FUNCTION_ARGS)
static int gserialized_datum_predicate_box2df_geom_2d(const BOX2DF *br1, Datum gs2, box2df_predicate predicate)
BOX2DF * box2df_copy(BOX2DF *b)
Datum gserialized_same_2d(PG_FUNCTION_ARGS)
Datum box2df_in(PG_FUNCTION_ARGS)
static void adjustBox(BOX2DF *b, BOX2DF *addon)
static float non_negative(float val)
#define LW_FALSE
Definition: liblwgeom.h:77
#define LW_FAILURE
Definition: liblwgeom.h:79
#define LW_SUCCESS
Definition: liblwgeom.h:80
#define FLAGS_GET_BBOX(flags)
Definition: liblwgeom.h:142
float next_float_up(double d)
Definition: lwgeom_api.c:73
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:76
float next_float_down(double d)
Definition: lwgeom_api.c:52
This library is the generic geometry handling section of PostGIS.
#define NAN
Definition: lwgeodetic.h:37
Datum distance(PG_FUNCTION_ARGS)
int value
Definition: genraster.py:61
double ymax
Definition: liblwgeom.h:298
double xmax
Definition: liblwgeom.h:296
double ymin
Definition: liblwgeom.h:297
double xmin
Definition: liblwgeom.h:295
uint8_t flags
Definition: liblwgeom.h:386
uint8_t data[1]
Definition: liblwgeom.h:387
unsigned char uint8_t
Definition: uthash.h:79