PostGIS  2.5.0dev-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 static inline void box2df_set_empty(BOX2DF *a)
165 {
166  a->xmin = a->xmax = a->ymin = a->ymax = NAN;
167  return;
168 }
169 
170 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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 static 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
504 
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  ** Because geometry is declared as "storage = main" anything large
653  ** enough to take serious advantage of PG_DETOAST_DATUM_SLICE will have
654  ** already been compressed, which means the entire object will be
655  ** fetched and decompressed before a slice is taken, thus removing
656  ** any efficiencies gained from slicing. We need to move to
657  ** "storage = external" and implement our own geometry compressor
658  ** before we can take advantage of sliced retrieval.
659  */
660  gpart = (GSERIALIZED*)PG_DETOAST_DATUM(gsdatum);
661  flags = gpart->flags;
662 
663  POSTGIS_DEBUGF(4, "got flags %d", gpart->flags);
664 
665  /* Do we even have a serialized bounding box? */
666  if ( FLAGS_GET_BBOX(flags) )
667  {
668  /* Yes! Copy it out into the box! */
669  POSTGIS_DEBUG(4, "copying box out of serialization");
670  memcpy(box2df, gpart->data, sizeof(BOX2DF));
671  result = LW_SUCCESS;
672  }
673  else
674  {
675  /* No, we need to calculate it from the full object. */
676  GBOX gbox;
677  gbox_init(&gbox);
678 
679  result = gserialized_get_gbox_p(gpart, &gbox);
680  if ( result == LW_SUCCESS )
681  {
682  result = box2df_from_gbox_p(&gbox, box2df);
683  }
684  else
685  {
686  POSTGIS_DEBUG(4, "could not calculate bbox");
687  }
688  }
689 
690  POSTGIS_FREE_IF_COPY_P(gpart, gsdatum);
691  POSTGIS_DEBUGF(4, "result = %d, got box2df %s", result, result == LW_SUCCESS ? box2df_to_string(box2df) : "NONE");
692 
693  return result;
694 }
695 
696 
701 static int
702 gserialized_datum_predicate_2d(Datum gs1, Datum gs2, box2df_predicate predicate)
703 {
704  BOX2DF b1, b2, *br1=NULL, *br2=NULL;
705  POSTGIS_DEBUG(3, "entered function");
706 
707  if (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) br1 = &b1;
708  if (gserialized_datum_get_box2df_p(gs2, &b2) == LW_SUCCESS) br2 = &b2;
709 
710  if ( predicate(br1, br2) )
711  {
712  POSTGIS_DEBUGF(3, "got boxes %s and %s", br1 ? box2df_to_string(&b1) : "(null)", br2 ? box2df_to_string(&b2) : "(null)");
713  return LW_TRUE;
714  }
715  return LW_FALSE;
716 }
717 
718 #if POSTGIS_PGSQL_VERSION > 94
719 static int
720 gserialized_datum_predicate_box2df_geom_2d(const BOX2DF *br1, Datum gs2, box2df_predicate predicate)
721 {
722  BOX2DF b2, *br2=NULL;
723  POSTGIS_DEBUG(3, "entered function");
724 
725  if (gserialized_datum_get_box2df_p(gs2, &b2) == LW_SUCCESS) br2 = &b2;
726 
727  if ( predicate(br1, br2) )
728  {
729  POSTGIS_DEBUGF(3, "got boxes %s", br2 ? box2df_to_string(&b2) : "(null)");
730  return LW_TRUE;
731  }
732  return LW_FALSE;
733 }
734 
735 /***********************************************************************
736 * BRIN 2-D Index Operator Functions
737 */
738 
740 Datum gserialized_contains_box2df_geom_2d(PG_FUNCTION_ARGS)
741 {
742  POSTGIS_DEBUG(3, "entered function");
743  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_contains) == LW_TRUE )
744  PG_RETURN_BOOL(true);
745 
746  PG_RETURN_BOOL(false);
747 }
748 
751 {
752  if ( box2df_contains((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
753  PG_RETURN_BOOL(true);
754 
755  PG_RETURN_BOOL(false);
756 }
757 
759 Datum gserialized_within_box2df_geom_2d(PG_FUNCTION_ARGS)
760 {
761  POSTGIS_DEBUG(3, "entered function");
762  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_within) == LW_TRUE )
763  PG_RETURN_BOOL(true);
764 
765  PG_RETURN_BOOL(false);
766 }
767 
769 Datum gserialized_within_box2df_box2df_2d(PG_FUNCTION_ARGS)
770 {
771  if ( box2df_within((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
772  PG_RETURN_BOOL(true);
773 
774  PG_RETURN_BOOL(false);
775 }
776 
778 Datum gserialized_overlaps_box2df_geom_2d(PG_FUNCTION_ARGS)
779 {
780  POSTGIS_DEBUG(3, "entered function");
781  if ( gserialized_datum_predicate_box2df_geom_2d((BOX2DF*)PG_GETARG_POINTER(0), PG_GETARG_DATUM(1), box2df_overlaps) == LW_TRUE )
782  PG_RETURN_BOOL(true);
783 
784  PG_RETURN_BOOL(false);
785 }
786 
789 {
790  if ( box2df_overlaps((BOX2DF *)PG_GETARG_POINTER(0), (BOX2DF *)PG_GETARG_POINTER(1)))
791  PG_RETURN_BOOL(true);
792 
793  PG_RETURN_BOOL(false);
794 }
795 #endif
796 
797 /***********************************************************************
798 * GiST 2-D Index Operator Functions
799 */
800 
802 Datum gserialized_distance_centroid_2d(PG_FUNCTION_ARGS)
803 {
804  BOX2DF b1, b2;
805  Datum gs1 = PG_GETARG_DATUM(0);
806  Datum gs2 = PG_GETARG_DATUM(1);
807 
808  POSTGIS_DEBUG(3, "entered function");
809 
810  /* Must be able to build box for each argument (ie, not empty geometry). */
811  if ( (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) &&
813  {
814  double distance = box2df_distance_leaf_centroid(&b1, &b2);
815  POSTGIS_DEBUGF(3, "got boxes %s and %s", box2df_to_string(&b1), box2df_to_string(&b2));
816  PG_RETURN_FLOAT8(distance);
817  }
818  PG_RETURN_FLOAT8(FLT_MAX);
819 }
820 
822 Datum gserialized_distance_box_2d(PG_FUNCTION_ARGS)
823 {
824  BOX2DF b1, b2;
825  Datum gs1 = PG_GETARG_DATUM(0);
826  Datum gs2 = PG_GETARG_DATUM(1);
827 
828  POSTGIS_DEBUG(3, "entered function");
829 
830  /* Must be able to build box for each argument (ie, not empty geometry). */
831  if ( (gserialized_datum_get_box2df_p(gs1, &b1) == LW_SUCCESS) &&
833  {
834  double distance = box2df_distance(&b1, &b2);
835  POSTGIS_DEBUGF(3, "got boxes %s and %s", box2df_to_string(&b1), box2df_to_string(&b2));
836  PG_RETURN_FLOAT8(distance);
837  }
838  PG_RETURN_FLOAT8(FLT_MAX);
839 }
840 
842 Datum gserialized_same_2d(PG_FUNCTION_ARGS)
843 {
844  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_equals) == LW_TRUE )
845  PG_RETURN_BOOL(true);
846 
847  PG_RETURN_BOOL(false);
848 }
849 
851 Datum gserialized_within_2d(PG_FUNCTION_ARGS)
852 {
853  POSTGIS_DEBUG(3, "entered function");
854  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_within) == LW_TRUE )
855  PG_RETURN_BOOL(true);
856 
857  PG_RETURN_BOOL(false);
858 }
859 
861 Datum gserialized_contains_2d(PG_FUNCTION_ARGS)
862 {
863  POSTGIS_DEBUG(3, "entered function");
864  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_contains) == LW_TRUE )
865  PG_RETURN_BOOL(true);
866 
867  PG_RETURN_BOOL(false);
868 }
869 
871 Datum gserialized_overlaps_2d(PG_FUNCTION_ARGS)
872 {
873  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overlaps) == LW_TRUE )
874  PG_RETURN_BOOL(true);
875 
876  PG_RETURN_BOOL(false);
877 }
878 
880 Datum gserialized_left_2d(PG_FUNCTION_ARGS)
881 {
882  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_left) == LW_TRUE )
883  PG_RETURN_BOOL(true);
884 
885  PG_RETURN_BOOL(false);
886 }
887 
889 Datum gserialized_right_2d(PG_FUNCTION_ARGS)
890 {
891  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_right) == LW_TRUE )
892  PG_RETURN_BOOL(true);
893 
894  PG_RETURN_BOOL(false);
895 }
896 
898 Datum gserialized_above_2d(PG_FUNCTION_ARGS)
899 {
900  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_above) == LW_TRUE )
901  PG_RETURN_BOOL(true);
902 
903  PG_RETURN_BOOL(false);
904 }
905 
907 Datum gserialized_below_2d(PG_FUNCTION_ARGS)
908 {
909  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_below) == LW_TRUE )
910  PG_RETURN_BOOL(true);
911 
912  PG_RETURN_BOOL(false);
913 }
914 
916 Datum gserialized_overleft_2d(PG_FUNCTION_ARGS)
917 {
918  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overleft) == LW_TRUE )
919  PG_RETURN_BOOL(true);
920 
921  PG_RETURN_BOOL(false);
922 }
923 
925 Datum gserialized_overright_2d(PG_FUNCTION_ARGS)
926 {
927  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overright) == LW_TRUE )
928  PG_RETURN_BOOL(true);
929 
930  PG_RETURN_BOOL(false);
931 }
932 
934 Datum gserialized_overabove_2d(PG_FUNCTION_ARGS)
935 {
936  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overabove) == LW_TRUE )
937  PG_RETURN_BOOL(true);
938 
939  PG_RETURN_BOOL(false);
940 }
941 
943 Datum gserialized_overbelow_2d(PG_FUNCTION_ARGS)
944 {
945  if ( gserialized_datum_predicate_2d(PG_GETARG_DATUM(0), PG_GETARG_DATUM(1), box2df_overbelow) == LW_TRUE )
946  PG_RETURN_BOOL(true);
947 
948  PG_RETURN_BOOL(false);
949 }
950 
951 
952 /***********************************************************************
953 * GiST Index Support Functions
954 */
955 
956 /*
957 ** GiST support function. Given a geography, return a "compressed"
958 ** version. In this case, we convert the geography into a geocentric
959 ** bounding box. If the geography already has the box embedded in it
960 ** we pull that out and hand it back.
961 */
963 Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS)
964 {
965  GISTENTRY *entry_in = (GISTENTRY*)PG_GETARG_POINTER(0);
966  GISTENTRY *entry_out = NULL;
967  BOX2DF bbox_out;
968  int result = LW_SUCCESS;
969 
970  POSTGIS_DEBUG(4, "[GIST] 'compress' function called");
971 
972  /*
973  ** Not a leaf key? There's nothing to do.
974  ** Return the input unchanged.
975  */
976  if ( ! entry_in->leafkey )
977  {
978  POSTGIS_DEBUG(4, "[GIST] non-leafkey entry, returning input unaltered");
979  PG_RETURN_POINTER(entry_in);
980  }
981 
982  POSTGIS_DEBUG(4, "[GIST] processing leafkey input");
983  entry_out = palloc(sizeof(GISTENTRY));
984 
985  /*
986  ** Null key? Make a copy of the input entry and
987  ** return.
988  */
989  if ( DatumGetPointer(entry_in->key) == NULL )
990  {
991  POSTGIS_DEBUG(4, "[GIST] leafkey is null");
992  gistentryinit(*entry_out, (Datum) 0, entry_in->rel,
993  entry_in->page, entry_in->offset, false);
994  POSTGIS_DEBUG(4, "[GIST] returning copy of input");
995  PG_RETURN_POINTER(entry_out);
996  }
997 
998  /* Extract our index key from the GiST entry. */
999  result = gserialized_datum_get_box2df_p(entry_in->key, &bbox_out);
1000 
1001  /* Is the bounding box valid (non-empty, non-infinite)? If not, return input uncompressed. */
1002  if ( result == LW_FAILURE )
1003  {
1004  box2df_set_empty(&bbox_out);
1005  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
1006  entry_in->rel, entry_in->page, entry_in->offset, false);
1007 
1008  POSTGIS_DEBUG(4, "[GIST] empty geometry!");
1009  PG_RETURN_POINTER(entry_out);
1010  }
1011 
1012  POSTGIS_DEBUGF(4, "[GIST] got entry_in->key: %s", box2df_to_string(&bbox_out));
1013 
1014  /* Check all the dimensions for finite values */
1015  if ( ! isfinite(bbox_out.xmax) || ! isfinite(bbox_out.xmin) ||
1016  ! isfinite(bbox_out.ymax) || ! isfinite(bbox_out.ymin) )
1017  {
1018  box2df_set_finite(&bbox_out);
1019  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
1020  entry_in->rel, entry_in->page, entry_in->offset, false);
1021 
1022  POSTGIS_DEBUG(4, "[GIST] infinite geometry!");
1023  PG_RETURN_POINTER(entry_out);
1024  }
1025 
1026  /* Enure bounding box has minimums below maximums. */
1027  box2df_validate(&bbox_out);
1028 
1029  /* Prepare GISTENTRY for return. */
1030  gistentryinit(*entry_out, PointerGetDatum(box2df_copy(&bbox_out)),
1031  entry_in->rel, entry_in->page, entry_in->offset, false);
1032 
1033  /* Return GISTENTRY. */
1034  POSTGIS_DEBUG(4, "[GIST] 'compress' function complete");
1035  PG_RETURN_POINTER(entry_out);
1036 }
1037 
1038 
1039 /*
1040 ** GiST support function.
1041 ** Decompress an entry. Unused for geography, so we return.
1042 */
1044 Datum gserialized_gist_decompress_2d(PG_FUNCTION_ARGS)
1045 {
1046  POSTGIS_DEBUG(5, "[GIST] 'decompress' function called");
1047  /* We don't decompress. Just return the input. */
1048  PG_RETURN_POINTER(PG_GETARG_POINTER(0));
1049 }
1050 
1051 
1052 
1053 /*
1054 ** GiST support function. Called from gserialized_gist_consistent below.
1055 */
1056 static inline bool gserialized_gist_consistent_leaf_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
1057 {
1058  bool retval;
1059 
1060  POSTGIS_DEBUGF(4, "[GIST] leaf consistent, strategy [%d], count[%i]",
1061  strategy, g2d_counter_leaf++);
1062 
1063  switch (strategy)
1064  {
1065 
1066  /* Basic overlaps */
1067  case RTOverlapStrategyNumber:
1068  retval = (bool) box2df_overlaps(key, query);
1069  break;
1070  case RTSameStrategyNumber:
1071  retval = (bool) box2df_equals(key, query);
1072  break;
1073  case RTContainsStrategyNumber:
1074  case RTOldContainsStrategyNumber:
1075  retval = (bool) box2df_contains(key, query);
1076  break;
1077  case RTContainedByStrategyNumber:
1078  case RTOldContainedByStrategyNumber:
1079  retval = (bool) box2df_contains(query, key);
1080  break;
1081 
1082  /* To one side */
1083  case RTAboveStrategyNumber:
1084  retval = (bool) box2df_above(key, query);
1085  break;
1086  case RTBelowStrategyNumber:
1087  retval = (bool) box2df_below(key, query);
1088  break;
1089  case RTRightStrategyNumber:
1090  retval = (bool) box2df_right(key, query);
1091  break;
1092  case RTLeftStrategyNumber:
1093  retval = (bool) box2df_left(key, query);
1094  break;
1095 
1096  /* Overlapping to one side */
1097  case RTOverAboveStrategyNumber:
1098  retval = (bool) box2df_overabove(key, query);
1099  break;
1100  case RTOverBelowStrategyNumber:
1101  retval = (bool) box2df_overbelow(key, query);
1102  break;
1103  case RTOverRightStrategyNumber:
1104  retval = (bool) box2df_overright(key, query);
1105  break;
1106  case RTOverLeftStrategyNumber:
1107  retval = (bool) box2df_overleft(key, query);
1108  break;
1109 
1110  default:
1111  retval = false;
1112  }
1113 
1114  return (retval);
1115 }
1116 
1117 /*
1118 ** GiST support function. Called from gserialized_gist_consistent below.
1119 */
1120 static inline bool gserialized_gist_consistent_internal_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
1121 {
1122  bool retval;
1123 
1124  POSTGIS_DEBUGF(4, "[GIST] internal consistent, strategy [%d], count[%i], query[%s], key[%s]",
1125  strategy, g2d_counter_internal++, box2df_to_string(query), box2df_to_string(key) );
1126 
1127  switch (strategy)
1128  {
1129 
1130  /* Basic overlaps */
1131  case RTOverlapStrategyNumber:
1132  retval = (bool) box2df_overlaps(key, query);
1133  break;
1134  case RTSameStrategyNumber:
1135  case RTContainsStrategyNumber:
1136  case RTOldContainsStrategyNumber:
1137  retval = (bool) box2df_contains(key, query);
1138  break;
1139  case RTContainedByStrategyNumber:
1140  case RTOldContainedByStrategyNumber:
1141  retval = (bool) box2df_overlaps(key, query);
1142  break;
1143 
1144  /* To one side */
1145  case RTAboveStrategyNumber:
1146  retval = (bool)(!box2df_overbelow(key, query));
1147  break;
1148  case RTBelowStrategyNumber:
1149  retval = (bool)(!box2df_overabove(key, query));
1150  break;
1151  case RTRightStrategyNumber:
1152  retval = (bool)(!box2df_overleft(key, query));
1153  break;
1154  case RTLeftStrategyNumber:
1155  retval = (bool)(!box2df_overright(key, query));
1156  break;
1157 
1158  /* Overlapping to one side */
1159  case RTOverAboveStrategyNumber:
1160  retval = (bool)(!box2df_below(key, query));
1161  break;
1162  case RTOverBelowStrategyNumber:
1163  retval = (bool)(!box2df_above(key, query));
1164  break;
1165  case RTOverRightStrategyNumber:
1166  retval = (bool)(!box2df_left(key, query));
1167  break;
1168  case RTOverLeftStrategyNumber:
1169  retval = (bool)(!box2df_right(key, query));
1170  break;
1171 
1172  default:
1173  retval = false;
1174  }
1175 
1176  return (retval);
1177 }
1178 
1179 /*
1180 ** GiST support function. Take in a query and an entry and see what the
1181 ** relationship is, based on the query strategy.
1182 */
1184 Datum gserialized_gist_consistent_2d(PG_FUNCTION_ARGS)
1185 {
1186  GISTENTRY *entry = (GISTENTRY*) PG_GETARG_POINTER(0);
1187  StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1188  bool result;
1189  BOX2DF query_gbox_index;
1190 
1191  /* PostgreSQL 8.4 and later require the RECHECK flag to be set here,
1192  rather than being supplied as part of the operator class definition */
1193  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1194 
1195  /* We set recheck to false to avoid repeatedly pulling every "possibly matched" geometry
1196  out during index scans. For cases when the geometries are large, rechecking
1197  can make things twice as slow. */
1198  *recheck = false;
1199 
1200  POSTGIS_DEBUG(4, "[GIST] 'consistent' function called");
1201 
1202  /* Quick sanity check on query argument. */
1203  if ( DatumGetPointer(PG_GETARG_DATUM(1)) == NULL )
1204  {
1205  POSTGIS_DEBUG(4, "[GIST] null query pointer (!?!), returning false");
1206  PG_RETURN_BOOL(false); /* NULL query! This is screwy! */
1207  }
1208 
1209  /* Quick sanity check on entry key. */
1210  if ( DatumGetPointer(entry->key) == NULL )
1211  {
1212  POSTGIS_DEBUG(4, "[GIST] null index entry, returning false");
1213  PG_RETURN_BOOL(false); /* NULL entry! */
1214  }
1215 
1216  /* Null box should never make this far. */
1217  if ( gserialized_datum_get_box2df_p(PG_GETARG_DATUM(1), &query_gbox_index) == LW_FAILURE )
1218  {
1219  POSTGIS_DEBUG(4, "[GIST] null query_gbox_index!");
1220  PG_RETURN_BOOL(false);
1221  }
1222 
1223  /* Treat leaf node tests different from internal nodes */
1224  if (GIST_LEAF(entry))
1225  {
1227  (BOX2DF*)DatumGetPointer(entry->key),
1228  &query_gbox_index, strategy);
1229  }
1230  else
1231  {
1233  (BOX2DF*)DatumGetPointer(entry->key),
1234  &query_gbox_index, strategy);
1235  }
1236 
1237  PG_RETURN_BOOL(result);
1238 }
1239 
1240 
1241 /*
1242 ** GiST support function. Take in a query and an entry and return the "distance"
1243 ** between them.
1244 **
1245 ** Given an index entry p and a query value q, this function determines the
1246 ** index entry's "distance" from the query value. This function must be
1247 ** supplied if the operator class contains any ordering operators. A query
1248 ** using the ordering operator will be implemented by returning index entries
1249 ** with the smallest "distance" values first, so the results must be consistent
1250 ** with the operator's semantics. For a leaf index entry the result just
1251 ** represents the distance to the index entry; for an internal tree node, the
1252 ** result must be the smallest distance that any child entry could have.
1253 **
1254 ** Strategy 13 = true distance tests <->
1255 ** Strategy 14 = box-based distance tests <#>
1256 */
1258 Datum gserialized_gist_distance_2d(PG_FUNCTION_ARGS)
1259 {
1260  GISTENTRY *entry = (GISTENTRY*) PG_GETARG_POINTER(0);
1261  BOX2DF query_box;
1262  BOX2DF *entry_box;
1263  StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
1264  double distance;
1265 #if POSTGIS_PGSQL_VERSION >= 95
1266  bool *recheck = (bool *) PG_GETARG_POINTER(4);
1267 #endif
1268 
1269  POSTGIS_DEBUG(4, "[GIST] 'distance' function called");
1270 
1271  /* We are using '13' as the gist true-distance <-> strategy number
1272  * and '14' as the gist distance-between-boxes <#> strategy number */
1273  if ( strategy != 13 && strategy != 14 ) {
1274  elog(ERROR, "unrecognized strategy number: %d", strategy);
1275  PG_RETURN_FLOAT8(FLT_MAX);
1276  }
1277 
1278  /* Null box should never make this far. */
1279  if ( gserialized_datum_get_box2df_p(PG_GETARG_DATUM(1), &query_box) == LW_FAILURE )
1280  {
1281  POSTGIS_DEBUG(4, "[GIST] null query_gbox_index!");
1282  PG_RETURN_FLOAT8(FLT_MAX);
1283  }
1284 
1285  /* Get the entry box */
1286  entry_box = (BOX2DF*)DatumGetPointer(entry->key);
1287 
1288 #if POSTGIS_PGSQL_VERSION >= 95
1289 
1290  /* Box-style distance test */
1291  if ( strategy == 14 ) /* operator <#> */
1292  {
1293  distance = box2df_distance(entry_box, &query_box);
1294  }
1295  /* True distance test (formerly centroid distance) */
1296  else if ( strategy == 13 ) /* operator <-> */
1297  {
1298  /* In all cases, since we only have keys (boxes) we'll return */
1299  /* the minimum possible distance, which is the box2df_distance */
1300  /* and let the recheck sort things out in the case of leaves */
1301  distance = box2df_distance(entry_box, &query_box);
1302 
1303  if (GIST_LEAF(entry))
1304  *recheck = true;
1305  }
1306  else
1307  {
1308  elog(ERROR, "%s: reached unreachable code", __func__);
1309  PG_RETURN_NULL();
1310  }
1311 #else
1312  /* Box-style distance test */
1313  if ( strategy == 14 )
1314  {
1315  distance = (double)box2df_distance(entry_box, &query_box);
1316  PG_RETURN_FLOAT8(distance);
1317  }
1318 
1319  /* Treat leaf node tests different from internal nodes */
1320  if (GIST_LEAF(entry))
1321  {
1322  /* Calculate distance to leaves */
1323  distance = (double)box2df_distance_leaf_centroid(entry_box, &query_box);
1324  }
1325  else
1326  {
1327  /* Calculate distance for internal nodes */
1328  distance = (double)box2df_distance_node_centroid(entry_box, &query_box);
1329  }
1330 #endif
1331 
1332  PG_RETURN_FLOAT8(distance);
1333 }
1334 
1335 /*
1336 ** Function to pack floats of different realms
1337 ** This function serves to pack bit flags inside float type
1338 ** Resulted value represent can be from four different "realms"
1339 ** Every value from realm 3 is greater than any value from realms 2, 1 and 0.
1340 ** Every value from realm 2 is less than every value from realm 3 and greater
1341 ** than any value from realm 1 and 0, and so on. Values from the same realm
1342 ** loose two bits of precision. This technique is possible due to floating
1343 ** point numbers specification according to IEEE 754: exponent bits are highest
1344 ** (excluding sign bits, but here penalty is always positive). If float a is
1345 ** greater than float b, integer A with same bit representation as a is greater
1346 ** than integer B with same bits as b.
1347 */
1348 static float pack_float(const float value, const int realm)
1349 {
1350  union {
1351  float f;
1352  struct { unsigned value:31, sign:1; } vbits;
1353  struct { unsigned value:29, realm:2, sign:1; } rbits;
1354  } a;
1355 
1356  a.f = value;
1357  a.rbits.value = a.vbits.value >> 2;
1358  a.rbits.realm = realm;
1359 
1360  return a.f;
1361 }
1362 
1363 /*
1364 ** GiST support function. Calculate the "penalty" cost of adding this entry into an existing entry.
1365 ** Calculate the change in volume of the old entry once the new entry is added.
1366 */
1368 Datum gserialized_gist_penalty_2d(PG_FUNCTION_ARGS)
1369 {
1370  GISTENTRY *origentry = (GISTENTRY*) PG_GETARG_POINTER(0);
1371  GISTENTRY *newentry = (GISTENTRY*) PG_GETARG_POINTER(1);
1372  float *result = (float*) PG_GETARG_POINTER(2);
1373  BOX2DF *gbox_index_orig, *gbox_index_new;
1374  float size_union, size_orig, edge_union, edge_orig;
1375 
1376  POSTGIS_DEBUG(4, "[GIST] 'penalty' function called");
1377 
1378  gbox_index_orig = (BOX2DF*)DatumGetPointer(origentry->key);
1379  gbox_index_new = (BOX2DF*)DatumGetPointer(newentry->key);
1380 
1381  /* Drop out if we're dealing with null inputs. Shouldn't happen. */
1382  if ( (gbox_index_orig == NULL) && (gbox_index_new == NULL) )
1383  {
1384  POSTGIS_DEBUG(4, "[GIST] both inputs NULL! returning penalty of zero");
1385  *result = 0.0;
1386  PG_RETURN_FLOAT8(*result);
1387  }
1388 
1389  /* Calculate the size difference of the boxes. */
1390  size_union = box2df_union_size(gbox_index_orig, gbox_index_new);
1391  size_orig = box2df_size(gbox_index_orig);
1392  *result = size_union - size_orig;
1393 
1394  /* REALM 0: No extension is required, volume is zero, return edge */
1395  /* REALM 1: No extension is required, return nonzero area */
1396  /* REALM 2: Area extension is zero, return nonzero edge extension */
1397  /* REALM 3: Area extension is nonzero, return it */
1398 
1399  if( *result == 0 )
1400  {
1401  if (size_orig > 0)
1402  {
1403  *result = pack_float(size_orig, 1); /* REALM 1 */
1404  }
1405  else
1406  {
1407  edge_union = box2df_union_edge(gbox_index_orig, gbox_index_new);
1408  edge_orig = box2df_edge(gbox_index_orig);
1409  *result = edge_union - edge_orig;
1410  if( *result == 0 )
1411  {
1412  *result = pack_float(edge_orig, 0); /* REALM 0 */
1413  }
1414  else
1415  {
1416  *result = pack_float(*result, 2); /* REALM 2 */
1417  }
1418  }
1419  }
1420  else
1421  {
1422  *result = pack_float(*result, 3); /* REALM 3 */
1423  }
1424 
1425  POSTGIS_DEBUGF(4, "[GIST] 'penalty', union size (%.12f), original size (%.12f), penalty (%.12f)", size_union, size_orig, *result);
1426 
1427  PG_RETURN_POINTER(result);
1428 }
1429 
1430 /*
1431 ** GiST support function. Merge all the boxes in a page into one master box.
1432 */
1434 Datum gserialized_gist_union_2d(PG_FUNCTION_ARGS)
1435 {
1436  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1437  int *sizep = (int *) PG_GETARG_POINTER(1); /* Size of the return value */
1438  int numranges, i;
1439  BOX2DF *box_cur, *box_union;
1440 
1441  POSTGIS_DEBUG(4, "[GIST] 'union' function called");
1442 
1443  numranges = entryvec->n;
1444 
1445  box_cur = (BOX2DF*) DatumGetPointer(entryvec->vector[0].key);
1446 
1447  box_union = box2df_copy(box_cur);
1448 
1449  for ( i = 1; i < numranges; i++ )
1450  {
1451  box_cur = (BOX2DF*) DatumGetPointer(entryvec->vector[i].key);
1452  box2df_merge(box_union, box_cur);
1453  }
1454 
1455  *sizep = sizeof(BOX2DF);
1456 
1457  POSTGIS_DEBUGF(4, "[GIST] 'union', numranges(%i), pageunion %s", numranges, box2df_to_string(box_union));
1458 
1459  PG_RETURN_POINTER(box_union);
1460 
1461 }
1462 
1463 /*
1464 ** GiST support function. Test equality of keys.
1465 */
1467 Datum gserialized_gist_same_2d(PG_FUNCTION_ARGS)
1468 {
1469  BOX2DF *b1 = (BOX2DF*)PG_GETARG_POINTER(0);
1470  BOX2DF *b2 = (BOX2DF*)PG_GETARG_POINTER(1);
1471  bool *result = (bool*)PG_GETARG_POINTER(2);
1472 
1473  POSTGIS_DEBUG(4, "[GIST] 'same' function called");
1474 
1475  *result = box2df_equals(b1, b2);
1476 
1477  PG_RETURN_POINTER(result);
1478 }
1479 
1480 #if KOROTKOV_SPLIT > 0
1481 /*
1482  * Adjust BOX2DF b boundaries with insertion of addon.
1483  */
1484 static void
1485 adjustBox(BOX2DF *b, BOX2DF *addon)
1486 {
1487  if (b->xmax < addon->xmax || isnan(b->xmax))
1488  b->xmax = addon->xmax;
1489  if (b->xmin > addon->xmin || isnan(b->xmin))
1490  b->xmin = addon->xmin;
1491  if (b->ymax < addon->ymax || isnan(b->ymax))
1492  b->ymax = addon->ymax;
1493  if (b->ymin > addon->ymin || isnan(b->ymin))
1494  b->ymin = addon->ymin;
1495 }
1496 
1497 /*
1498  * Trivial split: half of entries will be placed on one page
1499  * and another half - to another
1500  */
1501 static void
1502 fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
1503 {
1504  OffsetNumber i,
1505  maxoff;
1506  BOX2DF *unionL = NULL,
1507  *unionR = NULL;
1508  int nbytes;
1509 
1510  maxoff = entryvec->n - 1;
1511 
1512  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
1513  v->spl_left = (OffsetNumber *) palloc(nbytes);
1514  v->spl_right = (OffsetNumber *) palloc(nbytes);
1515  v->spl_nleft = v->spl_nright = 0;
1516 
1517  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1518  {
1519  BOX2DF *cur = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1520 
1521  if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
1522  {
1523  v->spl_left[v->spl_nleft] = i;
1524  if (unionL == NULL)
1525  {
1526  unionL = (BOX2DF *) palloc(sizeof(BOX2DF));
1527  *unionL = *cur;
1528  }
1529  else
1530  adjustBox(unionL, cur);
1531 
1532  v->spl_nleft++;
1533  }
1534  else
1535  {
1536  v->spl_right[v->spl_nright] = i;
1537  if (unionR == NULL)
1538  {
1539  unionR = (BOX2DF *) palloc(sizeof(BOX2DF));
1540  *unionR = *cur;
1541  }
1542  else
1543  adjustBox(unionR, cur);
1544 
1545  v->spl_nright++;
1546  }
1547  }
1548 
1549  if (v->spl_ldatum_exists)
1550  adjustBox(unionL, (BOX2DF *) DatumGetPointer(v->spl_ldatum));
1551  v->spl_ldatum = BoxPGetDatum(unionL);
1552 
1553  if (v->spl_rdatum_exists)
1554  adjustBox(unionR, (BOX2DF *) DatumGetPointer(v->spl_rdatum));
1555  v->spl_rdatum = BoxPGetDatum(unionR);
1556 
1557  v->spl_ldatum_exists = v->spl_rdatum_exists = false;
1558 }
1559 
1560 /*
1561  * Represents information about an entry that can be placed to either group
1562  * without affecting overlap over selected axis ("common entry").
1563  */
1564 typedef struct
1565 {
1566  /* Index of entry in the initial array */
1567  int index;
1568  /* Delta between penalties of entry insertion into different groups */
1569  float delta;
1570 } CommonEntry;
1571 
1572 /*
1573  * Context for g_box_consider_split. Contains information about currently
1574  * selected split and some general information.
1575  */
1576 typedef struct
1577 {
1578  int entriesCount; /* total number of entries being split */
1579  BOX2DF boundingBox; /* minimum bounding box across all entries */
1580 
1581  /* Information about currently selected split follows */
1582 
1583  bool first; /* true if no split was selected yet */
1584 
1585  float leftUpper; /* upper bound of left interval */
1586  float rightLower; /* lower bound of right interval */
1587 
1588  float4 ratio;
1589  float4 overlap;
1590  int dim; /* axis of this split */
1591  float range; /* width of general MBR projection to the
1592  * selected axis */
1594 
1595 /*
1596  * Interval represents projection of box to axis.
1597  */
1598 typedef struct
1599 {
1600  float lower,
1601  upper;
1602 } SplitInterval;
1603 
1604 /*
1605  * Interval comparison function by lower bound of the interval;
1606  */
1607 static int
1608 interval_cmp_lower(const void *i1, const void *i2)
1609 {
1610  float lower1 = ((const SplitInterval *) i1)->lower,
1611  lower2 = ((const SplitInterval *) i2)->lower;
1612 
1613  if (isnan(lower1))
1614  {
1615  if (isnan(lower2))
1616  return 0;
1617  else
1618  return 1;
1619  }
1620  else if (isnan(lower2))
1621  {
1622  return -1;
1623  }
1624  else
1625  {
1626  if (lower1 < lower2)
1627  return -1;
1628  else if (lower1 > lower2)
1629  return 1;
1630  else
1631  return 0;
1632  }
1633 }
1634 
1635 
1636 /*
1637  * Interval comparison function by upper bound of the interval;
1638  */
1639 static int
1640 interval_cmp_upper(const void *i1, const void *i2)
1641 {
1642  float upper1 = ((const SplitInterval *) i1)->upper,
1643  upper2 = ((const SplitInterval *) i2)->upper;
1644 
1645  if (isnan(upper1))
1646  {
1647  if (isnan(upper2))
1648  return 0;
1649  else
1650  return -1;
1651  }
1652  else if (isnan(upper2))
1653  {
1654  return 1;
1655  }
1656  else
1657  {
1658  if (upper1 < upper2)
1659  return -1;
1660  else if (upper1 > upper2)
1661  return 1;
1662  else
1663  return 0;
1664  }
1665 }
1666 
1667 /*
1668  * Replace negative value with zero.
1669  */
1670 static inline float
1671 non_negative(float val)
1672 {
1673  if (val >= 0.0f)
1674  return val;
1675  else
1676  return 0.0f;
1677 }
1678 
1679 /*
1680  * Consider replacement of currently selected split with the better one.
1681  */
1682 static inline void
1684  float rightLower, int minLeftCount,
1685  float leftUpper, int maxLeftCount)
1686 {
1687  int leftCount,
1688  rightCount;
1689  float4 ratio,
1690  overlap;
1691  float range;
1692 
1693  POSTGIS_DEBUGF(5, "consider split: dimNum = %d, rightLower = %f, "
1694  "minLeftCount = %d, leftUpper = %f, maxLeftCount = %d ",
1695  dimNum, rightLower, minLeftCount, leftUpper, maxLeftCount);
1696 
1697  /*
1698  * Calculate entries distribution ratio assuming most uniform distribution
1699  * of common entries.
1700  */
1701  if (minLeftCount >= (context->entriesCount + 1) / 2)
1702  {
1703  leftCount = minLeftCount;
1704  }
1705  else
1706  {
1707  if (maxLeftCount <= context->entriesCount / 2)
1708  leftCount = maxLeftCount;
1709  else
1710  leftCount = context->entriesCount / 2;
1711  }
1712  rightCount = context->entriesCount - leftCount;
1713 
1714  /*
1715  * Ratio of split - quotient between size of lesser group and total
1716  * entries count.
1717  */
1718  ratio = ((float4) Min(leftCount, rightCount)) /
1719  ((float4) context->entriesCount);
1720 
1721  if (ratio > LIMIT_RATIO)
1722  {
1723  bool selectthis = false;
1724 
1725  /*
1726  * The ratio is acceptable, so compare current split with previously
1727  * selected one. Between splits of one dimension we search for minimal
1728  * overlap (allowing negative values) and minimal ration (between same
1729  * overlaps. We switch dimension if find less overlap (non-negative)
1730  * or less range with same overlap.
1731  */
1732  if (dimNum == 0)
1733  range = context->boundingBox.xmax - context->boundingBox.xmin;
1734  else
1735  range = context->boundingBox.ymax - context->boundingBox.ymin;
1736 
1737  overlap = (leftUpper - rightLower) / range;
1738 
1739  /* If there is no previous selection, select this */
1740  if (context->first)
1741  selectthis = true;
1742  else if (context->dim == dimNum)
1743  {
1744  /*
1745  * Within the same dimension, choose the new split if it has a
1746  * smaller overlap, or same overlap but better ratio.
1747  */
1748  if (overlap < context->overlap ||
1749  (overlap == context->overlap && ratio > context->ratio))
1750  selectthis = true;
1751  }
1752  else
1753  {
1754  /*
1755  * Across dimensions, choose the new split if it has a smaller
1756  * *non-negative* overlap, or same *non-negative* overlap but
1757  * bigger range. This condition differs from the one described in
1758  * the article. On the datasets where leaf MBRs don't overlap
1759  * themselves, non-overlapping splits (i.e. splits which have zero
1760  * *non-negative* overlap) are frequently possible. In this case
1761  * splits tends to be along one dimension, because most distant
1762  * non-overlapping splits (i.e. having lowest negative overlap)
1763  * appears to be in the same dimension as in the previous split.
1764  * Therefore MBRs appear to be very prolonged along another
1765  * dimension, which leads to bad search performance. Using range
1766  * as the second split criteria makes MBRs more quadratic. Using
1767  * *non-negative* overlap instead of overlap as the first split
1768  * criteria gives to range criteria a chance to matter, because
1769  * non-overlapping splits are equivalent in this criteria.
1770  */
1771  if (non_negative(overlap) < non_negative(context->overlap) ||
1772  (range > context->range &&
1773  non_negative(overlap) <= non_negative(context->overlap)))
1774  selectthis = true;
1775  }
1776 
1777  if (selectthis)
1778  {
1779  /* save information about selected split */
1780  context->first = false;
1781  context->ratio = ratio;
1782  context->range = range;
1783  context->overlap = overlap;
1784  context->rightLower = rightLower;
1785  context->leftUpper = leftUpper;
1786  context->dim = dimNum;
1787  POSTGIS_DEBUG(5, "split selected");
1788  }
1789  }
1790 }
1791 
1792 /*
1793  * Return increase of original BOX2DF area by new BOX2DF area insertion.
1794  */
1795 static float
1796 box_penalty(BOX2DF *original, BOX2DF *new)
1797 {
1798  float union_width,
1799  union_height;
1800 
1801  union_width = Max(original->xmax, new->xmax) -
1802  Min(original->xmin, new->xmin);
1803  union_height = Max(original->ymax, new->ymax) -
1804  Min(original->ymin, new->ymin);
1805  return union_width * union_height - (original->xmax - original->xmin) *
1806  (original->ymax - original->ymin);
1807 }
1808 
1809 /*
1810  * Compare common entries by their deltas.
1811  */
1812 static int
1813 common_entry_cmp(const void *i1, const void *i2)
1814 {
1815  float delta1 = ((const CommonEntry *) i1)->delta,
1816  delta2 = ((const CommonEntry *) i2)->delta;
1817 
1818  if (delta1 < delta2)
1819  return -1;
1820  else if (delta1 > delta2)
1821  return 1;
1822  else
1823  return 0;
1824 }
1825 
1826 /*
1827  * --------------------------------------------------------------------------
1828  * Double sorting split algorithm. This is used for both boxes and points.
1829  *
1830  * The algorithm finds split of boxes by considering splits along each axis.
1831  * Each entry is first projected as an interval on the X-axis, and different
1832  * ways to split the intervals into two groups are considered, trying to
1833  * minimize the overlap of the groups. Then the same is repeated for the
1834  * Y-axis, and the overall best split is chosen. The quality of a split is
1835  * determined by overlap along that axis and some other criteria (see
1836  * g_box_consider_split).
1837  *
1838  * After that, all the entries are divided into three groups:
1839  *
1840  * 1) Entries which should be placed to the left group
1841  * 2) Entries which should be placed to the right group
1842  * 3) "Common entries" which can be placed to any of groups without affecting
1843  * of overlap along selected axis.
1844  *
1845  * The common entries are distributed by minimizing penalty.
1846  *
1847  * For details see:
1848  * "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
1849  * http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
1850  * --------------------------------------------------------------------------
1851  */
1853 Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS)
1854 {
1855  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1856  GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
1857  OffsetNumber i,
1858  maxoff;
1859  ConsiderSplitContext context;
1860  BOX2DF *box,
1861  *leftBox,
1862  *rightBox;
1863  int dim,
1864  commonEntriesCount;
1865  SplitInterval *intervalsLower,
1866  *intervalsUpper;
1867  CommonEntry *commonEntries;
1868  int nentries;
1869 
1870  POSTGIS_DEBUG(3, "[GIST] 'picksplit' entered");
1871 
1872  memset(&context, 0, sizeof(ConsiderSplitContext));
1873 
1874  maxoff = entryvec->n - 1;
1875  nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
1876 
1877  /* Allocate arrays for intervals along axes */
1878  intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1879  intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1880 
1881  /*
1882  * Calculate the overall minimum bounding box over all the entries.
1883  */
1884  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1885  {
1886  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1887  if (i == FirstOffsetNumber)
1888  context.boundingBox = *box;
1889  else
1890  adjustBox(&context.boundingBox, box);
1891  }
1892 
1893  POSTGIS_DEBUGF(4, "boundingBox is %s", box2df_to_string(
1894  &context.boundingBox));
1895 
1896  /*
1897  * Iterate over axes for optimal split searching.
1898  */
1899  context.first = true; /* nothing selected yet */
1900  for (dim = 0; dim < 2; dim++)
1901  {
1902  float leftUpper,
1903  rightLower;
1904  int i1,
1905  i2;
1906 
1907  /* Project each entry as an interval on the selected axis. */
1908  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1909  {
1910  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1911  if (dim == 0)
1912  {
1913  intervalsLower[i - FirstOffsetNumber].lower = box->xmin;
1914  intervalsLower[i - FirstOffsetNumber].upper = box->xmax;
1915  }
1916  else
1917  {
1918  intervalsLower[i - FirstOffsetNumber].lower = box->ymin;
1919  intervalsLower[i - FirstOffsetNumber].upper = box->ymax;
1920  }
1921  }
1922 
1923  /*
1924  * Make two arrays of intervals: one sorted by lower bound and another
1925  * sorted by upper bound.
1926  */
1927  memcpy(intervalsUpper, intervalsLower,
1928  sizeof(SplitInterval) * nentries);
1929  qsort(intervalsLower, nentries, sizeof(SplitInterval),
1931  qsort(intervalsUpper, nentries, sizeof(SplitInterval),
1933 
1934  /*----
1935  * The goal is to form a left and right interval, so that every entry
1936  * interval is contained by either left or right interval (or both).
1937  *
1938  * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
1939  *
1940  * 0 1 2 3 4
1941  * +-+
1942  * +---+
1943  * +-+
1944  * +---+
1945  *
1946  * The left and right intervals are of the form (0,a) and (b,4).
1947  * We first consider splits where b is the lower bound of an entry.
1948  * We iterate through all entries, and for each b, calculate the
1949  * smallest possible a. Then we consider splits where a is the
1950  * upper bound of an entry, and for each a, calculate the greatest
1951  * possible b.
1952  *
1953  * In the above example, the first loop would consider splits:
1954  * b=0: (0,1)-(0,4)
1955  * b=1: (0,1)-(1,4)
1956  * b=2: (0,3)-(2,4)
1957  *
1958  * And the second loop:
1959  * a=1: (0,1)-(1,4)
1960  * a=3: (0,3)-(2,4)
1961  * a=4: (0,4)-(2,4)
1962  */
1963 
1964  /*
1965  * Iterate over lower bound of right group, finding smallest possible
1966  * upper bound of left group.
1967  */
1968  i1 = 0;
1969  i2 = 0;
1970  rightLower = intervalsLower[i1].lower;
1971  leftUpper = intervalsUpper[i2].lower;
1972  while (true)
1973  {
1974  /*
1975  * Find next lower bound of right group.
1976  */
1977  while (i1 < nentries && (rightLower == intervalsLower[i1].lower ||
1978  isnan(intervalsLower[i1].lower)))
1979  {
1980  leftUpper = Max(leftUpper, intervalsLower[i1].upper);
1981  i1++;
1982  }
1983  if (i1 >= nentries)
1984  break;
1985  rightLower = intervalsLower[i1].lower;
1986 
1987  /*
1988  * Find count of intervals which anyway should be placed to the
1989  * left group.
1990  */
1991  while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
1992  i2++;
1993 
1994  /*
1995  * Consider found split.
1996  */
1997  g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
1998  }
1999 
2000  /*
2001  * Iterate over upper bound of left group finding greatest possible
2002  * lower bound of right group.
2003  */
2004  i1 = nentries - 1;
2005  i2 = nentries - 1;
2006  rightLower = intervalsLower[i1].upper;
2007  leftUpper = intervalsUpper[i2].upper;
2008  while (true)
2009  {
2010  /*
2011  * Find next upper bound of left group.
2012  */
2013  while (i2 >= 0 && (leftUpper == intervalsUpper[i2].upper ||
2014  isnan(intervalsUpper[i2].upper)))
2015  {
2016  rightLower = Min(rightLower, intervalsUpper[i2].lower);
2017  i2--;
2018  }
2019  if (i2 < 0)
2020  break;
2021  leftUpper = intervalsUpper[i2].upper;
2022 
2023  /*
2024  * Find count of intervals which anyway should be placed to the
2025  * right group.
2026  */
2027  while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
2028  i1--;
2029 
2030  /*
2031  * Consider found split.
2032  */
2033  g_box_consider_split(&context, dim,
2034  rightLower, i1 + 1, leftUpper, i2 + 1);
2035  }
2036  }
2037 
2038  /*
2039  * If we failed to find any acceptable splits, use trivial split.
2040  */
2041  if (context.first)
2042  {
2043  POSTGIS_DEBUG(4, "no acceptable splits, trivial split");
2044  fallbackSplit(entryvec, v);
2045  PG_RETURN_POINTER(v);
2046  }
2047 
2048  /*
2049  * Ok, we have now selected the split across one axis.
2050  *
2051  * While considering the splits, we already determined that there will be
2052  * enough entries in both groups to reach the desired ratio, but we did
2053  * not memorize which entries go to which group. So determine that now.
2054  */
2055 
2056  POSTGIS_DEBUGF(4, "split direction: %d", context.dim);
2057 
2058  /* Allocate vectors for results */
2059  v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
2060  v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
2061  v->spl_nleft = 0;
2062  v->spl_nright = 0;
2063 
2064  /* Allocate bounding boxes of left and right groups */
2065  leftBox = palloc0(sizeof(BOX2DF));
2066  rightBox = palloc0(sizeof(BOX2DF));
2067 
2068  /*
2069  * Allocate an array for "common entries" - entries which can be placed to
2070  * either group without affecting overlap along selected axis.
2071  */
2072  commonEntriesCount = 0;
2073  commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
2074 
2075  /* Helper macros to place an entry in the left or right group */
2076 #define PLACE_LEFT(box, off) \
2077  do { \
2078  if (v->spl_nleft > 0) \
2079  adjustBox(leftBox, box); \
2080  else \
2081  *leftBox = *(box); \
2082  v->spl_left[v->spl_nleft++] = off; \
2083  } while(0)
2084 
2085 #define PLACE_RIGHT(box, off) \
2086  do { \
2087  if (v->spl_nright > 0) \
2088  adjustBox(rightBox, box); \
2089  else \
2090  *rightBox = *(box); \
2091  v->spl_right[v->spl_nright++] = off; \
2092  } while(0)
2093 
2094  /*
2095  * Distribute entries which can be distributed unambiguously, and collect
2096  * common entries.
2097  */
2098  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2099  {
2100  float lower,
2101  upper;
2102 
2103  /*
2104  * Get upper and lower bounds along selected axis.
2105  */
2106  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
2107  if (context.dim == 0)
2108  {
2109  lower = box->xmin;
2110  upper = box->xmax;
2111  }
2112  else
2113  {
2114  lower = box->ymin;
2115  upper = box->ymax;
2116  }
2117 
2118  if (upper <= context.leftUpper || isnan(upper))
2119  {
2120  /* Fits to the left group */
2121  if (lower >= context.rightLower || isnan(lower))
2122  {
2123  /* Fits also to the right group, so "common entry" */
2124  commonEntries[commonEntriesCount++].index = i;
2125  }
2126  else
2127  {
2128  /* Doesn't fit to the right group, so join to the left group */
2129  PLACE_LEFT(box, i);
2130  }
2131  }
2132  else
2133  {
2134  /*
2135  * Each entry should fit on either left or right group. Since this
2136  * entry didn't fit on the left group, it better fit in the right
2137  * group.
2138  */
2139  Assert(lower >= context.rightLower);
2140 
2141  /* Doesn't fit to the left group, so join to the right group */
2142  PLACE_RIGHT(box, i);
2143  }
2144  }
2145 
2146  POSTGIS_DEBUGF(4, "leftBox is %s", box2df_to_string(leftBox));
2147  POSTGIS_DEBUGF(4, "rightBox is %s", box2df_to_string(rightBox));
2148 
2149  /*
2150  * Distribute "common entries", if any.
2151  */
2152  if (commonEntriesCount > 0)
2153  {
2154  /*
2155  * Calculate minimum number of entries that must be placed in both
2156  * groups, to reach LIMIT_RATIO.
2157  */
2158  int m = ceil(LIMIT_RATIO * (double) nentries);
2159 
2160  /*
2161  * Calculate delta between penalties of join "common entries" to
2162  * different groups.
2163  */
2164  for (i = 0; i < commonEntriesCount; i++)
2165  {
2166  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
2167  commonEntries[i].index].key);
2168  commonEntries[i].delta = Abs(box_penalty(leftBox, box) -
2169  box_penalty(rightBox, box));
2170  }
2171 
2172  /*
2173  * Sort "common entries" by calculated deltas in order to distribute
2174  * the most ambiguous entries first.
2175  */
2176  qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
2177 
2178  /*
2179  * Distribute "common entries" between groups.
2180  */
2181  for (i = 0; i < commonEntriesCount; i++)
2182  {
2183  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
2184  commonEntries[i].index].key);
2185 
2186  /*
2187  * Check if we have to place this entry in either group to achieve
2188  * LIMIT_RATIO.
2189  */
2190  if (v->spl_nleft + (commonEntriesCount - i) <= m)
2191  PLACE_LEFT(box, commonEntries[i].index);
2192  else if (v->spl_nright + (commonEntriesCount - i) <= m)
2193  PLACE_RIGHT(box, commonEntries[i].index);
2194  else
2195  {
2196  /* Otherwise select the group by minimal penalty */
2197  if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
2198  PLACE_LEFT(box, commonEntries[i].index);
2199  else
2200  PLACE_RIGHT(box, commonEntries[i].index);
2201  }
2202  }
2203  }
2204  v->spl_ldatum = PointerGetDatum(leftBox);
2205  v->spl_rdatum = PointerGetDatum(rightBox);
2206 
2207  POSTGIS_DEBUG(4, "[GIST] 'picksplit' completed");
2208 
2209  PG_RETURN_POINTER(v);
2210 }
2211 
2212 #else /* !KOROTOV_SPLIT */
2213 
2214 typedef struct
2215 {
2216  BOX2DF *key;
2217  int pos;
2218 }
2219 KBsort;
2220 
2221 static int
2222 compare_KB(const void* a, const void* b)
2223 {
2224  BOX2DF *abox = ((KBsort*)a)->key;
2225  BOX2DF *bbox = ((KBsort*)b)->key;
2226  float sa = (abox->xmax - abox->xmin) * (abox->ymax - abox->ymin);
2227  float sb = (bbox->xmax - bbox->xmin) * (bbox->ymax - bbox->ymin);
2228 
2229  if ( sa==sb ) return 0;
2230  return ( sa>sb ) ? 1 : -1;
2231 }
2232 
2239 Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS)
2240 {
2241  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
2242 
2243  GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
2244  OffsetNumber i;
2245  OffsetNumber *listL, *listR, *listB, *listT;
2246  BOX2DF *unionL, *unionR, *unionB, *unionT;
2247  int posL, posR, posB, posT;
2248  BOX2DF pageunion;
2249  BOX2DF *cur;
2250  char direction = ' ';
2251  bool allisequal = true;
2252  OffsetNumber maxoff;
2253  int nbytes;
2254 
2255  POSTGIS_DEBUG(3, "[GIST] 'picksplit' entered");
2256 
2257  posL = posR = posB = posT = 0;
2258 
2259  maxoff = entryvec->n - 1;
2260  cur = (BOX2DF*) DatumGetPointer(entryvec->vector[FirstOffsetNumber].key);
2261 
2262  memcpy((void *) &pageunion, (void *) cur, sizeof(BOX2DF));
2263 
2264  /* find MBR */
2265  for (i = OffsetNumberNext(FirstOffsetNumber); i <= maxoff; i = OffsetNumberNext(i))
2266  {
2267  cur = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
2268 
2269  if ( allisequal == true && (
2270  pageunion.xmax != cur->xmax ||
2271  pageunion.ymax != cur->ymax ||
2272  pageunion.xmin != cur->xmin ||
2273  pageunion.ymin != cur->ymin
2274  ) )
2275  allisequal = false;
2276 
2277  if (pageunion.xmax < cur->xmax)
2278  pageunion.xmax = cur->xmax;
2279  if (pageunion.xmin > cur->xmin)
2280  pageunion.xmin = cur->xmin;
2281  if (pageunion.ymax < cur->ymax)
2282  pageunion.ymax = cur->ymax;
2283  if (pageunion.ymin > cur->ymin)
2284  pageunion.ymin = cur->ymin;
2285  }
2286 
2287  POSTGIS_DEBUGF(4, "pageunion is %s", box2df_to_string(&pageunion));
2288 
2289  nbytes = (maxoff + 2) * sizeof(OffsetNumber);
2290  listL = (OffsetNumber *) palloc(nbytes);
2291  listR = (OffsetNumber *) palloc(nbytes);
2292  unionL = (BOX2DF *) palloc(sizeof(BOX2DF));
2293  unionR = (BOX2DF *) palloc(sizeof(BOX2DF));
2294 
2295  if (allisequal)
2296  {
2297  POSTGIS_DEBUG(4, " AllIsEqual!");
2298 
2299  cur = (BOX2DF*) DatumGetPointer(entryvec->vector[OffsetNumberNext(FirstOffsetNumber)].key);
2300 
2301 
2302  if (memcmp((void *) cur, (void *) &pageunion, sizeof(BOX2DF)) == 0)
2303  {
2304  v->spl_left = listL;
2305  v->spl_right = listR;
2306  v->spl_nleft = v->spl_nright = 0;
2307  memcpy((void *) unionL, (void *) &pageunion, sizeof(BOX2DF));
2308  memcpy((void *) unionR, (void *) &pageunion, sizeof(BOX2DF));
2309 
2310  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2311  {
2312  if (i <= (maxoff - FirstOffsetNumber + 1) / 2)
2313  {
2314  v->spl_left[v->spl_nleft] = i;
2315  v->spl_nleft++;
2316  }
2317  else
2318  {
2319  v->spl_right[v->spl_nright] = i;
2320  v->spl_nright++;
2321  }
2322  }
2323  v->spl_ldatum = PointerGetDatum(unionL);
2324  v->spl_rdatum = PointerGetDatum(unionR);
2325 
2326  PG_RETURN_POINTER(v);
2327  }
2328  }
2329 
2330  listB = (OffsetNumber *) palloc(nbytes);
2331  listT = (OffsetNumber *) palloc(nbytes);
2332  unionB = (BOX2DF *) palloc(sizeof(BOX2DF));
2333  unionT = (BOX2DF *) palloc(sizeof(BOX2DF));
2334 
2335 #define ADDLIST( list, unionD, pos, num ) do { \
2336  if ( pos ) { \
2337  if ( unionD->xmax < cur->xmax ) unionD->xmax = cur->xmax; \
2338  if ( unionD->xmin > cur->xmin ) unionD->xmin = cur->xmin; \
2339  if ( unionD->ymax < cur->ymax ) unionD->ymax = cur->ymax; \
2340  if ( unionD->ymin > cur->ymin ) unionD->ymin = cur->ymin; \
2341  } else { \
2342  memcpy( (void*)unionD, (void*) cur, sizeof( BOX2DF ) ); \
2343  } \
2344  list[pos] = num; \
2345  (pos)++; \
2346 } while(0)
2347 
2348  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2349  {
2350  cur = (BOX2DF*) DatumGetPointer(entryvec->vector[i].key);
2351 
2352  if (cur->xmin - pageunion.xmin < pageunion.xmax - cur->xmax)
2353  ADDLIST(listL, unionL, posL,i);
2354  else
2355  ADDLIST(listR, unionR, posR,i);
2356  if (cur->ymin - pageunion.ymin < pageunion.ymax - cur->ymax)
2357  ADDLIST(listB, unionB, posB,i);
2358  else
2359  ADDLIST(listT, unionT, posT,i);
2360  }
2361 
2362  POSTGIS_DEBUGF(4, "unionL is %s", box2df_to_string(unionL));
2363  POSTGIS_DEBUGF(4, "unionR is %s", box2df_to_string(unionR));
2364  POSTGIS_DEBUGF(4, "unionT is %s", box2df_to_string(unionT));
2365  POSTGIS_DEBUGF(4, "unionB is %s", box2df_to_string(unionB));
2366 
2367  /* bad disposition, sort by ascending and resplit */
2368  if ( (posR==0 || posL==0) && (posT==0 || posB==0) )
2369  {
2370  KBsort *arr = (KBsort*)palloc( sizeof(KBsort) * maxoff );
2371  posL = posR = posB = posT = 0;
2372  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2373  {
2374  arr[i-1].key = (BOX2DF*) DatumGetPointer(entryvec->vector[i].key);
2375  arr[i-1].pos = i;
2376  }
2377  qsort( arr, maxoff, sizeof(KBsort), compare_KB );
2378  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2379  {
2380  cur = arr[i-1].key;
2381  if (cur->xmin - pageunion.xmin < pageunion.xmax - cur->xmax)
2382  ADDLIST(listL, unionL, posL,arr[i-1].pos);
2383  else if ( cur->xmin - pageunion.xmin == pageunion.xmax - cur->xmax )
2384  {
2385  if ( posL>posR )
2386  ADDLIST(listR, unionR, posR,arr[i-1].pos);
2387  else
2388  ADDLIST(listL, unionL, posL,arr[i-1].pos);
2389  }
2390  else
2391  ADDLIST(listR, unionR, posR,arr[i-1].pos);
2392 
2393  if (cur->ymin - pageunion.ymin < pageunion.ymax - cur->ymax)
2394  ADDLIST(listB, unionB, posB,arr[i-1].pos);
2395  else if ( cur->ymin - pageunion.ymin == pageunion.ymax - cur->ymax )
2396  {
2397  if ( posB>posT )
2398  ADDLIST(listT, unionT, posT,arr[i-1].pos);
2399  else
2400  ADDLIST(listB, unionB, posB,arr[i-1].pos);
2401  }
2402  else
2403  ADDLIST(listT, unionT, posT,arr[i-1].pos);
2404  }
2405  pfree(arr);
2406  }
2407 
2408  /* which split more optimal? */
2409  if (Max(posL, posR) < Max(posB, posT))
2410  direction = 'x';
2411  else if (Max(posL, posR) > Max(posB, posT))
2412  direction = 'y';
2413  else
2414  {
2415  float sizeLR, sizeBT;
2416  BOX2DF interLR, interBT;
2417 
2418  if ( box2df_intersection(unionL, unionR, &interLR) == false )
2419  sizeLR = 0.0;
2420  else
2421  sizeLR = box2df_size(&interLR);
2422 
2423  if ( box2df_intersection(unionB, unionT, &interBT) == false )
2424  sizeBT = 0.0;
2425  else
2426  sizeBT = box2df_size(&interBT);
2427 
2428  if (sizeLR < sizeBT)
2429  direction = 'x';
2430  else
2431  direction = 'y';
2432  }
2433 
2434  POSTGIS_DEBUGF(4, "split direction '%c'", direction);
2435 
2436  if (direction == 'x')
2437  {
2438  pfree(unionB);
2439  pfree(listB);
2440  pfree(unionT);
2441  pfree(listT);
2442 
2443  v->spl_left = listL;
2444  v->spl_right = listR;
2445  v->spl_nleft = posL;
2446  v->spl_nright = posR;
2447  v->spl_ldatum = PointerGetDatum(unionL);
2448  v->spl_rdatum = PointerGetDatum(unionR);
2449  }
2450  else
2451  {
2452  pfree(unionR);
2453  pfree(listR);
2454  pfree(unionL);
2455  pfree(listL);
2456 
2457  v->spl_left = listB;
2458  v->spl_right = listT;
2459  v->spl_nleft = posB;
2460  v->spl_nright = posT;
2461  v->spl_ldatum = PointerGetDatum(unionB);
2462  v->spl_rdatum = PointerGetDatum(unionT);
2463  }
2464 
2465  POSTGIS_DEBUG(4, "[GIST] 'picksplit' completed");
2466 
2467  PG_RETURN_POINTER(v);
2468 }
2469 
2470 #endif
2471 
2472 
2473 /*
2474 ** The BOX32DF key must be defined as a PostgreSQL type, even though it is only
2475 ** ever used internally. These no-op stubs are used to bind the type.
2476 */
2478 Datum box2df_in(PG_FUNCTION_ARGS)
2479 {
2480  ereport(ERROR,(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2481  errmsg("function box2df_in not implemented")));
2482  PG_RETURN_POINTER(NULL);
2483 }
2484 
2486 Datum box2df_out(PG_FUNCTION_ARGS)
2487 {
2488  BOX2DF *box = (BOX2DF *) PG_GETARG_POINTER(0);
2489  char *result = box2df_to_string(box);
2490  PG_RETURN_CSTRING(result);
2491 }
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:639
static float non_negative(float val)
Datum gserialized_above_2d(PG_FUNCTION_ARGS)
Datum gserialized_overabove_2d(PG_FUNCTION_ARGS)
static float box2df_union_edge(const BOX2DF *a, const BOX2DF *b)
static void box2df_validate(BOX2DF *b)
uint8_t data[1]
Definition: liblwgeom.h:386
#define LIMIT_RATIO
Datum gserialized_gist_penalty_2d(PG_FUNCTION_ARGS)
static bool box2df_overlaps(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_gist_compress_2d(PG_FUNCTION_ARGS)
int box2df_to_gbox_p(BOX2DF *a, GBOX *box)
Datum gserialized_contains_box2df_box2df_2d(PG_FUNCTION_ARGS)
static bool box2df_left(const BOX2DF *a, const BOX2DF *b)
double xmax
Definition: liblwgeom.h:295
#define NAN
Definition: lwgeodetic.h:37
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
#define LW_SUCCESS
Definition: liblwgeom.h:79
static bool box2df_below(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_left_2d(PG_FUNCTION_ARGS)
static bool gserialized_gist_consistent_leaf_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, float rightLower, int minLeftCount, float leftUpper, int maxLeftCount)
static int interval_cmp_lower(const void *i1, const void *i2)
static void box2df_set_finite(BOX2DF *a)
static void adjustBox(BOX2DF *b, BOX2DF *addon)
static bool box2df_right(const BOX2DF *a, const BOX2DF *b)
float next_float_down(double d)
Definition: lwgeom_api.c:52
BOX2DF * box2df_copy(BOX2DF *b)
Datum gserialized_contains_box2df_geom_2d(PG_FUNCTION_ARGS)
static bool box2df_above(const BOX2DF *a, const BOX2DF *b)
static float box2df_size(const BOX2DF *a)
bool(* box2df_predicate)(const BOX2DF *a, const BOX2DF *b)
static bool box2df_within(const BOX2DF *a, const BOX2DF *b)
#define LW_FAILURE
Definition: liblwgeom.h:78
float next_float_up(double d)
Definition: lwgeom_api.c:68
static int box2df_from_gbox_p(GBOX *box, BOX2DF *a)
double ymin
Definition: liblwgeom.h:296
Datum gserialized_overlaps_2d(PG_FUNCTION_ARGS)
Datum gserialized_distance_centroid_2d(PG_FUNCTION_ARGS)
Datum gserialized_within_box2df_geom_2d(PG_FUNCTION_ARGS)
Datum gserialized_overbelow_2d(PG_FUNCTION_ARGS)
void gbox_init(GBOX *gbox)
Zero out all the entries in the GBOX.
Definition: g_box.c:47
Datum gserialized_within_box2df_box2df_2d(PG_FUNCTION_ARGS)
double xmin
Definition: liblwgeom.h:294
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.
#define FLAGS_GET_BBOX(flags)
Definition: liblwgeom.h:141
static char * box2df_to_string(const BOX2DF *a)
#define LW_FALSE
Definition: liblwgeom.h:76
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
static void box2df_set_empty(BOX2DF *a)
Datum gserialized_below_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_same_2d(PG_FUNCTION_ARGS)
Datum gserialized_within_2d(PG_FUNCTION_ARGS)
int gserialized_datum_get_box2df_p(Datum gsdatum, BOX2DF *box2df)
Peak into a GSERIALIZED datum to find the bounding box.
Datum gserialized_overleft_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_consistent_2d(PG_FUNCTION_ARGS)
Datum box2df_out(PG_FUNCTION_ARGS)
double ymax
Definition: liblwgeom.h:297
Datum gserialized_overlaps_box2df_box2df_2d(PG_FUNCTION_ARGS)
static float pack_float(const float value, const int realm)
Datum gserialized_same_2d(PG_FUNCTION_ARGS)
static int interval_cmp_upper(const void *i1, const void *i2)
static double pt_distance(double ax, double ay, double bx, double by)
Datum distance(PG_FUNCTION_ARGS)
static bool box2df_overright(const BOX2DF *a, const BOX2DF *b)
static int common_entry_cmp(const void *i1, const void *i2)
Datum gserialized_gist_picksplit_2d(PG_FUNCTION_ARGS)
static bool box2df_overabove(const BOX2DF *a, const BOX2DF *b)
static bool box2df_overbelow(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_gist_decompress_2d(PG_FUNCTION_ARGS)
static bool box2df_overleft(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_overright_2d(PG_FUNCTION_ARGS)
bool box2df_contains(const BOX2DF *a, const BOX2DF *b)
#define PLACE_RIGHT(box, off)
static float box2df_union_size(const BOX2DF *a, const BOX2DF *b)
static int gserialized_datum_predicate_2d(Datum gs1, Datum gs2, box2df_predicate predicate)
Support function.
int value
Definition: genraster.py:61
static int gserialized_datum_predicate_box2df_geom_2d(const BOX2DF *br1, Datum gs2, box2df_predicate predicate)
Datum gserialized_overlaps_box2df_geom_2d(PG_FUNCTION_ARGS)
static bool box2df_equals(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_right_2d(PG_FUNCTION_ARGS)
unsigned char uint8_t
Definition: uthash.h:79
Datum box2df_in(PG_FUNCTION_ARGS)
void box2df_merge(BOX2DF *b_union, BOX2DF *b_new)
Datum gserialized_contains_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_union_2d(PG_FUNCTION_ARGS)
Datum gserialized_gist_distance_2d(PG_FUNCTION_ARGS)
#define PLACE_LEFT(box, off)
bool box2df_is_empty(const BOX2DF *a)
static bool gserialized_gist_consistent_internal_2d(BOX2DF *key, BOX2DF *query, StrategyNumber strategy)
static float box_penalty(BOX2DF *original, BOX2DF *new)
Datum gserialized_distance_box_2d(PG_FUNCTION_ARGS)
PG_FUNCTION_INFO_V1(gserialized_contains_box2df_geom_2d)
This library is the generic geometry handling section of PostGIS.
uint8_t flags
Definition: liblwgeom.h:385
static float box2df_edge(const BOX2DF *a)