1 // Copyright (c) 2017, 2018, Oracle and/or its affiliates. All rights reserved.
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 utility functions for working with geometrycollections.
26 
27 #include "sql/gis/gc_utils.h"
28 
29 #include <boost/geometry.hpp>  // boost::geometry::difference
30 
31 #include "my_dbug.h"  // DBUG_ASSERT
32 #include "sql/gis/difference_functor.h"
33 #include "sql/gis/geometries.h"
34 #include "sql/gis/geometries_cs.h"
35 #include "sql/gis/geometries_traits.h"
36 #include "sql/gis/union_functor.h"
37 #include "template_utils.h"  // down_cast
38 
39 namespace bg = boost::geometry;
40 
41 namespace gis {
42 
43 template <typename Pt, typename Ls, typename Py, typename GC, typename MPt,
44           typename MLs, typename MPy>
typed_split_gc(const GC * gc,MPt * mpt,MLs * mls,MPy * mpy)45 static void typed_split_gc(const GC *gc, MPt *mpt, MLs *mls, MPy *mpy) {
46   DBUG_ASSERT(gc->coordinate_system() == mpt->coordinate_system() &&
47               gc->coordinate_system() == mls->coordinate_system() &&
48               gc->coordinate_system() == mpy->coordinate_system());
49 
50   for (const auto g : *gc) {
51     switch (g->type()) {
52       case Geometry_type::kPoint:
53         mpt->push_back(*down_cast<Pt *>(g));
54         break;
55       case Geometry_type::kLinestring:
56         mls->push_back(*down_cast<Ls *>(g));
57         break;
58       case Geometry_type::kPolygon:
59         mpy->push_back(*down_cast<Py *>(g));
60         break;
61       case Geometry_type::kGeometrycollection:
62         typed_split_gc<Pt, Ls, Py, GC, MPt, MLs, MPy>(down_cast<GC *>(g), mpt,
63                                                       mls, mpy);
64         break;
65       case Geometry_type::kMultipoint: {
66         const MPt *m = down_cast<const MPt *>(g);
67         for (std::size_t i = 0; i < m->size(); i++)
68           mpt->push_back(static_cast<const Pt &>((*m)[i]));
69         break;
70       }
71       case Geometry_type::kMultilinestring: {
72         const MLs *m = down_cast<const MLs *>(g);
73         for (std::size_t i = 0; i < m->size(); i++)
74           mls->push_back(static_cast<const Ls &>((*m)[i]));
75         break;
76       }
77       case Geometry_type::kMultipolygon: {
78         const MPy *m = down_cast<const MPy *>(g);
79         for (std::size_t i = 0; i < m->size(); i++)
80           mpy->push_back(static_cast<const Py &>((*m)[i]));
81         break;
82       }
83       case Geometry_type::kGeometry:
84         DBUG_ASSERT(false);
85         break;
86     }
87   }
88 }
89 
split_gc(const Geometrycollection * gc,std::unique_ptr<Multipoint> * mpt,std::unique_ptr<Multilinestring> * mls,std::unique_ptr<Multipolygon> * mpy)90 void split_gc(const Geometrycollection *gc, std::unique_ptr<Multipoint> *mpt,
91               std::unique_ptr<Multilinestring> *mls,
92               std::unique_ptr<Multipolygon> *mpy) {
93   switch (gc->coordinate_system()) {
94     case Coordinate_system::kCartesian:
95       mpt->reset(new Cartesian_multipoint());
96       mls->reset(new Cartesian_multilinestring());
97       mpy->reset(new Cartesian_multipolygon());
98       typed_split_gc<Cartesian_point, Cartesian_linestring, Cartesian_polygon,
99                      Cartesian_geometrycollection, Cartesian_multipoint,
100                      Cartesian_multilinestring, Cartesian_multipolygon>(
101           down_cast<const Cartesian_geometrycollection *>(gc),
102           down_cast<Cartesian_multipoint *>(mpt->get()),
103           down_cast<Cartesian_multilinestring *>(mls->get()),
104           down_cast<Cartesian_multipolygon *>(mpy->get()));
105       break;
106     case Coordinate_system::kGeographic:
107       mpt->reset(new Geographic_multipoint());
108       mls->reset(new Geographic_multilinestring());
109       mpy->reset(new Geographic_multipolygon());
110       typed_split_gc<Geographic_point, Geographic_linestring,
111                      Geographic_polygon, Geographic_geometrycollection,
112                      Geographic_multipoint, Geographic_multilinestring,
113                      Geographic_multipolygon>(
114           down_cast<const Geographic_geometrycollection *>(gc),
115           down_cast<Geographic_multipoint *>(mpt->get()),
116           down_cast<Geographic_multilinestring *>(mls->get()),
117           down_cast<Geographic_multipolygon *>(mpy->get()));
118       break;
119   }
120 }
121 
122 template <typename MPt, typename MLs, typename MPy>
typed_gc_union(double semi_major,double semi_minor,std::unique_ptr<Multipoint> * mpt,std::unique_ptr<Multilinestring> * mls,std::unique_ptr<Multipolygon> * mpy)123 void typed_gc_union(double semi_major, double semi_minor,
124                     std::unique_ptr<Multipoint> *mpt,
125                     std::unique_ptr<Multilinestring> *mls,
126                     std::unique_ptr<Multipolygon> *mpy) {
127   Difference difference(semi_major, semi_minor);
128   Union union_(semi_major, semi_minor);
129 
130   std::unique_ptr<MPy> polygons(new MPy());
131   for (auto &py : *down_cast<MPy *>(mpy->get())) {
132     polygons.reset(down_cast<MPy *>(union_(polygons.get(), &py)));
133     if (polygons->coordinate_system() == Coordinate_system::kGeographic &&
134         polygons->is_empty()) {
135       // The result of a union between a geographic multipolygon and a
136       // geographic polygon is empty. There are two reasons why this may happen:
137       //
138       // 1. One of the polygons involved are invalid.
139       // 2. One of the polygons involved covers half the globe, or more.
140       //
141       // Since invalid input is only reported to the extent it is explicitly
142       // detected, we can simply return a too large polygon error in both cases.
143       throw too_large_polygon_exception();
144     }
145   }
146 
147   std::unique_ptr<MLs> linestrings(new MLs());
148   linestrings.reset(down_cast<MLs *>(difference(mls->get(), polygons.get())));
149 
150   std::unique_ptr<MPt> points(down_cast<MPt *>(
151       difference(down_cast<MPt *>(mpt->get()), linestrings.get())));
152   points.reset(down_cast<MPt *>(difference(points.get(), polygons.get())));
153 
154   mpy->reset(polygons.release());
155   mls->reset(linestrings.release());
156   mpt->reset(points.release());
157 }
158 
gc_union(double semi_major,double semi_minor,std::unique_ptr<Multipoint> * mpt,std::unique_ptr<Multilinestring> * mls,std::unique_ptr<Multipolygon> * mpy)159 void gc_union(double semi_major, double semi_minor,
160               std::unique_ptr<Multipoint> *mpt,
161               std::unique_ptr<Multilinestring> *mls,
162               std::unique_ptr<Multipolygon> *mpy) {
163   DBUG_ASSERT(mpt->get() && mls->get() && mpy->get());
164   DBUG_ASSERT((*mpt)->coordinate_system() == (*mls)->coordinate_system() &&
165               (*mpt)->coordinate_system() == (*mpy)->coordinate_system());
166   // We're using empty GCs to detect invalid geometries, so empty geometry
167   // collections should be filtered out before calling gc_union.
168   DBUG_ASSERT(!(*mpt)->empty() || !(*mls)->empty() || !(*mpy)->empty());
169 
170   switch ((*mpt)->coordinate_system()) {
171     case Coordinate_system::kCartesian: {
172       typed_gc_union<Cartesian_multipoint, Cartesian_multilinestring,
173                      Cartesian_multipolygon>(semi_major, semi_minor, mpt, mls,
174                                              mpy);
175       break;
176     }
177     case Coordinate_system::kGeographic: {
178       typed_gc_union<Geographic_multipoint, Geographic_multilinestring,
179                      Geographic_multipolygon>(semi_major, semi_minor, mpt, mls,
180                                               mpy);
181       break;
182     }
183   }
184 
185   // If all collections are empty, we've encountered at least one invalid
186   // geometry.
187   if ((*mpt)->empty() && (*mls)->empty() && (*mpy)->empty())
188     throw invalid_geometry_exception();
189 
190   DBUG_ASSERT(mpt->get() && mls->get() && mpy->get());
191   DBUG_ASSERT(!(*mpt)->empty() || !(*mls)->empty() || !(*mpy)->empty());
192 }
193 
194 }  // namespace gis
195