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-1335 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 27 class Gis_read_stream; 28 29 #include "gcalc_tools.h" 30 31 const uint SRID_SIZE= 4; 32 const uint SIZEOF_STORED_DOUBLE= 8; 33 const uint POINT_DATA_SIZE= (SIZEOF_STORED_DOUBLE * 2); 34 const uint WKB_HEADER_SIZE= 1+4; 35 const uint32 GET_SIZE_ERROR= ((uint32) -1); 36 37 struct st_point_2d 38 { 39 double x; 40 double y; 41 }; 42 43 struct 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 57 struct 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 int contains(const MBR *mbr) 151 { 152 /* The following should be safe, even if we compare doubles */ 153 return ((mbr->xmin >= xmin) && (mbr->ymin >= ymin) && 154 (mbr->xmax <= xmax) && (mbr->ymax <= ymax)); 155 } 156 157 bool inner_point(double x, double y) const 158 { 159 /* The following should be safe, even if we compare doubles */ 160 return (xmin<x) && (xmax>x) && (ymin<y) && (ymax>y); 161 } 162 163 /** 164 The dimension maps to an integer as: 165 - Polygon -> 2 166 - Horizontal or vertical line -> 1 167 - Point -> 0 168 - Invalid MBR -> -1 169 */ 170 int dimension() const 171 { 172 int d= 0; 173 174 if (xmin > xmax) 175 return -1; 176 else if (xmin < xmax) 177 d++; 178 179 if (ymin > ymax) 180 return -1; 181 else if (ymin < ymax) 182 d++; 183 184 return d; 185 } 186 187 int overlaps(const MBR *mbr) 188 { 189 /* 190 overlaps() requires that some point inside *this is also inside 191 *mbr, and that both geometries and their intersection are of the 192 same dimension. 193 */ 194 int d = dimension(); 195 196 if (d != mbr->dimension() || d <= 0 || contains(mbr) || within(mbr)) 197 return 0; 198 199 MBR intersection(MY_MAX(xmin, mbr->xmin), MY_MAX(ymin, mbr->ymin), 200 MY_MIN(xmax, mbr->xmax), MY_MIN(ymax, mbr->ymax)); 201 202 return (d == intersection.dimension()); 203 } 204 205 int valid() const 206 { return xmin <= xmax && ymin <= ymax; } 207 }; 208 209 210 /***************************** Geometry *******************************/ 211 212 struct Geometry_buffer; 213 214 class Geometry 215 { 216 public: 217 Geometry() {} /* Remove gcc warning */ 218 virtual ~Geometry() {} /* Remove gcc warning */ 219 static void *operator new(size_t size, void *buffer) 220 { 221 return buffer; 222 } 223 224 static void operator delete(void *ptr, void *buffer) 225 {} 226 227 static void operator delete(void *buffer) 228 {} 229 230 static String bad_geometry_data; 231 232 enum wkbType 233 { 234 wkb_point= 1, 235 wkb_linestring= 2, 236 wkb_polygon= 3, 237 wkb_multipoint= 4, 238 wkb_multilinestring= 5, 239 wkb_multipolygon= 6, 240 wkb_geometrycollection= 7, 241 wkb_last=7 242 }; 243 enum wkbByteOrder 244 { 245 wkb_xdr= 0, /* Big Endian */ 246 wkb_ndr= 1 /* Little Endian */ 247 }; 248 enum geojson_errors 249 { 250 GEOJ_INCORRECT_GEOJSON= 1, 251 GEOJ_TOO_FEW_POINTS= 2, 252 GEOJ_POLYGON_NOT_CLOSED= 3, 253 GEOJ_DIMENSION_NOT_SUPPORTED= 4, 254 GEOJ_EMPTY_COORDINATES= 5, 255 }; 256 257 258 /** Callback which creates Geometry objects on top of a given placement. */ 259 typedef Geometry *(*create_geom_t)(char *); 260 261 class Class_info 262 { 263 public: 264 LEX_STRING m_name; 265 LEX_STRING m_geojson_name; 266 int m_type_id; 267 create_geom_t m_create_func; 268 Class_info(const char *name, const char *gejson_name, 269 int type_id, create_geom_t create_func); 270 }; 271 272 virtual const Class_info *get_class_info() const=0; 273 virtual uint32 get_data_size() const=0; 274 virtual bool init_from_wkt(Gis_read_stream *trs, String *wkb)=0; 275 /* returns the length of the wkb that was read */ 276 virtual uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, 277 String *res)=0; 278 virtual uint init_from_opresult(String *bin, 279 const char *opres, uint res_len) 280 { return init_from_wkb(opres + 4, UINT_MAX32, wkb_ndr, bin) + 4; } 281 virtual bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb) 282 { return true; } 283 284 virtual bool get_data_as_wkt(String *txt, const char **end) const=0; 285 virtual bool get_data_as_json(String *txt, uint max_dec_digits, 286 const char **end) const=0; 287 virtual bool get_mbr(MBR *mbr, const char **end) const=0; 288 virtual bool dimension(uint32 *dim, const char **end) const=0; 289 virtual int get_x(double *x) const { return -1; } 290 virtual int get_y(double *y) const { return -1; } 291 virtual int geom_length(double *len, const char **end) const { return -1; } 292 virtual int area(double *ar, const char **end) const { return -1;} 293 virtual int is_closed(int *closed) const { return -1; } 294 virtual int num_interior_ring(uint32 *n_int_rings) const { return -1; } 295 virtual int num_points(uint32 *n_points) const { return -1; } 296 virtual int num_geometries(uint32 *num) const { return -1; } 297 virtual int start_point(String *point) const { return -1; } 298 virtual int end_point(String *point) const { return -1; } 299 virtual int exterior_ring(String *ring) const { return -1; } 300 virtual int centroid(String *point) const { return -1; } 301 virtual int point_n(uint32 num, String *result) const { return -1; } 302 virtual int interior_ring_n(uint32 num, String *result) const { return -1; } 303 virtual int geometry_n(uint32 num, String *result) const { return -1; } 304 virtual int store_shapes(Gcalc_shape_transporter *trn) const=0; 305 306 public: 307 static Geometry *create_by_typeid(Geometry_buffer *buffer, int type_id); 308 309 static Geometry *construct(Geometry_buffer *buffer, 310 const char *data, uint32 data_len); 311 static Geometry *create_from_wkt(Geometry_buffer *buffer, 312 Gis_read_stream *trs, String *wkt, 313 bool init_stream=1); 314 static Geometry *create_from_wkb(Geometry_buffer *buffer, 315 const char *wkb, uint32 len, String *res); 316 static Geometry *create_from_json(Geometry_buffer *buffer, json_engine_t *je, 317 bool er_on_3D, String *res); 318 static Geometry *create_from_opresult(Geometry_buffer *g_buf, 319 String *res, Gcalc_result_receiver &rr); 320 int as_wkt(String *wkt, const char **end); 321 int as_json(String *wkt, uint max_dec_digits, const char **end); 322 int bbox_as_json(String *wkt); 323 324 inline void set_data_ptr(const char *data, uint32 data_len) 325 { 326 m_data= data; 327 m_data_end= data + data_len; 328 } 329 330 inline void shift_wkb_header() 331 { 332 m_data+= WKB_HEADER_SIZE; 333 } 334 335 const char *get_data_ptr() const 336 { 337 return m_data; 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); 344 protected: 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 394 class Gis_point: public Geometry 395 { 396 public: 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_xy_radian(double *x, double *y) const 419 { 420 if (!get_xy(x, y)) 421 { 422 *x= (*x)*M_PI/180; 423 *y= (*y)*M_PI/180; 424 return 0; 425 } 426 return 1; 427 } 428 429 int get_x(double *x) const 430 { 431 if (no_data(m_data, SIZEOF_STORED_DOUBLE)) 432 return 1; 433 float8get(*x, m_data); 434 return 0; 435 } 436 437 int get_y(double *y) const 438 { 439 const char *data= m_data; 440 if (no_data(data, SIZEOF_STORED_DOUBLE * 2)) return 1; 441 float8get(*y, data + SIZEOF_STORED_DOUBLE); 442 return 0; 443 } 444 445 int geom_length(double *len, const char **end) const; 446 int area(double *ar, const char **end) const; 447 bool dimension(uint32 *dim, const char **end) const 448 { 449 *dim= 0; 450 *end= 0; /* No default end */ 451 return 0; 452 } 453 int store_shapes(Gcalc_shape_transporter *trn) const; 454 const Class_info *get_class_info() const; 455 double calculate_haversine(const Geometry *g, const double sphere_radius, 456 int *error); 457 int spherical_distance_multipoints(Geometry *g, const double r, double *result, 458 int *error); 459 }; 460 461 462 /***************************** LineString *******************************/ 463 464 class Gis_line_string: public Geometry 465 { 466 public: 467 Gis_line_string() {} /* Remove gcc warning */ 468 virtual ~Gis_line_string() {} /* Remove gcc warning */ 469 uint32 get_data_size() const; 470 bool init_from_wkt(Gis_read_stream *trs, String *wkb); 471 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res); 472 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb); 473 bool get_data_as_wkt(String *txt, const char **end) const; 474 bool get_data_as_json(String *txt, uint max_dec_digits, 475 const char **end) const; 476 bool get_mbr(MBR *mbr, const char **end) const; 477 int geom_length(double *len, const char **end) const; 478 int area(double *ar, const char **end) const; 479 int is_closed(int *closed) const; 480 int num_points(uint32 *n_points) const; 481 int start_point(String *point) const; 482 int end_point(String *point) const; 483 int point_n(uint32 n, String *result) const; 484 bool dimension(uint32 *dim, const char **end) const 485 { 486 *dim= 1; 487 *end= 0; /* No default end */ 488 return 0; 489 } 490 int store_shapes(Gcalc_shape_transporter *trn) const; 491 const Class_info *get_class_info() const; 492 }; 493 494 495 /***************************** Polygon *******************************/ 496 497 class Gis_polygon: public Geometry 498 { 499 public: 500 Gis_polygon() {} /* Remove gcc warning */ 501 virtual ~Gis_polygon() {} /* Remove gcc warning */ 502 uint32 get_data_size() const; 503 bool init_from_wkt(Gis_read_stream *trs, String *wkb); 504 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res); 505 uint init_from_opresult(String *bin, const char *opres, uint res_len); 506 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb); 507 bool get_data_as_wkt(String *txt, const char **end) const; 508 bool get_data_as_json(String *txt, uint max_dec_digits, 509 const char **end) const; 510 bool get_mbr(MBR *mbr, const char **end) const; 511 int area(double *ar, const char **end) const; 512 int exterior_ring(String *result) const; 513 int num_interior_ring(uint32 *n_int_rings) const; 514 int interior_ring_n(uint32 num, String *result) const; 515 int centroid_xy(double *x, double *y) const; 516 int centroid(String *result) const; 517 bool dimension(uint32 *dim, const char **end) const 518 { 519 *dim= 2; 520 *end= 0; /* No default end */ 521 return 0; 522 } 523 int store_shapes(Gcalc_shape_transporter *trn) const; 524 const Class_info *get_class_info() const; 525 }; 526 527 528 /***************************** MultiPoint *******************************/ 529 530 class Gis_multi_point: public Geometry 531 { 532 // Maximum number of points in MultiPoint that can fit into String 533 static const uint32 max_n_points= 534 (uint32) (UINT_MAX32 - WKB_HEADER_SIZE - 4 /* n_points */) / 535 (WKB_HEADER_SIZE + POINT_DATA_SIZE); 536 public: 537 Gis_multi_point() {} /* Remove gcc warning */ 538 virtual ~Gis_multi_point() {} /* Remove gcc warning */ 539 uint32 get_data_size() const; 540 bool init_from_wkt(Gis_read_stream *trs, String *wkb); 541 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res); 542 uint init_from_opresult(String *bin, const char *opres, uint res_len); 543 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb); 544 bool get_data_as_wkt(String *txt, const char **end) const; 545 bool get_data_as_json(String *txt, uint max_dec_digits, 546 const char **end) const; 547 bool get_mbr(MBR *mbr, const char **end) const; 548 int num_geometries(uint32 *num) const; 549 int geometry_n(uint32 num, String *result) const; 550 bool dimension(uint32 *dim, const char **end) const 551 { 552 *dim= 0; 553 *end= 0; /* No default end */ 554 return 0; 555 } 556 int store_shapes(Gcalc_shape_transporter *trn) const; 557 const Class_info *get_class_info() const; 558 int spherical_distance_multipoints(Geometry *g, const double r, double *res, 559 int *error); 560 }; 561 562 563 /***************************** MultiLineString *******************************/ 564 565 class Gis_multi_line_string: public Geometry 566 { 567 public: 568 Gis_multi_line_string() {} /* Remove gcc warning */ 569 virtual ~Gis_multi_line_string() {} /* Remove gcc warning */ 570 uint32 get_data_size() const; 571 bool init_from_wkt(Gis_read_stream *trs, String *wkb); 572 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res); 573 uint init_from_opresult(String *bin, const char *opres, uint res_len); 574 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb); 575 bool get_data_as_wkt(String *txt, const char **end) const; 576 bool get_data_as_json(String *txt, uint max_dec_digits, 577 const char **end) const; 578 bool get_mbr(MBR *mbr, const char **end) const; 579 int num_geometries(uint32 *num) const; 580 int geometry_n(uint32 num, String *result) const; 581 int geom_length(double *len, const char **end) const; 582 int is_closed(int *closed) const; 583 bool dimension(uint32 *dim, const char **end) const 584 { 585 *dim= 1; 586 *end= 0; /* No default end */ 587 return 0; 588 } 589 int store_shapes(Gcalc_shape_transporter *trn) const; 590 const Class_info *get_class_info() const; 591 }; 592 593 594 /***************************** MultiPolygon *******************************/ 595 596 class Gis_multi_polygon: public Geometry 597 { 598 public: 599 Gis_multi_polygon() {} /* Remove gcc warning */ 600 virtual ~Gis_multi_polygon() {} /* Remove gcc warning */ 601 uint32 get_data_size() const; 602 bool init_from_wkt(Gis_read_stream *trs, String *wkb); 603 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res); 604 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb); 605 bool get_data_as_wkt(String *txt, const char **end) const; 606 bool get_data_as_json(String *txt, uint max_dec_digits, 607 const char **end) const; 608 bool get_mbr(MBR *mbr, const char **end) const; 609 int num_geometries(uint32 *num) const; 610 int geometry_n(uint32 num, String *result) const; 611 int area(double *ar, const char **end) const; 612 int centroid(String *result) const; 613 bool dimension(uint32 *dim, const char **end) const 614 { 615 *dim= 2; 616 *end= 0; /* No default end */ 617 return 0; 618 } 619 int store_shapes(Gcalc_shape_transporter *trn) const; 620 const Class_info *get_class_info() const; 621 uint init_from_opresult(String *bin, const char *opres, uint res_len); 622 }; 623 624 625 /*********************** GeometryCollection *******************************/ 626 627 class Gis_geometry_collection: public Geometry 628 { 629 public: 630 Gis_geometry_collection() {} /* Remove gcc warning */ 631 virtual ~Gis_geometry_collection() {} /* Remove gcc warning */ 632 uint32 get_data_size() const; 633 bool init_from_wkt(Gis_read_stream *trs, String *wkb); 634 uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res); 635 uint init_from_opresult(String *bin, const char *opres, uint res_len); 636 bool init_from_json(json_engine_t *je, bool er_on_3D, String *wkb); 637 bool get_data_as_wkt(String *txt, const char **end) const; 638 bool get_data_as_json(String *txt, uint max_dec_digits, 639 const char **end) const; 640 bool get_mbr(MBR *mbr, const char **end) const; 641 int area(double *ar, const char **end) const; 642 int geom_length(double *len, const char **end) const; 643 int num_geometries(uint32 *num) const; 644 int geometry_n(uint32 num, String *result) const; 645 bool dimension(uint32 *dim, const char **end) const; 646 int store_shapes(Gcalc_shape_transporter *trn) const; 647 const Class_info *get_class_info() const; 648 }; 649 650 struct Geometry_buffer : public 651 my_aligned_storage<sizeof(Gis_point), MY_ALIGNOF(Gis_point)> {}; 652 653 #endif /*HAVE_SPATIAL*/ 654 #endif 655