1 #ifndef SQL_GIS_RTREE_SUPPORT_H_INCLUDED 2 #define SQL_GIS_RTREE_SUPPORT_H_INCLUDED 3 4 // Copyright (c) 2017, 2020, Oracle and/or its affiliates. All rights reserved. 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; 48 } rtr_mbr_t; 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. 61 dd::Spatial_reference_system *fetch_srs(gis::srid_t srid); 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. 77 bool mbr_contain_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, 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. 91 bool mbr_equal_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, 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. 105 bool mbr_intersect_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, 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. 115 bool mbr_disjoint_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, 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. 134 bool mbr_within_cmp(const dd::Spatial_reference_system *srs, rtr_mbr_t *a, 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. 202 int get_mbr_from_store(const dd::Spatial_reference_system *srs, 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. 221 double rtree_area_increase(const dd::Spatial_reference_system *srs, 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. 233 double rtree_area_overlapping(const dd::Spatial_reference_system *srs, 234 const uchar *mbr_a, const uchar *mbr_b, 235 int mbr_len); 236 237 #endif // SQL_GIS_RTREE_SUPPORT_H_INCLUDED 238