spatial.h

/* Copyright (c) 2002, 2013, Oracle and/or its affiliates. All rights reserved.

   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; version 2 of the License.

   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,
   51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */

#ifndef _spatial_h
#define _spatial_h

#include "sql_string.h"                         /* String, LEX_STRING */
#include <my_compiler.h>

#ifdef HAVE_SPATIAL

#include <algorithm>

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);

   
/**
  Point with coordinates X and Y.
*/ 
class point_xy
{
public:
  double x;
  double y;
  point_xy() { }
  point_xy(double x_arg, double y_arg): x(x_arg), y(y_arg) { } 
  /**
    Distance to another point.
  */
  double distance(point_xy p)
  {
    return sqrt(pow(x - p.x, 2) + pow(y - p.y, 2));
  }
  /**
    Compare to another point.
    Return true if equal, false if not equal.
  */
  bool eq(point_xy p)
  {  
    return (x == p.x) && (y == p.y);
  }
};

typedef struct wkb_header_st
{
  uchar byte_order;
  uint32 wkb_type;
} wkb_header;


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


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

struct MBR
{
  double xmin, ymin, xmax, ymax;

  MBR()
  {
    xmin= ymin= DBL_MAX;
    xmax= ymax= -DBL_MAX;
  }

  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)
  {}

  MBR(const point_xy &min, const point_xy &max)
    :xmin(min.x), ymin(min.y), xmax(max.x), ymax(max.y)
  {}
 
  inline void add_xy(double x, double y)
  {
    /* Not using "else" for proper one point MBR calculation */
    if (x < xmin)
      xmin= x;
    if (x > xmax)
      xmax= x;
    if (y < ymin)
      ymin= y;
    if (y > ymax)
      ymax= y;
  }
  void add_xy(point_xy p)
  {
    add_xy(p.x, p.y);
  }
  void add_xy(const char *px, const char *py)
  {
    double x, y;
    float8get(x, px);
    float8get(y, py);
    add_xy(x,y);
  }
  void add_mbr(const MBR *mbr)
  {
    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;
  }

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

  int disjoint(const MBR *mbr)
  {
    /* The following should be safe, even if we compare doubles */
    return ((mbr->xmin > xmax) || (mbr->ymin > ymax) ||
	    (mbr->xmax < xmin) || (mbr->ymax < ymin));
  }

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

  int touches(const MBR *mbr)
  {
    /* The following should be safe, even if we compare doubles */
    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)));
  }

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

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

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

  /**
    The dimension maps to an integer as:
    - Polygon -> 2
    - Horizontal or vertical line -> 1
    - Point -> 0
    - Invalid MBR -> -1
  */
  int dimension() const
  {
    int d= 0;

    if (xmin > xmax)
      return -1;
    else if (xmin < xmax)
      d++;

    if (ymin > ymax)
      return -1;
    else if (ymin < ymax)
      d++;

    return d;
  }

  int overlaps(const MBR *mbr)
  {
    /*
      overlaps() requires that some point inside *this is also inside
      *mbr, and that both geometries and their intersection are of the
      same dimension.
    */
    int d = dimension();

    if (d != mbr->dimension() || d <= 0 || contains(mbr) || within(mbr))
      return 0;

    using std::min;
    using std::max;
    MBR intersection(max(xmin, mbr->xmin), max(ymin, mbr->ymin),
                     min(xmax, mbr->xmax), min(ymax, mbr->ymax));

    return (d == intersection.dimension());
  }
};


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

struct Geometry_buffer;

class Geometry
{
public:
  Geometry() {}                               /* Remove gcc warning */
  virtual ~Geometry() {}                        /* Remove gcc warning */
  static void *operator new(size_t size, void *buffer)
  {
    return buffer;
  }

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

  static void operator delete(void *buffer)
  {}

  static String bad_geometry_data;

  enum wkbType
  {
    wkb_point= 1,
    wkb_linestring= 2,
    wkb_polygon= 3,
    wkb_multipoint= 4,
    wkb_multilinestring= 5,
    wkb_multipolygon= 6,
    wkb_geometrycollection= 7,
    wkb_last=7
  };
  enum wkbByteOrder
  {
    wkb_xdr= 0,    /* Big Endian */
    wkb_ndr= 1     /* Little Endian */
  };

  /**
    Constant storage for WKB.
    Encapsulation and the available methods make it impossible
    to update the members of wkb_container once it is initialized.
    The only allowed modification method is set(),
    which fully replaces the previous buffer.  
  */ 
  class wkb_container
  {  
  protected:
    const char *m_data;
    const char *m_data_end;
  public:
    wkb_container() { }
    wkb_container(const char *data, const char *data_end)
    {
      set(data, data_end);
    }
    void set(const char *data, const char *data_end)
    {
      m_data= data;
      m_data_end= data_end;
    }
    const char *data() const
    {
      return m_data;
    }
    const char *data_end() const
    {
      return m_data_end;
    }
    uint32 length() const
    {
      return (uint32) (m_data_end - m_data);   
    }
    /**
      Check if there's enough data remaining as requested.

      @arg data_amount  data requested

      @return           true if not enough data
    */
    inline bool no_data(size_t data_amount) const
    {
      return (m_data + data_amount > m_data_end);
    }

    /**
      Check if there're enough points remaining as requested.

      Need to perform the calculation in logical units, since multiplication
      can overflow the size data type.

      @arg expected_points   number of points expected
      @arg extra_point_space extra space for each point element in the array

      @return               true if there are not enough points
    */
    inline bool not_enough_points(uint32 expected_points,
                                  uint32 extra_point_space= 0) const
    {
      return (m_data_end < m_data ||
              expected_points > ((m_data_end - m_data) /
                                 (POINT_DATA_SIZE + extra_point_space)));
    }
  };

  /**
    WKB parser, designed to traverse through WKB data from
    beginning of the buffer towards the end using a set   
    of scan_xxx(), get_xxx() and skip_xxx() routines,
    with safety tests to avoid going beyond the buffer end.
  */
  class wkb_parser: public wkb_container
  {
    /* Low level routines to get data of various types */
    void get_uint4(uint32 *number)
    {
      *number= uint4korr(m_data); //GIS-TODO: byte order
    }
    void get_float8(double *x)
    {
      float8get(*x, m_data);      //GIS-TODO: byte order
    }
  public:
    wkb_parser(const char *data, const char *data_end):
      wkb_container(data, data_end) { }
    wkb_parser(const wkb_container *container):
      wkb_container(*container) { }

    /* Routines to skip non-interesting data */
    void skip_unsafe(size_t nbytes)
    {
      DBUG_ASSERT(!no_data(nbytes));
      m_data+= nbytes;
    }
    bool skip(size_t nbytes)
    {
      if (no_data(nbytes))
        return true;
      m_data+= nbytes;
      return false;   
    }
    bool skip_wkb_header()
    {
      return skip(WKB_HEADER_SIZE);
    }
    bool skip_coord()
    {
      return skip(SIZEOF_STORED_DOUBLE);
    }

    /* Routines to scan wkb header information */
    bool scan_wkb_header(wkb_header *header)
    {
      if (no_data(WKB_HEADER_SIZE))
        return true;
      header->byte_order= (uchar) (*m_data);
      m_data++;
      get_uint4(&header->wkb_type);
      m_data+= 4;
      return false;
    }

    /* Routines to scan uint4 information */
    bool scan_uint4(uint32 *number)
    {
      if (no_data(4))
        return true; 
      get_uint4(number);
      m_data+= 4;
      return false;
    }
    bool scan_non_zero_uint4(uint32 *number)
    {
      return (scan_uint4(number) || 0 == *number);
    }
    bool scan_n_points_and_check_data(uint32 *n_points,
                                      uint32 extra_point_space= 0)
    {
      return scan_non_zero_uint4(n_points) ||
             not_enough_points(*n_points, extra_point_space);
    }

    /* Routines to scan coordinate information */
    void scan_xy_unsafe(point_xy *p)
    {
      DBUG_ASSERT(!no_data(POINT_DATA_SIZE));
      get_float8(&p->x);
      m_data+= SIZEOF_STORED_DOUBLE;
      get_float8(&p->y);
      m_data+= SIZEOF_STORED_DOUBLE;
    }
    bool scan_xy(point_xy *p)
    {
     if (no_data(SIZEOF_STORED_DOUBLE * 2))
        return true;
      scan_xy_unsafe(p);
      return false;
    }
    bool scan_coord(double *x)
    {
      if (no_data(SIZEOF_STORED_DOUBLE))
        return true;
      get_float8(x);
      m_data+= SIZEOF_STORED_DOUBLE;
      return false;
    }
  }; 

  /** Callback which creates Geometry objects on top of a given placement. */
  typedef Geometry *(*create_geom_t)(char *);

  class Class_info
  {
  public:
    LEX_STRING m_name;
    int m_type_id;
    create_geom_t m_create_func;
    Class_info(const char *name, int type_id, create_geom_t create_func);
  };

  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;
  /* returns the length of the wkb that was read */
  virtual uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo,
                             String *res)=0;
  virtual uint init_from_opresult(String *bin,
                                  const char *opres, uint opres_length)
  { return init_from_wkb(opres + 4, UINT_MAX32, wkb_ndr, bin) + 4; }

  virtual bool get_data_as_wkt(String *txt, wkb_parser *wkb) const=0;
  virtual bool get_mbr(MBR *mbr, wkb_parser *wkb) const=0;
  bool get_mbr(MBR *mbr)
  {
    wkb_parser wkb(&m_wkb_data);
    return get_mbr(mbr, &wkb);
  }
  virtual bool dimension(uint32 *dim, wkb_parser *wkb) const
  {
    *dim= feature_dimension();
    uint32 length;
    if ((length= get_data_size()) == GET_SIZE_ERROR)
      return true;
    wkb->skip(length);
    return false;   
  }
  bool dimension(uint32 *dim)
  {  
    wkb_parser wkb(&m_wkb_data);
    return dimension(dim, &wkb);
  }
  virtual uint32 feature_dimension() const= 0;
  virtual int get_x(double *x) const { return -1; }
  virtual int get_y(double *y) const { return -1; }
  virtual int geom_length(double *len) const  { return -1; }
  /**
    Calculate area of a Geometry.
    This default implementation returns 0 for the types that have zero area:
    Point, LineString, MultiPoint, MultiLineString.
    The over geometry types (Polygon, MultiPolygon, GeometryCollection)
    override the default method.
  */
  virtual bool area(double *ar, wkb_parser *wkb) const
  {
    uint32 data_size= get_data_size();
    if (data_size == GET_SIZE_ERROR || wkb->no_data(data_size))
      return true;
    wkb->skip_unsafe(data_size);
    *ar= 0;
    return false;
  }
  bool area(double *ar) const
  {
    wkb_parser wkb(&m_wkb_data);
    return area(ar, &wkb);
  }
  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; }

public:
  static Geometry *construct(Geometry_buffer *buffer,
                             const char *data, uint32 data_len);
  static Geometry *construct(Geometry_buffer *buffer, const String *str)
  {
    return construct(buffer, str->ptr(), str->length());
  }
  bool as_wkt(String *wkt, wkb_parser *wkb)
  {
    uint32 len= (uint) get_class_info()->m_name.length;
    if (wkt->reserve(len + 2, 512))
      return true;
    wkt->qs_append(get_class_info()->m_name.str, len);
    wkt->qs_append('(');
    if (get_data_as_wkt(wkt, wkb))
      return true;
    wkt->qs_append(')');
    return false;
  }
  bool as_wkt(String *wkt)
  {
    wkb_parser wkb(&m_wkb_data);
    return as_wkt(wkt, &wkb);   
  }

  inline void set_data_ptr(const char *data, uint32 data_len)
  {
    m_wkb_data.set(data, data + data_len);
  }

  inline void set_data_ptr(const wkb_container *wkb)
  {
    m_wkb_data= *wkb;
  }

  bool envelope(String *result) const;
  static Class_info *ci_collection[wkb_last+1];

protected:
  static Class_info *find_class(int type_id)
  {
    return ((type_id < wkb_point) || (type_id > wkb_last)) ?
      NULL : ci_collection[type_id];
  }  
  static Class_info *find_class(const char *name, uint32 len);
  void append_points(String *txt, uint32 n_points,
                     wkb_parser *wkb, uint32 offset) const;
  bool create_point(String *result, wkb_parser *wkb) const; 
  bool create_point(String *result, point_xy p) const;
  bool get_mbr_for_points(MBR *mbr, wkb_parser *wkb, uint offset) const;
  wkb_container m_wkb_data;
};


/***************************** Point *******************************/
 
class Gis_point: public Geometry
{
public:
  Gis_point() {}                              /* Remove gcc warning */
  virtual ~Gis_point() {}                     /* Remove gcc warning */
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
  bool get_data_as_wkt(String *txt, wkb_parser *wkb) const; 
  bool get_mbr(MBR *mbr, wkb_parser *wkb) const;

  int get_xy(point_xy *p) const
  {
    wkb_parser wkb(&m_wkb_data);
    return wkb.scan_xy(p);
  }
  int get_x(double *x) const
  {
    wkb_parser wkb(&m_wkb_data);
    return wkb.scan_coord(x);
  }
  int get_y(double *y) const
  {
    wkb_parser wkb(&m_wkb_data);
    return wkb.skip_coord() || wkb.scan_coord(y);
  }
  uint32 feature_dimension() const { return 0; }
  const Class_info *get_class_info() const;
};


/***************************** LineString *******************************/

class Gis_line_string: public Geometry
{
  // Maximum number of points in LineString that can fit into String
  static const uint32 max_n_points=
    (uint32) (UINT_MAX32 - WKB_HEADER_SIZE - 4 /* n_points */) /
    POINT_DATA_SIZE;
public:
  Gis_line_string() {}                        /* Remove gcc warning */
  virtual ~Gis_line_string() {}               /* Remove gcc warning */
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
  bool get_data_as_wkt(String *txt, wkb_parser *wkb) const;
  bool get_mbr(MBR *mbr, wkb_parser *wkb) const;
  int geom_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;
  uint32 feature_dimension() const { return 1; }
  const Class_info *get_class_info() const;
};


/***************************** Polygon *******************************/

class Gis_polygon: public Geometry
{
public:
  Gis_polygon() {}                            /* Remove gcc warning */
  virtual ~Gis_polygon() {}                   /* Remove gcc warning */
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
  uint init_from_opresult(String *bin, const char *opres, uint opres_length);
  bool get_data_as_wkt(String *txt, wkb_parser *wkb) const;
  bool get_mbr(MBR *mbr, wkb_parser *wkb) const;
  bool area(double *ar, wkb_parser *wkb) 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;
  bool centroid_xy(point_xy *p) const;
  int centroid(String *result) const;
  uint32 feature_dimension() const { return 2; }
  const Class_info *get_class_info() const;
};


/***************************** MultiPoint *******************************/

class Gis_multi_point: public Geometry
{
  // Maximum number of points in MultiPoint that can fit into String
  static const uint32 max_n_points=
    (uint32) (UINT_MAX32 - WKB_HEADER_SIZE - 4 /* n_points */) /
    (WKB_HEADER_SIZE + POINT_DATA_SIZE);
public:
  Gis_multi_point() {}                        /* Remove gcc warning */
  virtual ~Gis_multi_point() {}               /* Remove gcc warning */
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
  uint init_from_opresult(String *bin, const char *opres, uint opres_length);
  bool get_data_as_wkt(String *txt, wkb_parser *wkb) const;
  bool get_mbr(MBR *mbr, wkb_parser *wkb) const;
  int num_geometries(uint32 *num) const;
  int geometry_n(uint32 num, String *result) const;
  uint32 feature_dimension() const { return 0; }
  const Class_info *get_class_info() const;
};


/***************************** MultiLineString *******************************/

class Gis_multi_line_string: public Geometry
{
public:
  Gis_multi_line_string() {}                  /* Remove gcc warning */
  virtual ~Gis_multi_line_string() {}         /* Remove gcc warning */
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
  uint init_from_opresult(String *bin, const char *opres, uint opres_length);
  bool get_data_as_wkt(String *txt, wkb_parser *wkb) const;
  bool get_mbr(MBR *mbr, wkb_parser *wkb) const;
  int num_geometries(uint32 *num) const;
  int geometry_n(uint32 num, String *result) const;
  int geom_length(double *len) const;
  int is_closed(int *closed) const;
  uint32 feature_dimension() const { return 1; }
  const Class_info *get_class_info() const;
};


/***************************** MultiPolygon *******************************/

class Gis_multi_polygon: public Geometry
{
public:
  Gis_multi_polygon() {}                      /* Remove gcc warning */
  virtual ~Gis_multi_polygon() {}             /* Remove gcc warning */
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
  bool get_data_as_wkt(String *txt, wkb_parser *wkb) const;
  bool get_mbr(MBR *mbr, wkb_parser *wkb) const;
  int num_geometries(uint32 *num) const;
  int geometry_n(uint32 num, String *result) const;
  bool area(double *ar, wkb_parser *wkb) const;
  int centroid(String *result) const;
  uint32 feature_dimension() const { return 2; }
  const Class_info *get_class_info() const;
  uint init_from_opresult(String *bin, const char *opres, uint opres_length);
};


/*********************** GeometryCollection *******************************/

class Gis_geometry_collection: public Geometry
{
public:
  Gis_geometry_collection() {}                /* Remove gcc warning */
  virtual ~Gis_geometry_collection() {}       /* Remove gcc warning */
  uint32 get_data_size() const;
  bool init_from_wkt(Gis_read_stream *trs, String *wkb);
  uint init_from_wkb(const char *wkb, uint len, wkbByteOrder bo, String *res);
  uint init_from_opresult(String *bin, const char *opres, uint opres_length);
  bool get_data_as_wkt(String *txt, wkb_parser *wkb) const;
  bool get_mbr(MBR *mbr, wkb_parser *wkb) const;
  bool area(double *ar, wkb_parser *wkb) const; 
  int num_geometries(uint32 *num) const;
  int geometry_n(uint32 num, String *result) const;
  bool dimension(uint32 *dim, wkb_parser *wkb) const; 
  uint32 feature_dimension() const
  {
    DBUG_ASSERT(0);
    return 0;
  }
  const Class_info *get_class_info() const;
};

struct Geometry_buffer : public
  my_aligned_storage<sizeof(Gis_point), MY_ALIGNOF(Gis_point)> {};

#endif /*HAVE_SPATAIAL*/
#endif