1 /*****************************************************************************
2
3 Copyright (c) 2013, 2021, Oracle and/or its affiliates.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24
25 *****************************************************************************/
26
27 /**************************************************//**
28 @file gis/gis0geo.cc
29 InnoDB R-tree related functions.
30
31 Created 2013/03/27 Allen Lai and Jimmy Yang
32 *******************************************************/
33
34 #include "page0types.h"
35 #include "gis0geo.h"
36 #include "page0cur.h"
37 #include "ut0rnd.h"
38 #include "mach0data.h"
39
40 #include <spatial.h>
41
42 /* These definitions are for comparing 2 mbrs. */
43
44 /* Check if a intersects b.
45 Return false if a intersects b, otherwise true. */
46 #define INTERSECT_CMP(amin, amax, bmin, bmax) \
47 (((amin) > (bmax)) || ((bmin) > (amax)))
48
49 /* Check if b contains a.
50 Return false if b contains a, otherwise true. */
51 #define CONTAIN_CMP(amin, amax, bmin, bmax) \
52 (((bmin) > (amin)) || ((bmax) < (amax)))
53
54 /* Check if b is within a.
55 Return false if b is within a, otherwise true. */
56 #define WITHIN_CMP(amin, amax, bmin, bmax) \
57 (((amin) > (bmin)) || ((amax) < (bmax)))
58
59 /* Check if a disjoints b.
60 Return false if a disjoints b, otherwise true. */
61 #define DISJOINT_CMP(amin, amax, bmin, bmax) \
62 (((amin) <= (bmax)) && ((bmin) <= (amax)))
63
64 /* Check if a equals b.
65 Return false if equal, otherwise true. */
66 #define EQUAL_CMP(amin, amax, bmin, bmax) \
67 (((amin) != (bmin)) || ((amax) != (bmax)))
68
69 /****************************************************************
70 Functions for generating mbr
71 ****************************************************************/
72 /*************************************************************//**
73 Add one point stored in wkb to a given mbr.
74 @return 0 if the point in wkb is valid, otherwise -1. */
75 static
76 int
rtree_add_point_to_mbr(uchar ** wkb,uchar * end,uint n_dims,uchar byte_order,double * mbr)77 rtree_add_point_to_mbr(
78 /*===================*/
79 uchar** wkb, /*!< in: pointer to wkb,
80 where point is stored */
81 uchar* end, /*!< in: end of wkb. */
82 uint n_dims, /*!< in: dimensions. */
83 uchar byte_order, /*!< in: byte order. */
84 double* mbr) /*!< in/out: mbr, which
85 must be of length n_dims * 2. */
86 {
87 double ord;
88 double* mbr_end = mbr + n_dims * 2;
89
90 while (mbr < mbr_end) {
91 if ((*wkb) + sizeof(double) > end) {
92 return(-1);
93 }
94
95 ord = mach_double_read(*wkb);
96 (*wkb) += sizeof(double);
97
98 if (ord < *mbr) {
99 *mbr = ord;
100 }
101 mbr++;
102
103 if (ord > *mbr) {
104 *mbr = ord;
105 }
106 mbr++;
107 }
108
109 return(0);
110 }
111
112 /*************************************************************//**
113 Get mbr of point stored in wkb.
114 @return 0 if ok, otherwise -1. */
115 static
116 int
rtree_get_point_mbr(uchar ** wkb,uchar * end,uint n_dims,uchar byte_order,double * mbr)117 rtree_get_point_mbr(
118 /*================*/
119 uchar** wkb, /*!< in: pointer to wkb,
120 where point is stored. */
121 uchar* end, /*!< in: end of wkb. */
122 uint n_dims, /*!< in: dimensions. */
123 uchar byte_order, /*!< in: byte order. */
124 double* mbr) /*!< in/out: mbr,
125 must be of length n_dims * 2. */
126 {
127 return rtree_add_point_to_mbr(wkb, end, n_dims, byte_order, mbr);
128 }
129
130
131 /*************************************************************//**
132 Get mbr of linestring stored in wkb.
133 @return 0 if the linestring is valid, otherwise -1. */
134 static
135 int
rtree_get_linestring_mbr(uchar ** wkb,uchar * end,uint n_dims,uchar byte_order,double * mbr)136 rtree_get_linestring_mbr(
137 /*=====================*/
138 uchar** wkb, /*!< in: pointer to wkb,
139 where point is stored. */
140 uchar* end, /*!< in: end of wkb. */
141 uint n_dims, /*!< in: dimensions. */
142 uchar byte_order, /*!< in: byte order. */
143 double* mbr) /*!< in/out: mbr,
144 must be of length n_dims * 2. */
145 {
146 uint n_points;
147
148 n_points = uint4korr(*wkb);
149 (*wkb) += 4;
150
151 for (; n_points > 0; --n_points) {
152 /* Add next point to mbr */
153 if (rtree_add_point_to_mbr(wkb, end, n_dims,
154 byte_order, mbr)) {
155 return(-1);
156 }
157 }
158
159 return(0);
160 }
161
162 /*************************************************************//**
163 Get mbr of polygon stored in wkb.
164 @return 0 if the polygon is valid, otherwise -1. */
165 static
166 int
rtree_get_polygon_mbr(uchar ** wkb,uchar * end,uint n_dims,uchar byte_order,double * mbr)167 rtree_get_polygon_mbr(
168 /*==================*/
169 uchar** wkb, /*!< in: pointer to wkb,
170 where point is stored. */
171 uchar* end, /*!< in: end of wkb. */
172 uint n_dims, /*!< in: dimensions. */
173 uchar byte_order, /*!< in: byte order. */
174 double* mbr) /*!< in/out: mbr,
175 must be of length n_dims * 2. */
176 {
177 uint n_linear_rings;
178 uint n_points;
179
180 n_linear_rings = uint4korr((*wkb));
181 (*wkb) += 4;
182
183 for (; n_linear_rings > 0; --n_linear_rings) {
184 n_points = uint4korr((*wkb));
185 (*wkb) += 4;
186
187 for (; n_points > 0; --n_points) {
188 /* Add next point to mbr */
189 if (rtree_add_point_to_mbr(wkb, end, n_dims,
190 byte_order, mbr)) {
191 return(-1);
192 }
193 }
194 }
195
196 return(0);
197 }
198
199 /*************************************************************//**
200 Get mbr of geometry stored in wkb.
201 @return 0 if the geometry is valid, otherwise -1. */
202 static
203 int
rtree_get_geometry_mbr(uchar ** wkb,uchar * end,uint n_dims,double * mbr,int top)204 rtree_get_geometry_mbr(
205 /*===================*/
206 uchar** wkb, /*!< in: pointer to wkb,
207 where point is stored. */
208 uchar* end, /*!< in: end of wkb. */
209 uint n_dims, /*!< in: dimensions. */
210 double* mbr, /*!< in/out: mbr. */
211 int top) /*!< in: if it is the top,
212 which means it's not called
213 by itself. */
214 {
215 int res;
216 uchar byte_order = 2;
217 uint wkb_type = 0;
218 uint n_items;
219
220 byte_order = *(*wkb);
221 ++(*wkb);
222
223 wkb_type = uint4korr((*wkb));
224 (*wkb) += 4;
225
226 switch ((enum wkbType) wkb_type) {
227 case wkbPoint:
228 res = rtree_get_point_mbr(wkb, end, n_dims, byte_order, mbr);
229 break;
230 case wkbLineString:
231 res = rtree_get_linestring_mbr(wkb, end, n_dims,
232 byte_order, mbr);
233 break;
234 case wkbPolygon:
235 res = rtree_get_polygon_mbr(wkb, end, n_dims, byte_order, mbr);
236 break;
237 case wkbMultiPoint:
238 n_items = uint4korr((*wkb));
239 (*wkb) += 4;
240 for (; n_items > 0; --n_items) {
241 byte_order = *(*wkb);
242 ++(*wkb);
243 (*wkb) += 4;
244 if (rtree_get_point_mbr(wkb, end, n_dims,
245 byte_order, mbr)) {
246 return(-1);
247 }
248 }
249 res = 0;
250 break;
251 case wkbMultiLineString:
252 n_items = uint4korr((*wkb));
253 (*wkb) += 4;
254 for (; n_items > 0; --n_items) {
255 byte_order = *(*wkb);
256 ++(*wkb);
257 (*wkb) += 4;
258 if (rtree_get_linestring_mbr(wkb, end, n_dims,
259 byte_order, mbr)) {
260 return(-1);
261 }
262 }
263 res = 0;
264 break;
265 case wkbMultiPolygon:
266 n_items = uint4korr((*wkb));
267 (*wkb) += 4;
268 for (; n_items > 0; --n_items) {
269 byte_order = *(*wkb);
270 ++(*wkb);
271 (*wkb) += 4;
272 if (rtree_get_polygon_mbr(wkb, end, n_dims,
273 byte_order, mbr)) {
274 return(-1);
275 }
276 }
277 res = 0;
278 break;
279 case wkbGeometryCollection:
280 if (!top) {
281 return(-1);
282 }
283
284 n_items = uint4korr((*wkb));
285 (*wkb) += 4;
286 for (; n_items > 0; --n_items) {
287 if (rtree_get_geometry_mbr(wkb, end, n_dims,
288 mbr, 0)) {
289 return(-1);
290 }
291 }
292 res = 0;
293 break;
294 default:
295 res = -1;
296 }
297
298 return(res);
299 }
300
301 /*************************************************************//**
302 Calculate Minimal Bounding Rectangle (MBR) of the spatial object
303 stored in "well-known binary representation" (wkb) format.
304 @return 0 if ok. */
305 int
rtree_mbr_from_wkb(uchar * wkb,uint size,uint n_dims,double * mbr)306 rtree_mbr_from_wkb(
307 /*===============*/
308 uchar* wkb, /*!< in: wkb */
309 uint size, /*!< in: size of wkb. */
310 uint n_dims, /*!< in: dimensions. */
311 double* mbr) /*!< in/out: mbr, which must
312 be of length n_dim2 * 2. */
313 {
314 for (uint i = 0; i < n_dims; ++i) {
315 mbr[i * 2] = DBL_MAX;
316 mbr[i * 2 + 1] = -DBL_MAX;
317 }
318
319 return rtree_get_geometry_mbr(&wkb, wkb + size, n_dims, mbr, 1);
320 }
321
322
323 /****************************************************************
324 Functions for Rtree split
325 ****************************************************************/
326 /*************************************************************//**
327 Join 2 mbrs of dimensions n_dim. */
328 static
329 void
mbr_join(double * a,const double * b,int n_dim)330 mbr_join(
331 /*=====*/
332 double* a, /*!< in/out: the first mbr,
333 where the joined result will be. */
334 const double* b, /*!< in: the second mbr. */
335 int n_dim) /*!< in: dimensions. */
336 {
337 double* end = a + n_dim * 2;
338
339 do {
340 if (a[0] > b[0]) {
341 a[0] = b[0];
342 }
343
344 if (a[1] < b[1]) {
345 a[1] = b[1];
346 }
347
348 a += 2;
349 b += 2;
350
351 } while (a != end);
352 }
353
354 /*************************************************************//**
355 Counts the square of mbr which is the join of a and b. Both a and b
356 are of dimensions n_dim. */
357 static
358 double
mbr_join_square(const double * a,const double * b,int n_dim)359 mbr_join_square(
360 /*============*/
361 const double* a, /*!< in: the first mbr. */
362 const double* b, /*!< in: the second mbr. */
363 int n_dim) /*!< in: dimensions. */
364 {
365 const double* end = a + n_dim * 2;
366 double square = 1.0;
367
368 do {
369 square *= std::max(a[1], b[1]) - std::min(a[0], b[0]);
370
371 a += 2;
372 b += 2;
373 } while (a != end);
374
375 /* Check for infinity or NaN, so we don't get NaN in calculations */
376 if (my_isinf(square) || my_isnan(square)) {
377 return DBL_MAX;
378 }
379
380 return square;
381 }
382
383 /*************************************************************//**
384 Counts the square of mbr of dimension n_dim. */
385 static
386 double
count_square(const double * a,int n_dim)387 count_square(
388 /*=========*/
389 const double* a, /*!< in: the mbr. */
390 int n_dim) /*!< in: dimensions. */
391 {
392 const double* end = a + n_dim * 2;
393 double square = 1.0;
394
395 do {
396 square *= a[1] - a[0];
397 a += 2;
398 } while (a != end);
399
400 return square;
401 }
402
403 /*************************************************************//**
404 Copy mbr of dimension n_dim from src to dst. */
405 inline
406 static
407 void
copy_coords(double * dst,const double * src,int n_dim)408 copy_coords(
409 /*========*/
410 double* dst, /*!< in/out: destination. */
411 const double* src, /*!< in: source. */
412 int n_dim) /*!< in: dimensions. */
413 {
414 memcpy(dst, src, DATA_MBR_LEN);
415 }
416
417 /*************************************************************//**
418 Select two nodes to collect group upon */
419 static
420 void
pick_seeds(rtr_split_node_t * node,int n_entries,rtr_split_node_t ** seed_a,rtr_split_node_t ** seed_b,int n_dim)421 pick_seeds(
422 /*=======*/
423 rtr_split_node_t* node, /*!< in: split nodes. */
424 int n_entries, /*!< in: entries number. */
425 rtr_split_node_t** seed_a, /*!< out: seed 1. */
426 rtr_split_node_t** seed_b, /*!< out: seed 2. */
427 int n_dim) /*!< in: dimensions. */
428 {
429 rtr_split_node_t* cur1;
430 rtr_split_node_t* lim1 = node + (n_entries - 1);
431 rtr_split_node_t* cur2;
432 rtr_split_node_t* lim2 = node + n_entries;
433
434 double max_d = -DBL_MAX;
435 double d;
436
437 *seed_a = node;
438 *seed_b = node + 1;
439
440 for (cur1 = node; cur1 < lim1; ++cur1) {
441 for (cur2 = cur1 + 1; cur2 < lim2; ++cur2) {
442 d = mbr_join_square(cur1->coords, cur2->coords, n_dim) -
443 cur1->square - cur2->square;
444 if (d > max_d) {
445 max_d = d;
446 *seed_a = cur1;
447 *seed_b = cur2;
448 }
449 }
450 }
451 }
452
453 /*********************************************************//**
454 Generates a random iboolean value.
455 @return the random value */
456 static
457 ibool
ut_rnd_gen_ibool(void)458 ut_rnd_gen_ibool(void)
459 /*=================*/
460 {
461 ulint x;
462
463 x = ut_rnd_gen_ulint();
464
465 if (((x >> 20) + (x >> 15)) & 1) {
466
467 return(TRUE);
468 }
469
470 return(FALSE);
471 }
472
473 /*************************************************************//**
474 Select next node and group where to add. */
475 static
476 void
pick_next(rtr_split_node_t * node,int n_entries,double * g1,double * g2,rtr_split_node_t ** choice,int * n_group,int n_dim)477 pick_next(
478 /*======*/
479 rtr_split_node_t* node, /*!< in: split nodes. */
480 int n_entries, /*!< in: entries number. */
481 double* g1, /*!< in: mbr of group 1. */
482 double* g2, /*!< in: mbr of group 2. */
483 rtr_split_node_t** choice, /*!< out: the next node.*/
484 int* n_group, /*!< out: group number.*/
485 int n_dim) /*!< in: dimensions. */
486 {
487 rtr_split_node_t* cur = node;
488 rtr_split_node_t* end = node + n_entries;
489 double max_diff = -DBL_MAX;
490
491 for (; cur < end; ++cur) {
492 double diff;
493 double abs_diff;
494
495 if (cur->n_node != 0) {
496 continue;
497 }
498
499 diff = mbr_join_square(g1, cur->coords, n_dim) -
500 mbr_join_square(g2, cur->coords, n_dim);
501
502 abs_diff = fabs(diff);
503 if (abs_diff > max_diff) {
504 max_diff = abs_diff;
505
506 /* Introduce some randomness if the record
507 is identical */
508 if (diff == 0) {
509 diff = static_cast<double>(
510 ut_rnd_gen_ibool());
511 }
512
513 *n_group = 1 + (diff > 0);
514 *choice = cur;
515 }
516 }
517 }
518
519 /*************************************************************//**
520 Mark not-in-group entries as n_group. */
521 static
522 void
mark_all_entries(rtr_split_node_t * node,int n_entries,int n_group)523 mark_all_entries(
524 /*=============*/
525 rtr_split_node_t* node, /*!< in/out: split nodes. */
526 int n_entries, /*!< in: entries number. */
527 int n_group) /*!< in: group number. */
528 {
529 rtr_split_node_t* cur = node;
530 rtr_split_node_t* end = node + n_entries;
531 for (; cur < end; ++cur) {
532 if (cur->n_node != 0) {
533 continue;
534 }
535 cur->n_node = n_group;
536 }
537 }
538
539 /*************************************************************//**
540 Split rtree node.
541 Return which group the first rec is in. */
542 int
split_rtree_node(rtr_split_node_t * node,int n_entries,int all_size,int key_size,int min_size,int size1,int size2,double ** d_buffer,int n_dim,uchar * first_rec)543 split_rtree_node(
544 /*=============*/
545 rtr_split_node_t* node, /*!< in: split nodes. */
546 int n_entries, /*!< in: entries number. */
547 int all_size, /*!< in: total key's size. */
548 int key_size, /*!< in: key's size. */
549 int min_size, /*!< in: minimal group size. */
550 int size1, /*!< in: size of group. */
551 int size2, /*!< in: initial group sizes */
552 double** d_buffer, /*!< in/out: buffer. */
553 int n_dim, /*!< in: dimensions. */
554 uchar* first_rec) /*!< in: the first rec. */
555 {
556 rtr_split_node_t* cur;
557 rtr_split_node_t* a = NULL;
558 rtr_split_node_t* b = NULL;
559 double* g1 = reserve_coords(d_buffer, n_dim);
560 double* g2 = reserve_coords(d_buffer, n_dim);
561 rtr_split_node_t* next = NULL;
562 int next_node = 0;
563 int i;
564 int first_rec_group = 1;
565 rtr_split_node_t* end = node + n_entries;
566
567 if (all_size < min_size * 2) {
568 return 1;
569 }
570
571 cur = node;
572 for (; cur < end; ++cur) {
573 cur->square = count_square(cur->coords, n_dim);
574 cur->n_node = 0;
575 }
576
577 pick_seeds(node, n_entries, &a, &b, n_dim);
578 a->n_node = 1;
579 b->n_node = 2;
580
581 copy_coords(g1, a->coords, n_dim);
582 size1 += key_size;
583 copy_coords(g2, b->coords, n_dim);
584 size2 += key_size;
585
586 for (i = n_entries - 2; i > 0; --i) {
587 /* Can't write into group 2 */
588 if (all_size - (size2 + key_size) < min_size) {
589 mark_all_entries(node, n_entries, 1);
590 break;
591 }
592
593 /* Can't write into group 1 */
594 if (all_size - (size1 + key_size) < min_size) {
595 mark_all_entries(node, n_entries, 2);
596 break;
597 }
598
599 pick_next(node, n_entries, g1, g2, &next, &next_node, n_dim);
600 if (next_node == 1) {
601 size1 += key_size;
602 mbr_join(g1, next->coords, n_dim);
603 } else {
604 size2 += key_size;
605 mbr_join(g2, next->coords, n_dim);
606 }
607
608 next->n_node = next_node;
609
610 /* Find out where the first rec (of the page) will be at,
611 and inform the caller */
612 if (first_rec && first_rec == next->key) {
613 first_rec_group = next_node;
614 }
615 }
616
617 return(first_rec_group);
618 }
619
620 /*************************************************************//**
621 Compares two keys a and b depending on nextflag
622 nextflag can contain these flags:
623 MBR_INTERSECT(a,b) a overlaps b
624 MBR_CONTAIN(a,b) a contains b
625 MBR_DISJOINT(a,b) a disjoint b
626 MBR_WITHIN(a,b) a within b
627 MBR_EQUAL(a,b) All coordinates of MBRs are equal
628 Return 0 on success, otherwise 1. */
629 int
rtree_key_cmp(page_cur_mode_t mode,const uchar * b,int b_len,const uchar * a,int a_len)630 rtree_key_cmp(
631 /*==========*/
632 page_cur_mode_t mode, /*!< in: compare method. */
633 const uchar* b, /*!< in: first key. */
634 int b_len, /*!< in: first key len. */
635 const uchar* a, /*!< in: second key. */
636 int a_len) /*!< in: second key len. */
637 {
638 double amin, amax, bmin, bmax;
639 int key_len;
640 int keyseg_len;
641
642 keyseg_len = 2 * sizeof(double);
643 for (key_len = a_len; key_len > 0; key_len -= keyseg_len) {
644 amin = mach_double_read(a);
645 bmin = mach_double_read(b);
646 amax = mach_double_read(a + sizeof(double));
647 bmax = mach_double_read(b + sizeof(double));
648
649 switch (mode) {
650 case PAGE_CUR_INTERSECT:
651 if (INTERSECT_CMP(amin, amax, bmin, bmax)) {
652 return(1);
653 }
654 break;
655 case PAGE_CUR_CONTAIN:
656 if (CONTAIN_CMP(amin, amax, bmin, bmax)) {
657 return(1);
658 }
659 break;
660 case PAGE_CUR_WITHIN:
661 if (WITHIN_CMP(amin, amax, bmin, bmax)) {
662 return(1);
663 }
664 break;
665 case PAGE_CUR_MBR_EQUAL:
666 if (EQUAL_CMP(amin, amax, bmin, bmax)) {
667 return(1);
668 }
669 break;
670 case PAGE_CUR_DISJOINT:
671 int result;
672
673 result = DISJOINT_CMP(amin, amax, bmin, bmax);
674 if (result == 0) {
675 return(0);
676 }
677
678 if (key_len - keyseg_len <= 0) {
679 return(1);
680 }
681
682 break;
683 default:
684 /* if unknown comparison operator */
685 ut_ad(0);
686 }
687
688 a += keyseg_len;
689 b += keyseg_len;
690 }
691
692 return(0);
693 }
694
695 /*************************************************************//**
696 Calculates MBR_AREA(a+b) - MBR_AREA(a)
697 Note: when 'a' and 'b' objects are far from each other,
698 the area increase can be really big, so this function
699 can return 'inf' as a result.
700 Return the area increaed. */
701 double
rtree_area_increase(const uchar * a,const uchar * b,int mbr_len,double * ab_area)702 rtree_area_increase(
703 const uchar* a, /*!< in: original mbr. */
704 const uchar* b, /*!< in: new mbr. */
705 int mbr_len, /*!< in: mbr length of a and b. */
706 double* ab_area) /*!< out: increased area. */
707 {
708 double a_area = 1.0;
709 double loc_ab_area = 1.0;
710 double amin, amax, bmin, bmax;
711 int key_len;
712 int keyseg_len;
713 double data_round = 1.0;
714
715 keyseg_len = 2 * sizeof(double);
716
717 for (key_len = mbr_len; key_len > 0; key_len -= keyseg_len) {
718 double area;
719
720 amin = mach_double_read(a);
721 bmin = mach_double_read(b);
722 amax = mach_double_read(a + sizeof(double));
723 bmax = mach_double_read(b + sizeof(double));
724
725 area = amax - amin;
726 if (area == 0) {
727 a_area *= LINE_MBR_WEIGHTS;
728 } else {
729 a_area *= area;
730 }
731
732 area = (double)std::max(amax, bmax) -
733 (double)std::min(amin, bmin);
734 if (area == 0) {
735 loc_ab_area *= LINE_MBR_WEIGHTS;
736 } else {
737 loc_ab_area *= area;
738 }
739
740 /* Value of amax or bmin can be so large that small difference
741 are ignored. For example: 3.2884281489988079e+284 - 100 =
742 3.2884281489988079e+284. This results some area difference
743 are not detected */
744 if (loc_ab_area == a_area) {
745 if (bmin < amin || bmax > amax) {
746 data_round *= ((double)std::max(amax, bmax)
747 - amax
748 + (amin - (double)std::min(
749 amin, bmin)));
750 } else {
751 data_round *= area;
752 }
753 }
754
755 a += keyseg_len;
756 b += keyseg_len;
757 }
758
759 *ab_area = loc_ab_area;
760
761 if (loc_ab_area == a_area && data_round != 1.0) {
762 return(data_round);
763 }
764
765 return(loc_ab_area - a_area);
766 }
767
768 /** Calculates overlapping area
769 @param[in] a mbr a
770 @param[in] b mbr b
771 @param[in] mbr_len mbr length
772 @return overlapping area */
773 double
rtree_area_overlapping(const uchar * a,const uchar * b,int mbr_len)774 rtree_area_overlapping(
775 const uchar* a,
776 const uchar* b,
777 int mbr_len)
778 {
779 double area = 1.0;
780 double amin;
781 double amax;
782 double bmin;
783 double bmax;
784 int key_len;
785 int keyseg_len;
786
787 keyseg_len = 2 * sizeof(double);
788
789 for (key_len = mbr_len; key_len > 0; key_len -= keyseg_len) {
790 amin = mach_double_read(a);
791 bmin = mach_double_read(b);
792 amax = mach_double_read(a + sizeof(double));
793 bmax = mach_double_read(b + sizeof(double));
794
795 amin = std::max(amin, bmin);
796 amax = std::min(amax, bmax);
797
798 if (amin > amax) {
799 return(0);
800 } else {
801 area *= (amax - amin);
802 }
803
804 a += keyseg_len;
805 b += keyseg_len;
806 }
807
808 return(area);
809 }
810
811 /** Get the wkb of default POINT value, which represents POINT(0 0)
812 if it's of dimension 2, etc.
813 @param[in] n_dims dimensions
814 @param[out] wkb wkb buffer for default POINT
815 @param[in] len length of wkb buffer
816 @return non-0 indicate the length of wkb of the default POINT,
817 0 if the buffer is too small */
818 uint
get_wkb_of_default_point(uint n_dims,uchar * wkb,uint len)819 get_wkb_of_default_point(
820 uint n_dims,
821 uchar* wkb,
822 uint len)
823 {
824 if (len < GEOM_HEADER_SIZE + sizeof(double) * n_dims) {
825 return(0);
826 }
827
828 /** POINT wkb comprises SRID, wkb header(byte order and type)
829 and coordinates of the POINT */
830 len = GEOM_HEADER_SIZE + sizeof(double) * n_dims;
831 /** We always use 0 as default coordinate */
832 memset(wkb, 0, len);
833 /** We don't need to write SRID, write 0x01 for Byte Order */
834 mach_write_to_n_little_endian(wkb + SRID_SIZE, 1, 0x01);
835 /** Write wkbType::wkbPoint for the POINT type */
836 mach_write_to_n_little_endian(wkb + SRID_SIZE + 1, 4, wkbPoint);
837
838 return(len);
839 }
840