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