1 /*****************************************************************************
2 Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
3 Copyright (c) 2019, MariaDB Corporation.
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 as published by
7 the Free Software Foundation; version 2 of the License.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software Foundation,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA
17 *****************************************************************************/
18
19 /**************************************************//**
20 @file gis0geo.h
21 The r-tree define from MyISAM
22 *******************************************************/
23
24 #ifndef _gis0geo_h
25 #define _gis0geo_h
26
27 #include "my_global.h"
28 #include "string.h"
29
30 #define SPTYPE HA_KEYTYPE_DOUBLE
31 #define SPLEN 8
32
33 /* Since the mbr could be a point or a linestring, in this case, area of
34 mbr is 0. So, we define this macro for calculating the area increasing
35 when we need to enlarge the mbr. */
36 #define LINE_MBR_WEIGHTS 0.001
37
38 /* Types of "well-known binary representation" (wkb) format. */
39 enum wkbType
40 {
41 wkbPoint = 1,
42 wkbLineString = 2,
43 wkbPolygon = 3,
44 wkbMultiPoint = 4,
45 wkbMultiLineString = 5,
46 wkbMultiPolygon = 6,
47 wkbGeometryCollection = 7
48 };
49
50 /* Byte order of "well-known binary representation" (wkb) format. */
51 enum wkbByteOrder
52 {
53 wkbXDR = 0, /* Big Endian */
54 wkbNDR = 1 /* Little Endian */
55 };
56
57 /*************************************************************//**
58 Calculate minimal bounding rectangle (mbr) of the spatial object
59 stored in "well-known binary representation" (wkb) format.
60 @return 0 if ok */
61 int
62 rtree_mbr_from_wkb(
63 /*===============*/
64 const uchar* wkb, /*!< in: pointer to wkb. */
65 uint size, /*!< in: size of wkb. */
66 uint n_dims, /*!< in: dimensions. */
67 double* mbr); /*!< in/out: mbr. */
68
69 /* Rtree split node structure. */
70 struct rtr_split_node_t
71 {
72 double square; /* square of the mbr.*/
73 int n_node; /* which group in.*/
74 uchar* key; /* key. */
75 double* coords; /* mbr. */
76 };
77
78 /*************************************************************//**
79 Inline function for reserving coords */
80 inline
81 static
82 double*
reserve_coords(double ** d_buffer,int n_dim)83 reserve_coords(double **d_buffer, /*!< in/out: buffer. */
84 int n_dim) /*!< in: dimensions. */
85 /*===========*/
86 {
87 double *coords = *d_buffer;
88 (*d_buffer) += n_dim * 2;
89 return coords;
90 }
91
92 /*************************************************************//**
93 Split rtree nodes.
94 Return which group the first rec is in. */
95 int
96 split_rtree_node(
97 /*=============*/
98 rtr_split_node_t* node, /*!< in: split nodes.*/
99 int n_entries, /*!< in: entries number.*/
100 int all_size, /*!< in: total key's size.*/
101 int key_size, /*!< in: key's size.*/
102 int min_size, /*!< in: minimal group size.*/
103 int size1, /*!< in: size of group.*/
104 int size2, /*!< in: initial group sizes */
105 double** d_buffer, /*!< in/out: buffer.*/
106 int n_dim, /*!< in: dimensions. */
107 uchar* first_rec); /*!< in: the first rec. */
108
109 /*************************************************************//**
110 Compares two keys a and b depending on nextflag
111 nextflag can contain these flags:
112 MBR_INTERSECT(a,b) a overlaps b
113 MBR_CONTAIN(a,b) a contains b
114 MBR_DISJOINT(a,b) a disjoint b
115 MBR_WITHIN(a,b) a within b
116 MBR_EQUAL(a,b) All coordinates of MBRs are equal
117 MBR_DATA(a,b) Data reference is the same
118 Returns 0 on success. */
119 int
120 rtree_key_cmp(
121 /*==========*/
122 page_cur_mode_t mode, /*!< in: compare method. */
123 const uchar* b, /*!< in: first key. */
124 int b_len, /*!< in: first key len. */
125 const uchar* a, /*!< in: second key. */
126 int a_len); /*!< in: second key len. */
127
128 /*************************************************************//**
129 Calculates MBR_AREA(a+b) - MBR_AREA(a)
130 Note: when 'a' and 'b' objects are far from each other,
131 the area increase can be really big, so this function
132 can return 'inf' as a result. */
133 double
134 rtree_area_increase(
135 const uchar* a, /*!< in: first mbr. */
136 const uchar* b, /*!< in: second mbr. */
137 int a_len, /*!< in: mbr length. */
138 double* ab_area); /*!< out: increased area. */
139
140 /** Calculates overlapping area
141 @param[in] a mbr a
142 @param[in] b mbr b
143 @param[in] mbr_len mbr length
144 @return overlapping area */
145 double
146 rtree_area_overlapping(
147 const uchar* a,
148 const uchar* b,
149 int mbr_len);
150 #endif
151