1 // Copyright (c) 2017, 2020, Oracle and/or its affiliates.
2 //
3 // This program is free software; you can redistribute it and/or modify
4 // it under the terms of the GNU General Public License, version 2.0,
5 // as published by the Free Software Foundation.
6 //
7 // This program is also distributed with certain software (including
8 // but not limited to OpenSSL) that is licensed under separate terms,
9 // as designated in a particular file or component or in included license
10 // documentation. The authors of MySQL hereby grant you an additional
11 // permission to link the program and your derivative works with the
12 // separately licensed software that they have included with MySQL.
13 //
14 // This program is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 // GNU General Public License, version 2.0, for more details.
18 //
19 // You should have received a copy of the GNU General Public License
20 // along with this program; if not, write to the Free Software
21 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
22
23 /// @file
24 ///
25 /// This file implements the mbr_disjoint function.
26
27 #include "sql/gis/mbr_utils.h"
28
29 #include <cmath> // std::isnan
30 #include <exception>
31
32 #include <boost/geometry.hpp>
33
34 #include "sql/dd/types/spatial_reference_system.h" // dd::Spatial_reference_system
35 #include "sql/gis/box.h"
36 #include "sql/gis/box_traits.h"
37 #include "sql/gis/geometries.h"
38 #include "sql/gis/geometries_cs.h"
39 #include "sql/gis/geometries_traits.h"
40 #include "template_utils.h" // down_cast
41
42 namespace bg = boost::geometry;
43
44 namespace gis {
45
mbrs_are_equal(Box const & mbr1,Box const & mbr2)46 bool mbrs_are_equal(Box const &mbr1, Box const &mbr2) {
47 DBUG_ASSERT(mbr1.coordinate_system() == mbr2.coordinate_system());
48 switch (mbr1.coordinate_system()) {
49 case Coordinate_system::kCartesian:
50 return bg::equals(*down_cast<const Cartesian_box *>(&mbr1),
51 *down_cast<const Cartesian_box *>(&mbr2));
52 case Coordinate_system::kGeographic:
53 return bg::equals(*down_cast<const Geographic_box *>(&mbr1),
54 *down_cast<const Geographic_box *>(&mbr2));
55 }
56 DBUG_ASSERT(false); /* purecov: inspected */
57 return false; /* purecov: inspected */
58 }
59
mbr_is_empty(Box const & mbr)60 bool mbr_is_empty(Box const &mbr) {
61 return std::isnan(mbr.min_corner().x()) && std::isnan(mbr.min_corner().y()) &&
62 std::isnan(mbr.max_corner().x()) && std::isnan(mbr.max_corner().y());
63 }
64
mbr_is_point(Box const & mbr)65 bool mbr_is_point(Box const &mbr) {
66 return mbr.min_corner().x() == mbr.max_corner().x() &&
67 mbr.min_corner().y() == mbr.max_corner().y();
68 }
69
mbr_is_line(Box const & mbr)70 bool mbr_is_line(Box const &mbr) {
71 return (mbr.min_corner().x() == mbr.max_corner().x()) !=
72 (mbr.min_corner().y() == mbr.max_corner().y());
73 }
74
75 /// Merges a vector of Cartesian MBRs into one common MBR.
76 ///
77 /// Since the coordinate system doesn't wrap, the order in which MBRs are
78 /// expanded doesn't matter.
79 ///
80 /// @param[in] boxes Vector of MBRs to merge.
81 /// @param[out] mbr The resulting MBR.
merge_mbrs(const std::vector<Cartesian_box> & boxes,Cartesian_box * mbr)82 static void merge_mbrs(const std::vector<Cartesian_box> &boxes,
83 Cartesian_box *mbr) {
84 if (!boxes.empty()) *mbr = boxes[0];
85 for (auto &box : boxes) bg::expand(*mbr, box);
86 }
87
88 /// Merges a vector of geographic MBRs into one common MBR.
89 ///
90 /// The coordinate system wraps, so the MBRs must be expanded in the correct
91 /// order to avoid creating an MBR that is larger than necessary.
92 ///
93 /// If the vector of boxes is empty, the result MBR is unchanged.
94 ///
95 /// @param[in] boxes Vector of MBRs to merge.
96 /// @param[out] mbr The resulting MBR.
merge_mbrs(const std::vector<Geographic_box> & boxes,Geographic_box * mbr)97 static void merge_mbrs(const std::vector<Geographic_box> &boxes,
98 Geographic_box *mbr) {
99 if (!boxes.empty())
100 bg::detail::envelope::envelope_range_of_boxes::apply(boxes, *mbr);
101 }
102
103 /// Computes the envelope of a Cartesian geometry.
104 ///
105 /// The MBR returned may be a collapsed box.
106 ///
107 /// @param[in] g The geometry.
108 /// @param[out] mbr The envelope of g.
cartesian_envelope(const Geometry * g,Cartesian_box * mbr)109 static void cartesian_envelope(const Geometry *g, Cartesian_box *mbr) {
110 switch (g->type()) {
111 case Geometry_type::kPoint:
112 bg::envelope(*down_cast<const Cartesian_point *>(g), *mbr);
113 break;
114 case Geometry_type::kLinestring:
115 bg::envelope(*down_cast<const Cartesian_linestring *>(g), *mbr);
116 break;
117 case Geometry_type::kPolygon:
118 bg::envelope(*down_cast<const Cartesian_polygon *>(g), *mbr);
119 break;
120 case Geometry_type::kGeometrycollection: {
121 std::vector<Cartesian_box> boxes;
122 Cartesian_box geom_mbr;
123 for (auto geom : *down_cast<const Cartesian_geometrycollection *>(g)) {
124 switch (geom->type()) {
125 case Geometry_type::kPoint:
126 bg::envelope(*down_cast<const Cartesian_point *>(geom), geom_mbr);
127 break;
128 case Geometry_type::kLinestring:
129 bg::envelope(*down_cast<const Cartesian_linestring *>(geom),
130 geom_mbr);
131 break;
132 case Geometry_type::kPolygon:
133 bg::envelope(*down_cast<const Cartesian_polygon *>(geom), geom_mbr);
134 break;
135 case Geometry_type::kGeometrycollection:
136 cartesian_envelope(geom, &geom_mbr);
137 break;
138 case Geometry_type::kMultipoint:
139 bg::envelope(*down_cast<const Cartesian_multipoint *>(geom),
140 geom_mbr);
141 break;
142 case Geometry_type::kMultilinestring:
143 bg::envelope(*down_cast<const Cartesian_multilinestring *>(geom),
144 geom_mbr);
145 break;
146 case Geometry_type::kMultipolygon:
147 bg::envelope(*down_cast<const Cartesian_multipolygon *>(geom),
148 geom_mbr);
149 break;
150 case Geometry_type::kGeometry:
151 DBUG_ASSERT(false);
152 throw new std::exception();
153 }
154
155 // Cartesian_boxxes around empty geometries contain NaN in all
156 // coordinates. If
157 // passed to bg::expand, the result will be a box with all NaN
158 // coordinates. Therefore, we skip empty boxes.
159 if (!mbr_is_empty(geom_mbr)) boxes.push_back(geom_mbr);
160 }
161 merge_mbrs(boxes, mbr);
162 break;
163 }
164 case Geometry_type::kMultipoint:
165 bg::envelope(*down_cast<const Cartesian_multipoint *>(g), *mbr);
166 break;
167 case Geometry_type::kMultilinestring:
168 bg::envelope(*down_cast<const Cartesian_multilinestring *>(g), *mbr);
169 break;
170 case Geometry_type::kMultipolygon:
171 bg::envelope(*down_cast<const Cartesian_multipolygon *>(g), *mbr);
172 break;
173 case Geometry_type::kGeometry:
174 DBUG_ASSERT(false);
175 throw new std::exception();
176 break;
177 }
178 }
179
180 /// Computes the envelope of a geographic geometry.
181 ///
182 /// The MBR returned may be a collapsed box.
183 ///
184 /// @param[in] g The geometry.
185 /// @param[in] semi_major Semi-major axis of ellipsoid.
186 /// @param[in] semi_minor Semi-minor axis of ellipsoid.
187 /// @param[out] mbr The envelope of g.
geographic_envelope(const Geometry * g,double semi_major,double semi_minor,Geographic_box * mbr)188 static void geographic_envelope(const Geometry *g, double semi_major,
189 double semi_minor, Geographic_box *mbr) {
190 bg::strategy::envelope::geographic<bg::strategy::andoyer,
191 bg::srs::spheroid<double>>
192 strategy(bg::srs::spheroid<double>(semi_major, semi_minor));
193 switch (g->type()) {
194 case Geometry_type::kPoint:
195 bg::envelope(*down_cast<const Geographic_point *>(g), *mbr);
196 break;
197 case Geometry_type::kLinestring:
198 bg::envelope(*down_cast<const Geographic_linestring *>(g), *mbr,
199 strategy);
200 break;
201 case Geometry_type::kPolygon:
202 bg::envelope(*down_cast<const Geographic_polygon *>(g), *mbr, strategy);
203 break;
204 case Geometry_type::kGeometrycollection: {
205 std::vector<Geographic_box> boxes;
206 Geographic_box geom_mbr;
207 for (auto geom : *down_cast<const Geographic_geometrycollection *>(g)) {
208 switch (geom->type()) {
209 case Geometry_type::kPoint:
210 bg::envelope(*down_cast<const Geographic_point *>(geom), geom_mbr);
211 break;
212 case Geometry_type::kLinestring:
213 bg::envelope(*down_cast<const Geographic_linestring *>(geom),
214 geom_mbr, strategy);
215 break;
216 case Geometry_type::kPolygon:
217 bg::envelope(*down_cast<const Geographic_polygon *>(geom), geom_mbr,
218 strategy);
219 break;
220 case Geometry_type::kGeometrycollection:
221 geographic_envelope(geom, semi_major, semi_minor, &geom_mbr);
222 break;
223 case Geometry_type::kMultipoint:
224 bg::envelope(*down_cast<const Geographic_multipoint *>(geom),
225 geom_mbr);
226 break;
227 case Geometry_type::kMultilinestring:
228 bg::envelope(*down_cast<const Geographic_multilinestring *>(geom),
229 geom_mbr, strategy);
230 break;
231 case Geometry_type::kMultipolygon:
232 bg::envelope(*down_cast<const Geographic_multipolygon *>(geom),
233 geom_mbr, strategy);
234 break;
235 case Geometry_type::kGeometry:
236 DBUG_ASSERT(false);
237 throw new std::exception();
238 }
239
240 // Geographic_boxxes around empty geometries contain NaN in all
241 // coordinates. If
242 // passed to bg::expand, the result will be a box with all NaN
243 // coordinates. Therefore, we skip empty boxes.
244 if (!mbr_is_empty(geom_mbr)) boxes.push_back(geom_mbr);
245 }
246 merge_mbrs(boxes, mbr);
247 break;
248 }
249 case Geometry_type::kMultipoint:
250 bg::envelope(*down_cast<const Geographic_multipoint *>(g), *mbr);
251 break;
252 case Geometry_type::kMultilinestring:
253 bg::envelope(*down_cast<const Geographic_multilinestring *>(g), *mbr,
254 strategy);
255 break;
256 case Geometry_type::kMultipolygon:
257 bg::envelope(*down_cast<const Geographic_multipolygon *>(g), *mbr,
258 strategy);
259 break;
260 case Geometry_type::kGeometry:
261 DBUG_ASSERT(false);
262 throw new std::exception();
263 break;
264 }
265 }
266
box_envelope(const Geometry * g,const dd::Spatial_reference_system * srs,Box * mbr)267 void box_envelope(const Geometry *g, const dd::Spatial_reference_system *srs,
268 Box *mbr) {
269 switch (g->coordinate_system()) {
270 case Coordinate_system::kCartesian:
271 cartesian_envelope(g, down_cast<Cartesian_box *>(mbr));
272 break;
273 case Coordinate_system::kGeographic:
274 geographic_envelope(g, srs ? srs->semi_major_axis() : 0.0,
275 srs ? srs->semi_minor_axis() : 0.0,
276 down_cast<Geographic_box *>(mbr));
277 break;
278 }
279 }
280
281 } // namespace gis
282