[Commits] Rev 3603: ST_Convexhull implemented. in file:///home/hf/wmar/5.3-gis/

holyfoot at askmonty.org holyfoot at askmonty.org
Thu Nov 22 08:30:38 EET 2012


At file:///home/hf/wmar/5.3-gis/

------------------------------------------------------------
revno: 3603
revision-id: holyfoot at askmonty.org-20121122062302-xxa1uxurik07unjd
parent: knielsen at knielsen-hq.org-20121120125749-l55gvliervi5nnaf
committer: Alexey Botchkov <holyfoot at askmonty.org>
branch nick: 5.3-gis
timestamp: Thu 2012-11-22 10:23:02 +0400
message:
  ST_Convexhull implemented.
-------------- next part --------------
=== modified file 'mysql-test/r/gis-precise.result'
--- a/mysql-test/r/gis-precise.result	2012-05-03 08:14:40 +0000
+++ b/mysql-test/r/gis-precise.result	2012-11-22 06:23:02 +0000
@@ -200,6 +200,21 @@ result
 SELECT ST_Equals(PointFromText('POINT (12 13)'),PointFromText('POINT (12 13)')) as result;
 result
 1
+select astext(st_convexhull(point(0,0)));
+astext(st_convexhull(point(0,0)))
+POINT(0 0)
+select astext(st_convexhull(GeomFromText('GeometryCollection EMPTY')));
+astext(st_convexhull(GeomFromText('GeometryCollection EMPTY')))
+GEOMETRYCOLLECTION EMPTY
+select astext(st_convexhull(GeomFromText('POLYGON((0 0, 0 1, 1 0, 0 0))')));
+astext(st_convexhull(GeomFromText('POLYGON((0 0, 0 1, 1 0, 0 0))')))
+POLYGON((0 0,0 1,1 0,0 0))
+select astext(st_convexhull(GeomFromText('POLYGON((10 0, 7 3, 10 6, 0 14, 10 16, 15 15, 12 10, 14 7, 10 0))')));
+astext(st_convexhull(GeomFromText('POLYGON((10 0, 7 3, 10 6, 0 14, 10 16, 15 15, 12 10, 14 7, 10 0))')))
+POLYGON((10 0,7 3,0 14,10 16,15 15,14 7,10 0))
+select astext(st_convexhull(GeomFromText('POLYGON((10 0, 7 3, 15 6, 0 14, 10 16, 15 15, 12 10, 14 7, 10 0))')));
+astext(st_convexhull(GeomFromText('POLYGON((10 0, 7 3, 15 6, 0 14, 10 16, 15 15, 12 10, 14 7, 10 0))')))
+POLYGON((10 0,7 3,0 14,10 16,15 15,15 6,10 0))
 SELECT astext(ST_UNION (
 PolyFromText('POLYGON(( 2 2 ,3 2,2 7,2 2),( 0 0,8 2,1 9,0 0))'),
 ExteriorRing( Envelope( MultiLineStringFromText('MULTILINESTRING((3 4,5 3),(3 0,0 5))')))));

=== modified file 'mysql-test/t/gis-precise.test'
--- a/mysql-test/t/gis-precise.test	2012-05-03 08:14:40 +0000
+++ b/mysql-test/t/gis-precise.test	2012-11-22 06:23:02 +0000
@@ -108,6 +108,13 @@ SELECT ST_Equals(PolyFromText('POLYGON((
 SELECT ST_Equals(PolyFromText('POLYGON((67 13, 67 18, 67 18, 59 18, 59 13, 67 13) )'),PolyFromText('POLYGON((67 13, 67 18, 59 18, 59 13, 59 13, 67 13) )')) as result;
 SELECT ST_Equals(PointFromText('POINT (12 13)'),PointFromText('POINT (12 13)')) as result;
 
+# ConvexHull test
+select astext(st_convexhull(point(0,0)));
+select astext(st_convexhull(GeomFromText('GeometryCollection EMPTY')));
+select astext(st_convexhull(GeomFromText('POLYGON((0 0, 0 1, 1 0, 0 0))')));
+select astext(st_convexhull(GeomFromText('POLYGON((10 0, 7 3, 10 6, 0 14, 10 16, 15 15, 12 10, 14 7, 10 0))')));
+select astext(st_convexhull(GeomFromText('POLYGON((10 0, 7 3, 15 6, 0 14, 10 16, 15 15, 12 10, 14 7, 10 0))')));
+
 # bug #801243 Assertion `(0)' failed in Gis_geometry_collection::init_from_opresult on ST_UNION
 
 SELECT astext(ST_UNION (

=== modified file 'sql/gcalc_slicescan.h'
--- a/sql/gcalc_slicescan.h	2011-12-08 12:29:45 +0000
+++ b/sql/gcalc_slicescan.h	2012-11-22 06:23:02 +0000
@@ -406,8 +406,8 @@ class Gcalc_scan_iterator : public Gcalc
 #endif /*GCALC_CHECK_WITH_FLOAT*/
   };
 
-  /* That class introduced mostly for the 'typecontrol' reason.      */
-  /* only difference from the point classis the get_next() function. */
+  /* That class introduced mostly for the 'typecontrol' reason.       */
+  /* Only difference from the point class is the get_next() function. */
   class event_point : public point
   {
   public:

=== modified file 'sql/item_create.cc'
--- a/sql/item_create.cc	2011-12-11 09:34:44 +0000
+++ b/sql/item_create.cc	2012-11-22 06:23:02 +0000
@@ -493,7 +493,20 @@ class Create_func_centroid : public Crea
   Create_func_centroid() {}
   virtual ~Create_func_centroid() {}
 };
-#endif
+
+
+class Create_func_convexhull : public Create_func_arg1
+{
+public:
+  virtual Item *create_1_arg(THD *thd, Item *arg1);
+
+  static Create_func_convexhull s_singleton;
+
+protected:
+  Create_func_convexhull() {}
+  virtual ~Create_func_convexhull() {}
+};
+#endif /*HAVE_SPATIAL*/
 
 
 class Create_func_char_length : public Create_func_arg1
@@ -3028,7 +3041,16 @@ Create_func_centroid::create_1_arg(THD *
 {
   return new (thd->mem_root) Item_func_centroid(arg1);
 }
-#endif
+
+
+Create_func_convexhull Create_func_convexhull::s_singleton;
+
+Item*
+Create_func_convexhull::create_1_arg(THD *thd, Item *arg1)
+{
+  return new (thd->mem_root) Item_func_convexhull(arg1);
+}
+#endif /*HAVE_SPATIAL*/
 
 
 Create_func_char_length Create_func_char_length::s_singleton;
@@ -5279,6 +5301,7 @@ static Native_func_registry func_array[]
   { { C_STRING_WITH_LEN("ST_BUFFER") }, GEOM_BUILDER(Create_func_buffer)},
   { { C_STRING_WITH_LEN("ST_CENTROID") }, GEOM_BUILDER(Create_func_centroid)},
   { { C_STRING_WITH_LEN("ST_CONTAINS") }, GEOM_BUILDER(Create_func_contains)},
+  { { C_STRING_WITH_LEN("ST_CONVEXHULL") }, GEOM_BUILDER(Create_func_convexhull)},
   { { C_STRING_WITH_LEN("ST_CROSSES") }, GEOM_BUILDER(Create_func_crosses)},
   { { C_STRING_WITH_LEN("ST_DIFFERENCE") }, GEOM_BUILDER(Create_func_difference)},
   { { C_STRING_WITH_LEN("ST_DIMENSION") }, GEOM_BUILDER(Create_func_dimension)},

=== modified file 'sql/item_geofunc.cc'
--- a/sql/item_geofunc.cc	2012-08-31 14:50:45 +0000
+++ b/sql/item_geofunc.cc	2012-11-22 06:23:02 +0000
@@ -246,6 +246,164 @@ String *Item_func_centroid::val_str(Stri
 }
 
 
+int Item_func_convexhull::add_node_to_line(ch_node **p_cur, int dir,
+                                           const Gcalc_heap::Info *pi)
+{
+  ch_node *new_node= NULL;
+  ch_node *cur= *p_cur;
+
+  while (cur->prev)
+  {
+    int v_sign= Gcalc_scan_iterator::point::cmp_dx_dy(
+                  cur->prev->pi, cur->pi, cur->pi, pi);
+    if (v_sign*dir <0)
+      break;
+    /* The last node in the line should be */
+    /* replaced with the curren one.       */
+    if (new_node)
+      res_heap.free_item(new_node);
+    new_node= cur;
+    cur= cur->prev;
+  }
+  if (!new_node && !(new_node= new_ch_node()))
+    return 1;
+  cur->next= new_node;
+  new_node->prev= cur;
+  new_node->pi= pi;
+  *p_cur= new_node;
+  return 0;
+}
+
+
+String *Item_func_convexhull::val_str(String *str_value)
+{
+  Geometry_buffer buffer;
+  Geometry *geom= NULL;
+  MBR mbr;
+  const char *c_end;
+  Gcalc_operation_transporter trn(&func, &collector);
+  const Gcalc_scan_iterator::event_point *ev;
+  uint32 srid= 0;
+  ch_node *left_first, *left_cur, *right_first, *right_cur;
+  
+  DBUG_ENTER("Item_func_convexhull::val_str");
+  DBUG_ASSERT(fixed == 1);
+  String *swkb= args[0]->val_str(&tmp_value);
+
+  if ((null_value=
+       args[0]->null_value ||
+       !(geom= Geometry::construct(&buffer, swkb->ptr(), swkb->length()))))
+    return 0;
+  
+  geom->get_mbr(&mbr, &c_end);
+  collector.set_extent(mbr.xmin, mbr.xmax, mbr.ymin, mbr.ymax);
+  if ((null_value= geom->store_shapes(&trn)))
+  {
+    str_value= 0;
+    goto mem_error;
+  }
+
+  collector.prepare_operation();
+  scan_it.init(&collector);
+  scan_it.killed= (int *) &(current_thd->killed);
+
+  if (!scan_it.more_points())
+    goto build_result; /* An EMPTY GEOMETRY */
+
+  if (scan_it.step())
+    goto mem_error;
+
+  if (!scan_it.more_points())
+  {
+    /* Single point. */
+    if (res_receiver.single_point(scan_it.get_events()->pi->x,
+                                  scan_it.get_events()->pi->y))
+      goto mem_error;
+    goto build_result;
+  }
+
+  left_cur= left_first= new_ch_node();
+  right_cur= right_first= new_ch_node();
+  right_first->pi= left_first->pi= scan_it.get_events()->pi;
+
+  while (scan_it.more_points())
+  {
+    if (scan_it.step())
+      goto mem_error;
+    ev= scan_it.get_events();
+    
+    /* Skip the intersections-only events. */
+    while (ev->event == scev_intersection)
+    {
+      ev= ev->get_next();
+      if (!ev)
+        goto skip_point;
+    }
+
+    {
+      Gcalc_point_iterator pit(&scan_it);
+      if (!pit.point() || pit.point()->event)
+      {
+        /* Handle left part of the hull. */
+        if (add_node_to_line(&left_cur, 1, ev->pi))
+          goto mem_error;
+      }
+      else
+      {
+        /* Check the rightmost point */
+        for(; pit.point()->c_get_next(); ++pit)
+          ;
+        if (!pit.point()->event)
+          goto skip_point;
+
+        /* Handle right part of the hull. */
+        if (add_node_to_line(&right_cur, -1, ev->pi))
+          goto mem_error;
+      }
+    }
+
+skip_point:
+    ;
+  }
+
+  left_cur->next= 0;
+  right_first->prev= 0;
+  if (res_receiver.start_shape(Gcalc_function::shape_polygon))
+    goto mem_error;
+
+  while (left_first)
+  {
+    if (res_receiver.add_point(left_first->pi->x, left_first->pi->y))
+      goto mem_error;
+    left_first= left_first->get_next();
+  }
+  while (right_cur->prev)
+  {
+    if (res_receiver.add_point(right_cur->pi->x, right_cur->pi->y))
+      goto mem_error;
+    right_cur= right_cur->prev;
+  }
+  res_receiver.complete_shape();
+
+build_result:
+  str_value->set_charset(&my_charset_bin);
+  if (str_value->reserve(SRID_SIZE, 512))
+    goto mem_error;
+  str_value->length(0);
+  str_value->q_append(srid);
+
+  if (!Geometry::create_from_opresult(&buffer, str_value, res_receiver))
+    goto mem_error;
+
+mem_error:
+  collector.reset();
+  func.reset();
+  res_receiver.reset();
+  res_heap.reset();
+  DBUG_RETURN(str_value);
+}
+
+
 /*
   Spatial decomposition functions
 */

=== modified file 'sql/item_geofunc.h'
--- a/sql/item_geofunc.h	2011-11-20 08:30:43 +0000
+++ b/sql/item_geofunc.h	2012-11-22 06:23:02 +0000
@@ -102,6 +102,34 @@ class Item_func_centroid: public Item_ge
   Field::geometry_type get_geometry_type() const;
 };
 
+class Item_func_convexhull: public Item_geometry_func
+{
+  class ch_node: public Gcalc_dyn_list::Item
+  {
+  public:
+    const Gcalc_heap::Info *pi;
+    ch_node *prev;
+    Gcalc_dyn_list::Item *next;
+    ch_node *get_next() { return (ch_node *) next; }
+  };
+
+  Gcalc_heap collector;
+  Gcalc_function func;
+  Gcalc_dyn_list res_heap;
+
+  Gcalc_result_receiver res_receiver;
+  String tmp_value;
+  Gcalc_scan_iterator scan_it;
+  ch_node *new_ch_node() { return (ch_node *) res_heap.new_item(); }
+  int add_node_to_line(ch_node **p_cur, int dir, const Gcalc_heap::Info *pi);
+public:
+  Item_func_convexhull(Item *a): Item_geometry_func(a),
+    res_heap(8192, sizeof(ch_node))
+    {}
+  const char *func_name() const { return "st_convexhull"; }
+  String *val_str(String *);
+};
+
 class Item_func_envelope: public Item_geometry_func
 {
 public:



More information about the commits mailing list