PostGIS  2.5.7dev-r@@SVN_REVISION@@
gserialized_spgist_3d.c
Go to the documentation of this file.
1 /*****************************************************************************
2  *
3  * gserialized_spgist_3d.c
4  * SP-GiST implementation of 6-dimensional oct-tree over 3D boxes
5  *
6  * This module provides SP-GiST implementation for boxes using oct tree
7  * analogy in 4-dimensional space. SP-GiST doesn't allow indexing of
8  * overlapping objects. We are making 3D objects never-overlapping in
9  * 6D 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 oct-tree, we are splitting the tree into 64
15  * octants in 6D space. It is easier to imagine it as splitting space
16  * three times into 3:
17  *
18  * | | | |
19  * | | | |
20  * | -----+----- | -----+-----
21  * | | | |
22  * | | | |
23  * -------------+------------- -+- -------------+-------------
24  * | |
25  * | |
26  * | |
27  * | |
28  * | |
29  * FRONT BACK
30  *
31  * We are using box3D data type as the prefix, but we are treating them
32  * as points in 6-dimensional space, because 3D boxes are not enough
33  * to represent the octant boundaries in 6D space. They however are
34  * sufficient to point out the additional boundaries of the next
35  * octant.
36  *
37  * We are using traversal values provided by SP-GiST to calculate and
38  * to store the bounds of the octants, while traversing into the tree.
39  * Traversal value has all the boundaries in the 6D 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 octant 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 octants in
55  * the current node will be checked for overlapping. The boundaries
56  * will be re-calculated for all octants. Overlap check answers
57  * the question: can any box from this octant overlap with the given
58  * box? If yes, then this octant will be walked. If no, then this
59  * octant 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 "gserialized_spgist_3d.h"
74 #include "lwgeom_box3d.h"
75 #include "lwgeom_pg.h"
76 
77 #include <float.h>
78 
80 Datum gserialized_overlaps_3d(PG_FUNCTION_ARGS)
81 {
82  BOX3D *box1 = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(0)));
83  BOX3D *box2 = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(1)));
84  bool resut = BOX3D_overlaps_internal(box1, box2);
85  pfree(box1);
86  pfree(box2);
87 
88  PG_RETURN_BOOL(resut);
89 }
90 
92 Datum gserialized_contains_3d(PG_FUNCTION_ARGS)
93 {
94  BOX3D *box1 = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(0)));
95  BOX3D *box2 = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(1)));
96  bool resut = BOX3D_contains_internal(box1, box2);
97  pfree(box1);
98  pfree(box2);
99 
100  PG_RETURN_BOOL(resut);
101 }
102 
104 Datum gserialized_contained_3d(PG_FUNCTION_ARGS)
105 {
106  BOX3D *box1 = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(0)));
107  BOX3D *box2 = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(1)));
108  bool resut = BOX3D_contained_internal(box1, box2);
109  pfree(box1);
110  pfree(box2);
111 
112  PG_RETURN_BOOL(resut);
113 }
114 
116 Datum gserialized_same_3d(PG_FUNCTION_ARGS)
117 {
118  BOX3D *box1 = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(0)));
119  BOX3D *box2 = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(1)));
120  bool resut = BOX3D_same_internal(box1, box2);
121  pfree(box1);
122  pfree(box2);
123 
124  PG_RETURN_BOOL(resut);
125 }
126 
127 /*
128  * Comparator for qsort
129  *
130  * We don't need to use the floating point macros in here, because this
131  * is only going to be used in a place to effect the performance
132  * of the index, not the correctness.
133  */
134 static int
135 compareDoubles(const void *a, const void *b)
136 {
137  double x = *(double *)a;
138  double y = *(double *)b;
139 
140  if (x == y)
141  return 0;
142  return (x > y) ? 1 : -1;
143 }
144 
145 typedef struct
146 {
149 } CubeBox3D;
150 
151 /*
152  * Calculate the octant
153  *
154  * The octant is 8 bit unsigned integer with 6 least bits in use.
155  * This function accepts 2 BOX3D as input. All 6 bits are set by comparing
156  * a corner of the box. This makes 64 octants in total.
157  */
158 static uint8
160 {
161  uint8 octant = 0;
162 
163  if (inBox->xmin > centroid->xmin)
164  octant |= 0x20;
165 
166  if (inBox->xmax > centroid->xmax)
167  octant |= 0x10;
168 
169  if (inBox->ymin > centroid->ymin)
170  octant |= 0x08;
171 
172  if (inBox->ymax > centroid->ymax)
173  octant |= 0x04;
174 
175  if (inBox->zmin > centroid->zmin)
176  octant |= 0x02;
177 
178  if (inBox->zmax > centroid->zmax)
179  octant |= 0x01;
180 
181  return octant;
182 }
183 
184 /*
185  * Initialize the traversal value
186  *
187  * In the beginning, we don't have any restrictions. We have to
188  * initialize the struct to cover the whole 6D space.
189  */
190 static CubeBox3D *
192 {
193  CubeBox3D *cube_box = (CubeBox3D *)palloc(sizeof(CubeBox3D));
194  double infinity = DBL_MAX;
195 
196  cube_box->left.xmin = -infinity;
197  cube_box->left.xmax = infinity;
198 
199  cube_box->left.ymin = -infinity;
200  cube_box->left.ymax = infinity;
201 
202  cube_box->left.zmin = -infinity;
203  cube_box->left.zmax = infinity;
204 
205  cube_box->right.xmin = -infinity;
206  cube_box->right.xmax = infinity;
207 
208  cube_box->right.ymin = -infinity;
209  cube_box->right.ymax = infinity;
210 
211  cube_box->right.zmin = -infinity;
212  cube_box->right.zmax = infinity;
213 
214  return cube_box;
215 }
216 
217 /*
218  * Calculate the next traversal value
219  *
220  * All centroids are bounded by CubeBox3D, but SP-GiST only keeps boxes.
221  * When we are traversing the tree, we must calculate CubeBox3D,
222  * using centroid and octant.
223  */
224 static CubeBox3D *
225 nextCubeBox3D(CubeBox3D *cube_box, BOX3D *centroid, uint8 octant)
226 {
227  CubeBox3D *next_cube_box = (CubeBox3D *)palloc(sizeof(CubeBox3D));
228 
229  memcpy(next_cube_box, cube_box, sizeof(CubeBox3D));
230 
231  if (octant & 0x20)
232  next_cube_box->left.xmin = centroid->xmin;
233  else
234  next_cube_box->left.xmax = centroid->xmin;
235 
236  if (octant & 0x10)
237  next_cube_box->right.xmin = centroid->xmax;
238  else
239  next_cube_box->right.xmax = centroid->xmax;
240 
241  if (octant & 0x08)
242  next_cube_box->left.ymin = centroid->ymin;
243  else
244  next_cube_box->left.ymax = centroid->ymin;
245 
246  if (octant & 0x04)
247  next_cube_box->right.ymin = centroid->ymax;
248  else
249  next_cube_box->right.ymax = centroid->ymax;
250 
251  if (octant & 0x02)
252  next_cube_box->left.zmin = centroid->zmin;
253  else
254  next_cube_box->left.zmax = centroid->zmin;
255 
256  if (octant & 0x01)
257  next_cube_box->right.zmin = centroid->zmax;
258  else
259  next_cube_box->right.zmax = centroid->zmax;
260 
261  return next_cube_box;
262 }
263 
264 /* Can any cube from cube_box overlap with query? */
265 static bool
266 overlap6D(CubeBox3D *cube_box, BOX3D *query)
267 {
268  return (cube_box->left.xmin <= query->xmax) && (cube_box->right.xmax >= query->xmin) &&
269  (cube_box->left.ymin <= query->ymax) && (cube_box->right.ymax >= query->ymin) &&
270  (cube_box->left.zmin <= query->zmax) && (cube_box->right.zmax >= query->zmin);
271 }
272 
273 /* Can any cube from cube_box contain query? */
274 static bool
275 contain6D(CubeBox3D *cube_box, BOX3D *query)
276 {
277  return (cube_box->right.xmax >= query->xmax) && (cube_box->left.xmin <= query->xmin) &&
278  (cube_box->right.ymax >= query->ymax) && (cube_box->left.ymin <= query->ymin) &&
279  (cube_box->right.zmax >= query->zmax) && (cube_box->left.zmin <= query->zmin);
280 }
281 
282 /* Can any cube from cube_box be left of query? */
283 static bool
284 left6D(CubeBox3D *cube_box, BOX3D *query)
285 {
286  return (cube_box->right.xmax < query->xmin);
287 }
288 
289 /* Can any cube from cube_box does not extend the right of query? */
290 static bool
291 overLeft6D(CubeBox3D *cube_box, BOX3D *query)
292 {
293  return (cube_box->right.xmax <= query->xmax);
294 }
295 
296 /* Can any cube from cube_box be right of query? */
297 static bool
298 right6D(CubeBox3D *cube_box, BOX3D *query)
299 {
300  return (cube_box->left.xmin > query->xmax);
301 }
302 
303 /* Can any cube from cube_box does not extend the left of query? */
304 static bool
305 overRight6D(CubeBox3D *cube_box, BOX3D *query)
306 {
307  return (cube_box->left.xmin >= query->xmin);
308 }
309 
310 /* Can any cube from cube_box be below of query? */
311 static bool
312 below6D(CubeBox3D *cube_box, BOX3D *query)
313 {
314  return (cube_box->right.ymax < query->ymin);
315 }
316 
317 /* Can any cube from cube_box does not extend above query? */
318 static bool
319 overBelow6D(CubeBox3D *cube_box, BOX3D *query)
320 {
321  return (cube_box->right.ymax <= query->ymax);
322 }
323 
324 /* Can any cube from cube_box be above of query? */
325 static bool
326 above6D(CubeBox3D *cube_box, BOX3D *query)
327 {
328  return (cube_box->left.ymin > query->ymax);
329 }
330 
331 /* Can any cube from cube_box does not extend below of query? */
332 static bool
333 overAbove6D(CubeBox3D *cube_box, BOX3D *query)
334 {
335  return (cube_box->left.ymin >= query->ymin);
336 }
337 
338 /* Can any cube from cube_box be before of query? */
339 static bool
340 front6D(CubeBox3D *cube_box, BOX3D *query)
341 {
342  return (cube_box->right.zmax < query->zmin);
343 }
344 
345 /* Can any cube from cube_box does not extend the after of query? */
346 static bool
347 overFront6D(CubeBox3D *cube_box, BOX3D *query)
348 {
349  return (cube_box->right.zmax <= query->zmax);
350 }
351 
352 /* Can any cube from cube_box be after of query? */
353 static bool
354 back6D(CubeBox3D *cube_box, BOX3D *query)
355 {
356  return (cube_box->left.zmin > query->zmax);
357 }
358 
359 /* Can any cube from cube_box does not extend the before of query? */
360 static bool
361 overBack6D(CubeBox3D *cube_box, BOX3D *query)
362 {
363  return (cube_box->left.zmin >= query->zmin);
364 }
365 
366 /*
367  * SP-GiST config function
368  */
369 
371 
372 PGDLLEXPORT Datum gserialized_spgist_config_3d(PG_FUNCTION_ARGS)
373 {
374  spgConfigOut *cfg = (spgConfigOut *)PG_GETARG_POINTER(1);
375 
376  Oid boxoid = InvalidOid;
377  postgis_initialize_cache(fcinfo);
378  boxoid = postgis_oid(BOX3DOID);
379 
380  cfg->prefixType = boxoid;
381  cfg->labelType = VOIDOID; /* We don't need node labels. */
382  cfg->leafType = boxoid;
383  cfg->canReturnData = false;
384  cfg->longValuesOK = false;
385 
386  PG_RETURN_VOID();
387 }
388 
389 /*
390  * SP-GiST choose function
391  */
392 
394 
395 PGDLLEXPORT Datum gserialized_spgist_choose_3d(PG_FUNCTION_ARGS)
396 {
397  spgChooseIn *in = (spgChooseIn *)PG_GETARG_POINTER(0);
398  spgChooseOut *out = (spgChooseOut *)PG_GETARG_POINTER(1);
399  BOX3D *centroid = DatumGetBox3DP(in->prefixDatum);
400  BOX3D *box = DatumGetBox3DP(in->leafDatum);
401 
402  out->resultType = spgMatchNode;
403  out->result.matchNode.restDatum = Box3DPGetDatum(box);
404 
405  /* nodeN will be set by core, when allTheSame. */
406  if (!in->allTheSame)
407  out->result.matchNode.nodeN = getOctant(centroid, box);
408 
409  PG_RETURN_VOID();
410 }
411 
412 /*
413  * SP-GiST pick-split function
414  *
415  * It splits a list of boxes into octants by choosing a central 6D
416  * point as the median of the coordinates of the boxes.
417  */
419 
420 PGDLLEXPORT Datum gserialized_spgist_picksplit_3d(PG_FUNCTION_ARGS)
421 {
422  spgPickSplitIn *in = (spgPickSplitIn *)PG_GETARG_POINTER(0);
423  spgPickSplitOut *out = (spgPickSplitOut *)PG_GETARG_POINTER(1);
424  BOX3D *centroid;
425  int median, i;
426  double *lowXs = palloc(sizeof(double) * in->nTuples);
427  double *highXs = palloc(sizeof(double) * in->nTuples);
428  double *lowYs = palloc(sizeof(double) * in->nTuples);
429  double *highYs = palloc(sizeof(double) * in->nTuples);
430  double *lowZs = palloc(sizeof(double) * in->nTuples);
431  double *highZs = palloc(sizeof(double) * in->nTuples);
432  BOX3D *box = DatumGetBox3DP(in->datums[0]);
433  int32_t srid = box->srid;
434 
435  /* Calculate median of all 6D coordinates */
436  for (i = 0; i < in->nTuples; i++)
437  {
438  BOX3D *box = DatumGetBox3DP(in->datums[i]);
439 
440  lowXs[i] = box->xmin;
441  highXs[i] = box->xmax;
442  lowYs[i] = box->ymin;
443  highYs[i] = box->ymax;
444  lowZs[i] = box->zmin;
445  highZs[i] = box->zmax;
446  }
447 
448  qsort(lowXs, in->nTuples, sizeof(double), compareDoubles);
449  qsort(highXs, in->nTuples, sizeof(double), compareDoubles);
450  qsort(lowYs, in->nTuples, sizeof(double), compareDoubles);
451  qsort(highYs, in->nTuples, sizeof(double), compareDoubles);
452  qsort(lowZs, in->nTuples, sizeof(double), compareDoubles);
453  qsort(highZs, in->nTuples, sizeof(double), compareDoubles);
454 
455  median = in->nTuples / 2;
456 
457  centroid = palloc(sizeof(BOX3D));
458 
459  centroid->xmin = lowXs[median];
460  centroid->xmax = highXs[median];
461  centroid->ymin = lowYs[median];
462  centroid->ymax = highYs[median];
463  centroid->zmin = lowZs[median];
464  centroid->zmax = highZs[median];
465  centroid->srid = srid;
466 
467  /* Fill the output */
468  out->hasPrefix = true;
469  out->prefixDatum = Box3DPGetDatum(centroid);
470 
471  out->nNodes = 64;
472  out->nodeLabels = NULL; /* We don't need node labels. */
473 
474  out->mapTuplesToNodes = palloc(sizeof(int) * in->nTuples);
475  out->leafTupleDatums = palloc(sizeof(Datum) * in->nTuples);
476 
477  /*
478  * Assign ranges to corresponding nodes according to octants relative to
479  * the "centroid" range
480  */
481  for (i = 0; i < in->nTuples; i++)
482  {
483  BOX3D *box = DatumGetBox3DP(in->datums[i]);
484  uint8 octant = getOctant(centroid, box);
485 
486  out->leafTupleDatums[i] = Box3DPGetDatum(box);
487  out->mapTuplesToNodes[i] = octant;
488  }
489 
490  pfree(lowXs);
491  pfree(highXs);
492  pfree(lowYs);
493  pfree(highYs);
494  pfree(lowZs);
495  pfree(highZs);
496 
497  PG_RETURN_VOID();
498 }
499 
500 /*
501  * SP-GiST inner consistent function
502  */
504 
505 PGDLLEXPORT Datum gserialized_spgist_inner_consistent_3d(PG_FUNCTION_ARGS)
506 {
507  spgInnerConsistentIn *in = (spgInnerConsistentIn *)PG_GETARG_POINTER(0);
508  spgInnerConsistentOut *out = (spgInnerConsistentOut *)PG_GETARG_POINTER(1);
509  int i;
510  MemoryContext old_ctx;
511  CubeBox3D *cube_box;
512  uint8 octant;
513  BOX3D *centroid;
514  int *nodeNumbers;
515  void **traversalValues;
516 
517  if (in->allTheSame)
518  {
519  /* Report that all nodes should be visited */
520  out->nNodes = in->nNodes;
521  out->nodeNumbers = (int *)palloc(sizeof(int) * in->nNodes);
522  for (i = 0; i < in->nNodes; i++)
523  out->nodeNumbers[i] = i;
524 
525  PG_RETURN_VOID();
526  }
527 
528  /*
529  * We are saving the traversal value or initialize it an unbounded one, if
530  * we have just begun to walk the tree.
531  */
532  if (in->traversalValue)
533  cube_box = in->traversalValue;
534  else
535  cube_box = initCubeBox();
536 
537  centroid = DatumGetBox3DP(in->prefixDatum);
538 
539  /* Allocate enough memory for nodes */
540  out->nNodes = 0;
541  nodeNumbers = (int *)palloc(sizeof(int) * in->nNodes);
542  traversalValues = (void **)palloc(sizeof(void *) * in->nNodes);
543 
544  /*
545  * We switch memory context, because we want to allocate memory for new
546  * traversal values (next_cube_box) and pass these pieces of memory to
547  * further call of this function.
548  */
549  old_ctx = MemoryContextSwitchTo(in->traversalMemoryContext);
550 
551  for (octant = 0; octant < in->nNodes; octant++)
552  {
553  CubeBox3D *next_cube_box = nextCubeBox3D(cube_box, centroid, octant);
554  bool flag = true;
555 
556  for (i = 0; i < in->nkeys; i++)
557  {
558  StrategyNumber strategy = in->scankeys[i].sk_strategy;
559  Datum query = in->scankeys[i].sk_argument;
560  BOX3D *box = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, query));
561 
562  switch (strategy)
563  {
566  flag = overlap6D(next_cube_box, box);
567  break;
568 
571  flag = contain6D(next_cube_box, box);
572  break;
573 
575  flag = !overRight6D(next_cube_box, box);
576  break;
577 
579  flag = !right6D(next_cube_box, box);
580  break;
581 
583  flag = !overLeft6D(next_cube_box, box);
584  break;
585 
587  flag = !left6D(next_cube_box, box);
588  break;
589 
591  flag = !overBelow6D(next_cube_box, box);
592  break;
593 
595  flag = !below6D(next_cube_box, box);
596  break;
597 
599  flag = !overAbove6D(next_cube_box, box);
600  break;
601 
603  flag = !above6D(next_cube_box, box);
604  break;
605 
607  flag = !overFront6D(next_cube_box, box);
608  break;
609 
611  flag = !front6D(next_cube_box, box);
612  break;
613 
615  flag = !overBack6D(next_cube_box, box);
616  break;
617 
619  flag = !back6D(next_cube_box, box);
620  break;
621 
622  default:
623  elog(ERROR, "unrecognized strategy: %d", strategy);
624  }
625 
626  /* If any check is failed, we have found our answer. */
627  if (!flag)
628  break;
629  }
630 
631  if (flag)
632  {
633  traversalValues[out->nNodes] = next_cube_box;
634  nodeNumbers[out->nNodes] = octant;
635  out->nNodes++;
636  }
637  else
638  {
639  /*
640  * If this node is not selected, we don't need to keep the next
641  * traversal value in the memory context.
642  */
643  pfree(next_cube_box);
644  }
645  }
646 
647  /* Pass to the next level only the values that need to be traversed */
648  out->nodeNumbers = (int *)palloc(sizeof(int) * out->nNodes);
649  out->traversalValues = (void **)palloc(sizeof(void *) * out->nNodes);
650  for (i = 0; i < out->nNodes; i++)
651  {
652  out->nodeNumbers[i] = nodeNumbers[i];
653  out->traversalValues[i] = traversalValues[i];
654  }
655  pfree(nodeNumbers);
656  pfree(traversalValues);
657 
658  /* Switch after */
659  MemoryContextSwitchTo(old_ctx);
660 
661  PG_RETURN_VOID();
662 }
663 
664 /*
665  * SP-GiST inner consistent function
666  */
668 
669 PGDLLEXPORT Datum gserialized_spgist_leaf_consistent_3d(PG_FUNCTION_ARGS)
670 {
671  spgLeafConsistentIn *in = (spgLeafConsistentIn *)PG_GETARG_POINTER(0);
672  spgLeafConsistentOut *out = (spgLeafConsistentOut *)PG_GETARG_POINTER(1);
673  BOX3D *leaf = DatumGetBox3DP(in->leafDatum);
674  bool flag = true;
675  int i;
676 
677  /* All tests are exact. */
678  out->recheck = false;
679 
680  /* leafDatum is what it is... */
681  out->leafValue = in->leafDatum;
682 
683  /* Perform the required comparison(s) */
684  for (i = 0; i < in->nkeys; i++)
685  {
686  StrategyNumber strategy = in->scankeys[i].sk_strategy;
687  Datum query = in->scankeys[i].sk_argument;
688  BOX3D *box = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, query));
689 
690  switch (strategy)
691  {
693  flag = BOX3D_overlaps_internal(leaf, box);
694  break;
695 
697  flag = BOX3D_contains_internal(leaf, box);
698  break;
699 
701  flag = BOX3D_contained_internal(leaf, box);
702  break;
703 
705  flag = BOX3D_same_internal(leaf, box);
706  break;
707 
709  flag = BOX3D_left_internal(leaf, box);
710  break;
711 
713  flag = BOX3D_overleft_internal(leaf, box);
714  break;
715 
717  flag = BOX3D_right_internal(leaf, box);
718  break;
719 
721  flag = BOX3D_overright_internal(leaf, box);
722  break;
723 
725  flag = BOX3D_above_internal(leaf, box);
726  break;
727 
729  flag = BOX3D_overabove_internal(leaf, box);
730  break;
731 
733  flag = BOX3D_below_internal(leaf, box);
734  break;
735 
737  flag = BOX3D_overbelow_internal(leaf, box);
738  break;
739 
741  flag = BOX3D_back_internal(leaf, box);
742  break;
743 
745  flag = BOX3D_overback_internal(leaf, box);
746  break;
747 
749  flag = BOX3D_front_internal(leaf, box);
750  break;
751 
753  flag = BOX3D_overfront_internal(leaf, box);
754  break;
755 
756  default:
757  elog(ERROR, "unrecognized strategy: %d", strategy);
758  }
759 
760  /* If any check is failed, we have found our answer. */
761  if (!flag)
762  break;
763  }
764 
765  PG_RETURN_BOOL(flag);
766 }
767 
769 
770 PGDLLEXPORT Datum gserialized_spgist_compress_3d(PG_FUNCTION_ARGS)
771 {
772  BOX3D *result = DatumGetBox3DP(DirectFunctionCall1(LWGEOM_to_BOX3D, PG_GETARG_DATUM(0)));
773 
774  /* Is the bounding box is null */
775  if (result == LW_FAILURE)
776  {
777  PG_RETURN_NULL();
778  }
779 
780  /* Return BOX3D. */
781  PG_RETURN_POINTER(result);
782 }
783 
784 /*****************************************************************************/
static bool front6D(CubeBox3D *cube_box, BOX3D *query)
static bool back6D(CubeBox3D *cube_box, BOX3D *query)
static bool right6D(CubeBox3D *cube_box, BOX3D *query)
Datum gserialized_overlaps_3d(PG_FUNCTION_ARGS)
static bool overBack6D(CubeBox3D *cube_box, BOX3D *query)
static bool overAbove6D(CubeBox3D *cube_box, BOX3D *query)
PG_FUNCTION_INFO_V1(gserialized_overlaps_3d)
static bool overlap6D(CubeBox3D *cube_box, BOX3D *query)
Datum gserialized_contains_3d(PG_FUNCTION_ARGS)
static int compareDoubles(const void *a, const void *b)
static CubeBox3D * nextCubeBox3D(CubeBox3D *cube_box, BOX3D *centroid, uint8 octant)
PGDLLEXPORT Datum gserialized_spgist_picksplit_3d(PG_FUNCTION_ARGS)
static bool overRight6D(CubeBox3D *cube_box, BOX3D *query)
static bool overFront6D(CubeBox3D *cube_box, BOX3D *query)
PGDLLEXPORT Datum gserialized_spgist_config_3d(PG_FUNCTION_ARGS)
static CubeBox3D * initCubeBox(void)
PGDLLEXPORT Datum gserialized_spgist_inner_consistent_3d(PG_FUNCTION_ARGS)
Datum gserialized_same_3d(PG_FUNCTION_ARGS)
PGDLLEXPORT Datum gserialized_spgist_compress_3d(PG_FUNCTION_ARGS)
static bool contain6D(CubeBox3D *cube_box, BOX3D *query)
static bool overBelow6D(CubeBox3D *cube_box, BOX3D *query)
static bool above6D(CubeBox3D *cube_box, BOX3D *query)
PGDLLEXPORT Datum gserialized_spgist_choose_3d(PG_FUNCTION_ARGS)
Datum gserialized_contained_3d(PG_FUNCTION_ARGS)
static bool below6D(CubeBox3D *cube_box, BOX3D *query)
static bool overLeft6D(CubeBox3D *cube_box, BOX3D *query)
PGDLLEXPORT Datum gserialized_spgist_leaf_consistent_3d(PG_FUNCTION_ARGS)
static bool left6D(CubeBox3D *cube_box, BOX3D *query)
static uint8 getOctant(BOX3D *centroid, BOX3D *inBox)
#define SPGOverlapStrategyNumber
#define SPGOverLeftStrategyNumber
#define SPGLeftStrategyNumber
#define SPGAboveStrategyNumber
#define SPGSameStrategyNumber
#define SPGOverBackStrategyNumber
#define SPGContainedByStrategyNumber
#define SPGOverRightStrategyNumber
#define SPGFrontStrategyNumber
#define SPGBelowStrategyNumber
#define SPGRightStrategyNumber
#define SPGOverFrontStrategyNumber
#define SPGContainsStrategyNumber
#define SPGOverBelowStrategyNumber
#define SPGBackStrategyNumber
#define SPGOverAboveStrategyNumber
#define LW_FAILURE
Definition: liblwgeom.h:79
Datum LWGEOM_to_BOX3D(PG_FUNCTION_ARGS)
Definition: lwgeom_box3d.c:390
bool BOX3D_above_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_back_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_overlaps_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_contains_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_overabove_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_right_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_overback_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_overleft_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_below_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_left_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_overright_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_same_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_contained_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_front_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_overfront_internal(BOX3D *box1, BOX3D *box2)
bool BOX3D_overbelow_internal(BOX3D *box1, BOX3D *box2)
Datum centroid(PG_FUNCTION_ARGS)
double xmax
Definition: liblwgeom.h:281
double zmin
Definition: liblwgeom.h:280
double ymax
Definition: liblwgeom.h:281
double ymin
Definition: liblwgeom.h:280
double zmax
Definition: liblwgeom.h:281
double xmin
Definition: liblwgeom.h:280
int32_t srid
Definition: liblwgeom.h:282