spatial.h 15.1 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

17 18 19
#ifndef _spatial_h
#define _spatial_h

20 21
#ifdef HAVE_SPATIAL

22 23 24 25 26
const uint SRID_SIZE= 4;
const uint SIZEOF_STORED_DOUBLE= 8;
const uint POINT_DATA_SIZE= SIZEOF_STORED_DOUBLE*2; 
const uint WKB_HEADER_SIZE= 1+4;
const uint32 GET_SIZE_ERROR= ((uint32) -1);
27

28
struct st_point_2d
29 30 31 32 33
{
  double x;
  double y;
};

34
struct st_linear_ring
35
{
36 37
  uint32 n_points;
  st_point_2d points;
38 39 40 41
};

/***************************** MBR *******************************/

42 43 44 45 46 47

/*
  It's ok that a lot of the functions are inline as these are only used once
  in MySQL
*/

48 49
struct MBR
{
50 51
  double xmin, ymin, xmax, ymax;

52 53
  MBR()
  {
54 55
    xmin= ymin= DBL_MAX;
    xmax= ymax= -DBL_MAX;
56 57
  }

58 59 60 61
  MBR(const double xmin_arg, const double ymin_arg,
      const double xmax_arg, const double ymax_arg)
    :xmin(xmin_arg), ymin(ymin_arg), xmax(xmax_arg), ymax(ymax_arg)
  {}
62

63 64 65 66 67
  MBR(const st_point_2d &min, const st_point_2d &max)
    :xmin(min.x), ymin(min.y), xmax(max.x), ymax(max.y)
  {}
 
  inline void add_xy(double x, double y)
68 69
  {
    /* Not using "else" for proper one point MBR calculation */
70 71 72 73 74 75 76 77
    if (x < xmin)
      xmin= x;
    if (x > xmax)
      xmax= x;
    if (y < ymin)
      ymin= y;
    if (y > ymax)
      ymax= y;
78
  }
ram@ram.(none)'s avatar
ram@ram.(none) committed
79
  void add_xy(const char *px, const char *py)
80
  {
81 82 83
    double x, y;
    float8get(x, px);
    float8get(y, py);
84
    add_xy(x,y);
85 86 87
  }
  void add_mbr(const MBR *mbr)
  {
88 89 90 91 92 93 94 95
    if (mbr->xmin < xmin)
      xmin= mbr->xmin;
    if (mbr->xmax > xmax)
      xmax= mbr->xmax;
    if (mbr->ymin < ymin)
      ymin= mbr->ymin;
    if (mbr->ymax > ymax)
      ymax= mbr->ymax;
96 97 98 99
  }

  int equals(const MBR *mbr)
  {
100
    /* The following should be safe, even if we compare doubles */
101 102
    return ((mbr->xmin == xmin) && (mbr->ymin == ymin) &&
	    (mbr->xmax == xmax) && (mbr->ymax == ymax));
103 104 105 106
  }

  int disjoint(const MBR *mbr)
  {
107
    /* The following should be safe, even if we compare doubles */
108 109
    return ((mbr->xmin > xmax) || (mbr->ymin > ymax) ||
	    (mbr->xmax < xmin) || (mbr->ymax < ymin));
110 111 112 113 114 115 116 117 118
  }

  int intersects(const MBR *mbr)
  {
    return !disjoint(mbr);
  }

  int touches(const MBR *mbr)
  {
119
    /* The following should be safe, even if we compare doubles */
120 121 122 123 124 125
    return ((((mbr->xmin == xmax) || (mbr->xmax == xmin)) && 
	     ((mbr->ymin >= ymin) && (mbr->ymin <= ymax) || 
	      (mbr->ymax >= ymin) && (mbr->ymax <= ymax))) ||
	    (((mbr->ymin == ymax) || (mbr->ymax == ymin)) &&
	     ((mbr->xmin >= xmin) && (mbr->xmin <= xmax) ||
	      (mbr->xmax >= xmin) && (mbr->xmax <= xmax))));
126 127 128 129
  }

  int within(const MBR *mbr)
  {
130
    /* The following should be safe, even if we compare doubles */
131 132
    return ((mbr->xmin <= xmin) && (mbr->ymin <= ymin) &&
	    (mbr->xmax >= xmax) && (mbr->ymax >= ymax));
133 134 135 136
  }

  int contains(const MBR *mbr)
  {
137
    /* The following should be safe, even if we compare doubles */
138 139
    return ((mbr->xmin >= xmin) && (mbr->ymin >= ymin) &&
	    (mbr->xmax <= xmax) && (mbr->ymax <= ymax));
140 141 142 143
  }

  bool inner_point(double x, double y) const
  {
144
    /* The following should be safe, even if we compare doubles */
145
    return (xmin<x) && (xmax>x) && (ymin<y) && (ymax>y);
146 147 148 149
  }

  int overlaps(const MBR *mbr)
  {
150 151 152 153
    int lb= mbr->inner_point(xmin, ymin);
    int rb= mbr->inner_point(xmax, ymin);
    int rt= mbr->inner_point(xmax, ymax);
    int lt= mbr->inner_point(xmin, ymax);
154

155
    int a = lb+rb+rt+lt;
156 157 158 159 160 161 162
    return (a>0) && (a<4) && (!within(mbr));
  }
};


/***************************** Geometry *******************************/

163
struct Geometry_buffer;
164 165 166 167

class Geometry
{
public:
168 169
  Geometry() {}                               /* Remove gcc warning */
  virtual ~Geometry() {}                        /* Remove gcc warning */
hf@deer.(none)'s avatar
hf@deer.(none) committed
170
  static void *operator new(size_t size, void *buffer)
171 172 173 174
  {
    return buffer;
  }

175 176 177
  static void operator delete(void *ptr, void *buffer)
  {}

monty@mysql.com's avatar
monty@mysql.com committed
178 179 180
  static void operator delete(void *buffer)
  {}

181 182
  static String bad_geometry_data;

183 184
  enum wkbType
  {
185 186 187 188 189 190 191 192
    wkb_point= 1,
    wkb_linestring= 2,
    wkb_polygon= 3,
    wkb_multipoint= 4,
    wkb_multilinestring= 5,
    wkb_multipolygon= 6,
    wkb_geometrycollection= 7,
    wkb_end=7
193 194 195
  };
  enum wkbByteOrder
  {
196 197
    wkb_xdr= 0,    /* Big Endian */
    wkb_ndr= 1     /* Little Endian */
198 199
  };                                    

200
  class Class_info
201 202
  {
  public:
203
    LEX_STRING m_name;
204
    int m_type_id;
205 206
    void (*m_create_func)(void *);
    Class_info(const char *name, int type_id, void(*create_func)(void *));
207 208
  };

209 210 211
  virtual const Class_info *get_class_info() const=0;
  virtual uint32 get_data_size() const=0;
  virtual bool init_from_wkt(Gis_read_stream *trs, String *wkb)=0;
212 213 214 215

  /* returns the length of the wkb that was read */
  virtual uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo,
                             String *res)=0;
216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233
  virtual bool get_data_as_wkt(String *txt, const char **end) const=0;
  virtual bool get_mbr(MBR *mbr, const char **end) const=0;
  virtual bool dimension(uint32 *dim, const char **end) const=0;
  virtual int get_x(double *x) const { return -1; }
  virtual int get_y(double *y) const { return -1; }
  virtual int length(double *len) const  { return -1; }
  virtual int area(double *ar, const char **end) const { return -1;}
  virtual int is_closed(int *closed) const { return -1; }
  virtual int num_interior_ring(uint32 *n_int_rings) const { return -1; }
  virtual int num_points(uint32 *n_points) const { return -1; }
  virtual int num_geometries(uint32 *num) const { return -1; }
  virtual int start_point(String *point) const { return -1; }
  virtual int end_point(String *point) const { return -1; }
  virtual int exterior_ring(String *ring) const { return -1; }
  virtual int centroid(String *point) const { return -1; }
  virtual int point_n(uint32 num, String *result) const { return -1; }
  virtual int interior_ring_n(uint32 num, String *result) const { return -1; }
  virtual int geometry_n(uint32 num, String *result) const { return -1; }
234 235

public:
monty@mysql.com's avatar
monty@mysql.com committed
236
  static Geometry *create_by_typeid(Geometry_buffer *buffer, int type_id)
237 238 239 240 241
  {
    Class_info *ci;
    if (!(ci= find_class((int) type_id)))
      return NULL;
    (*ci->m_create_func)((void *)buffer);
242
    return my_reinterpret_cast(Geometry *)(buffer);
243
  }
244

245 246
  static Geometry *construct(Geometry_buffer *buffer,
                             const char *data, uint32 data_len);
247 248 249
  static Geometry *create_from_wkt(Geometry_buffer *buffer,
				   Gis_read_stream *trs, String *wkt,
				   bool init_stream=1);
250 251
  static int create_from_wkb(Geometry_buffer *buffer,
                             const char *wkb, uint32 len, String *res);
252
  int as_wkt(String *wkt, const char **end)
253
  {
254 255
    uint32 len= get_class_info()->m_name.length;
    if (wkt->reserve(len + 2, 512))
256
      return 1;
257
    wkt->qs_append(get_class_info()->m_name.str, len);
258
    wkt->qs_append('(');
259
    if (get_data_as_wkt(wkt, end))
260 261 262 263 264
      return 1;
    wkt->qs_append(')');
    return 0;
  }

265
  inline void set_data_ptr(const char *data, uint32 data_len)
266
  {
267 268
    m_data= data;
    m_data_end= data + data_len;
269 270
  }

271
  inline void shift_wkb_header()
272
  {
273
    m_data+= WKB_HEADER_SIZE;
274 275
  }

276
  bool envelope(String *result) const;
monty@mysql.com's avatar
monty@mysql.com committed
277
  static Class_info *ci_collection[wkb_end+1];
278 279

protected:
280 281 282 283 284 285
  static Class_info *find_class(int type_id)
  {
    return ((type_id < wkb_point) || (type_id > wkb_end)) ?
      NULL : ci_collection[type_id];
  }  
  static Class_info *find_class(const char *name, uint32 len);
286
  const char *append_points(String *txt, uint32 n_points,
287 288 289
			    const char *data, uint32 offset) const;
  bool create_point(String *result, const char *data) const;
  bool create_point(String *result, double x, double y) const;
290 291 292 293
  const char *get_mbr_for_points(MBR *mbr, const char *data, uint offset)
    const;

  inline bool no_data(const char *cur_data, uint32 data_amount) const
294
  {
295
    return (cur_data + data_amount > m_data_end);
296 297 298 299 300
  }
  const char *m_data;
  const char *m_data_end;
};

301

302 303
/***************************** Point *******************************/
 
304
class Gis_point: public Geometry
305 306
{
public:
307 308
  Gis_point() {}                              /* Remove gcc warning */
  virtual ~Gis_point() {}                     /* Remove gcc warning */
309 310
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
311
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
312 313
  bool get_data_as_wkt(String *txt, const char **end) const;
  bool get_mbr(MBR *mbr, const char **end) const;
314
  
315
  int get_xy(double *x, double *y) const
316
  {
317 318 319
    const char *data= m_data;
    if (no_data(data, SIZEOF_STORED_DOUBLE * 2))
      return 1;
320
    float8get(*x, data);
321
    float8get(*y, data + SIZEOF_STORED_DOUBLE);
322 323 324
    return 0;
  }

325
  int get_x(double *x) const
326
  {
327 328
    if (no_data(m_data, SIZEOF_STORED_DOUBLE))
      return 1;
329 330 331 332
    float8get(*x, m_data);
    return 0;
  }

333
  int get_y(double *y) const
334
  {
335
    const char *data= m_data;
336 337
    if (no_data(data, SIZEOF_STORED_DOUBLE * 2)) return 1;
    float8get(*y, data + SIZEOF_STORED_DOUBLE);
338 339 340
    return 0;
  }

341 342 343 344 345 346
  bool dimension(uint32 *dim, const char **end) const
  {
    *dim= 0;
    *end= 0;					/* No default end */
    return 0;
  }
347
  const Class_info *get_class_info() const;
348 349
};

350

351 352
/***************************** LineString *******************************/

353
class Gis_line_string: public Geometry
354 355
{
public:
356 357
  Gis_line_string() {}                        /* Remove gcc warning */
  virtual ~Gis_line_string() {}               /* Remove gcc warning */
358 359
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
360
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
361
  bool get_data_as_wkt(String *txt, const char **end) const;
362
  bool get_mbr(MBR *mbr, const char **end) const;
363 364 365 366 367 368
  int length(double *len) const;
  int is_closed(int *closed) const;
  int num_points(uint32 *n_points) const;
  int start_point(String *point) const;
  int end_point(String *point) const;
  int point_n(uint32 n, String *result) const;
369 370 371 372 373 374
  bool dimension(uint32 *dim, const char **end) const
  {
    *dim= 1;
    *end= 0;					/* No default end */
    return 0;
  }
375
  const Class_info *get_class_info() const;
376 377
};

378

379 380
/***************************** Polygon *******************************/

381
class Gis_polygon: public Geometry
382 383
{
public:
384 385
  Gis_polygon() {}                            /* Remove gcc warning */
  virtual ~Gis_polygon() {}                   /* Remove gcc warning */
386 387
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
388
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
389
  bool get_data_as_wkt(String *txt, const char **end) const;
390
  bool get_mbr(MBR *mbr, const char **end) const;
391 392 393 394 395 396
  int area(double *ar, const char **end) const;
  int exterior_ring(String *result) const;
  int num_interior_ring(uint32 *n_int_rings) const;
  int interior_ring_n(uint32 num, String *result) const;
  int centroid_xy(double *x, double *y) const;
  int centroid(String *result) const;
397 398 399 400 401 402
  bool dimension(uint32 *dim, const char **end) const
  {
    *dim= 2;
    *end= 0;					/* No default end */
    return 0;
  }
403
  const Class_info *get_class_info() const;
404 405
};

406

407 408
/***************************** MultiPoint *******************************/

409
class Gis_multi_point: public Geometry
410 411
{
public:
412 413
  Gis_multi_point() {}                        /* Remove gcc warning */
  virtual ~Gis_multi_point() {}               /* Remove gcc warning */
414 415
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
416
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
417
  bool get_data_as_wkt(String *txt, const char **end) const;
418
  bool get_mbr(MBR *mbr, const char **end) const;
419 420
  int num_geometries(uint32 *num) const;
  int geometry_n(uint32 num, String *result) const;
421 422 423 424 425 426
  bool dimension(uint32 *dim, const char **end) const
  {
    *dim= 0;
    *end= 0;					/* No default end */
    return 0;
  }
427
  const Class_info *get_class_info() const;
428 429
};

430

431 432
/***************************** MultiLineString *******************************/

433
class Gis_multi_line_string: public Geometry
434 435
{
public:
436 437
  Gis_multi_line_string() {}                  /* Remove gcc warning */
  virtual ~Gis_multi_line_string() {}         /* Remove gcc warning */
438 439
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
440
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
441
  bool get_data_as_wkt(String *txt, const char **end) const;
442
  bool get_mbr(MBR *mbr, const char **end) const;
443 444 445 446
  int num_geometries(uint32 *num) const;
  int geometry_n(uint32 num, String *result) const;
  int length(double *len) const;
  int is_closed(int *closed) const;
447 448 449 450 451 452
  bool dimension(uint32 *dim, const char **end) const
  {
    *dim= 1;
    *end= 0;					/* No default end */
    return 0;
  }
453
  const Class_info *get_class_info() const;
454 455
};

456

457 458
/***************************** MultiPolygon *******************************/

459
class Gis_multi_polygon: public Geometry
460 461
{
public:
462 463
  Gis_multi_polygon() {}                      /* Remove gcc warning */
  virtual ~Gis_multi_polygon() {}             /* Remove gcc warning */
464 465
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
466
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
467
  bool get_data_as_wkt(String *txt, const char **end) const;
468
  bool get_mbr(MBR *mbr, const char **end) const;
469 470 471 472
  int num_geometries(uint32 *num) const;
  int geometry_n(uint32 num, String *result) const;
  int area(double *ar, const char **end) const;
  int centroid(String *result) const;
473 474 475 476 477 478
  bool dimension(uint32 *dim, const char **end) const
  {
    *dim= 2;
    *end= 0;					/* No default end */
    return 0;
  }
479
  const Class_info *get_class_info() const;
480 481 482
};


483 484 485
/*********************** GeometryCollection *******************************/

class Gis_geometry_collection: public Geometry
486 487
{
public:
488 489
  Gis_geometry_collection() {}                /* Remove gcc warning */
  virtual ~Gis_geometry_collection() {}       /* Remove gcc warning */
490 491
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
492
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
493
  bool get_data_as_wkt(String *txt, const char **end) const;
494
  bool get_mbr(MBR *mbr, const char **end) const;
495 496
  int num_geometries(uint32 *num) const;
  int geometry_n(uint32 num, String *result) const;
497
  bool dimension(uint32 *dim, const char **end) const;
498 499 500 501 502 503 504
  const Class_info *get_class_info() const;
};

const int geometry_buffer_size= sizeof(Gis_point);
struct Geometry_buffer
{
  void *arr[(geometry_buffer_size - 1)/sizeof(void *) + 1];
505 506
};

507
#endif /*HAVE_SPATAIAL*/
508
#endif