MySQL  8.0.28
Source Code Documentation
rtree_support.h
Go to the documentation of this file.
1 #ifndef SQL_GIS_RTREE_SUPPORT_H_INCLUDED
2 #define SQL_GIS_RTREE_SUPPORT_H_INCLUDED
3 
4 // Copyright (c) 2017, 2021, Oracle and/or its affiliates.
5 //
6 // This program is free software; you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License, version 2.0,
8 // as published by the Free Software Foundation.
9 //
10 // This program is also distributed with certain software (including
11 // but not limited to OpenSSL) that is licensed under separate terms,
12 // as designated in a particular file or component or in included license
13 // documentation. The authors of MySQL hereby grant you an additional
14 // permission to link the program and your derivative works with the
15 // separately licensed software that they have included with MySQL.
16 //
17 // This program is distributed in the hope that it will be useful,
18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 // GNU General Public License, version 2.0, for more details.
21 //
22 // You should have received a copy of the GNU General Public License
23 // along with this program; if not, write to the Free Software
24 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
25 
26 /// @file
27 ///
28 /// This file declares a set of functions that storage engines can call to do
29 /// geometrical operations.
30 
31 #include "my_inttypes.h" // uchar, uint
32 #include "sql/gis/srid.h"
33 
34 namespace dd {
35 class Spatial_reference_system;
36 }
37 
38 /// In memory representation of a minimum bounding rectangle
39 typedef struct rtr_mbr {
40  /// minimum on x
41  double xmin;
42  /// maximum on x
43  double xmax;
44  /// minimum on y
45  double ymin;
46  /// maximum on y
47  double ymax;
49 
50 /// Fetches a copy of the dictionary entry for a spatial reference system.
51 ///
52 /// Spatial reference dictionary cache objects have a limited lifetime,
53 /// typically until the end of a transaction. This function returns a clone of
54 /// the dictionary object so that it is valid also after the transaction has
55 /// ended. This is necessary since InnoDB may do index operations after the
56 /// transaction has ended.
57 ///
58 /// @param[in] srid The spatial reference system ID to look up.
59 ///
60 /// @return The spatial reference system dictionary entry, or nullptr.
62 
63 /// Checks if one MBR covers another MBR.
64 ///
65 /// @warning Despite the name, this function computes the covers relation, not
66 /// contains.
67 ///
68 /// For both MBRs, the coordinates of the MBR's minimum corners must be smaller
69 /// than or equal to the corresponding coordinates of the maximum corner.
70 ///
71 /// @param[in] srs Spatial reference system.
72 /// @param[in] a The first MBR.
73 /// @param[in] b The second MBR.
74 ///
75 /// @retval true MBR a contains MBR b.
76 /// @retval false MBR a doesn't contain MBR b.
78  rtr_mbr_t *b);
79 
80 /// Checks if two MBRs are equal
81 ///
82 /// For both MBRs, the coordinates of the MBR's minimum corners must be smaller
83 /// than or equal to the corresponding coordinates of the maximum corner.
84 ///
85 /// @param[in] srs Spatial reference system.
86 /// @param[in] a The first MBR.
87 /// @param[in] b The second MBR.
88 ///
89 /// @retval true The two MBRs are equal.
90 /// @retval false The two MBRs aren't equal.
92  rtr_mbr_t *b);
93 
94 /// Checks if two MBRs intersect each other
95 ///
96 /// @param[in] srs Spatial reference system.
97 /// @param[in] a The first MBR.
98 /// @param[in] b The second MBR.
99 ///
100 /// For both MBRs, the coordinates of the MBR's minimum corners must be smaller
101 /// than or equal to the corresponding coordinates of the maximum corner.
102 ///
103 /// @retval true The MBRs intersect each other.
104 /// @retval false The MBRs are disjoint.
106  rtr_mbr_t *b);
107 
108 /// Checks if two MBRs are disjoint
109 ///
110 /// For both MBRs, the coordinates of the MBR's minimum corners must be smaller
111 /// than or equal to the corresponding coordinates of the maximum corner.
112 ///
113 /// @retval true The MBRs are disjoint.
114 /// @retval false The MBRs intersect each other.
116  rtr_mbr_t *b);
117 
118 /// Checks if one MBR is covered by another MBR.
119 ///
120 /// @warning Despite the name, this function computes the covered_by relation,
121 /// not within.
122 ///
123 /// @note If the minimum corner coordinates are larger than the corresponding
124 /// coordinates of the maximum corner, and if not all a and b coordinates are
125 /// the same, the function returns the inverse result, i.e., return true if a is
126 /// not covered by b.
127 ///
128 /// @param[in] srs Spatial reference system.
129 /// @param[in] a The first MBR.
130 /// @param[in] b The second MBR.
131 ///
132 /// @retval true MBR a is within MBR b.
133 /// @retval false MBR a isn't within MBR b.
135  rtr_mbr_t *b);
136 
137 /// Expands an MBR to also cover another MBR.
138 ///
139 /// @note The function takes a dimension parameter, but currently only supports
140 /// 2d MBRs.
141 ///
142 /// MBR format: a[0] = xmin, a[1] = xmax, a[2] = ymin, a[3] = ymax. Same for b.
143 ///
144 /// @param[in] srs Spatial reference system.
145 /// @param[in,out] a The first MBR, where the joined result will be.
146 /// @param[in] b The second MBR.
147 /// @param[in] n_dim Number of dimensions. Must be 2.
148 void mbr_join(const dd::Spatial_reference_system *srs, double *a,
149  const double *b, int n_dim);
150 
151 /// Computes the combined area of two MBRs.
152 ///
153 /// The MBRs may overlap.
154 ///
155 /// @note The function takes a dimension parameter, but currently only supports
156 /// 2d MBRs.
157 ///
158 /// @param[in] srs Spatial reference system.
159 /// @param[in] a The first MBR.
160 /// @param[in] b The second MBR.
161 /// @param[in] n_dim Number of dimensions. Must be 2.
162 ///
163 /// @return The area of MBR a expanded by MBR b.
164 double mbr_join_area(const dd::Spatial_reference_system *srs, const double *a,
165  const double *b, int n_dim);
166 
167 /// Computes the area of an MBR.
168 ///
169 /// @note The function takes a dimension parameter, but currently only supports
170 /// 2d MBRs.
171 ///
172 /// @param[in] srs Spatial reference system.
173 /// @param[in] a The MBR.
174 /// @param[in] n_dim Number of dimensions. Must be 2.
175 ///
176 /// @return Are of the MBR.
177 double compute_area(const dd::Spatial_reference_system *srs, const double *a,
178  int n_dim);
179 
180 /// Computes the MBR of a geometry.
181 ///
182 /// If the geometry is empty, a box that covers the entire domain is returned.
183 ///
184 /// The geometry is expected to be on the storage format (SRID + WKB). The
185 /// caller is expected to provide an output buffer that is large enough.
186 ///
187 /// @note The function takes a dimension parameter, but currently only supports
188 /// 2d MBRs.
189 ///
190 /// The SRID of the SRS parameter must match the SRID stored in the first four
191 /// bytes of the geometry string.
192 ///
193 /// @param[in] srs Spatial reference system.
194 /// @param[in] store The geometry.
195 /// @param[in] size Number of bytes in the geometry string.
196 /// @param[in] n_dims Number of dimensions. Must be 2.
197 /// @param[out] mbr The computed MBR.
198 /// @param[out] srid SRID of the geometry
199 ///
200 /// @retval 0 The geometry is valid.
201 /// @retval -1 The geometry is invalid.
203  const uchar *store, uint size, uint n_dims, double *mbr,
204  gis::srid_t *srid);
205 
206 /// Computes the extra area covered if an MBR is expanded to cover another MBR.
207 ///
208 /// The formula is area(a + b) - area(a). This is generally different from
209 /// area(b). If MBR b overlaps MBR a, area(a+b) - area(a) < area(b). If they are
210 /// far apart, area(a+b) - area(a) > area(b).
211 ///
212 /// @note If MBRs a and b are far apart, the function may return Inf.
213 ///
214 /// @param[in] srs Spatial reference system.
215 /// @param[in] mbr_a First MBR.
216 /// @param[in] mbr_b Second MBR.
217 /// @param[in] mbr_len MBR length in bytes. Must be 4 * sizeof(double).
218 /// @param[out] ab_area The total area of MBRs a and b combined into one MBR.
219 ///
220 /// @return The increase in area when expanding from MBR a to also cover MBR b.
222  const uchar *mbr_a, const uchar *mbr_b, int mbr_len,
223  double *ab_area);
224 
225 /// Calculates the overlapping area between two MBRs.
226 ///
227 /// @param[in] srs Spatial reference system.
228 /// @param[in] mbr_a First MBR.
229 /// @param[in] mbr_b Second MBR.
230 /// @param[in] mbr_len MBR length in bytes. Must be 4 * sizeof(double).
231 ///
232 /// @return The area of the overlapping region.
234  const uchar *mbr_a, const uchar *mbr_b,
235  int mbr_len);
236 
237 #endif // SQL_GIS_RTREE_SUPPORT_H_INCLUDED
Definition: spatial_reference_system.h:52
bool store(THD *thd, const Table *tp)
Stores the SDI for a table.
Definition: sdi.cc:606
Some integer typedefs for easier portability.
unsigned char uchar
Definition: my_inttypes.h:51
The version of the current data dictionary table definitions.
Definition: dictionary_client.h:42
std::uint32_t srid_t
A spatial reference system ID (SRID).
Definition: srid.h:32
double rtree_area_increase(const dd::Spatial_reference_system *srs, const uchar *mbr_a, const uchar *mbr_b, int mbr_len, double *ab_area)
Computes the extra area covered if an MBR is expanded to cover another MBR.
struct rtr_mbr rtr_mbr_t
In memory representation of a minimum bounding rectangle.
bool mbr_disjoint_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, rtr_mbr_t *b)
Checks if two MBRs are disjoint.
Definition: rtree_support.cc:177
double mbr_join_area(const dd::Spatial_reference_system *srs, const double *a, const double *b, int n_dim)
Computes the combined area of two MBRs.
bool mbr_equal_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, rtr_mbr_t *b)
Checks if two MBRs are equal.
Definition: rtree_support.cc:108
int get_mbr_from_store(const dd::Spatial_reference_system *srs, const uchar *store, uint size, uint n_dims, double *mbr, gis::srid_t *srid)
Computes the MBR of a geometry.
double rtree_area_overlapping(const dd::Spatial_reference_system *srs, const uchar *mbr_a, const uchar *mbr_b, int mbr_len)
Calculates the overlapping area between two MBRs.
bool mbr_contain_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, rtr_mbr_t *b)
Checks if one MBR covers another MBR.
Definition: rtree_support.cc:72
bool mbr_within_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, rtr_mbr_t *b)
Checks if one MBR is covered by another MBR.
Definition: rtree_support.cc:208
bool mbr_intersect_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, rtr_mbr_t *b)
Checks if two MBRs intersect each other.
Definition: rtree_support.cc:146
double compute_area(const dd::Spatial_reference_system *srs, const double *a, int n_dim)
Computes the area of an MBR.
void mbr_join(const dd::Spatial_reference_system *srs, double *a, const double *b, int n_dim)
Expands an MBR to also cover another MBR.
dd::Spatial_reference_system * fetch_srs(gis::srid_t srid)
Fetches a copy of the dictionary entry for a spatial reference system.
Definition: rtree_support.cc:59
In memory representation of a minimum bounding rectangle.
Definition: rtree_support.h:39
double xmin
minimum on x
Definition: rtree_support.h:41
double xmax
maximum on x
Definition: rtree_support.h:43
double ymin
minimum on y
Definition: rtree_support.h:45
double ymax
maximum on y
Definition: rtree_support.h:47
unsigned int uint
Definition: uca-dump.cc:29