1/*
2 Copyright (c) 2002, 2013, Oracle and/or its affiliates.
3 Copyright (c) 2009, 2013, Monty Program Ab.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; version 2 of the License.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
17
18#ifndef _spatial_h
19#define _spatial_h
20
21#include "sql_string.h" /* String, LEX_STRING */
22#include <my_compiler.h>
23#include <json_lib.h>
24
25#ifdef HAVE_SPATIAL
26
27class Gis_read_stream;
28
29#include "gcalc_tools.h"
30
31const uint SRID_SIZE= 4;
32const uint SIZEOF_STORED_DOUBLE= 8;
33const uint POINT_DATA_SIZE= (SIZEOF_STORED_DOUBLE * 2);
34const uint WKB_HEADER_SIZE= 1+4;
35const uint32 GET_SIZE_ERROR= ((uint32) -1);
36
37struct st_point_2d
38{
39 double x;
40 double y;
41};
42
43struct st_linear_ring
44{
45 uint32 n_points;
46 st_point_2d points;
47};
48
49/***************************** MBR *******************************/
50
51
52/*
53 It's ok that a lot of the functions are inline as these are only used once
54 in MySQL
55*/
56
57struct MBR
58{
59 double xmin, ymin, xmax, ymax;
60
61 MBR()
62 {
63 xmin= ymin= DBL_MAX;
64 xmax= ymax= -DBL_MAX;
65 }
66
67 MBR(const double xmin_arg, const double ymin_arg,
68 const double xmax_arg, const double ymax_arg)
69 :xmin(xmin_arg), ymin(ymin_arg), xmax(xmax_arg), ymax(ymax_arg)
70 {}
71
72 MBR(const st_point_2d &min, const st_point_2d &max)
73 :xmin(min.x), ymin(min.y), xmax(max.x), ymax(max.y)
74 {}
75
76 MBR(const MBR &mbr1, const MBR &mbr2)
77 :xmin(mbr1.xmin), ymin(mbr1.ymin), xmax(mbr1.xmax), ymax(mbr1.ymax)
78 { add_mbr(&mbr2); }
79
80 inline void add_xy(double x, double y)
81 {
82 /* Not using "else" for proper one point MBR calculation */
83 if (x < xmin)
84 xmin= x;
85 if (x > xmax)
86 xmax= x;
87 if (y < ymin)
88 ymin= y;
89 if (y > ymax)
90 ymax= y;
91 }
92 void add_xy(const char *px, const char *py)
93 {
94 double x, y;
95 float8get(x, px);
96 float8get(y, py);
97 add_xy(x,y);
98 }
99 void add_mbr(const MBR *mbr)
100 {
101 if (mbr->xmin < xmin)
102 xmin= mbr->xmin;
103 if (mbr->xmax > xmax)
104 xmax= mbr->xmax;
105 if (mbr->ymin < ymin)
106 ymin= mbr->ymin;
107 if (mbr->ymax > ymax)
108 ymax= mbr->ymax;
109 }
110 void buffer(double d)
111 {
112 xmin-= d;
113 ymin-= d;
114 xmax+= d;
115 ymax+= d;
116 }
117
118 int equals(const MBR *mbr)
119 {
120 /* The following should be safe, even if we compare doubles */
121 return ((mbr->xmin == xmin) && (mbr->ymin == ymin) &&
122 (mbr->xmax == xmax) && (mbr->ymax == ymax));
123 }
124
125 int disjoint(const MBR *mbr)
126 {
127 /* The following should be safe, even if we compare doubles */
128 return ((mbr->xmin > xmax) || (mbr->ymin > ymax) ||
129 (mbr->xmax < xmin) || (mbr->ymax < ymin));
130 }
131
132 int intersects(const MBR *mbr)
133 {
134 return !disjoint(mbr);
135 }
136
137 int touches(const MBR *mbr)
138 {
139 /* The following should be safe, even if we compare doubles */
140 return ((mbr->xmin == xmax || mbr->xmax == xmin) &&
141 ((mbr->ymin >= ymin && mbr->ymin <= ymax) ||
142 (mbr->ymax >= ymin && mbr->ymax <= ymax))) ||
143 ((mbr->ymin == ymax || mbr->ymax == ymin) &&
144 ((mbr->xmin >= xmin && mbr->xmin <= xmax) ||
145 (mbr->xmax >= xmin && mbr->xmax <= xmax)));
146 }
147
148 int within(const MBR *mbr)
149 {
150 /* The following should be safe, even if we compare doubles */
151 return ((mbr->xmin <= xmin) && (mbr->ymin <= ymin) &&
152 (mbr->xmax >= xmax) && (mbr->ymax >= ymax));
153 }
154
155 int contains(const MBR *mbr)
156 {
157 /* The following should be safe, even if we compare doubles */
158 return ((mbr->xmin >= xmin) && (mbr->ymin >= ymin) &&
159 (mbr->xmax <= xmax) && (mbr->ymax <= ymax));
160 }
161
162 bool inner_point(double x, double y) const
163 {
164 /* The following should be safe, even if we compare doubles */
165 return (xmin<x) && (xmax>x) && (ymin<y) && (ymax>y);
166 }
167
168 /**
169 The dimension maps to an integer as:
170 - Polygon -> 2
171 - Horizontal or vertical line -> 1
172 - Point -> 0
173 - Invalid MBR -> -1
174 */
175 int dimension() const
176 {
177 int d= 0;
178
179 if (xmin > xmax)
180 return -1;
181 else if (xmin < xmax)
182 d++;
183
184 if (ymin > ymax)
185 return -1;
186 else if (ymin < ymax)
187 d++;
188
189 return d;
190 }
191
192 int overlaps(const MBR *mbr)
193 {
194 /*
195 overlaps() requires that some point inside *this is also inside
196 *mbr, and that both geometries and their intersection are of the
197 same dimension.
198 */
199 int d = dimension();
200
201 if (d != mbr->dimension() || d <= 0 || contains(mbr) || within(mbr))
202 return 0;
203
204 MBR intersection(MY_MAX(xmin, mbr->xmin), MY_MAX(ymin, mbr->ymin),
205 MY_MIN(xmax, mbr->xmax), MY_MIN(ymax, mbr->ymax));
206
207 return (d == intersection.dimension());
208 }
209
210 int valid() const
211 { return xmin <= xmax && ymin <= ymax; }
212};
213
214
215/***************************** Geometry *******************************/
216
217struct Geometry_buffer;
218
219class Geometry
220{
221public:
222 Geometry() {} /* Remove gcc warning */
223 virtual ~Geometry() {} /* Remove gcc warning */
224 static void *operator new(size_t size, void *buffer)
225 {
226 return buffer;
227 }
228
229 static void operator delete(void *ptr, void *buffer)
230 {}
231
232 static void operator delete(void *buffer)
233 {}
234
235 static String bad_geometry_data;
236
237 enum wkbType
238 {
239 wkb_point= 1,
240 wkb_linestring= 2,
241 wkb_polygon= 3,
242 wkb_multipoint= 4,
243 wkb_multilinestring= 5,
244 wkb_multipolygon= 6,
245 wkb_geometrycollection= 7,
246 wkb_last=7
247 };
248 enum wkbByteOrder
249 {
250 wkb_xdr= 0, /* Big Endian */
251 wkb_ndr= 1 /* Little Endian */
252 };
253 enum geojson_errors
254 {
255 GEOJ_INCORRECT_GEOJSON= 1,
256 GEOJ_TOO_FEW_POINTS= 2,
257 GEOJ_POLYGON_NOT_CLOSED= 3,
258 GEOJ_DIMENSION_NOT_SUPPORTED= 4,
259 GEOJ_EMPTY_COORDINATES= 5,
260 };
261
262
263 /** Callback which creates Geometry objects on top of a given placement. */
264 typedef Geometry *(*create_geom_t)(char *);
265
266 class Class_info
267 {
268 public:
269 LEX_STRING m_name;
270 LEX_STRING m_geojson_name;
271 int m_type_id;
272 create_geom_t m_create_func;
273 Class_info(const char *name, const char *gejson_name,
274 int type_id, create_geom_t create_func);
275 };
276
277 virtual const Class_info *get_class_info() const=0;
278 virtual uint32 get_data_size() const=0;
279 virtual bool init_from_wkt(Gis_read_stream *trs, String *wkb)=0;
280 /* returns the length of the wkb that was read */
281 virtual uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo,
282 String *res)=0;
283 virtual uint init_from_opresult(String *bin,
284 const char *opres, uint res_len)
285 { return init_from_wkb(opres + 4, UINT_MAX32, wkb_ndr, bin) + 4; }
286 virtual bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb)
287 { return true; }
288
289 virtual bool get_data_as_wkt(String *txt, const char **end) const=0;
290 virtual bool get_data_as_json(String *txt, uint max_dec_digits,
291 const char **end) const=0;
292 virtual bool get_mbr(MBR *mbr, const char **end) const=0;
293 virtual bool dimension(uint32 *dim, const char **end) const=0;
294 virtual int get_x(double *x) const { return -1; }
295 virtual int get_y(double *y) const { return -1; }
296 virtual int geom_length(double *len, const char **end) const { return -1; }
297 virtual int area(double *ar, const char **end) const { return -1;}
298 virtual int is_closed(int *closed) const { return -1; }
299 virtual int num_interior_ring(uint32 *n_int_rings) const { return -1; }
300 virtual int num_points(uint32 *n_points) const { return -1; }
301 virtual int num_geometries(uint32 *num) const { return -1; }
302 virtual int start_point(String *point) const { return -1; }
303 virtual int end_point(String *point) const { return -1; }
304 virtual int exterior_ring(String *ring) const { return -1; }
305 virtual int centroid(String *point) const { return -1; }
306 virtual int point_n(uint32 num, String *result) const { return -1; }
307 virtual int interior_ring_n(uint32 num, String *result) const { return -1; }
308 virtual int geometry_n(uint32 num, String *result) const { return -1; }
309 virtual int store_shapes(Gcalc_shape_transporter *trn) const=0;
310
311public:
312 static Geometry *create_by_typeid(Geometry_buffer *buffer, int type_id);
313
314 static Geometry *construct(Geometry_buffer *buffer,
315 const char *data, uint32 data_len);
316 static Geometry *create_from_wkt(Geometry_buffer *buffer,
317 Gis_read_stream *trs, String *wkt,
318 bool init_stream=1);
319 static Geometry *create_from_wkb(Geometry_buffer *buffer,
320 const char *wkb, uint32 len, String *res);
321 static Geometry *create_from_json(Geometry_buffer *buffer, json_engine_t *je,
322 bool er_on_3D, String *res);
323 static Geometry *create_from_opresult(Geometry_buffer *g_buf,
324 String *res, Gcalc_result_receiver &rr);
325 int as_wkt(String *wkt, const char **end);
326 int as_json(String *wkt, uint max_dec_digits, const char **end);
327 int bbox_as_json(String *wkt);
328
329 inline void set_data_ptr(const char *data, uint32 data_len)
330 {
331 m_data= data;
332 m_data_end= data + data_len;
333 }
334
335 inline void shift_wkb_header()
336 {
337 m_data+= WKB_HEADER_SIZE;
338 }
339
340 bool envelope(String *result) const;
341 static Class_info *ci_collection[wkb_last+1];
342
343 static bool create_point(String *result, double x, double y);
344protected:
345 static Class_info *find_class(int type_id)
346 {
347 return ((type_id < wkb_point) || (type_id > wkb_last)) ?
348 NULL : ci_collection[type_id];
349 }
350 static Class_info *find_class(const char *name, size_t len);
351 const char *append_points(String *txt, uint32 n_points,
352 const char *data, uint32 offset) const;
353 bool create_point(String *result, const char *data) const;
354 const char *get_mbr_for_points(MBR *mbr, const char *data, uint offset)
355 const;
356
357 /**
358 Check if there're enough data remaining as requested
359
360 @arg cur_data pointer to the position in the binary form
361 @arg data_amount number of points expected
362 @return true if not enough data
363 */
364 inline bool no_data(const char *cur_data, size_t data_amount) const
365 {
366 return (cur_data + data_amount > m_data_end);
367 }
368
369 /**
370 Check if there're enough points remaining as requested
371
372 Need to perform the calculation in logical units, since multiplication
373 can overflow the size data type.
374
375 @arg data pointer to the beginning of the points array
376 @arg expected_points number of points expected
377 @arg extra_point_space extra space for each point element in the array
378 @return true if there are not enough points
379 */
380 inline bool not_enough_points(const char *data, uint32 expected_points,
381 uint32 extra_point_space = 0) const
382 {
383 return (m_data_end < data ||
384 (expected_points > ((m_data_end - data) /
385 (POINT_DATA_SIZE + extra_point_space))));
386 }
387 const char *m_data;
388 const char *m_data_end;
389};
390
391
392/***************************** Point *******************************/
393
394class Gis_point: public Geometry
395{
396public:
397 Gis_point() {} /* Remove gcc warning */
398 virtual ~Gis_point() {} /* Remove gcc warning */
399 uint32 get_data_size() const;
400 bool init_from_wkt(Gis_read_stream *trs, String *wkb);
401 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
402 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb);
403 bool get_data_as_wkt(String *txt, const char **end) const;
404 bool get_data_as_json(String *txt, uint max_dec_digits,
405 const char **end) const;
406 bool get_mbr(MBR *mbr, const char **end) const;
407
408 int get_xy(double *x, double *y) const
409 {
410 const char *data= m_data;
411 if (no_data(data, SIZEOF_STORED_DOUBLE * 2))
412 return 1;
413 float8get(*x, data);
414 float8get(*y, data + SIZEOF_STORED_DOUBLE);
415 return 0;
416 }
417
418 int get_x(double *x) const
419 {
420 if (no_data(m_data, SIZEOF_STORED_DOUBLE))
421 return 1;
422 float8get(*x, m_data);
423 return 0;
424 }
425
426 int get_y(double *y) const
427 {
428 const char *data= m_data;
429 if (no_data(data, SIZEOF_STORED_DOUBLE * 2)) return 1;
430 float8get(*y, data + SIZEOF_STORED_DOUBLE);
431 return 0;
432 }
433
434 int geom_length(double *len, const char **end) const;
435 int area(double *ar, const char **end) const;
436 bool dimension(uint32 *dim, const char **end) const
437 {
438 *dim= 0;
439 *end= 0; /* No default end */
440 return 0;
441 }
442 int store_shapes(Gcalc_shape_transporter *trn) const;
443 const Class_info *get_class_info() const;
444};
445
446
447/***************************** LineString *******************************/
448
449class Gis_line_string: public Geometry
450{
451public:
452 Gis_line_string() {} /* Remove gcc warning */
453 virtual ~Gis_line_string() {} /* Remove gcc warning */
454 uint32 get_data_size() const;
455 bool init_from_wkt(Gis_read_stream *trs, String *wkb);
456 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
457 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb);
458 bool get_data_as_wkt(String *txt, const char **end) const;
459 bool get_data_as_json(String *txt, uint max_dec_digits,
460 const char **end) const;
461 bool get_mbr(MBR *mbr, const char **end) const;
462 int geom_length(double *len, const char **end) const;
463 int area(double *ar, const char **end) const;
464 int is_closed(int *closed) const;
465 int num_points(uint32 *n_points) const;
466 int start_point(String *point) const;
467 int end_point(String *point) const;
468 int point_n(uint32 n, String *result) const;
469 bool dimension(uint32 *dim, const char **end) const
470 {
471 *dim= 1;
472 *end= 0; /* No default end */
473 return 0;
474 }
475 int store_shapes(Gcalc_shape_transporter *trn) const;
476 const Class_info *get_class_info() const;
477};
478
479
480/***************************** Polygon *******************************/
481
482class Gis_polygon: public Geometry
483{
484public:
485 Gis_polygon() {} /* Remove gcc warning */
486 virtual ~Gis_polygon() {} /* Remove gcc warning */
487 uint32 get_data_size() const;
488 bool init_from_wkt(Gis_read_stream *trs, String *wkb);
489 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
490 uint init_from_opresult(String *bin, const char *opres, uint res_len);
491 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb);
492 bool get_data_as_wkt(String *txt, const char **end) const;
493 bool get_data_as_json(String *txt, uint max_dec_digits,
494 const char **end) const;
495 bool get_mbr(MBR *mbr, const char **end) const;
496 int area(double *ar, const char **end) const;
497 int exterior_ring(String *result) const;
498 int num_interior_ring(uint32 *n_int_rings) const;
499 int interior_ring_n(uint32 num, String *result) const;
500 int centroid_xy(double *x, double *y) const;
501 int centroid(String *result) const;
502 bool dimension(uint32 *dim, const char **end) const
503 {
504 *dim= 2;
505 *end= 0; /* No default end */
506 return 0;
507 }
508 int store_shapes(Gcalc_shape_transporter *trn) const;
509 const Class_info *get_class_info() const;
510};
511
512
513/***************************** MultiPoint *******************************/
514
515class Gis_multi_point: public Geometry
516{
517 // Maximum number of points in MultiPoint that can fit into String
518 static const uint32 max_n_points=
519 (uint32) (UINT_MAX32 - WKB_HEADER_SIZE - 4 /* n_points */) /
520 (WKB_HEADER_SIZE + POINT_DATA_SIZE);
521public:
522 Gis_multi_point() {} /* Remove gcc warning */
523 virtual ~Gis_multi_point() {} /* Remove gcc warning */
524 uint32 get_data_size() const;
525 bool init_from_wkt(Gis_read_stream *trs, String *wkb);
526 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
527 uint init_from_opresult(String *bin, const char *opres, uint res_len);
528 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb);
529 bool get_data_as_wkt(String *txt, const char **end) const;
530 bool get_data_as_json(String *txt, uint max_dec_digits,
531 const char **end) const;
532 bool get_mbr(MBR *mbr, const char **end) const;
533 int num_geometries(uint32 *num) const;
534 int geometry_n(uint32 num, String *result) const;
535 bool dimension(uint32 *dim, const char **end) const
536 {
537 *dim= 0;
538 *end= 0; /* No default end */
539 return 0;
540 }
541 int store_shapes(Gcalc_shape_transporter *trn) const;
542 const Class_info *get_class_info() const;
543};
544
545
546/***************************** MultiLineString *******************************/
547
548class Gis_multi_line_string: public Geometry
549{
550public:
551 Gis_multi_line_string() {} /* Remove gcc warning */
552 virtual ~Gis_multi_line_string() {} /* Remove gcc warning */
553 uint32 get_data_size() const;
554 bool init_from_wkt(Gis_read_stream *trs, String *wkb);
555 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
556 uint init_from_opresult(String *bin, const char *opres, uint res_len);
557 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb);
558 bool get_data_as_wkt(String *txt, const char **end) const;
559 bool get_data_as_json(String *txt, uint max_dec_digits,
560 const char **end) const;
561 bool get_mbr(MBR *mbr, const char **end) const;
562 int num_geometries(uint32 *num) const;
563 int geometry_n(uint32 num, String *result) const;
564 int geom_length(double *len, const char **end) const;
565 int is_closed(int *closed) const;
566 bool dimension(uint32 *dim, const char **end) const
567 {
568 *dim= 1;
569 *end= 0; /* No default end */
570 return 0;
571 }
572 int store_shapes(Gcalc_shape_transporter *trn) const;
573 const Class_info *get_class_info() const;
574};
575
576
577/***************************** MultiPolygon *******************************/
578
579class Gis_multi_polygon: public Geometry
580{
581public:
582 Gis_multi_polygon() {} /* Remove gcc warning */
583 virtual ~Gis_multi_polygon() {} /* Remove gcc warning */
584 uint32 get_data_size() const;
585 bool init_from_wkt(Gis_read_stream *trs, String *wkb);
586 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
587 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb);
588 bool get_data_as_wkt(String *txt, const char **end) const;
589 bool get_data_as_json(String *txt, uint max_dec_digits,
590 const char **end) const;
591 bool get_mbr(MBR *mbr, const char **end) const;
592 int num_geometries(uint32 *num) const;
593 int geometry_n(uint32 num, String *result) const;
594 int area(double *ar, const char **end) const;
595 int centroid(String *result) const;
596 bool dimension(uint32 *dim, const char **end) const
597 {
598 *dim= 2;
599 *end= 0; /* No default end */
600 return 0;
601 }
602 int store_shapes(Gcalc_shape_transporter *trn) const;
603 const Class_info *get_class_info() const;
604 uint init_from_opresult(String *bin, const char *opres, uint res_len);
605};
606
607
608/*********************** GeometryCollection *******************************/
609
610class Gis_geometry_collection: public Geometry
611{
612public:
613 Gis_geometry_collection() {} /* Remove gcc warning */
614 virtual ~Gis_geometry_collection() {} /* Remove gcc warning */
615 uint32 get_data_size() const;
616 bool init_from_wkt(Gis_read_stream *trs, String *wkb);
617 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
618 uint init_from_opresult(String *bin, const char *opres, uint res_len);
619 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb);
620 bool get_data_as_wkt(String *txt, const char **end) const;
621 bool get_data_as_json(String *txt, uint max_dec_digits,
622 const char **end) const;
623 bool get_mbr(MBR *mbr, const char **end) const;
624 int area(double *ar, const char **end) const;
625 int geom_length(double *len, const char **end) const;
626 int num_geometries(uint32 *num) const;
627 int geometry_n(uint32 num, String *result) const;
628 bool dimension(uint32 *dim, const char **end) const;
629 int store_shapes(Gcalc_shape_transporter *trn) const;
630 const Class_info *get_class_info() const;
631};
632
633struct Geometry_buffer : public
634 my_aligned_storage<sizeof(Gis_point), MY_ALIGNOF(Gis_point)> {};
635
636#endif /*HAVE_SPATIAL*/
637#endif
638