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