MySQL  8.0.23
Source Code Documentation
geometries.h
Go to the documentation of this file.
1 #ifndef SQL_GIS_GEOMETRIES_H_INCLUDED
2 #define SQL_GIS_GEOMETRIES_H_INCLUDED
3 
4 // Copyright (c) 2017, 2018, 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 the geometry class hierarchy used by the server as the
29 /// internal representation of geometries.
30 ///
31 /// The hierarchy is closely modelled after the hierarchy in SFA-CA
32 /// (OGC 06-103r4), but since Boost.Geometry depends on type traits to
33 /// know if a geometry is in a Cartesian or geographic SRS, there are
34 /// Cartesian and geographic specializations of each instantiable type
35 /// in the SFA-CA. These are defined in geometries_cs.h.
36 ///
37 /// Because of Boost.Geometry, iterators have to be of coordinate system
38 /// specific types. It is therefore not possible to have the standard begin()
39 /// and end() iterators in the common superclass. Instead, operator[] is
40 /// provided as a coordinate system agnostic option.
41 ///
42 /// @see geometries_cs.h
43 
44 #include <cmath>
45 #include <cstdint>
46 
47 namespace gis {
48 
49 /// Types of geometry objects. Not all are instantiable.
50 ///
51 /// The values and the storage type are the same as used in WKB.
52 enum class Geometry_type : std::uint32_t {
53  kGeometry = 0,
54  kPoint = 1,
55  kLinestring = 2,
56  kPolygon = 3,
57  kMultipoint = 4,
58  kMultilinestring = 5,
59  kMultipolygon = 6,
61  // kMulticurve = 11,
62  // kMultisurface = 12,
63  // kCurve = 13,
64  // kSurface = 14,
65 };
66 
67 /// Types of coordinate systems.
68 enum class Coordinate_system {
69  /// A Cartesian plane with the same unit in both directions.
70  kCartesian = 0,
71  /// An ellipsoidal system with longitude and latitude coordinates,
72  /// both in the same unit.
73  kGeographic = 1
74 };
75 
76 /// Direction of a ring.
77 enum class Ring_direction {
78  /// Clockwise.
79  kCW = 0,
80  /// Counterclockwise.
81  kCCW = 1,
82  /// Unknown.
83  ///
84  /// Used only as an output value when the function is unable to determine the
85  /// ring direction, e.g., if the ring contains only repetitions of the same
86  /// point, or if there is a spike in the ring.
87  kUnknown = 2
88 };
89 
90 class Geometry_visitor;
91 
92 /// Abstract superclass for all geometric objects.
93 ///
94 /// Geometry is a non-instantiable type in SQL.
95 ///
96 /// The hierarchy is first divided into abstract classes according to the SFA-CA
97 /// geometry type hierarchy, and then divided into concrete subclasses for each
98 /// coordinate system.
99 class Geometry {
100  public:
101  Geometry() = default;
102  virtual ~Geometry() = default;
103  Geometry(const Geometry &) = default;
104  Geometry &operator=(const Geometry &) = default;
105 
106  /// Gets the geometry type of the object.
107  ///
108  /// @return The type of this object
109  virtual Geometry_type type() const = 0;
110 
111  /// Gets the coordinate system.
112  ///
113  /// @return The coordiante system type.
115 
116  /// Applies a hierarchical visitor to this geometry.
117  ///
118  /// @see gis::Geometry_visitor
119  ///
120  /// @param v A hierarchical visitor.
121  ///
122  /// @retval true The execution was aborted by the visitor.
123  /// @retval false The execution completed.
124  virtual bool accept(Geometry_visitor *v) = 0;
125 
126  /// Check if this is an empty geometry.
127  ///
128  /// The definition of empty geometries is the one in SFA-CA (OGC 06-103r4,
129  /// Sect. 6.1.2.2), i.e., an empty point set.
130  ///
131  /// @note This is different from the function "empty", which returns true if a
132  /// geometry contains no subgeometries. E.g., a geometry collection may
133  /// contain another geometry collection which is empty. In this case, the
134  /// "empty" function would return false on the outermost geometry collection,
135  /// while "is_empty" would return true.
136  ///
137  /// @retval true The geometry represents the empty point set.
138  /// @retval false The geometry represent a non-empty point set.
139  virtual bool is_empty() const = 0;
140 };
141 
142 /// A 2d point.
143 ///
144 /// Point is an instantiable type in SQL.
145 class Point : public Geometry {
146  public:
147  Point() : m_x(std::nan("")), m_y(std::nan("")) {}
148  Point(double x, double y) : m_x(x), m_y(y) {}
149  Geometry_type type() const override { return Geometry_type::kPoint; }
150  bool accept(Geometry_visitor *v) override;
151  bool is_empty() const override {
152  return (std::isnan(m_x) || std::isnan(m_y));
153  }
154 
155  /// Gets a coordinate value.
156  ///
157  /// This function signature must match the expectations of Boost.Geometry.
158  ///
159  /// @tparam K Coordinate number, zero indexed.
160  /// @return The coordinate value.
161  template <std::size_t K>
162  double get() const;
163 
164  /// Gets the first coordinate value.
165  ///
166  /// For geographic points, the first coordinate is longitude.
167  ///
168  /// @return The first coordinate value.
169  double x() const;
170 
171  /// Gets the second coordinate value.
172  ///
173  /// For geographic points, the second coordinate is latitude.
174  ///
175  /// @return The second coordinate value.
176  double y() const;
177 
178  /// Sets a coordinate.
179  ///
180  /// This function signature must match the expectations of Boost.Geometry.
181  ///
182  /// @tparam K Coordinate number, zero indexed.
183  /// @param d The coordinate value.
184  template <std::size_t K>
185  void set(double d);
186 
187  /// Sets the first coordinate value.
188  ///
189  /// For geographic points, the first coordinate is longitude.
190  ///
191  /// @param d The coordinate value.
192  void x(double d);
193 
194  /// Sets the second coordinate value.
195  ///
196  /// For geographic points, the second coordinate is latitude.
197  ///
198  /// @param d The coordinate value.
199  void y(double d);
200 
201  private:
202  /// First coordinate (X or longitude).
203  ///
204  /// Geographic coordinates are in radians, positive to the East of
205  /// Greenwich. Cartesian coordinates are in the SRSs length unit.
206  double m_x;
207 
208  /// Second coordinate (Y or latitude).
209  ///
210  /// Geographic coordinates are in radians, positive to the North of the
211  /// Equator. Cartesian coordinates are in the SRSs length unit.
212  double m_y;
213 };
214 
215 /// Compares two points.
216 ///
217 /// The point with the lowest X coordinate is the smaller point. If X
218 /// coordinates are equal, the point with the lowest Y coordinate is the
219 /// smaller.
220 ///
221 /// @param lhs Left hand side.
222 /// @param rhs Right hand side.
223 ///
224 /// @retval true Left hand side sorts before right hand side.
225 /// @retval false Left hand side does not sort before right hand side.
226 inline bool operator<(const Point &lhs, const Point &rhs) {
227  return (lhs.x() < rhs.x()) || (lhs.x() == rhs.x() && lhs.y() < rhs.y());
228 }
229 
230 /// An abstract 2d curve.
231 ///
232 /// Curve is a non-instantiable type in SQL.
233 class Curve : public Geometry {
234  public:
235  Geometry_type type() const override = 0;
236  bool accept(Geometry_visitor *v) override = 0;
237 };
238 
239 /// A string of connected line segments.
240 ///
241 /// Linestring is an instantiable type in SQL.
242 ///
243 /// According to the SFA-CA, linestrings have a linear interpolation between
244 /// points. In MySQL, a linestring represents the geodesic. On a plane, this is
245 /// linear interpolation, but on an ellipsoid, it's the shortest path along the
246 /// ellipsoid surface.
247 class Linestring : public Curve {
248  public:
249  Geometry_type type() const override { return Geometry_type::kLinestring; }
250  bool accept(Geometry_visitor *v) override = 0;
251  bool is_empty() const override { return empty(); }
252 
253  /// Adds a point to the end of the linestring.
254  ///
255  /// @param pt The point to add.
256  virtual void push_back(const Point &pt) = 0;
257  virtual void push_back(Point &&pt) = 0;
258 
259  /// Checks if the linestring is empty.
260  ///
261  /// Here, the definition of empty is that the linestring does not contain any
262  /// points. An invalid linestring with only one coordinate is not empty.
263  ///
264  /// @retval true The linestring is empty.
265  /// @retval false The linestring is not empty.
266  virtual bool empty() const = 0;
267 
268  /// Returns the size of (number of points in) the linestring.
269  ///
270  /// @return Number of points in the linestring.
271  virtual std::size_t size() const = 0;
272 
273  /// Removes all points from the linestring.
274  virtual void clear() noexcept = 0;
275 
276  virtual Point &operator[](std::size_t i) = 0;
277  virtual const Point &operator[](std::size_t i) const = 0;
278 };
279 
280 /// A ring-shaped linestring.
281 ///
282 /// Linearring is a non-instantiable type in SQL. It is used to represent
283 /// polygon rings.
284 ///
285 /// The start and end point of the linestring must be the same (assumed, but not
286 /// enforced, by the implementation).
287 class Linearring : public Linestring {
288  public:
289  bool accept(Geometry_visitor *v) override = 0;
290 };
291 
292 /// An abstract 2d surface.
293 ///
294 /// Surface is a non-instantiable type in SQL.
295 class Surface : public Geometry {
296  public:
297  bool accept(Geometry_visitor *v) override = 0;
298 
299  Geometry_type type() const override = 0;
300 };
301 
302 /// A polygon consisting of an outer ring and zero or more interior rings
303 /// defining holes in the polygon.
304 ///
305 /// Polygon is an instantiable type in SQL.
306 ///
307 /// The interior rings must be inside the exterior ring (not enforced by the
308 /// implementation).
309 class Polygon : public Surface {
310  public:
311  Geometry_type type() const override { return Geometry_type::kPolygon; }
312  bool accept(Geometry_visitor *v) override = 0;
313  bool is_empty() const override { return empty(); }
314 
315  /// Adds a linear ring to the polygon.
316  ///
317  /// The first ring will become the exterior ring. All following rings will be
318  /// interior rings (holes).
319  ///
320  /// @param lr The linear ring to add.
321  virtual void push_back(const Linearring &lr) = 0;
322  virtual void push_back(Linearring &&lr) = 0;
323 
324  /// Checks if the polygon is empty.
325  ///
326  /// The polygon is considered empty if it has no rings.
327  ///
328  /// @retval true The polygon is empty.
329  /// @retval false The polygon is not empty.
330  virtual bool empty() const = 0;
331 
332  /// Returns the size of the polygon.
333  ///
334  /// @return Number of rings in the polygon (exterior + interior).
335  virtual std::size_t size() const = 0;
336 
337  /// Returns the exterior ring of the polygon.
338  ///
339  /// @note If the polygon currently has no exterior ring, an empty one is
340  /// added.
341  ///
342  /// @return The exterior ring.
343  virtual Linearring &exterior_ring() = 0;
344 
345  /// Returns an interior ring of the polygon.
346  ///
347  /// @param n Ring number, zero indexed.
348  ///
349  /// @return The interior ring.
350  virtual Linearring &interior_ring(std::size_t n) = 0;
351 };
352 
353 /// A collection of geometries.
354 ///
355 /// Geometrycollection is an instantiable type in SQL. It is the only
356 /// instantiable non-leaf geometry type.
357 ///
358 /// The Geometrycollection class places no restrictions on type, overlapping,
359 /// etc. Subclasses do.
360 class Geometrycollection : public Geometry {
361  public:
362  Geometry_type type() const override {
364  }
365  bool accept(Geometry_visitor *v) override = 0;
366 
367  /// Adds a geometry to the collection.
368  ///
369  /// @param g The geometry to add.
370  virtual void push_back(const Geometry &g) = 0;
371  virtual void push_back(Geometry &&g) = 0;
372 
373  /// Checks if the collection is empty.
374  ///
375  /// @retval true The polygon is empty.
376  /// @retval false The polygon is not empty.
377  virtual bool empty() const = 0;
378 
379  /// Returns the size of the geometrycollection.
380  ///
381  /// @return Number of geometries in the geometrycollection.
382  virtual std::size_t size() const = 0;
383 
384  /// Resizes the geometrycollection to contain a given number of elements.
385  ///
386  /// If the new size is smaller than the current size, the remaining geometries
387  /// are discarded.
388  ///
389  /// @param[in] count The new number of geometries.
390  virtual void resize(std::size_t count) = 0;
391 
392  /// Removes all geometries from the geometrycollection.
393  virtual void clear() noexcept = 0;
394 
395  virtual Geometry &operator[](std::size_t i) = 0;
396  virtual const Geometry &operator[](std::size_t i) const = 0;
397 };
398 
399 /// A collection of points.
400 ///
401 /// Multipoint is an instantiable type in SQL.
403  public:
404  Geometry_type type() const override { return Geometry_type::kMultipoint; }
405 
406  bool accept(Geometry_visitor *v) override = 0;
407 };
408 
409 /// An abstract collection of curves.
410 ///
411 /// Multicurve is a non-instantiable type in SQL.
413  public:
414  Geometry_type type() const override = 0;
415  bool accept(Geometry_visitor *v) override = 0;
416 };
417 
418 /// A colletion of linestrings.
419 ///
420 /// Multilinestring is an instantiable type in SQL.
421 class Multilinestring : public Multicurve {
422  public:
423  Geometry_type type() const override {
425  }
426  bool accept(Geometry_visitor *v) override = 0;
427 };
428 
429 /// An abstract collection of surfaces.
430 ///
431 /// Multisurface is a non-instantiable type in SQL.
433  public:
434  Geometry_type type() const override = 0;
435  bool accept(Geometry_visitor *v) override = 0;
436 };
437 
438 /// A collection of polygons.
439 ///
440 /// Multipolygon is an instantiable type in SQL.
441 class Multipolygon : public Multisurface {
442  public:
443  Geometry_type type() const override { return Geometry_type::kMultipolygon; }
444  bool accept(Geometry_visitor *v) override = 0;
445 };
446 
447 /// Get the type name string corresponding to a geometry type.
448 ///
449 /// @param type The geometry type.
450 ///
451 /// @return A string containing the type name (in uppercase).
452 const char *type_to_name(Geometry_type type);
453 
454 } // namespace gis
455 
456 #endif // SQL_GIS_GEOMETRIES_H_INCLUDED
gis::Multicurve::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Linestring::size
virtual std::size_t size() const =0
Returns the size of (number of points in) the linestring.
gis::type_to_name
const char * type_to_name(Geometry_type type)
Get the type name string corresponding to a geometry type.
Definition: geometries.cc:629
gis::Polygon::exterior_ring
virtual Linearring & exterior_ring()=0
Returns the exterior ring of the polygon.
gis::Geometry_type::kMultilinestring
@ kMultilinestring
gis::Multilinestring
A colletion of linestrings.
Definition: geometries.h:421
gis::operator<
bool operator<(const Point &lhs, const Point &rhs)
Compares two points.
Definition: geometries.h:226
gis::Linearring
A ring-shaped linestring.
Definition: geometries.h:287
gis::Geometry_type::kMultipolygon
@ kMultipolygon
gis::Multipolygon::type
Geometry_type type() const override
Gets the geometry type of the object.
Definition: geometries.h:443
gis::Ring_direction
Ring_direction
Direction of a ring.
Definition: geometries.h:77
gis::Polygon::push_back
virtual void push_back(const Linearring &lr)=0
Adds a linear ring to the polygon.
gis::Point::get
double get() const
Gets a coordinate value.
gis::Geometry_type
Geometry_type
Types of geometry objects.
Definition: geometries.h:52
gis::Polygon::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis
Definition: area.cc:45
gis::Multisurface::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Ring_direction::kUnknown
@ kUnknown
Unknown.
gis::Multilinestring::type
Geometry_type type() const override
Gets the geometry type of the object.
Definition: geometries.h:423
gis::Point::m_x
double m_x
First coordinate (X or longitude).
Definition: geometries.h:206
gis::Multipoint::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Linestring::empty
virtual bool empty() const =0
Checks if the linestring is empty.
gis::Point::y
double y() const
Gets the second coordinate value.
Definition: geometries.cc:47
gis::Point::Point
Point(double x, double y)
Definition: geometries.h:148
gis::Geometry_type::kGeometrycollection
@ kGeometrycollection
gis::Multicurve::type
Geometry_type type() const override=0
Gets the geometry type of the object.
gis::Point::x
double x() const
Gets the first coordinate value.
Definition: geometries.cc:45
gis::Point::is_empty
bool is_empty() const override
Check if this is an empty geometry.
Definition: geometries.h:151
gis::Geometry_type::kPoint
@ kPoint
gis::Geometrycollection::push_back
virtual void push_back(Geometry &&g)=0
gis::Geometry_type::kMultipoint
@ kMultipoint
gis::Geometry
Abstract superclass for all geometric objects.
Definition: geometries.h:99
gis::Geometrycollection::empty
virtual bool empty() const =0
Checks if the collection is empty.
n
int n
Definition: xcom_base.cc:445
gis::Linestring
A string of connected line segments.
Definition: geometries.h:247
gis::Curve
An abstract 2d curve.
Definition: geometries.h:233
gis::Coordinate_system
Coordinate_system
Types of coordinate systems.
Definition: geometries.h:68
gis::Multipolygon
A collection of polygons.
Definition: geometries.h:441
gis::Geometry::is_empty
virtual bool is_empty() const =0
Check if this is an empty geometry.
gis::Coordinate_system::kCartesian
@ kCartesian
A Cartesian plane with the same unit in both directions.
gis::Polygon::is_empty
bool is_empty() const override
Check if this is an empty geometry.
Definition: geometries.h:313
gis::Geometry_type::kLinestring
@ kLinestring
gis::Geometry::type
virtual Geometry_type type() const =0
Gets the geometry type of the object.
gis::Polygon::type
Geometry_type type() const override
Gets the geometry type of the object.
Definition: geometries.h:311
gis::Linestring::push_back
virtual void push_back(Point &&pt)=0
gis::Linearring::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Point::set
void set(double d)
Sets a coordinate.
gis::Surface::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Multisurface
An abstract collection of surfaces.
Definition: geometries.h:432
gis::Polygon::push_back
virtual void push_back(Linearring &&lr)=0
gis::Linestring::type
Geometry_type type() const override
Gets the geometry type of the object.
Definition: geometries.h:249
gis::Geometry_type::kPolygon
@ kPolygon
gis::Geometry::~Geometry
virtual ~Geometry()=default
gis::Point::type
Geometry_type type() const override
Gets the geometry type of the object.
Definition: geometries.h:149
gis::Polygon::size
virtual std::size_t size() const =0
Returns the size of the polygon.
gis::Geometry_visitor
Abstract visitor class to be used on class Geometry and descendants.
Definition: geometry_visitor.h:45
gis::Multilinestring::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Geometrycollection::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Surface
An abstract 2d surface.
Definition: geometries.h:295
gis::Curve::type
Geometry_type type() const override=0
Gets the geometry type of the object.
gis::Point::m_y
double m_y
Second coordinate (Y or latitude).
Definition: geometries.h:212
gis::Geometrycollection::type
Geometry_type type() const override
Gets the geometry type of the object.
Definition: geometries.h:362
gis::Geometrycollection
A collection of geometries.
Definition: geometries.h:360
gis::Geometry_type::kGeometry
@ kGeometry
gis::Geometry::Geometry
Geometry(const Geometry &)=default
gis::Geometry::operator=
Geometry & operator=(const Geometry &)=default
gis::Polygon::interior_ring
virtual Linearring & interior_ring(std::size_t n)=0
Returns an interior ring of the polygon.
gis::Point
A 2d point.
Definition: geometries.h:145
gis::Multipoint
A collection of points.
Definition: geometries.h:402
gis::Ring_direction::kCW
@ kCW
Clockwise.
gis::Multipoint::type
Geometry_type type() const override
Gets the geometry type of the object.
Definition: geometries.h:404
gis::Point::Point
Point()
Definition: geometries.h:147
gis::Polygon::empty
virtual bool empty() const =0
Checks if the polygon is empty.
std
Definition: varlen_sort.h:182
gis::Geometrycollection::push_back
virtual void push_back(const Geometry &g)=0
Adds a geometry to the collection.
count
ssize_t count
Definition: memcached.c:386
gis::Point::accept
bool accept(Geometry_visitor *v) override
Applies a hierarchical visitor to this geometry.
Definition: geometries.cc:33
gis::Multisurface::type
Geometry_type type() const override=0
Gets the geometry type of the object.
gis::Curve::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Linestring::is_empty
bool is_empty() const override
Check if this is an empty geometry.
Definition: geometries.h:251
gis::Surface::type
Geometry_type type() const override=0
Gets the geometry type of the object.
gis::Geometrycollection::clear
virtual void clear() noexcept=0
Removes all geometries from the geometrycollection.
gis::Linestring::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Geometry::accept
virtual bool accept(Geometry_visitor *v)=0
Applies a hierarchical visitor to this geometry.
gis::Coordinate_system::kGeographic
@ kGeographic
An ellipsoidal system with longitude and latitude coordinates, both in the same unit.
gis::Polygon
A polygon consisting of an outer ring and zero or more interior rings defining holes in the polygon.
Definition: geometries.h:309
gis::Multicurve
An abstract collection of curves.
Definition: geometries.h:412
gis::Geometrycollection::size
virtual std::size_t size() const =0
Returns the size of the geometrycollection.
gis::Multipolygon::accept
bool accept(Geometry_visitor *v) override=0
Applies a hierarchical visitor to this geometry.
gis::Geometrycollection::resize
virtual void resize(std::size_t count)=0
Resizes the geometrycollection to contain a given number of elements.
gis::Ring_direction::kCCW
@ kCCW
Counterclockwise.
gis::Linestring::clear
virtual void clear() noexcept=0
Removes all points from the linestring.
gis::Geometry::coordinate_system
virtual Coordinate_system coordinate_system() const =0
Gets the coordinate system.
gis::Geometry::Geometry
Geometry()=default
gis::Linestring::push_back
virtual void push_back(const Point &pt)=0
Adds a point to the end of the linestring.