PostGIS  2.5.7dev-r@@SVN_REVISION@@
gserialized_spgist_2d.c
Go to the documentation of this file.
1 /*****************************************************************************
2  *
3  * gserialized_spgist_2d.c
4  * SP-GiST implementation of 4-dimensional quad-tree over box2df
5  *
6  * This module provides SP-GiST implementation for boxes using quad tree
7  * analogy in 4-dimensional space. SP-GiST doesn't allow indexing of
8  * overlapping objects. We are making objects never-overlapping in
9  * 4D space. This technique has some benefits compared to traditional
10  * R-Tree which is implemented as GiST. The performance tests reveal
11  * that this technique especially beneficial with too much overlapping
12  * objects, so called "spaghetti data".
13  *
14  * Unlike the original quad-tree, we are splitting the tree into 16
15  * quadrants in 4D space. It is easier to imagine it as splitting space
16  * two times into 2:
17  *
18  * | |
19  * | |
20  * | -----+-----
21  * | |
22  * | |
23  * -------------+-------------
24  * |
25  * |
26  * |
27  * |
28  * |
29  * FRONT
30  *
31  * We are using box data type as the prefix, but we are treating them
32  * as points in 4-dimensional space, because boxes are not enough
33  * to represent the quadrant boundaries in 4D space. They however are
34  * sufficient to point out the additional boundaries of the next
35  * quadrant.
36  *
37  * We are using traversal values provided by SP-GiST to calculate and
38  * to store the bounds of the quadrants, while traversing into the tree.
39  * Traversal value has all the boundaries in the 4D space, and is is
40  * capable of transferring the required boundaries to the following
41  * traversal values. In conclusion, three things are necessary
42  * to calculate the next traversal value:
43  *
44  * (1) the traversal value of the parent
45  * (2) the quadrant of the current node
46  * (3) the prefix of the current node
47  *
48  * If we visualize them on our simplified drawing (see the drawing above);
49  * transferred boundaries of (1) would be the outer axis, relevant part
50  * of (2) would be the up range_y part of the other axis, and (3) would be
51  * the inner axis.
52  *
53  * For example, consider the case of overlapping. When recursion
54  * descends deeper and deeper down the tree, all quadrants in
55  * the current node will be checked for overlapping. The boundaries
56  * will be re-calculated for all quadrants. Overlap check answers
57  * the question: can any box from this quadrant overlap with the given
58  * box? If yes, then this quadrant will be walked. If no, then this
59  * quadrant will be skipped.
60  *
61  * This method provides restrictions for minimum and maximum values of
62  * every dimension of every corner of the box on every level of the tree
63  * except the root. For the root node, we are setting the boundaries
64  * that we don't yet have as infinity.
65  *
66  * Portions Copyright (c) 2018, Esteban Zimanyi, Arthur Lesuisse,
67  * Universit√© Libre de Bruxelles
68  * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
69  * Portions Copyright (c) 1994, Regents of the University of California
70  *
71  *****************************************************************************/
72 
73 #include <postgres.h>
74 #include <utils/builtins.h> /* For float manipulation */
75 #include "access/spgist.h" /* For SP-GiST */
76 #include "catalog/pg_type_d.h" /* For VOIDOID */
77 
78 #include "../postgis_config.h"
79 
80 #include "liblwgeom.h" /* For standard geometry types. */
81 #include "lwgeom_pg.h" /* For debugging macros. */
82 #include <gserialized_gist.h> /* For utility functions. */
83 #include <lwgeom_pg.h> /* For debugging macros. */
84 
85 /*
86 ** SP-GiST 2D index function prototypes
87 */
88 
89 Datum gserialized_spgist_config_2d(PG_FUNCTION_ARGS);
90 Datum gserialized_spgist_choose_2d(PG_FUNCTION_ARGS);
91 Datum gserialized_spgist_picksplit_2d(PG_FUNCTION_ARGS);
92 Datum gserialized_spgist_inner_consistent_2d(PG_FUNCTION_ARGS);
93 Datum gserialized_spgist_leaf_consistent_2d(PG_FUNCTION_ARGS);
94 Datum gserialized_spgist_compress_2d(PG_FUNCTION_ARGS);
95 
96 /*
97  * Comparator for qsort
98  *
99  * We don't need to use the floating point macros in here, because this
100  * is only going to be used in a place to effect the performance
101  * of the index, not the correctness.
102  */
103 static int
104 compareDoubles(const void *a, const void *b)
105 {
106  double x = *(double *)a;
107  double y = *(double *)b;
108 
109  if (x == y)
110  return 0;
111  return (x > y) ? 1 : -1;
112 }
113 
114 typedef struct
115 {
116  BOX2DF left;
117  BOX2DF right;
118 } RectBox;
119 
120 /*
121  * Calculate the quadrant
122  *
123  * The quadrant is 4 bit unsigned integer with 4 least bits in use.
124  * This function accepts 2 BOX2DF as input. All 4 bits are set by comparing
125  * a corner of the box. This makes 16 quadrants in total.
126  */
127 static uint8
128 getQuadrant4D(BOX2DF *centroid, BOX2DF *inBox)
129 {
130  uint8 quadrant = 0;
131 
132  if (inBox->xmin > centroid->xmin)
133  quadrant |= 0x8;
134 
135  if (inBox->xmax > centroid->xmax)
136  quadrant |= 0x4;
137 
138  if (inBox->ymin > centroid->ymin)
139  quadrant |= 0x2;
140 
141  if (inBox->ymax > centroid->ymax)
142  quadrant |= 0x1;
143 
144  return quadrant;
145 }
146 
147 /*
148  * Initialize the traversal value
149  *
150  * In the beginning, we don't have any restrictions. We have to
151  * initialize the struct to cover the whole 4D space.
152  */
153 static RectBox *
155 {
156  RectBox *rect_box = (RectBox *)palloc(sizeof(RectBox));
157  float infinity = FLT_MAX;
158 
159  rect_box->left.xmin = -infinity;
160  rect_box->left.xmax = infinity;
161 
162  rect_box->left.ymin = -infinity;
163  rect_box->left.ymax = infinity;
164 
165  rect_box->right.xmin = -infinity;
166  rect_box->right.xmax = infinity;
167 
168  rect_box->right.ymin = -infinity;
169  rect_box->right.ymax = infinity;
170 
171  return rect_box;
172 }
173 
174 /*
175  * Calculate the next traversal value
176  *
177  * All centroids are bounded by RectBox, but SP-GiST only keeps
178  * boxes. When we are traversing the tree, we must calculate RectBox,
179  * using centroid and quadrant.
180  */
181 static RectBox *
182 nextRectBox(RectBox *rect_box, BOX2DF *centroid, uint8 quadrant)
183 {
184  RectBox *next_rect_box = (RectBox *)palloc(sizeof(RectBox));
185 
186  memcpy(next_rect_box, rect_box, sizeof(RectBox));
187 
188  if (quadrant & 0x8)
189  next_rect_box->left.xmin = centroid->xmin;
190  else
191  next_rect_box->left.xmax = centroid->xmin;
192 
193  if (quadrant & 0x4)
194  next_rect_box->right.xmin = centroid->xmax;
195  else
196  next_rect_box->right.xmax = centroid->xmax;
197 
198  if (quadrant & 0x2)
199  next_rect_box->left.ymin = centroid->ymin;
200  else
201  next_rect_box->left.ymax = centroid->ymin;
202 
203  if (quadrant & 0x1)
204  next_rect_box->right.ymin = centroid->ymax;
205  else
206  next_rect_box->right.ymax = centroid->ymax;
207 
208  return next_rect_box;
209 }
210 
211 /* Can any cube from rect_box overlap with query? */
212 static bool
213 overlap4D(RectBox *rect_box, BOX2DF *query)
214 {
215  return (rect_box->left.xmin <= query->xmax && rect_box->right.xmax >= query->xmin) &&
216  (rect_box->left.ymin <= query->ymax && rect_box->right.ymax >= query->ymin);
217 }
218 
219 /* Can any cube from rect_box contain query? */
220 static bool
221 contain4D(RectBox *rect_box, BOX2DF *query)
222 {
223  return (rect_box->right.xmax >= query->xmax && rect_box->left.xmin <= query->xmin) &&
224  (rect_box->right.ymax >= query->ymax && rect_box->left.ymin <= query->ymin);
225 }
226 
227 /* Can any cube from rect_box be left of query? */
228 static bool
229 left4D(RectBox *rect_box, BOX2DF *query)
230 {
231  return rect_box->right.xmax <= query->xmin;
232 }
233 
234 /* Can any cube from rect_box does not extend the right of query? */
235 static bool
236 overLeft4D(RectBox *rect_box, BOX2DF *query)
237 {
238  return rect_box->right.xmax <= query->xmax;
239 }
240 
241 /* Can any cube from rect_box be right of query? */
242 static bool
243 right4D(RectBox *rect_box, BOX2DF *query)
244 {
245  return rect_box->left.xmin >= query->xmax;
246 }
247 
248 /* Can any cube from rect_box does not extend the left of query? */
249 static bool
250 overRight4D(RectBox *rect_box, BOX2DF *query)
251 {
252  return rect_box->left.xmin >= query->xmin;
253 }
254 
255 /* Can any cube from rect_box be below of query? */
256 static bool
257 below4D(RectBox *rect_box, BOX2DF *query)
258 {
259  return rect_box->right.ymax <= query->ymin;
260 }
261 
262 /* Can any cube from rect_box does not extend above query? */
263 static bool
264 overBelow4D(RectBox *rect_box, BOX2DF *query)
265 {
266  return rect_box->right.ymax <= query->ymax;
267 }
268 
269 /* Can any cube from rect_box be above of query? */
270 static bool
271 above4D(RectBox *rect_box, BOX2DF *query)
272 {
273  return rect_box->left.ymin >= query->ymax;
274 }
275 
276 /* Can any cube from rect_box does not extend below of query? */
277 static bool
278 overAbove4D(RectBox *rect_box, BOX2DF *query)
279 {
280  return rect_box->left.ymin >= query->ymin;
281 }
282 
283 /*
284  * SP-GiST config function
285  */
286 
288 
289 PGDLLEXPORT Datum gserialized_spgist_config_2d(PG_FUNCTION_ARGS)
290 {
291  spgConfigOut *cfg = (spgConfigOut *)PG_GETARG_POINTER(1);
292  Oid boxoid = InvalidOid;
293  postgis_initialize_cache(fcinfo);
294  boxoid = postgis_oid(BOX2DFOID);
295 
296  cfg->prefixType = boxoid;
297  cfg->labelType = VOIDOID; /* We don't need node labels. */
298  cfg->leafType = boxoid;
299  cfg->canReturnData = false;
300  cfg->longValuesOK = false;
301 
302  PG_RETURN_VOID();
303 }
304 
305 /*
306  * SP-GiST choose function
307  */
308 
310 
311 PGDLLEXPORT Datum gserialized_spgist_choose_2d(PG_FUNCTION_ARGS)
312 {
313  spgChooseIn *in = (spgChooseIn *)PG_GETARG_POINTER(0);
314  spgChooseOut *out = (spgChooseOut *)PG_GETARG_POINTER(1);
315  BOX2DF *centroid = (BOX2DF *)DatumGetPointer(in->prefixDatum), *box = (BOX2DF *)DatumGetPointer(in->leafDatum);
316 
317  out->resultType = spgMatchNode;
318  out->result.matchNode.restDatum = PointerGetDatum(box);
319 
320  /* nodeN will be set by core, when allTheSame. */
321  if (!in->allTheSame)
322  out->result.matchNode.nodeN = getQuadrant4D(centroid, box);
323 
324  PG_RETURN_VOID();
325 }
326 
327 /*
328  * SP-GiST pick-split function
329  *
330  * It splits a list of boxes into quadrants by choosing a central 4D
331  * point as the median of the coordinates of the boxes.
332  */
334 
335 PGDLLEXPORT Datum gserialized_spgist_picksplit_2d(PG_FUNCTION_ARGS)
336 {
337  spgPickSplitIn *in = (spgPickSplitIn *)PG_GETARG_POINTER(0);
338  spgPickSplitOut *out = (spgPickSplitOut *)PG_GETARG_POINTER(1);
339  BOX2DF *centroid;
340  int median, i;
341  double *lowXs = palloc(sizeof(double) * in->nTuples);
342  double *highXs = palloc(sizeof(double) * in->nTuples);
343  double *lowYs = palloc(sizeof(double) * in->nTuples);
344  double *highYs = palloc(sizeof(double) * in->nTuples);
345 
346  /* Calculate median of all 4D coordinates */
347  for (i = 0; i < in->nTuples; i++)
348  {
349  BOX2DF *box = (BOX2DF *)DatumGetPointer(in->datums[i]);
350 
351  lowXs[i] = (double)box->xmin;
352  highXs[i] = (double)box->xmax;
353  lowYs[i] = (double)box->ymin;
354  highYs[i] = (double)box->ymax;
355  }
356 
357  qsort(lowXs, in->nTuples, sizeof(double), compareDoubles);
358  qsort(highXs, in->nTuples, sizeof(double), compareDoubles);
359  qsort(lowYs, in->nTuples, sizeof(double), compareDoubles);
360  qsort(highYs, in->nTuples, sizeof(double), compareDoubles);
361 
362  median = in->nTuples / 2;
363 
364  centroid = palloc(sizeof(BOX2DF));
365 
366  centroid->xmin = (float)lowXs[median];
367  centroid->xmax = (float)highXs[median];
368  centroid->ymin = (float)lowYs[median];
369  centroid->ymax = (float)highYs[median];
370 
371  /* Fill the output */
372  out->hasPrefix = true;
373  out->prefixDatum = BoxPGetDatum(centroid);
374 
375  out->nNodes = 16;
376  out->nodeLabels = NULL; /* We don't need node labels. */
377 
378  out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
379  out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
380 
381  /*
382  * Assign ranges to corresponding nodes according to quadrants relative to the "centroid" range
383  */
384  for (i = 0; i < in->nTuples; i++)
385  {
386  BOX2DF *box = (BOX2DF *)DatumGetPointer(in->datums[i]);
387  uint8 quadrant = getQuadrant4D(centroid, box);
388 
389  out->leafTupleDatums[i] = PointerGetDatum(box);
390  out->mapTuplesToNodes[i] = quadrant;
391  }
392 
393  pfree(lowXs);
394  pfree(highXs);
395  pfree(lowYs);
396  pfree(highYs);
397 
398  PG_RETURN_VOID();
399 }
400 
401 /*
402  * SP-GiST inner consistent function
403  */
405 
406 PGDLLEXPORT Datum gserialized_spgist_inner_consistent_2d(PG_FUNCTION_ARGS)
407 {
408  spgInnerConsistentIn *in = (spgInnerConsistentIn *)PG_GETARG_POINTER(0);
409  spgInnerConsistentOut *out = (spgInnerConsistentOut *)PG_GETARG_POINTER(1);
410  int i;
411  MemoryContext old_ctx;
412  RectBox *rect_box;
413  uint8 quadrant;
414  BOX2DF *centroid;
415 
416  if (in->allTheSame)
417  {
418  /* Report that all nodes should be visited */
419  out->nNodes = in->nNodes;
420  out->nodeNumbers = (int *)palloc(sizeof(int) * in->nNodes);
421  for (i = 0; i < in->nNodes; i++)
422  out->nodeNumbers[i] = i;
423 
424  PG_RETURN_VOID();
425  }
426 
427  /*
428  * We are saving the traversal value or initialize it an unbounded one, if
429  * we have just begun to walk the tree.
430  */
431  if (in->traversalValue)
432  rect_box = in->traversalValue;
433  else
434  rect_box = initRectBox();
435 
436  centroid = (BOX2DF *)DatumGetPointer(in->prefixDatum);
437 
438  /* Allocate enough memory for nodes */
439  out->nNodes = 0;
440  out->nodeNumbers = (int *)palloc(sizeof(int) * in->nNodes);
441  out->traversalValues = (void **)palloc(sizeof(void *) * in->nNodes);
442 
443  /*
444  * We switch memory context, because we want to allocate memory for new
445  * traversal values (next_rect_box) and pass these pieces of memory to
446  * further call of this function.
447  */
448  old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
449 
450  for (quadrant = 0; quadrant < in->nNodes; quadrant++)
451  {
452  RectBox *next_rect_box = nextRectBox(rect_box, centroid, quadrant);
453  bool flag = true;
454 
455  for (i = 0; i < in->nkeys; i++)
456  {
457  StrategyNumber strategy = in->scankeys[i].sk_strategy;
458 
459  Datum query = in->scankeys[i].sk_argument;
460  BOX2DF query_gbox_index;
461 
462  /* Quick sanity check on query argument. */
463  if (DatumGetPointer(query) == NULL)
464  {
465  POSTGIS_DEBUG(4, "[SPGIST] null query pointer (!?!), returning false");
466  PG_RETURN_BOOL(false); /* NULL query! This is screwy! */
467  }
468 
469  if (gserialized_datum_get_box2df_p(query, &query_gbox_index) == LW_FAILURE)
470  {
471  POSTGIS_DEBUG(4, "[SPGIST] null query_gbox_index!");
472  PG_RETURN_BOOL(false);
473  }
474 
475  switch (strategy)
476  {
477  case RTOverlapStrategyNumber:
478  case RTContainedByStrategyNumber:
479  case RTOldContainedByStrategyNumber:
480  flag = overlap4D(next_rect_box, &query_gbox_index);
481  break;
482 
483  case RTContainsStrategyNumber:
484  case RTSameStrategyNumber:
485  flag = contain4D(next_rect_box, &query_gbox_index);
486  break;
487 
488  case RTLeftStrategyNumber:
489  flag = !overRight4D(next_rect_box, &query_gbox_index);
490  break;
491 
492  case RTOverLeftStrategyNumber:
493  flag = !right4D(next_rect_box, &query_gbox_index);
494  break;
495 
496  case RTRightStrategyNumber:
497  flag = !overLeft4D(next_rect_box, &query_gbox_index);
498  break;
499 
500  case RTOverRightStrategyNumber:
501  flag = !left4D(next_rect_box, &query_gbox_index);
502  break;
503 
504  case RTAboveStrategyNumber:
505  flag = !overBelow4D(next_rect_box, &query_gbox_index);
506  break;
507 
508  case RTOverAboveStrategyNumber:
509  flag = !below4D(next_rect_box, &query_gbox_index);
510  break;
511 
512  case RTBelowStrategyNumber:
513  flag = !overAbove4D(next_rect_box, &query_gbox_index);
514  break;
515 
516  case RTOverBelowStrategyNumber:
517  flag = !above4D(next_rect_box, &query_gbox_index);
518  break;
519 
520  default:
521  elog(ERROR, "unrecognized strategy: %d", strategy);
522  }
523 
524  /* If any check is failed, we have found our answer. */
525  if (!flag)
526  break;
527  }
528 
529  if (flag)
530  {
531  out->traversalValues[out->nNodes] = next_rect_box;
532  out->nodeNumbers[out->nNodes] = quadrant;
533  out->nNodes++;
534  }
535  else
536  {
537  /*
538  * If this node is not selected, we don't need to keep the next
539  * traversal value in the memory context.
540  */
541  pfree(next_rect_box);
542  }
543  }
544 
545  /* Switch after */
546  MemoryContextSwitchTo(old_ctx);
547 
548  PG_RETURN_VOID();
549 }
550 
551 /*
552  * SP-GiST inner consistent function
553  */
555 
556 PGDLLEXPORT Datum gserialized_spgist_leaf_consistent_2d(PG_FUNCTION_ARGS)
557 {
558  spgLeafConsistentIn *in = (spgLeafConsistentIn *)PG_GETARG_POINTER(0);
559  spgLeafConsistentOut *out = (spgLeafConsistentOut *)PG_GETARG_POINTER(1);
560  BOX2DF *key = (BOX2DF *)DatumGetPointer(in->leafDatum);
561  bool flag = true;
562  int i;
563 
564  /* Quick sanity check on entry key. */
565  if (DatumGetPointer(key) == NULL)
566  {
567  POSTGIS_DEBUG(4, "[SPGIST] null index entry, returning false");
568  PG_RETURN_BOOL(false); /* NULL entry! */
569  }
570 
571  /* All tests are exact. */
572  out->recheck = false;
573 
574  /* leafDatum is what it is... */
575  out->leafValue = in->leafDatum;
576 
577  /* Perform the required comparison(s) */
578  for (i = 0; i < in->nkeys; i++)
579  {
580  StrategyNumber strategy = in->scankeys[i].sk_strategy;
581  Datum query = in->scankeys[i].sk_argument;
582  BOX2DF query_gbox_index;
583 
584  /* Quick sanity check on query argument. */
585  if (DatumGetPointer(query) == NULL)
586  {
587  POSTGIS_DEBUG(4, "[SPGIST] null query pointer (!?!), returning false");
588  PG_RETURN_BOOL(false); /* NULL query! This is screwy! */
589  }
590 
591  if (gserialized_datum_get_box2df_p(query, &query_gbox_index) == LW_FAILURE)
592  {
593  POSTGIS_DEBUG(4, "[SPGIST] null query_gbox_index!");
594  PG_RETURN_BOOL(false);
595  }
596 
597  switch (strategy)
598  {
599  case RTOverlapStrategyNumber:
600  flag = box2df_overlaps(key, &query_gbox_index);
601  break;
602 
603  case RTContainsStrategyNumber:
604  case RTOldContainsStrategyNumber:
605  flag = box2df_contains(key, &query_gbox_index);
606  break;
607 
608  case RTContainedByStrategyNumber:
609  case RTOldContainedByStrategyNumber:
610  flag = box2df_contains(&query_gbox_index, key);
611  break;
612 
613  case RTSameStrategyNumber:
614  flag = box2df_equals(key, &query_gbox_index);
615  break;
616 
617  case RTLeftStrategyNumber:
618  flag = box2df_left(key, &query_gbox_index);
619  break;
620 
621  case RTOverLeftStrategyNumber:
622  flag = box2df_overleft(key, &query_gbox_index);
623  break;
624 
625  case RTRightStrategyNumber:
626  flag = box2df_right(key, &query_gbox_index);
627  break;
628 
629  case RTOverRightStrategyNumber:
630  flag = box2df_overright(key, &query_gbox_index);
631  break;
632 
633  case RTAboveStrategyNumber:
634  flag = box2df_above(key, &query_gbox_index);
635  break;
636 
637  case RTOverAboveStrategyNumber:
638  flag = box2df_overabove(key, &query_gbox_index);
639  break;
640 
641  case RTBelowStrategyNumber:
642  flag = box2df_below(key, &query_gbox_index);
643  break;
644 
645  case RTOverBelowStrategyNumber:
646  flag = box2df_overbelow(key, &query_gbox_index);
647  break;
648 
649  default:
650  elog(ERROR, "unrecognized strategy: %d", strategy);
651  }
652 
653  /* If any check is failed, we have found our answer. */
654  if (!flag)
655  break;
656  }
657 
658  PG_RETURN_BOOL(flag);
659 }
660 
662 
663 PGDLLEXPORT Datum gserialized_spgist_compress_2d(PG_FUNCTION_ARGS)
664 {
665  Datum gsdatum = PG_GETARG_DATUM(0);
666  BOX2DF *bbox_out = palloc(sizeof(BOX2DF));
667  int result = LW_SUCCESS;
668 
669  POSTGIS_DEBUG(4, "[SPGIST] 'compress' function called");
670 
671  /* Extract the index key from the argument. */
672  result = gserialized_datum_get_box2df_p(gsdatum, bbox_out);
673 
674  /* Is the bounding box valid (non-empty, non-infinite)? If not, return input uncompressed. */
675  if (result == LW_FAILURE)
676  {
677  box2df_set_empty(bbox_out);
678 
679  POSTGIS_DEBUG(4, "[SPGIST] empty geometry!");
680  PG_RETURN_POINTER(bbox_out);
681  }
682 
683  /* Check all the dimensions for finite values */
684  if ((!isfinite(bbox_out->xmax) || !isfinite(bbox_out->xmin)) ||
685  (!isfinite(bbox_out->ymax) || !isfinite(bbox_out->ymin)))
686  {
687  box2df_set_finite(bbox_out);
688 
689  POSTGIS_DEBUG(4, "[SPGIST] infinite geometry!");
690  PG_RETURN_POINTER(bbox_out);
691  }
692 
693  /* Ensure bounding box has minimums below maximums. */
694  box2df_validate(bbox_out);
695 
696  /* Return BOX2DF. */
697  POSTGIS_DEBUG(4, "[SPGIST] 'compress' function complete");
698  PG_RETURN_POINTER(bbox_out);
699 }
700 
701 /*****************************************************************************/
bool box2df_left(const BOX2DF *a, const BOX2DF *b)
void box2df_set_empty(BOX2DF *a)
bool box2df_equals(const BOX2DF *a, const BOX2DF *b)
bool box2df_contains(const BOX2DF *a, const BOX2DF *b)
bool box2df_right(const BOX2DF *a, const BOX2DF *b)
bool box2df_overlaps(const BOX2DF *a, const BOX2DF *b)
void box2df_set_finite(BOX2DF *a)
bool box2df_above(const BOX2DF *a, const BOX2DF *b)
bool box2df_overbelow(const BOX2DF *a, const BOX2DF *b)
bool box2df_overright(const BOX2DF *a, const BOX2DF *b)
int gserialized_datum_get_box2df_p(Datum gsdatum, BOX2DF *box2df)
Peak into a GSERIALIZED datum to find the bounding box.
bool box2df_overabove(const BOX2DF *a, const BOX2DF *b)
void box2df_validate(BOX2DF *b)
bool box2df_below(const BOX2DF *a, const BOX2DF *b)
bool box2df_overleft(const BOX2DF *a, const BOX2DF *b)
Datum gserialized_spgist_compress_2d(PG_FUNCTION_ARGS)
Datum gserialized_spgist_choose_2d(PG_FUNCTION_ARGS)
static bool right4D(RectBox *rect_box, BOX2DF *query)
static bool overRight4D(RectBox *rect_box, BOX2DF *query)
static bool overlap4D(RectBox *rect_box, BOX2DF *query)
static bool overAbove4D(RectBox *rect_box, BOX2DF *query)
static bool above4D(RectBox *rect_box, BOX2DF *query)
static int compareDoubles(const void *a, const void *b)
Datum gserialized_spgist_config_2d(PG_FUNCTION_ARGS)
static uint8 getQuadrant4D(BOX2DF *centroid, BOX2DF *inBox)
static RectBox * nextRectBox(RectBox *rect_box, BOX2DF *centroid, uint8 quadrant)
PG_FUNCTION_INFO_V1(gserialized_spgist_config_2d)
static RectBox * initRectBox(void)
static bool contain4D(RectBox *rect_box, BOX2DF *query)
static bool left4D(RectBox *rect_box, BOX2DF *query)
Datum gserialized_spgist_picksplit_2d(PG_FUNCTION_ARGS)
Datum gserialized_spgist_leaf_consistent_2d(PG_FUNCTION_ARGS)
static bool below4D(RectBox *rect_box, BOX2DF *query)
static bool overBelow4D(RectBox *rect_box, BOX2DF *query)
static bool overLeft4D(RectBox *rect_box, BOX2DF *query)
Datum gserialized_spgist_inner_consistent_2d(PG_FUNCTION_ARGS)
#define LW_FAILURE
Definition: liblwgeom.h:79
#define LW_SUCCESS
Definition: liblwgeom.h:80
This library is the generic geometry handling section of PostGIS.
Datum centroid(PG_FUNCTION_ARGS)