GIS code.

Forward calculations introduced.

per-file comments:
  sql/gcalc_slicescan.cc
  sql/gcalc_slicescan.h
  sql/gcalc_tools.cc
  sql/gcalc_tools.h
  sql/item_geofunc.cc

5 files changed, 1038 insertions, 1042 deletions

diff --git a/sql/gcalc_slicescan.cc b/sql/gcalc_slicescan.cc
index 10c64aa5d08..6e32baab8de 100644
--- a/sql/gcalc_slicescan.cc
+++ b/sql/gcalc_slicescan.cc
@@ -40,6 +40,20 @@ typedef int (*sc_compare_func)(const void*, const void*);
 #include "plistsort.c"
 
 
+static Gcalc_scan_iterator::point *eq_sp(const Gcalc_heap::Info *pi)
+{
+  GCALC_DBUG_ASSERT(pi->type == Gcalc_heap::nt_eq_node);
+  return (Gcalc_scan_iterator::point *) pi->eq_data;
+}
+
+
+static Gcalc_scan_iterator::intersection_info *i_data(const Gcalc_heap::Info *pi)
+{
+  GCALC_DBUG_ASSERT(pi->type == Gcalc_heap::nt_intersection);
+  return (Gcalc_scan_iterator::intersection_info *) pi->intersection_data;
+}
+
+
 #ifndef GCALC_DBUG_OFF
 
 int gcalc_step_counter= 0;
@@ -80,53 +94,101 @@ const char *gcalc_ev_name(int ev)
 }
 
 
+static int gcalc_pi_str(char *str, const Gcalc_heap::Info *pi, const char *postfix)
+{
+  return sprintf(str, "%s %d %d | %s %d %d%s",
+                     pi->ix.sign ? "-":"", pi->ix.digits[0],pi->ix.digits[1],
+                     pi->iy.sign ? "-":"", pi->iy.digits[0],pi->iy.digits[1],
+                     postfix);
+
+}
+
+
+static void GCALC_DBUG_PRINT_PI(const Gcalc_heap::Info *pi)
+{
+  char buf[128];
+  int n_buf;
+  if (pi->type == Gcalc_heap::nt_intersection)
+  {
+    const Gcalc_scan_iterator::intersection_info *ic= i_data(pi);
+
+    GCALC_DBUG_PRINT(("intersection point %d %d",
+                      ic->edge_a->thread, ic->edge_b->thread));
+    return;
+  }
+  if (pi->type == Gcalc_heap::nt_eq_node)
+  {
+    const Gcalc_scan_iterator::point *e= eq_sp(pi);
+    GCALC_DBUG_PRINT(("eq point %d", e->thread));
+    return;
+  }
+  n_buf= gcalc_pi_str(buf, pi, "");
+  buf[n_buf]= 0;
+  GCALC_DBUG_PRINT(("%s", buf));
+}
+
+
+#ifdef TMP_BLOCK
 static void GCALC_DBUG_PRINT_SLICE(const char *header,
                                    const Gcalc_scan_iterator::point *slice)
 {
   int nbuf1, nbuf2;
+  int nbuf3, nbuf4;
   char buf1[1024], buf2[1024];
-  nbuf1= nbuf2= strlen(header);
+  char buf3[1024], buf4[1024];
+  nbuf1= nbuf2= nbuf3= nbuf4= strlen(header);
   strcpy(buf1, header);
   strcpy(buf2, header);
+  strcpy(buf3, header);
+  strcpy(buf4, header);
   for (; slice; slice= slice->get_next())
   {
     nbuf1+= sprintf(buf1+nbuf1, "%d\t", slice->thread);
     nbuf2+= sprintf(buf2+nbuf2, "%s\t", gcalc_ev_name(slice->event));
+
+    nbuf3+= gcalc_pi_str(buf3+nbuf3, slice->pi, "\t");
+    if (slice->is_bottom())
+      nbuf4+= sprintf(buf4+nbuf4, "bt\t");
+    else
+      nbuf4+= gcalc_pi_str(buf4+nbuf4, slice->next_pi, "\t");
   }
   buf1[nbuf1]= 0;
   buf2[nbuf2]= 0;
+  buf3[nbuf3]= 0;
+  buf4[nbuf4]= 0;
   GCALC_DBUG_PRINT((buf1));
   GCALC_DBUG_PRINT((buf2));
+  GCALC_DBUG_PRINT((buf3));
+  GCALC_DBUG_PRINT((buf4));
 }
-
-
-static void GCALC_DBUG_PRINT_INTERSECTIONS(
-    Gcalc_scan_iterator::intersection *isc)
+#endif /*TMP_BLOCK*/
+static void GCALC_DBUG_PRINT_SLICE(const char *header,
+                                   const Gcalc_scan_iterator::point *slice)
 {
-  for (; isc; isc= isc->get_next())
+  int nbuf;
+  char buf[1024];
+  nbuf= strlen(header);
+  strcpy(buf, header);
+  for (; slice; slice= slice->get_next())
   {
-    long double ix, iy;
-    isc->ii->calc_xy_ld(&ix, &iy);
-    GCALC_DBUG_PRINT(("%d %d %d %.8LG %.8LG", isc->thread_a, isc->thread_b,
-                      isc->n_row, ix, iy));
-  }
-}
+    int lnbuf= nbuf;
+    lnbuf+= sprintf(buf + lnbuf, "%d\t", slice->thread);
+    lnbuf+= sprintf(buf + lnbuf, "%s\t", gcalc_ev_name(slice->event));
 
-
-static void GCALC_DBUG_PRINT_STATE(Gcalc_scan_iterator::slice_state *s)
-{
-  if (s->event_position)
-    GCALC_DBUG_PRINT(("%d %d %d", s->event_position->thread,
-     ((Gcalc_scan_iterator::point *) *s->event_position_hook)->thread,
-     *s->event_end_hook ?
-       ((Gcalc_scan_iterator::point *) *s->event_end_hook)->thread : -1));
-  else
-    GCALC_DBUG_PRINT(("position null"));
+    lnbuf+= gcalc_pi_str(buf + lnbuf, slice->pi, "\t");
+    if (slice->is_bottom())
+      lnbuf+= sprintf(buf+lnbuf, "bt\t");
+    else
+      lnbuf+= gcalc_pi_str(buf+lnbuf, slice->next_pi, "\t");
+    buf[lnbuf]= 0;
+    GCALC_DBUG_PRINT((buf));
+  }
 }
 
 
 #else
 #define GCALC_DBUG_CHECK_COUNTER(a)             do { } while(0)
+#define GCALC_DBUG_PRINT_PI(pi)                 do { } while(0)
 #define GCALC_DBUG_PRINT_SLICE(a, b)            do { } while(0)
 #define GCALC_DBUG_PRINT_INTERSECTIONS(a)       do { } while(0)
 #define GCALC_DBUG_PRINT_STATE(a)               do { } while(0)
@@ -463,6 +525,9 @@ int gcalc_cmp_coord(const Gcalc_internal_coord *a,
 }
 
 
+#define gcalc_cmp_coord1(a, b) gcalc_cmp_coord(a, b)
+
+
 int Gcalc_coord1::set_double(double d, double ext)
 {
   double ds= d * ext;
@@ -491,66 +556,6 @@ void Gcalc_coord1::copy(const Gcalc_coord1 *from)
   sign= from->sign;
 }
 
-/* Internal coordinates implementation end */
-
-
-Gcalc_heap::Info *Gcalc_heap::new_point_info(double x, double y,
-                                             gcalc_shape_info shape)
-{
-  double abs= fabs(x);
-  Info *result= (Info *)new_item();
-  if (!result)
-    return NULL;
-  *m_hook= result;
-  m_hook= &result->next;
-  result->x= x;
-  result->y= y;
-  result->shape= shape;
-  if (m_n_points)
-  {
-    if (abs > coord_extent)
-      coord_extent= abs;
-  }
-  else
-    coord_extent= abs;
-
-  abs= fabs(y);
-  if (abs > coord_extent)
-    coord_extent= abs;
-
-  m_n_points++;
-  return result;
-}
-
-
-Gcalc_heap::Intersection_info *Gcalc_heap::new_intersection(
-    const Info *p1, const Info *p2,
-    const Info *p3, const Info *p4)
-{
-  Intersection_info *isc= (Intersection_info *)new_item();
-  if (!isc)
-    return 0;
-  isc->p1= p1;
-  isc->p2= p2;
-  isc->p3= p3;
-  isc->p4= p4;
-  *m_intersection_hook= isc;
-  m_intersection_hook= &isc->next;
-  return isc;
-}
-
-
-class Gcalc_coord3 : public Gcalc_internal_coord
-{
-  gcalc_digit_t c[GCALC_COORD_BASE*3];
-  public:
-  void init()
-  {
-    n_digits= GCALC_COORD_BASE*3;
-    digits= c;
-  }
-};
-
 
 static void calc_t(Gcalc_coord2 *t_a, Gcalc_coord2 *t_b,
                    Gcalc_coord1 *b1x,
@@ -582,6 +587,8 @@ static void calc_t(Gcalc_coord2 *t_a, Gcalc_coord2 *t_b,
   gcalc_sub_coord(&b2x, &p4->ix, &p3->ix);
   gcalc_sub_coord(&b2y, &p4->iy, &p3->iy);
 
+  GCALC_DBUG_ASSERT(!b1y->is_zero() || !b2y.is_zero());
+
   gcalc_mul_coord(&x1y2, b1x, &b2y);
   gcalc_mul_coord(&x2y1, &b2x, b1y);
   gcalc_sub_coord(t_b, &x1y2, &x2y1);
@@ -593,16 +600,224 @@ static void calc_t(Gcalc_coord2 *t_a, Gcalc_coord2 *t_b,
 }
 
 
-inline void calc_t(Gcalc_coord2 *t_a, Gcalc_coord2 *t_b,
+static void calc_t(Gcalc_coord2 *t_a, Gcalc_coord2 *t_b,
                    Gcalc_coord1 *b1x,
                    Gcalc_coord1 *b1y,
-                   const Gcalc_heap::Intersection_info *isc)
+                   const Gcalc_heap::Info *i)
 {
-  calc_t(t_a, t_b, b1x, b1y, isc->p1, isc->p2, isc->p3, isc->p4);
+  GCALC_DBUG_ASSERT(i->type == Gcalc_heap::nt_intersection);
+  calc_t(t_a, t_b, b1x, b1y, i->p1, i->p2, i->p3, i->p4);
 }
 
 
-void Gcalc_heap::Intersection_info::calc_xy(double *x, double *y) const
+class Gcalc_coord4 : public Gcalc_internal_coord
+{
+  gcalc_digit_t c[GCALC_COORD_BASE*4];
+  public:
+  void init()
+  {
+    n_digits= GCALC_COORD_BASE*4;
+    digits= c;
+  }
+};
+
+
+class Gcalc_coord5 : public Gcalc_internal_coord
+{
+  gcalc_digit_t c[GCALC_COORD_BASE*5];
+  public:
+  void init()
+  {
+    n_digits= GCALC_COORD_BASE*5;
+    digits= c;
+  }
+};
+
+
+static void calc_isc_exp(Gcalc_coord5 *exp,
+                         const Gcalc_coord2 *bb2,
+                         const Gcalc_coord1 *ya1,
+                         const Gcalc_coord2 *bb1,
+                         const Gcalc_coord1 *yb1,
+                         const Gcalc_coord2 *a21_b1)
+{
+  Gcalc_coord3 p1, p2, sum;
+  p1.init();
+  p2.init();
+  sum.init();
+  exp->init();
+
+  gcalc_mul_coord(&p1, ya1, bb1);
+  gcalc_mul_coord(&p2, yb1, a21_b1);
+  gcalc_add_coord(&sum, &p1, &p2);
+  gcalc_mul_coord(exp, bb2, &sum);
+}
+
+
+static int cmp_intersections(const Gcalc_heap::Info *i1,
+                             const Gcalc_heap::Info *i2)
+{
+  Gcalc_coord2 t_a1, t_b1;
+  Gcalc_coord2 t_a2, t_b2;
+  Gcalc_coord1 yb1, yb2;
+  Gcalc_coord1 xb1, xb2;
+  Gcalc_coord5 exp_a, exp_b;
+  int result;
+
+  calc_t(&t_a1, &t_b1, &xb1, &yb1, i1);
+  calc_t(&t_a2, &t_b2, &xb2, &yb2, i2);
+
+  calc_isc_exp(&exp_a, &t_b2, &i1->p1->iy, &t_b1, &yb1, &t_a1);
+  calc_isc_exp(&exp_b, &t_b1, &i2->p1->iy, &t_b2, &yb2, &t_a2);
+
+  result= gcalc_cmp_coord(&exp_a, &exp_b);
+#ifdef GCALC_CHECK_WITH_FLOAT
+  long double x1, y1, x2, y2;
+  i1->calc_xy_ld(&x1, &y1);
+  i2->calc_xy_ld(&x2, &y2);
+
+  if (result == 0)
+    GCALC_DBUG_ASSERT(de_check(y1, y2));
+  if (result < 0)
+    GCALC_DBUG_ASSERT(de_check(y1, y2) || y1 < y2);
+  if (result > 0)
+    GCALC_DBUG_ASSERT(de_check(y1, y2) || y1 > y2);
+#endif /*GCALC_CHECK_WITH_FLOAT*/
+
+  if (result != 0)
+    return result;
+
+
+  calc_isc_exp(&exp_a, &t_b2, &i1->p1->ix, &t_b1, &xb1, &t_a1);
+  calc_isc_exp(&exp_b, &t_b1, &i2->p1->ix, &t_b2, &xb2, &t_a2);
+  result= gcalc_cmp_coord(&exp_a, &exp_b);
+#ifdef GCALC_CHECK_WITH_FLOAT
+  if (result == 0)
+    GCALC_DBUG_ASSERT(de_check(x1, x2));
+  if (result < 0)
+    GCALC_DBUG_ASSERT(de_check(x1, x2) || x1 < x2);
+  if (result > 0)
+    GCALC_DBUG_ASSERT(de_check(x1, x2) || x1 > x2);
+#endif /*GCALC_CHECK_WITH_FLOAT*/
+  return result;
+}
+
+
+static int cmp_node_isc(const Gcalc_heap::Info *node,
+                        const Gcalc_heap::Info *isc)
+{
+  GCALC_DBUG_ASSERT(node->type == Gcalc_heap::nt_shape_node);
+  Gcalc_coord3 exp_a, exp_b;
+  Gcalc_coord1 xb1, yb1, d0;
+  Gcalc_coord2 t_a, t_b;
+  int result;
+  exp_a.init();
+  exp_b.init();
+  d0.init();
+
+  calc_t(&t_a, &t_b, &xb1, &yb1, isc);
+
+  gcalc_sub_coord(&d0, &node->iy, &isc->p1->iy);
+  gcalc_mul_coord(&exp_a, &d0, &t_b);
+  gcalc_mul_coord(&exp_b, &yb1, &t_a);
+
+  result= gcalc_cmp_coord(&exp_a, &exp_b);
+#ifdef GCALC_CHECK_WITH_FLOAT
+  long double int_x, int_y;
+  isc->calc_xy_ld(&int_x, &int_y);
+  if (result < 0)
+    GCALC_DBUG_ASSERT(de_check(int_y, node->y) || node->y < int_y);
+  else if (result > 0)
+    GCALC_DBUG_ASSERT(de_check(int_y, node->y) || node->y > int_y);
+  else
+    GCALC_DBUG_ASSERT(de_check(int_y, node->y));
+#endif /*GCALC_CHECK_WITH_FLOAT*/
+  if (result)
+    goto exit;
+
+  gcalc_sub_coord(&d0, &node->ix, &isc->p1->ix);
+  gcalc_mul_coord(&exp_a, &d0, &t_b);
+  gcalc_mul_coord(&exp_b, &xb1, &t_a);
+
+  result= gcalc_cmp_coord(&exp_a, &exp_b);
+#ifdef GCALC_CHECK_WITH_FLOAT
+  if (result < 0)
+    GCALC_DBUG_ASSERT(de_check(int_x, node->x) || node->x < int_x);
+  else if (result > 0)
+    GCALC_DBUG_ASSERT(de_check(int_x, node->x) || node->x > int_x);
+  else
+    GCALC_DBUG_ASSERT(de_check(int_x, node->x));
+#endif /*GCALC_CHECK_WITH_FLOAT*/
+exit:
+  return result;
+}
+
+
+/* Internal coordinates implementation end */
+
+
+Gcalc_heap::Info *Gcalc_heap::new_point_info(double x, double y,
+                                             gcalc_shape_info shape)
+{
+  double abs= fabs(x);
+  Info *result= (Info *)new_item();
+  if (!result)
+    return NULL;
+  *m_hook= result;
+  m_hook= &result->next;
+  result->x= x;
+  result->y= y;
+  result->shape= shape;
+  result->top_node= 1;
+  result->type= nt_shape_node;
+  if (m_n_points)
+  {
+    if (abs > coord_extent)
+      coord_extent= abs;
+  }
+  else
+    coord_extent= abs;
+
+  abs= fabs(y);
+  if (abs > coord_extent)
+    coord_extent= abs;
+
+  m_n_points++;
+  return result;
+}
+
+
+static Gcalc_heap::Info *new_intersection(
+    Gcalc_heap *heap, Gcalc_scan_iterator::intersection_info *ii)
+{
+  Gcalc_heap::Info *isc= (Gcalc_heap::Info *)heap->new_item();
+  if (!isc)
+    return 0;
+  isc->type= Gcalc_heap::nt_intersection;
+  isc->p1= ii->edge_a->pi;
+  isc->p2= ii->edge_a->next_pi;
+  isc->p3= ii->edge_b->pi;
+  isc->p4= ii->edge_b->next_pi;
+  isc->intersection_data= ii;
+  return isc;
+}
+
+
+static Gcalc_heap::Info *new_eq_point(
+    Gcalc_heap *heap, const Gcalc_heap::Info *p,
+    Gcalc_scan_iterator::point *edge)
+{
+  Gcalc_heap::Info *eqp= (Gcalc_heap::Info *)heap->new_item();
+  if (!eqp)
+    return 0;
+  eqp->type= Gcalc_heap::nt_eq_node;
+  eqp->node= p;
+  eqp->eq_data= edge;
+  return eqp;
+}
+
+
+void Gcalc_heap::Info::calc_xy(double *x, double *y) const
 {
   double b0_x= p2->x - p1->x;
   double b0_y= p2->y - p1->y;
@@ -619,8 +834,7 @@ void Gcalc_heap::Intersection_info::calc_xy(double *x, double *y) const
 
 
 #ifdef GCALC_CHECK_WITH_FLOAT
-void Gcalc_heap::Intersection_info::calc_xy_ld(long double *x,
-                                               long double *y) const
+void Gcalc_heap::Info::calc_xy_ld(long double *x, long double *y) const
 {
   long double b0_x= p2->x - p1->x;
   long double b0_y= p2->y - p1->y;
@@ -663,24 +877,26 @@ void Gcalc_heap::Intersection_info::calc_xy_ld(long double *x,
 #endif /*GCALC_CHECK_WITH_FLOAT*/
 
 
+static int cmp_point_info(const Gcalc_heap::Info *i0,
+                          const Gcalc_heap::Info *i1)
+{
+  int cmp_y= gcalc_cmp_coord(&i0->iy, &i1->iy);
+  if (cmp_y)
+    return cmp_y;
+  return gcalc_cmp_coord(&i0->ix, &i1->ix);
+}
+
+
 static inline void trim_node(Gcalc_heap::Info *node, Gcalc_heap::Info *prev_node)
 {
   if (!node)
     return;
+  node->top_node= 0;
   GCALC_DBUG_ASSERT((node->left == prev_node) || (node->right == prev_node));
   if (node->left == prev_node)
     node->left= node->right;
   node->right= NULL;
-}
-
-
-static int cmp_point_info(const Gcalc_heap::Info *i0,
-                          const Gcalc_heap::Info *i1)
-{
-  int cmp_y= gcalc_cmp_coord(&i0->iy, &i1->iy);
-  if (cmp_y)
-    return cmp_y;
-  return gcalc_cmp_coord(&i0->ix, &i1->ix);
+  GCALC_DBUG_ASSERT(cmp_point_info(node, prev_node));
 }
 
 
@@ -711,14 +927,14 @@ void Gcalc_heap::prepare_operation()
 #ifdef GCALC_CHECK_WITH_FLOAT
   Gcalc_internal_coord::coord_extent= &coord_extent;
 #endif /*GCALC_CHECK_WITH_FLOAT*/
+  *m_hook= NULL;
+  m_hook= NULL; /* just to check it's not called twice */
   for (cur= get_first(); cur; cur= cur->get_next())
   {
     cur->ix.set_double(cur->x, coord_extent);
     cur->iy.set_double(cur->y, coord_extent);
   }
-  *m_hook= NULL;
   m_first= sort_list(compare_point_info, m_first, m_n_points);
-  m_hook= NULL; /* just to check it's not called twice */
 
   /* TODO - move this to the 'normal_scan' loop */
   for (cur= get_first(); cur; cur= cur->get_next())
@@ -745,9 +961,6 @@ void Gcalc_heap::reset()
   if (m_n_points)
   {
     free_list(m_first);
-    free_list((Gcalc_dyn_list::Item **) &m_first_intersection,
-              m_intersection_hook);
-    m_intersection_hook= (Gcalc_dyn_list::Item **) &m_first_intersection;
     m_n_points= 0;
   }
   m_hook= &m_first;
@@ -829,86 +1042,44 @@ inline void calc_dx_dy(Gcalc_scan_iterator::point *p)
     p->r_border= &p->next_pi->ix;
     p->l_border= &p->pi->ix;
   }
-  p->always_on_left= 0;
 }
 
 
 Gcalc_scan_iterator::Gcalc_scan_iterator(size_t blk_size) :
-  Gcalc_dyn_list(blk_size,
-	         (sizeof(point) > sizeof(intersection)) ?
-	          sizeof(point) : sizeof(intersection))
-{}
-		  
-Gcalc_scan_iterator::point
-  *Gcalc_scan_iterator::new_slice(Gcalc_scan_iterator::point *example)
+  Gcalc_dyn_list(blk_size, sizeof(point) > sizeof(intersection_info) ?
+                             sizeof(point) :
+                             sizeof(intersection_info))
 {
-  point *result= NULL;
-  Gcalc_dyn_list::Item **result_hook= (Gcalc_dyn_list::Item **) &result;
-  while (example)
-  {
-    *result_hook= new_slice_point();
-    result_hook= &(*result_hook)->next;
-    example= example->get_next();
-  }
-  *result_hook= NULL;
-  return result;
+  state.slice= NULL;
+  m_bottom_points= NULL;
+  m_bottom_hook= &m_bottom_points;
 }
-
+		  
 
 void Gcalc_scan_iterator::init(Gcalc_heap *points)
 {
   GCALC_DBUG_ASSERT(points->ready());
-  GCALC_DBUG_ASSERT(!state0.slice && !state1.slice);
+  GCALC_DBUG_ASSERT(!state.slice);
 
   if (!(m_cur_pi= points->get_first()))
     return;
   m_heap= points;
+  state.event_position_hook= &state.slice;
+  state.event_end= NULL;
+#ifndef GCALC_DBUG_OFF
   m_cur_thread= 0;
-  m_intersections= NULL;
-  m_cur_intersection= NULL;
-  m_next_is_top_point= true;
-  m_events= NULL;
-  current_state= &state0;
-  next_state= &state1;
-  saved_state= &state_s;
-  next_state->intersection_scan= 0;
-  next_state->pi= m_cur_pi;
+#endif /*GCALC_DBUG_OFF*/
 }
 
 void Gcalc_scan_iterator::reset()
 {
-  state0.slice= state1.slice= m_events= state_s.slice= NULL;
-  m_intersections= NULL;
+  state.slice= NULL;
+  m_bottom_points= NULL;
+  m_bottom_hook= &m_bottom_points;
   Gcalc_dyn_list::reset();
 }
 
 
-void Gcalc_scan_iterator::point::copy_core(const point *from)
-{
-  pi= from->pi;
-  next_pi= from->next_pi;
-  thread= from->thread;
-  dx.copy(&from->dx);
-  dy.copy(&from->dy);
-  l_border= from->l_border;
-  r_border= from->r_border;
-}
-
-
-void Gcalc_scan_iterator::point::copy_all(const point *from)
-{
-  pi= from->pi;
-  next_pi= from->next_pi;
-  thread= from->thread;
-  dx.copy(&from->dx);
-  dy.copy(&from->dy);
-  intersection_link= from->intersection_link;
-  event= from->event;
-  l_border= from->l_border;
-  r_border= from->r_border;
-}
-
-
 int Gcalc_scan_iterator::point::cmp_dx_dy(const Gcalc_coord1 *dx_a,
                                           const Gcalc_coord1 *dy_a,
                                           const Gcalc_coord1 *dx_b,
@@ -945,10 +1116,7 @@ int Gcalc_scan_iterator::point::cmp_dx_dy(const Gcalc_heap::Info *p1,
 
 int Gcalc_scan_iterator::point::cmp_dx_dy(const point *p) const
 {
-  if (is_bottom())
-    return p->is_bottom() ? 0 : -1;
-  if (p->is_bottom())
-    return 1;
+  GCALC_DBUG_ASSERT(!is_bottom());
   return cmp_dx_dy(&dx, &dy, &p->dx, &p->dy);
 }
 
@@ -968,215 +1136,259 @@ void Gcalc_scan_iterator::point::calc_x(long double *x, long double y,
 #endif /*GCALC_CHECK_WITH_FLOAT*/
 
 
-static int cmp_sp_pi(const Gcalc_scan_iterator::point *sp,
-                     const Gcalc_heap::Info *pi)
+static int compare_events(const void *e0, const void *e1)
 {
-  Gcalc_coord1 dx_pi, dy_pi;
-  Gcalc_coord2 dx_sp_dy_pi, dy_sp_dx_pi;
-
-  if (!sp->next_pi)
-    return cmp_point_info(sp->pi, pi);
-
-  dx_pi.init();
-  dy_pi.init();
-  dx_sp_dy_pi.init();
-  dy_sp_dx_pi.init();
-
-
-  gcalc_sub_coord(&dx_pi, &pi->ix, &sp->pi->ix);
-  gcalc_sub_coord(&dy_pi, &pi->iy, &sp->pi->iy);
-  gcalc_mul_coord(&dx_sp_dy_pi, &sp->dx, &dy_pi);
-  gcalc_mul_coord(&dy_sp_dx_pi, &sp->dy, &dx_pi);
-
-  int result= gcalc_cmp_coord(&dx_sp_dy_pi, &dy_sp_dx_pi);
-#ifdef GCALC_CHECK_WITH_FLOAT
-  long double sp_x;
-  sp->calc_x(&sp_x, pi->y, pi->x);
-  if (result == 0)
-    GCALC_DBUG_ASSERT(de_check(sp->dy.get_double(), 0.0) ||
-                de_check(sp_x, pi->x));
-  if (result < 0)
-    GCALC_DBUG_ASSERT(de_check(sp->dy.get_double(), 0.0) ||
-                de_check(sp_x, pi->x) ||
-                sp_x < pi->x);
-  if (result > 0)
-    GCALC_DBUG_ASSERT(de_check(sp->dy.get_double(), 0.0) ||
-                de_check(sp_x, pi->x) ||
-                sp_x > pi->x);
-#endif /*GCALC_CHECK_WITH_FLOAT*/
-  return result;
+  const Gcalc_scan_iterator::point *p0= (const Gcalc_scan_iterator::point *)e0;
+  const Gcalc_scan_iterator::point *p1= (const Gcalc_scan_iterator::point *)e1;
+  return p0->cmp_dx_dy(p1) > 0;
 }
 
 
-static void calc_cmp_sp_sp_exp(Gcalc_coord3 *result,
-                               const Gcalc_scan_iterator::point *a,
-                               const Gcalc_scan_iterator::point *b,
-                               const Gcalc_coord1 *ly)
+int Gcalc_scan_iterator::arrange_event(int do_sorting, int n_intersections)
 {
-  Gcalc_coord2 x_dy, dx_ly, sum;
+  int ev_counter;
+  point *sp;
+  point **sp_hook;
 
-  x_dy.init();
-  dx_ly.init();
-  sum.init();
-  result->init();
+  ev_counter= 0;
 
-  gcalc_mul_coord(&x_dy, &a->pi->ix, &a->dy);
-  gcalc_mul_coord(&dx_ly, &a->dx, ly);
-  gcalc_add_coord(&sum, &x_dy, &dx_ly);
-  gcalc_mul_coord(result, &sum, &b->dy);
-}
+  *m_bottom_hook= NULL;
+  for (sp= m_bottom_points; sp; sp= sp->get_next())
+    sp->ev_next= sp->get_next();
 
+  for (sp= state.slice, sp_hook= &state.slice;
+       sp; sp_hook= sp->next_ptr(), sp= sp->get_next())
+  {
+    if (sp->event)
+    {
+      state.event_position_hook= sp_hook;
+      break;
+    }
+  }
 
-static int cmp_sp_sp_cnt(const Gcalc_scan_iterator::point *a,
-                         const Gcalc_scan_iterator::point *b,
-                         const Gcalc_coord1 *y)
-{
-  Gcalc_coord1 lya, lyb;
-  Gcalc_coord3 a_exp, b_exp;
+  for (sp= *(sp_hook= state.event_position_hook);
+       sp && sp->event; sp_hook= sp->next_ptr(), sp= sp->get_next())
+  {
+    ev_counter++;
+    if (sp->get_next() && sp->get_next()->event)
+      sp->ev_next= sp->get_next();
+    else
+      sp->ev_next= m_bottom_points;
+  }
 
-  lya.init();
-  lyb.init();
-  gcalc_sub_coord(&lya, y, &a->pi->iy);
-  gcalc_sub_coord(&lyb, y, &b->pi->iy);
+#ifndef GCALC_DBUG_OFF
+  {
+    point *cur_p= sp;
+    for (; cur_p; cur_p= cur_p->get_next())
+      GCALC_DBUG_ASSERT(!cur_p->event);
+  }
+#endif /*GCALC_DBUG_OFF*/
 
-  calc_cmp_sp_sp_exp(&a_exp, a, b, &lya);
-  calc_cmp_sp_sp_exp(&b_exp, b, a, &lyb);
+  state.event_end= sp;
 
-  int result= gcalc_cmp_coord(&a_exp, &b_exp);
-#ifdef GCALC_CHECK_WITH_FLOAT
-  long double a_x, b_x;
-  a->calc_x(&a_x, y->get_double(), 0);
-  b->calc_x(&b_x, y->get_double(), 0);
-  if (result == 0)
-    GCALC_DBUG_ASSERT(de_check(a_x, b_x));
-  if (result < 0)
-    GCALC_DBUG_ASSERT(de_check(a_x, b_x) || a_x < b_x);
-  if (result > 0)
-    GCALC_DBUG_ASSERT(de_check(a_x, b_x) || a_x > b_x);
-#endif /*GCALC_CHECK_WITH_FLOAT*/
-  return result;
+  if (ev_counter == 2 && n_intersections == 1)
+  {
+    /* If we had only intersection, just swap the two points. */
+    sp= *state.event_position_hook;
+    *state.event_position_hook= sp->get_next();
+    sp->next= (*state.event_position_hook)->next;
+    (*state.event_position_hook)->next= sp;
+
+    /* The list of the events should be restored. */
+    (*state.event_position_hook)->ev_next= sp;
+    sp->ev_next= m_bottom_points;
+  }
+  else if (ev_counter == 2 && get_events()->event == scev_two_threads)
+  {
+    /* Do nothing. */
+  }
+  else if (ev_counter > 1 && do_sorting)
+  {
+    point *cur_p;
+    *sp_hook= NULL;
+    sp= (point *) sort_list(compare_events, *state.event_position_hook,
+                            ev_counter);
+    /* Find last item in the list, it's changed after the sorting. */
+    for (cur_p= sp->get_next(); cur_p->get_next();
+        cur_p= cur_p->get_next())
+    {}
+    cur_p->next= state.event_end;
+    *state.event_position_hook= sp;
+    /* The list of the events should be restored. */
+    for (; sp && sp->event; sp= sp->get_next())
+    {
+      if (sp->get_next() && sp->get_next()->event)
+        sp->ev_next= sp->get_next();
+      else
+        sp->ev_next= m_bottom_points;
+    }
+  }
+
+#ifndef GCALC_DBUG_OFF
+  {
+    const event_point *ev= get_events();
+    for (; ev && ev->get_next(); ev= ev->get_next())
+    {
+      if (ev->is_bottom() || ev->get_next()->is_bottom())
+        break;
+      GCALC_DBUG_ASSERT(ev->cmp_dx_dy(ev->get_next()) <= 0);
+    }
+  }
+#endif /*GCALC_DBUG_OFF*/
+  return 0;
 }
 
 
-static int cmp_sp_sp(const Gcalc_scan_iterator::point *a,
-                     const Gcalc_scan_iterator::point *b,
-                     const Gcalc_heap::Info *pi)
+int Gcalc_heap::Info::equal_pi(const Info *pi) const
 {
-  if (a->event == scev_none && b->event == scev_none)
-    return cmp_sp_sp_cnt(a, b, &pi->iy);
-  if (a->event == scev_none)
-    return cmp_sp_pi(a, pi);
-  if (b->event == scev_none)
-    return -1 * cmp_sp_pi(b, pi);
-
-  return 0;
+  if (type == nt_intersection)
+    return equal_intersection;
+  if (pi->type == nt_eq_node)
+    return 1;
+  if (type == nt_eq_node || pi->type == nt_intersection)
+    return 0;
+  return cmp_point_info(this, pi) == 0;
 }
 
-
-void Gcalc_scan_iterator::mark_event_position1(
-    point *ep, Gcalc_dyn_list::Item **ep_hook)
+int Gcalc_scan_iterator::step()
 {
-  if (!next_state->event_position)
+  int result= 0;
+  int do_sorting= 0;
+  int n_intersections= 0;
+  point *sp;
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::step");
+  GCALC_DBUG_ASSERT(more_points());
+
+  /* Clear the old event marks. */
+  if (m_bottom_points)
   {
-    next_state->event_position= ep;
-    next_state->event_position_hook= ep_hook;
+    free_list((Gcalc_dyn_list::Item **) &m_bottom_points,
+              (Gcalc_dyn_list::Item **) m_bottom_hook);
+    m_bottom_points= NULL;
+    m_bottom_hook= &m_bottom_points;
   }
-  next_state->event_end_hook= &ep->next;
+  for (sp= *state.event_position_hook;
+       sp != state.event_end; sp= sp->get_next())
+    sp->event= scev_none;
+
+//#ifndef GCALC_DBUG_OFF
+  state.event_position_hook= NULL;
+  state.pi= NULL;
+//#endif /*GCALC_DBUG_OFF*/
+
+  do
+  {
+#ifndef GCALC_DBUG_OFF
+    if (m_cur_pi->type == Gcalc_heap::nt_intersection &&
+        m_cur_pi->get_next()->type == Gcalc_heap::nt_intersection &&
+        m_cur_pi->equal_intersection)
+      GCALC_DBUG_ASSERT(cmp_intersections(m_cur_pi, m_cur_pi->get_next()) == 0);
+#endif /*GCALC_DBUG_OFF*/
+    GCALC_DBUG_CHECK_COUNTER();
+    GCALC_DBUG_PRINT_SLICE("step:", state.slice);
+    GCALC_DBUG_PRINT_PI(m_cur_pi);
+    if (m_cur_pi->type == Gcalc_heap::nt_shape_node)
+    {
+      if (m_cur_pi->is_top())
+      {
+        result= insert_top_node();
+        if (!m_cur_pi->is_bottom())
+          do_sorting++;
+      }
+      else if (m_cur_pi->is_bottom())
+        remove_bottom_node();
+      else
+      {
+        do_sorting++;
+        result= node_scan();
+      }
+      if (result)
+        GCALC_DBUG_RETURN(result);
+      state.pi= m_cur_pi;
+    }
+    else if (m_cur_pi->type == Gcalc_heap::nt_eq_node)
+    {
+      do_sorting++;
+      eq_scan();
+    }
+    else
+    {
+      /* nt_intersection */
+      do_sorting++;
+      n_intersections++;
+      intersection_scan();
+      if (!state.pi || state.pi->type == Gcalc_heap::nt_intersection)
+        state.pi= m_cur_pi;
+    }
+
+    m_cur_pi= m_cur_pi->get_next();
+  } while (m_cur_pi && state.pi->equal_pi(m_cur_pi));
+
+  GCALC_DBUG_RETURN(arrange_event(do_sorting, n_intersections));
 }
 
 
-static int compare_events(const void *e0, const void *e1)
+static int node_on_right(const Gcalc_heap::Info *node, 
+    const Gcalc_heap::Info *edge_a, const Gcalc_heap::Info *edge_b)
 {
-  const Gcalc_scan_iterator::point *p0= (const Gcalc_scan_iterator::point *)e0;
-  const Gcalc_scan_iterator::point *p1= (const Gcalc_scan_iterator::point *)e1;
-  return p0->cmp_dx_dy(p1) > 0;
+  Gcalc_coord1 a_x, a_y;
+  Gcalc_coord1 b_x, b_y;
+  Gcalc_coord2 ax_by, ay_bx;
+  a_x.init();
+  a_y.init();
+  b_x.init();
+  b_y.init();
+  ax_by.init();
+  ay_bx.init();
+
+  gcalc_sub_coord(&a_x, &node->ix, &edge_a->ix);
+  gcalc_sub_coord(&a_y, &node->iy, &edge_a->iy);
+  gcalc_sub_coord(&b_x, &edge_b->ix, &edge_a->ix);
+  gcalc_sub_coord(&b_y, &edge_b->iy, &edge_a->iy);
+  gcalc_mul_coord(&ax_by, &a_x, &b_y);
+  gcalc_mul_coord(&ay_bx, &a_y, &b_x);
+  return gcalc_cmp_coord(&ax_by, &ay_bx);
 }
 
 
-int Gcalc_scan_iterator::arrange_event()
+static int cmp_tops(const Gcalc_heap::Info *top_node, 
+    const Gcalc_heap::Info *edge_a, const Gcalc_heap::Info *edge_b)
 {
-  int ev_counter;
-  point *sp, *new_sp;
-  point *after_event;
-  Gcalc_dyn_list::Item **ae_hook= (Gcalc_dyn_list::Item **) &after_event;
+  int cmp_res_a, cmp_res_b;
 
-  if (m_events)
-    free_list(m_events);
-  ev_counter= 0;
-  GCALC_DBUG_ASSERT(current_state->event_position ==
-                      *current_state->event_position_hook);
-  for (sp= current_state->event_position;
-       sp != *current_state->event_end_hook; sp= sp->get_next())
-  {
-    if (sp->is_bottom())
-      continue;
-    if (!(new_sp= new_slice_point()))
-      return 1;
-    new_sp->copy_all(sp);
-    *ae_hook= new_sp;
-    ae_hook= &new_sp->next;
-    ev_counter++;
-  }
-  *ae_hook= NULL;
-  m_events= current_state->event_position;
-  if (after_event)
-  {
-    if (after_event->get_next())
-    {
-      point *cur_p;
-      after_event= (point *) sort_list(compare_events, after_event, ev_counter);
-      /* Find last item in the list, ae_hook can change after the sorting */
-      for (cur_p= after_event->get_next(); cur_p->get_next();
-           cur_p= cur_p->get_next())
-      {
-        cur_p->always_on_left= 1;
-      }
-      ae_hook= &cur_p->next;
+  cmp_res_a= gcalc_cmp_coord1(&edge_a->ix, &top_node->ix);
+  cmp_res_b= gcalc_cmp_coord1(&edge_b->ix, &top_node->ix);
 
-    }
-    *ae_hook= *current_state->event_end_hook;
-    *current_state->event_end_hook= NULL;
-    *current_state->event_position_hook= after_event;
-    current_state->event_end_hook= ae_hook;
-    current_state->event_position= after_event;
-  }
-  else
-  {
-    *current_state->event_position_hook= *current_state->event_end_hook;
-    *current_state->event_end_hook= NULL;
-    current_state->event_position= sp;
-    current_state->event_end_hook= current_state->event_position_hook;
-  }
+  if (cmp_res_a <= 0 && cmp_res_b > 0)
+    return -1;
+  if (cmp_res_b <= 0 && cmp_res_a > 0)
+    return 1;
+  if (cmp_res_a == 0 && cmp_res_b == 0)
+    return 0;
 
-  return 0;
+  return node_on_right(edge_a, top_node, edge_b);
 }
 
 
-int Gcalc_scan_iterator::insert_top_point()
+int Gcalc_scan_iterator::insert_top_node()
 {
-  point *sp= next_state->slice;
-  Gcalc_dyn_list::Item **prev_hook=
-    (Gcalc_dyn_list::Item **) &next_state->slice;
+  point *sp= state.slice;
+  point **prev_hook= &state.slice;
   point *sp1;
   point *sp0= new_slice_point();
-  point *sp_inc;
+  int cmp_res;
 
-  GCALC_DBUG_ENTER("Gcalc_scan_iterator::insert_top_point");
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::insert_top_node");
   if (!sp0)
     GCALC_DBUG_RETURN(1);
   sp0->pi= m_cur_pi;
   sp0->next_pi= m_cur_pi->left;
+#ifndef GCALC_DBUG_OFF
   sp0->thread= m_cur_thread++;
+#endif /*GCALC_DBUG_OFF*/
   if (m_cur_pi->left)
   {
     calc_dx_dy(sp0);
-    sp0->event= scev_thread;
-
-    /*Now just to increase the size of m_slice0 to be same*/
-    if (!(sp_inc= new_slice_point()))
-      GCALC_DBUG_RETURN(1);
-    sp_inc->next= current_state->slice;
-    current_state->slice= sp_inc;
     if (m_cur_pi->right)
     {
       if (!(sp1= new_slice_point()))
@@ -1184,683 +1396,424 @@ int Gcalc_scan_iterator::insert_top_point()
       sp1->event= sp0->event= scev_two_threads;
       sp1->pi= m_cur_pi;
       sp1->next_pi= m_cur_pi->right;
+#ifndef GCALC_DBUG_OFF
       sp1->thread= m_cur_thread++;
+#endif /*GCALC_DBUG_OFF*/
       calc_dx_dy(sp1);
       /* We have two threads so should decide which one will be first */
-      if (sp0->cmp_dx_dy(sp1)>0)
+      cmp_res= cmp_tops(m_cur_pi, m_cur_pi->left, m_cur_pi->right);
+      if (cmp_res > 0)
       {
         point *tmp= sp0;
         sp0= sp1;
         sp1= tmp;
       }
-
-      /*Now just to increase the size of m_slice0 to be same*/
-      if (!(sp_inc= new_slice_point()))
-        GCALC_DBUG_RETURN(1);
-      sp_inc->next= current_state->slice;
-      current_state->slice= sp_inc;
+      else if (cmp_res == 0)
+      {
+        /* Exactly same direction of the edges. */
+        cmp_res= gcalc_cmp_coord1(&m_cur_pi->left->iy, &m_cur_pi->right->iy);
+        if (cmp_res != 0)
+        {
+          if (cmp_res < 0)
+          {
+            if (add_eq_node(sp0->next_pi, sp1))
+              GCALC_DBUG_RETURN(1);
+          }
+          else
+          {
+            if (add_eq_node(sp1->next_pi, sp0))
+              GCALC_DBUG_RETURN(1);
+          }
+        }
+        else
+        {
+          cmp_res= gcalc_cmp_coord1(&m_cur_pi->left->ix, &m_cur_pi->right->ix);
+          if (cmp_res != 0)
+          {
+            if (cmp_res < 0)
+            {
+              if (add_eq_node(sp0->next_pi, sp1))
+                GCALC_DBUG_RETURN(1);
+            }
+            else
+            {
+              if (add_eq_node(sp1->next_pi, sp0))
+                GCALC_DBUG_RETURN(1);
+            }
+          }
+        }
+      }
     }
+    else
+      sp0->event= scev_thread;
   }
   else
-  {
     sp0->event= scev_single_point;
-  }
 
 
-  /* We need to find the place to insert. */
-  for (; sp && cmp_sp_pi(sp, m_cur_pi) < 0;
-         prev_hook= &sp->next, sp=sp->get_next())
+  /* Check if we already have an event - then we'll place the node there */
+  for (; sp && !sp->event; prev_hook= sp->next_ptr(), sp=sp->get_next())
   {}
-
-  next_state->event_position_hook= prev_hook;
-  if (sp && cmp_sp_pi(sp, m_cur_pi) == 0)
+  if (!sp)
   {
-    next_state->event_position= sp;
-    do
+    sp= state.slice;
+    prev_hook= &state.slice;
+    /* We need to find the place to insert. */
+    for (; sp; prev_hook= sp->next_ptr(), sp=sp->get_next())
     {
-      if (!sp->event)
+      if (sp->event || gcalc_cmp_coord(sp->r_border, &m_cur_pi->ix) < 0)
+        continue;
+      cmp_res= node_on_right(m_cur_pi, sp->pi, sp->next_pi);
+      if (cmp_res == 0)
+      {
+        /* The top node lies on the edge. */
+        /* Nodes of that edge will be handled in other places. */
         sp->event= scev_intersection;
-      prev_hook= &sp->next;
-      sp= sp->get_next();
-    } while (sp && cmp_sp_pi(sp, m_cur_pi) == 0);
+      }
+      else if (cmp_res < 0)
+        break;
+    }
+#ifdef TMP_BLOCK
+    state.event_position_hook= prev_hook;
+#endif /*TMP_BLOCK*/
   }
-  else
-    next_state->event_position= sp0;
 
-  *prev_hook= sp0;
-  if (sp0->event == scev_two_threads)
+  if (sp0->event == scev_single_point)
   {
-    sp1->next= sp;
-    sp0->next= sp1;
-    next_state->event_end_hook= &sp1->next;
+    /* Add single point to the bottom list. */
+    *m_bottom_hook= sp0;
+    m_bottom_hook= sp0->next_ptr();
+    state.event_position_hook= prev_hook;
   }
   else
   {
+    *prev_hook= sp0;
     sp0->next= sp;
-    next_state->event_end_hook= &sp0->next;
+    if (add_events_for_node(sp0))
+      GCALC_DBUG_RETURN(1);
+
+    if (sp0->event == scev_two_threads)
+    {
+      *prev_hook= sp1;
+      sp1->next= sp;
+      if (add_events_for_node(sp1))
+        GCALC_DBUG_RETURN(1);
+
+      sp0->next= sp1;
+      *prev_hook= sp0;
+    }
   }
+
   GCALC_DBUG_RETURN(0);
 }
 
 
-int Gcalc_scan_iterator::normal_scan()
+void Gcalc_scan_iterator::remove_bottom_node()
 {
-  point *sp;
-  Gcalc_dyn_list::Item **sp_hook;
-  Gcalc_heap::Info *next_pi;
-  point *first_bottom_point;
-
-  GCALC_DBUG_ENTER("Gcalc_scan_iterator::normal_scan");
-  GCALC_DBUG_CHECK_COUNTER();
-  GCALC_DBUG_PRINT_SLICE("in\t", next_state->slice);
-  if (m_next_is_top_point && insert_top_point())
-    GCALC_DBUG_RETURN(1);
+  point *sp= state.slice;
+  point **sp_hook= &state.slice;
+  point *first_bottom_point= NULL;
 
-  for (next_pi= m_cur_pi->get_next();
-       next_pi && cmp_point_info(m_cur_pi, next_pi) == 0;
-       next_pi= next_pi->get_next())
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::remove_bottom_node");
+  for (; sp; sp= sp->get_next())
   {
-    GCALC_DBUG_PRINT(("eq_loop equal pi"));
-    next_state->clear_event_position();
-    m_next_is_top_point= true;
-    first_bottom_point= NULL;
-    for (sp= next_state->slice,
-         sp_hook= (Gcalc_dyn_list::Item **) &next_state->slice; sp;
-         sp_hook= &sp->next, sp= sp->get_next())
+    if (sp->next_pi == m_cur_pi)
     {
-      GCALC_DBUG_PRINT(("eq_loop normal_eq_step %s%d", gcalc_ev_name(sp->event),
-                                               sp->thread));
-      if (sp->next_pi == next_pi) /* End of the segment */
+      *sp_hook= sp->get_next();
+      sp->pi= m_cur_pi;
+      sp->next_pi= NULL;
+      if (first_bottom_point)
       {
-        GCALC_DBUG_PRINT(("eq_loop edge end"));
-        if (cmp_point_info(sp->pi, next_pi))
-        {
-          GCALC_DBUG_PRINT(("eq_loop zero-len edge"));
-          sp->pi= next_pi;
-        }
-        sp->next_pi= next_pi->left;
-        m_next_is_top_point= false;
-        if (next_pi->is_bottom())
-        {
-          GCALC_DBUG_PRINT(("eq_loop bottom_point"));
-          if (sp->event == scev_thread)
-          {
-            /* Beginning of the thread, and the end are same */
-            /* Make single point out of the line then.       */
-            GCALC_DBUG_PRINT(("eq_loop line_to_point"));
-            sp->event= scev_single_point;
-          }
-          else if (sp->event == scev_two_threads)
-          {
-            if (sp->get_next() && sp->get_next()->pi == sp->pi)
-            {
-              GCALC_DBUG_PRINT(("eq_loop two_threads_to_line %d",
-                               sp->get_next()->thread));
-              sp->get_next()->event= scev_thread;
-            }
-            else if (sp != next_state->slice)
-            {
-              point *fnd_sp;
-              for (fnd_sp= next_state->slice; fnd_sp->get_next() != sp;
-                   fnd_sp= fnd_sp->get_next())
-              {}
-              GCALC_DBUG_ASSERT(fnd_sp->pi == sp->pi);
-              GCALC_DBUG_PRINT(("eq_loop two_threads_to_line %d",
-                                fnd_sp->thread));
-              fnd_sp->event= scev_thread;
-            }
-            sp->event= scev_single_point;
-          }
-          else if (first_bottom_point)
-          {
-            GCALC_DBUG_PRINT(("eq_loop two_ends"));
-            first_bottom_point->event= sp->event= scev_two_ends;
-          }
-          else
-          {
-            first_bottom_point= sp;
-            sp->event= scev_end;
-          }
-        }
-        else
-        {
-          GCALC_DBUG_PRINT(("eq_loop no_bottom_point %d%s", sp->thread,
-                            gcalc_ev_name(sp->event)));
-          if ((sp->event & (scev_point | scev_thread | scev_two_threads)) == 0)
-            sp->event= scev_point;
-          calc_dx_dy(sp);
-        }
-        mark_event_position1(sp, sp_hook);
-      }
-      else if (sp->event || (cmp_sp_pi(sp, next_pi) == 0))
-      {
-        GCALC_DBUG_PRINT(("eq_loop l_event %d%s", sp->thread,
-                           gcalc_ev_name(sp->event)));
-        if (!sp->event)
-          sp->event= scev_intersection;
-        mark_event_position1(sp, sp_hook);
-      }
-    }
-    m_cur_pi= next_pi;
-    if (m_next_is_top_point)
-    {
-      if (insert_top_point())
-        GCALC_DBUG_RETURN(1);
-      /* Set proper values to the event position */
-      /* TODO: can be done faster                */
-      next_state->clear_event_position();
-      if (next_state->slice->event)
-        mark_event_position1(next_state->slice,
-          (Gcalc_dyn_list::Item **) &next_state->slice);
-      for (sp= next_state->slice; sp->get_next(); sp= sp->get_next())
-      {
-        if (sp->get_next()->event)
-          mark_event_position1(sp->get_next(), &sp->next);
+        first_bottom_point->event= sp->event= scev_two_ends;
+        break;
       }
+      first_bottom_point= sp;
+      sp->event= scev_end;
+      state.event_position_hook= sp_hook;
     }
-    GCALC_DBUG_PRINT_SLICE("eq_loop\t", next_state->slice);
+    else
+      sp_hook= sp->next_ptr();
   }
-
-  /* Swap current <-> next */
+  GCALC_DBUG_ASSERT(first_bottom_point);
+  *m_bottom_hook= first_bottom_point;
+  m_bottom_hook= first_bottom_point->next_ptr();
+  if (sp)
   {
-    slice_state *tmp= current_state;
-    current_state= next_state;
-    next_state= tmp;
+    *m_bottom_hook= sp;
+    m_bottom_hook= sp->next_ptr();
   }
 
-  if (arrange_event())
-    GCALC_DBUG_RETURN(1);
-  GCALC_DBUG_PRINT_SLICE("after_arrange\t", current_state->slice);
-  GCALC_DBUG_PRINT_SLICE("events\t", m_events);
-  GCALC_DBUG_PRINT_STATE(current_state);
-
-  point *sp0= current_state->slice;
-  point *sp1= next_state->slice;
-  point *prev_sp1= NULL;
+  GCALC_DBUG_VOID_RETURN;
+}
 
-  if (!(m_cur_pi= next_pi))
-  {
-    free_list(sp1);
-    next_state->slice= NULL;
-    GCALC_DBUG_RETURN(0);
-  }
-  
-  next_state->intersection_scan= 0;
-  next_state->pi= m_cur_pi;
-  Gcalc_heap::Info *cur_pi= m_cur_pi;
 
+int Gcalc_scan_iterator::add_events_for_node(point *sp_node)
+{
+  point *sp= state.slice;
+  int cur_pi_r, sp_pi_r;
 
-  first_bottom_point= NULL;
-  m_next_is_top_point= true;
-  bool intersections_found= false;
-  next_state->clear_event_position();
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::add_events_for_node");
 
-  for (; sp0; sp0= sp0->get_next())
+  /* Scan to the event point. */
+  for (; sp != sp_node; sp= sp->get_next())
   {
-    GCALC_DBUG_ASSERT(!sp0->is_bottom());
-    if (sp0->next_pi == cur_pi) /* End of the segment */
+    GCALC_DBUG_ASSERT(!sp->is_bottom());
+    GCALC_DBUG_PRINT(("left cut_edge %d", sp->thread));
+    if (sp->next_pi == sp_node->next_pi ||
+        gcalc_cmp_coord1(sp->r_border, sp_node->l_border) < 0)
+      continue;
+    sp_pi_r= node_on_right(sp->next_pi, sp_node->pi, sp_node->next_pi);
+    if (sp_pi_r < 0)
+      continue;
+    cur_pi_r= node_on_right(sp_node->next_pi, sp->pi, sp->next_pi);
+    if (cur_pi_r > 0)
+      continue;
+    if (cur_pi_r == 0 && sp_pi_r == 0)
     {
-      GCALC_DBUG_PRINT(("edge_end %d", sp0->thread));
-      sp1->pi= cur_pi;
-      sp1->thread= sp0->thread;
-      sp1->next_pi= cur_pi->left;
-
-      m_next_is_top_point= false;
-      
-      if (sp1->is_bottom())
+      int cmp_res= cmp_point_info(sp->next_pi, sp_node->next_pi);
+      if (cmp_res > 0)
       {
-        GCALC_DBUG_PRINT(("bottom_point"));
-	if (!first_bottom_point)
-	{
-          sp1->event= scev_end;
-          first_bottom_point= sp1;
-	}
-	else
-        {
-          GCALC_DBUG_PRINT(("two_ends"));
-          first_bottom_point->event= sp1->event= scev_two_ends;
-        }
+        if (add_eq_node(sp_node->next_pi, sp))
+          GCALC_DBUG_RETURN(1);
       }
-      else
+      else if (cmp_res < 0)
       {
-        sp1->event= scev_point;
-        calc_dx_dy(sp1);
+        if (add_eq_node(sp->next_pi, sp_node))
+          GCALC_DBUG_RETURN(1);
       }
-      mark_event_position1(sp1,
-        prev_sp1 ? &prev_sp1->next :
-                   (Gcalc_dyn_list::Item **) &next_state->slice);
+      continue;
     }
-    else
+
+    if (cur_pi_r == 0)
     {
-      GCALC_DBUG_PRINT(("cut_edge %d", sp0->thread));
-      /* Cut current string with the height of the new point*/
-      sp1->copy_core(sp0);
-      if (cmp_sp_pi(sp1, cur_pi) == 0)
-      {
-        GCALC_DBUG_PRINT(("equal_point"));
-        mark_event_position1(sp1,
-          prev_sp1 ? &prev_sp1->next :
-                     (Gcalc_dyn_list::Item **) &next_state->slice);
-        sp1->event= scev_intersection;
-      }
-      else
-        sp1->event= scev_none;
+      if (add_eq_node(sp_node->next_pi, sp))
+        GCALC_DBUG_RETURN(1);
+      continue;
+    }
+    else if (sp_pi_r == 0)
+    {
+      if (add_eq_node(sp->next_pi, sp_node))
+        GCALC_DBUG_RETURN(1);
+      continue;
     }
 
-    intersections_found= intersections_found ||
-                         (prev_sp1 && cmp_sp_sp(prev_sp1, sp1, cur_pi) > 0);
-    GCALC_DBUG_PRINT(("%s", intersections_found ? "X":"-"));
-
-    prev_sp1= sp1;
-    sp1= sp1->get_next();
-  }
-
-  if (sp1)
-  {
-    if (prev_sp1)
-      prev_sp1->next= NULL;
-    else
-      next_state->slice= NULL;
-    free_list(sp1);
-  }
-
-  GCALC_DBUG_PRINT_SLICE("after_loop\t", next_state->slice);
-  if (intersections_found)
-    GCALC_DBUG_RETURN(handle_intersections());
-
-  GCALC_DBUG_RETURN(0);
-}
-
-
-int Gcalc_scan_iterator::add_intersection(int n_row,
-                                          const point *a, const point *b,
-		                          Gcalc_dyn_list::Item ***p_hook)
-{
-  const point *a0= a->intersection_link;
-  const point *b0= b->intersection_link;
-  intersection *isc= new_intersection();
-
-  GCALC_DBUG_ENTER("Gcalc_scan_iterator::add_intersection");
-  if (!isc)
-    GCALC_DBUG_RETURN(1);
-
-  m_n_intersections++;
-  **p_hook= isc;
-  *p_hook= &isc->next;
-  isc->n_row= n_row;
-  isc->thread_a= a->thread;
-  isc->thread_b= b->thread;
-
-  isc->ii= m_heap->new_intersection(a0->pi, a0->next_pi,
-                                    b0->pi, b0->next_pi);
-  GCALC_DBUG_RETURN(isc->ii == NULL);
-}
-
-
-int Gcalc_scan_iterator::find_intersections()
-{
-  Gcalc_dyn_list::Item **hook;
-
-  GCALC_DBUG_ENTER("Gcalc_scan_iterator::find_intersections");
-  m_n_intersections= 0;
-  {
-    /* Set links between slicepoints */
-    point *sp0= current_state->slice;
-    point *sp1= next_state->slice;
-    for (; sp1; sp0= sp0->get_next(),sp1= sp1->get_next())
+    if (sp->event)
     {
-      GCALC_DBUG_ASSERT(!sp0->is_bottom());
-      GCALC_DBUG_ASSERT(sp0->thread == sp1->thread);
-      sp1->intersection_link= sp0;
+#ifndef GCALC_DBUG_OFF
+      cur_pi_r= node_on_right(sp_node->pi, sp->pi, sp->next_pi);
+      GCALC_DBUG_ASSERT(cur_pi_r == 0);
+#endif /*GCALC_DBUG_OFF*/
+      continue;
     }
+    cur_pi_r= node_on_right(sp_node->pi, sp->pi, sp->next_pi);
+    GCALC_DBUG_ASSERT(cur_pi_r >= 0);
+    //GCALC_DBUG_ASSERT(cur_pi_r > 0); /* Is it ever violated? */
+    if (cur_pi_r > 0 && add_intersection(sp, sp_node, m_cur_pi))
+      GCALC_DBUG_RETURN(1);
   }
 
-  hook= (Gcalc_dyn_list::Item **)&m_intersections;
-  bool intersections_found;
-  int n_row= 0;
+  /* Scan to the end of the slice */
+  sp= sp->get_next();
 
-  do
+  for (; sp; sp= sp->get_next())
   {
-    point **pprev_s1= &next_state->slice;
-    intersections_found= false;
-    n_row++;
-    for (;;)
+    GCALC_DBUG_ASSERT(!sp->is_bottom());
+    GCALC_DBUG_PRINT(("right cut_edge %d", sp->thread));
+    if (sp->next_pi == sp_node->next_pi ||
+        gcalc_cmp_coord1(sp_node->r_border, sp->l_border) < 0)
+      continue;
+    sp_pi_r= node_on_right(sp->next_pi, sp_node->pi, sp_node->next_pi);
+    if (sp_pi_r > 0)
+      continue;
+    cur_pi_r= node_on_right(sp_node->next_pi, sp->pi, sp->next_pi);
+    if (cur_pi_r < 0)
+      continue;
+    if (cur_pi_r == 0 && sp_pi_r == 0)
     {
-      point *prev_s1= *pprev_s1;
-      point *s1= prev_s1->get_next();
-      if (!s1)
-        break;
-      if (cmp_sp_sp(prev_s1, s1, m_cur_pi) <= 0)
+      int cmp_res= cmp_point_info(sp->next_pi, sp_node->next_pi);
+      if (cmp_res > 0)
       {
-        pprev_s1= (point **) &prev_s1->next;
-        continue;
+        if (add_eq_node(sp_node->next_pi, sp))
+          GCALC_DBUG_RETURN(1);
       }
-      intersections_found= true;
-      if (add_intersection(n_row, prev_s1, s1, &hook))
+      else if (cmp_res < 0)
+      {
+        if (add_eq_node(sp->next_pi, sp_node))
+          GCALC_DBUG_RETURN(1);
+      }
+      continue;
+    }
+    if (cur_pi_r == 0)
+    {
+      if (add_eq_node(sp_node->next_pi, sp))
         GCALC_DBUG_RETURN(1);
-      *pprev_s1= s1;
-      prev_s1->next= s1->next;
-      s1->next= prev_s1;
-      pprev_s1= (point **) &prev_s1->next;
-      if (!*pprev_s1)
-        break;
-    };
-  } while (intersections_found);
-
-  *hook= NULL;
-  GCALC_DBUG_RETURN(0);
-}
-
-
-class Gcalc_coord4 : public Gcalc_internal_coord
-{
-  gcalc_digit_t c[GCALC_COORD_BASE*4];
-  public:
-  void init()
-  {
-    n_digits= GCALC_COORD_BASE*4;
-    digits= c;
-  }
-};
+      continue;
+    }
+    else if (sp_pi_r == 0)
+    {
+      if (add_eq_node(sp->next_pi, sp_node))
+        GCALC_DBUG_RETURN(1);
+      continue;
+    }
 
-class Gcalc_coord5 : public Gcalc_internal_coord
-{
-  gcalc_digit_t c[GCALC_COORD_BASE*5];
-  public:
-  void init()
-  {
-    n_digits= GCALC_COORD_BASE*5;
-    digits= c;
+    if (sp->event)
+    {
+#ifndef GCALC_DBUG_OFF
+      cur_pi_r= node_on_right(sp_node->pi, sp->pi, sp->next_pi);
+      GCALC_DBUG_ASSERT(cur_pi_r == 0);
+#endif /*GCALC_DBUG_OFF*/
+      continue;
+    }
+    cur_pi_r= node_on_right(sp_node->pi, sp->pi, sp->next_pi);
+    GCALC_DBUG_ASSERT(cur_pi_r <= 0);
+    //GCALC_DBUG_ASSERT(cur_pi_r < 0); /* Is it ever violated? */
+    if (cur_pi_r < 0 && add_intersection(sp_node, sp, m_cur_pi))
+      GCALC_DBUG_RETURN(1);
   }
-};
-
 
-static void calc_isc_exp(Gcalc_coord5 *exp,
-                         const Gcalc_coord2 *bb2,
-                         const Gcalc_coord1 *ya1,
-                         const Gcalc_coord2 *bb1,
-                         const Gcalc_coord1 *yb1,
-                         const Gcalc_coord2 *a21_b1)
-{
-  Gcalc_coord3 p1, p2, sum;
-  p1.init();
-  p2.init();
-  sum.init();
-  exp->init();
-
-  gcalc_mul_coord(&p1, ya1, bb1);
-  gcalc_mul_coord(&p2, yb1, a21_b1);
-  gcalc_add_coord(&sum, &p1, &p2);
-  gcalc_mul_coord(exp, bb2, &sum);
+  GCALC_DBUG_RETURN(0);
 }
 
 
-static int cmp_intersections(const Gcalc_heap::Intersection_info *i1,
-                             const Gcalc_heap::Intersection_info *i2)
+int Gcalc_scan_iterator::node_scan()
 {
-  Gcalc_coord2 t_a1, t_b1;
-  Gcalc_coord2 t_a2, t_b2;
-  Gcalc_coord1 yb1, yb2;
-  Gcalc_coord1 xb1, xb2;
-  Gcalc_coord5 exp_a, exp_b;
-  int result;
-
-  calc_t(&t_a1, &t_b1, &xb1, &yb1, i1);
-  calc_t(&t_a2, &t_b2, &xb2, &yb2, i2);
-
-  calc_isc_exp(&exp_a, &t_b2, &i1->p1->iy, &t_b1, &yb1, &t_a1);
-  calc_isc_exp(&exp_b, &t_b1, &i2->p1->iy, &t_b2, &yb2, &t_a2);
-
-  result= gcalc_cmp_coord(&exp_a, &exp_b);
-#ifdef GCALC_CHECK_WITH_FLOAT
-  long double x1, y1, x2, y2;
-  i1->calc_xy_ld(&x1, &y1);
-  i2->calc_xy_ld(&x2, &y2);
+  point *sp= state.slice;
+  Gcalc_heap::Info *cur_pi= m_cur_pi;
 
-  if (result == 0)
-    GCALC_DBUG_ASSERT(de_check(y1, y2));
-  if (result < 0)
-    GCALC_DBUG_ASSERT(de_check(y1, y2) || y1 < y2);
-  if (result > 0)
-    GCALC_DBUG_ASSERT(de_check(y1, y2) || y1 > y2);
-#endif /*GCALC_CHECK_WITH_FLOAT*/
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::node_scan");
 
-  if (result != 0)
-    return result;
+  /* Scan to the event point.                             */
+  /* Can be avoided if we add link to the sp to the Info. */
+  for (; sp->next_pi != cur_pi; sp= sp->get_next())
+  {}
 
+  GCALC_DBUG_PRINT(("node for %d", sp->thread));
+  /* Handle the point itself. */
+  sp->pi= cur_pi;
+  sp->next_pi= cur_pi->left;
+  sp->event= scev_point;
+  calc_dx_dy(sp);
 
-  calc_isc_exp(&exp_a, &t_b2, &i1->p1->ix, &t_b1, &xb1, &t_a1);
-  calc_isc_exp(&exp_b, &t_b1, &i2->p1->ix, &t_b2, &xb2, &t_a2);
-  result= gcalc_cmp_coord(&exp_a, &exp_b);
-#ifdef GCALC_CHECK_WITH_FLOAT
-  if (result == 0)
-    GCALC_DBUG_ASSERT(de_check(x1, x2));
-  if (result < 0)
-    GCALC_DBUG_ASSERT(de_check(x1, x2) || x1 < x2);
-  if (result > 0)
-    GCALC_DBUG_ASSERT(de_check(x1, x2) || x1 > x2);
-#endif /*GCALC_CHECK_WITH_FLOAT*/
-  return result;
+  GCALC_DBUG_RETURN(add_events_for_node(sp));
 }
 
-static int compare_intersections(const void *e1, const void *e2)
-{
-  Gcalc_scan_iterator::intersection *i1= (Gcalc_scan_iterator::intersection *)e1;
-  Gcalc_scan_iterator::intersection *i2= (Gcalc_scan_iterator::intersection *)e2;
-  int result= cmp_intersections(i1->ii, i2->ii);
-  if (result != 0)
-    return result > 0;
-  return (i1->n_row > i2->n_row);
-}
 
-inline int intersections_eq(const Gcalc_heap::Intersection_info *i1,
-                            const Gcalc_heap::Intersection_info *i2)
+void Gcalc_scan_iterator::eq_scan()
 {
-  return cmp_intersections(i1, i2) == 0;
+  point *sp= eq_sp(m_cur_pi);
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::eq_scan");
+  
+#ifndef GCALC_DBUG_OFF
+  {
+    point *cur_p= state.slice;
+    for (; cur_p && cur_p != sp; cur_p= cur_p->get_next())
+    {}
+    GCALC_DBUG_ASSERT(cur_p);
+  }
+#endif /*GCALC_DBUG_OFF*/
+  if (!sp->event)
+  {
+    sp->event= scev_intersection;
+    sp->ev_pi= m_cur_pi;
+  }
+
+  GCALC_DBUG_VOID_RETURN;
 }
 
 
-static int sp_isc_eq(const Gcalc_scan_iterator::point *sp,
-                     const Gcalc_heap::Intersection_info *isc)
+void Gcalc_scan_iterator::intersection_scan()
 {
+  intersection_info *ii= i_data(m_cur_pi);
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::intersection_scan");
+  
+#ifndef GCALC_DBUG_OFF
+  {
+    point *sp= state.slice;
+    for (; sp && sp != ii->edge_a; sp= sp->get_next())
+    {}
+    GCALC_DBUG_ASSERT(sp);
+    for (; sp && sp != ii->edge_b; sp= sp->get_next())
+    {}
+    GCALC_DBUG_ASSERT(sp);
+  }
+#endif /*GCALC_DBUG_OFF*/
 
-  Gcalc_coord4 exp_a, exp_b;
-  Gcalc_coord1 xb1, yb1;
-  Gcalc_coord2 t_a, t_b;
-  Gcalc_coord2 t_sp_a, t_sp_b;
-  exp_a.init();
-  exp_b.init();
-  calc_t(&t_a, &t_b, &xb1, &yb1, isc);
-  calc_t(&t_sp_a, &t_sp_b, &xb1, &yb1, isc->p1, isc->p2, sp->pi, sp->next_pi);
-
-  gcalc_mul_coord(&exp_a, &t_a, &t_sp_b);
-  gcalc_mul_coord(&exp_b, &t_b, &t_sp_a);
-  int result= gcalc_cmp_coord(&exp_a, &exp_b);
-#ifdef GCALC_CHECK_WITH_FLOAT
-  long double int_x, int_y, sp_x;
-  isc->calc_xy_ld(&int_x, &int_y);
-  sp->calc_x(&sp_x, int_y, int_x);
-  if (result == 0)
-    GCALC_DBUG_ASSERT(de_check(sp->dy.get_double(), 0.0) ||
-                      de_check(sp_x, int_x));
-#endif /*GCALC_CHECK_WITH_FLOAT*/
-  return result == 0;
-}
-
+  ii->edge_a->event= ii->edge_b->event= scev_intersection;
+  ii->edge_a->ev_pi= ii->edge_b->ev_pi= m_cur_pi;
+  free_item(ii);
+  m_cur_pi->intersection_data= NULL;
 
-inline void Gcalc_scan_iterator::sort_intersections()
-{
-  m_intersections= (intersection *)sort_list(compare_intersections,
-                                             m_intersections,m_n_intersections);
+  GCALC_DBUG_VOID_RETURN;
 }
 
 
-int Gcalc_scan_iterator::handle_intersections()
+int Gcalc_scan_iterator::add_intersection(point *sp_a, point *sp_b,
+                                          Gcalc_heap::Info *pi_from)
 {
-  GCALC_DBUG_ENTER("Gcalc_scan_iterator::handle_intersections");
-  GCALC_DBUG_ASSERT(next_state->slice->next);
+  Gcalc_heap::Info *ii;
+  intersection_info *i_calc;
+  int cmp_res;
+  int skip_next= 0;
 
-  if (find_intersections())
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::add_intersection");
+  if (!(i_calc= new_intersection_info(sp_a, sp_b)) ||
+      !(ii= new_intersection(m_heap, i_calc)))
     GCALC_DBUG_RETURN(1);
-  GCALC_DBUG_PRINT_INTERSECTIONS(m_intersections);
-  sort_intersections();
-  GCALC_DBUG_PRINT(("After sorting"));
-  GCALC_DBUG_PRINT_INTERSECTIONS(m_intersections);
 
-  /* Swap saved <-> next */
-  {
-    slice_state *tmp= next_state;
-    next_state= saved_state;
-    saved_state= tmp;
-  }
-  /* We need the next slice to be just equal */
-  next_state->slice= new_slice(saved_state->slice);
-  m_cur_intersection= m_intersections;
-  GCALC_DBUG_RETURN(intersection_scan());
-}
+  ii->equal_intersection= 0;
 
-
-int Gcalc_scan_iterator::intersection_scan()
-{
-  point *sp0, *sp1;
-  Gcalc_dyn_list::Item **hook;
-  intersection *next_intersection= NULL;
-
-  GCALC_DBUG_ENTER("Gcalc_scan_iterator::intersection_scan");
-  GCALC_DBUG_CHECK_COUNTER();
-  if (m_cur_intersection != m_intersections)
+  for (;
+       pi_from->get_next() != sp_a->next_pi &&
+         pi_from->get_next() != sp_b->next_pi;
+       pi_from= pi_from->get_next())
   {
-    GCALC_DBUG_PRINT_SLICE("in_isc\t", next_state->slice);
-    /* Swap current <-> next */
+    Gcalc_heap::Info *cur= pi_from->get_next();
+    if (skip_next)
     {
-      slice_state *tmp= current_state;
-      current_state= next_state;
-      next_state= tmp;
-    }
-
-    if (arrange_event())
-      GCALC_DBUG_RETURN(1);
-
-    GCALC_DBUG_PRINT_SLICE("isc_after_arrange\t", current_state->slice);
-    if (!m_cur_intersection)
-    {
-      /* Swap saved <-> next */
-      {
-        slice_state *tmp= next_state;
-        next_state= saved_state;
-        saved_state= tmp;
-      }
-      Gcalc_dyn_list::Item **n_hook=
-        (Gcalc_dyn_list::Item **) &next_state->slice;
-
-      next_state->clear_event_position();
-      sp0= current_state->slice;
-      sp1= next_state->slice;
-
-      for (; sp0;
-           sp0= sp0->get_next(), n_hook= &sp1->next, sp1= sp1->get_next())
-      {
-        if (sp0->thread != sp1->thread)
-        {
-          point *fnd_s= sp1->get_next();
-          Gcalc_dyn_list::Item **fnd_hook= &sp1->next;
-          for (; fnd_s && fnd_s->thread != sp0->thread;
-               fnd_hook= &fnd_s->next, fnd_s= fnd_s->get_next())
-          {}
-          GCALC_DBUG_ASSERT(fnd_s && fnd_s == *fnd_hook);
-          /* Now swap items of the next_state->slice */
-          *n_hook= fnd_s;
-          *fnd_hook= fnd_s->next;
-          fnd_s->next= sp1;
-          sp1= fnd_s;
-        }
-        if (sp1->event)
-          mark_event_position1(sp1, n_hook);
-      }
-#ifndef GCALC_DBUG_OFF
-      sp0= current_state->slice;
-      sp1= next_state->slice;
-      for (; sp0; sp0= sp0->get_next(), sp1= sp1->get_next())
-        GCALC_DBUG_ASSERT(sp0->thread == sp1->thread);
-      GCALC_DBUG_ASSERT(!sp1);
-#endif /*GCALC_DBUG_OFF*/
-      free_list(saved_state->slice);
-      saved_state->slice= NULL;
-
-      free_list(m_intersections);
-      m_intersections= NULL;
-      GCALC_DBUG_RETURN(0);
+      if (cur->type == Gcalc_heap::nt_intersection)
+        skip_next= cur->equal_intersection;
+      else
+        skip_next= 0;
+      continue;
     }
-  }
-
-  sp0= current_state->slice;
-  hook= (Gcalc_dyn_list::Item **) &next_state->slice;
-  sp1= next_state->slice;
-  next_state->clear_event_position();
-  next_state->intersection_scan= 1;
-  next_state->isc= m_cur_intersection->ii;
-
-  for (; sp0;
-       hook= &sp1->next, sp1= sp1->get_next(), sp0= sp0->get_next())
-  {
-    if (sp0->thread == m_cur_intersection->thread_a ||
-        sp0->thread == m_cur_intersection->thread_b)
+    if (cur->type == Gcalc_heap::nt_intersection)
     {
-      GCALC_DBUG_ASSERT(sp0->thread != m_cur_intersection->thread_a ||
-        sp0->get_next()->thread == m_cur_intersection->thread_b ||
-        sp_isc_eq(sp0->get_next(), m_cur_intersection->ii));
-      GCALC_DBUG_PRINT(("isc_i_thread %d", sp0->thread));
-      sp1->copy_core(sp0);
-      sp1->event= scev_intersection;
-      mark_event_position1(sp1, hook);
+      cmp_res= cmp_intersections(cur, ii);
+      skip_next= cur->equal_intersection;
     }
+    else if (cur->type == Gcalc_heap::nt_eq_node)
+      continue;
     else
+      cmp_res= cmp_node_isc(cur, ii);
+    if (cmp_res == 0)
     {
-      GCALC_DBUG_PRINT(("isc_cut %d", sp0->thread));
-      sp1->copy_core(sp0);
-      if (sp_isc_eq(sp1, m_cur_intersection->ii))
-      {
-        sp1->event= scev_intersection;
-        mark_event_position1(sp1, hook);
-      }
-      else
-        sp1->event= scev_none;
+      ii->equal_intersection= 1;
+      break;
     }
+    else if (cmp_res > 0)
+      break;
   }
 
-  if (sp1)
-  {
-    free_list(sp1);
-    *hook= NULL;
-  }
+  /* Intersection inserted before the equal point. */
+  ii->next= pi_from->get_next();
+  pi_from->next= ii;
 
-  /* Now check equal intersections */
-  for (next_intersection= m_cur_intersection->get_next();
-       next_intersection &&
-         intersections_eq(next_intersection->ii, m_cur_intersection->ii);
-       next_intersection= next_intersection->get_next())
-  {
-    /* Handle equal intersections. We only need to set proper events */
-    GCALC_DBUG_PRINT(("isc_eq_intersection"));
-    sp0= current_state->slice;
-    hook= (Gcalc_dyn_list::Item **) &next_state->slice;
-    sp1= next_state->slice;
-    next_state->clear_event_position();
-
-    for (; sp0;
-        hook= &sp1->next, sp1= sp1->get_next(), sp0= sp0->get_next())
-    {
-      if (sp0->thread == next_intersection->thread_a ||
-          sp0->thread == next_intersection->thread_b ||
-          sp1->event == scev_intersection)
-      {
-        GCALC_DBUG_PRINT(("isc_eq_thread %d", sp0->thread));
-        sp1->event= scev_intersection;
-        mark_event_position1(sp1, hook);
-      }
-    }
-  }
-  m_cur_intersection= next_intersection;
+  GCALC_DBUG_RETURN(0);
+}
+
+
+int Gcalc_scan_iterator::add_eq_node(Gcalc_heap::Info *node, point *sp)
+{
+  Gcalc_heap::Info *en;
+
+  GCALC_DBUG_ENTER("Gcalc_scan_iterator::add_intersection");
+  en= new_eq_point(m_heap, node, sp);
+  if (!en)
+    GCALC_DBUG_RETURN(1);
+
+  /* eq_node iserted after teh equal point. */
+  en->next= node->get_next();
+  node->next= en;
 
   GCALC_DBUG_RETURN(0);
 }
@@ -1868,40 +1821,40 @@ int Gcalc_scan_iterator::intersection_scan()
 
 double Gcalc_scan_iterator::get_y() const
 {
-  if (current_state->intersection_scan)
+  if (state.pi->type == Gcalc_heap::nt_intersection)
   {
     double x, y;
-    current_state->isc->calc_xy(&x, &y);
+    state.pi->calc_xy(&x, &y);
     return y;
   }
   else
-    return current_state->pi->y;
+    return state.pi->y;
 }
 
 
 double Gcalc_scan_iterator::get_event_x() const
 {
-  if (current_state->intersection_scan)
+  if (state.pi->type == Gcalc_heap::nt_intersection)
   {
     double x, y;
-    current_state->isc->calc_xy(&x, &y);
+    state.pi->calc_xy(&x, &y);
     return x;
   }
   else
-    return current_state->pi->x;
+    return state.pi->x;
 }
 
 double Gcalc_scan_iterator::get_h() const
 {
   double cur_y= get_y();
   double next_y;
-  if (next_state->intersection_scan)
+  if (state.pi->type == Gcalc_heap::nt_intersection)
   {
     double x;
-    next_state->isc->calc_xy(&x, &next_y);
+    state.pi->calc_xy(&x, &next_y);
   }
   else
-    next_y= next_state->pi->y;
+    next_y= state.pi->y;
   return next_y - cur_y;
 }
 
@@ -1919,4 +1872,3 @@ double Gcalc_scan_iterator::get_sp_x(const point *sp) const
 
 
 #endif /* HAVE_SPATIAL */
-
diff --git a/sql/gcalc_slicescan.h b/sql/gcalc_slicescan.h
index 22b7cc44027..3655b11bc15 100644
--- a/sql/gcalc_slicescan.h
+++ b/sql/gcalc_slicescan.h
@@ -28,11 +28,13 @@
 #define GCALC_DBUG_PRINT(b) DBUG_PRINT("Gcalc", b)
 #define GCALC_DBUG_ENTER(a) DBUG_ENTER("Gcalc "a)
 #define GCALC_DBUG_RETURN(r) DBUG_RETURN(r)
+#define GCALC_DBUG_VOID_RETURN DBUG_VOID_RETURN
 #define GCALC_DBUG_ASSERT(r) DBUG_ASSERT(r)
 #else
 #define GCALC_DBUG_PRINT(b)     do {} while(0)
 #define GCALC_DBUG_ENTER(a)     do {} while(0)
 #define GCALC_DBUG_RETURN(r)    return (r)
+#define GCALC_DBUG_VOID_RETURN  do {} while(0)
 #define GCALC_DBUG_ASSERT(r)    do {} while(0)
 #endif /*GCALC_DBUG_OFF*/
 
@@ -158,6 +160,18 @@ public:
 };
 
 
+class Gcalc_coord3 : public Gcalc_internal_coord
+{
+  gcalc_digit_t c[GCALC_COORD_BASE*3];
+  public:
+  void init()
+  {
+    n_digits= GCALC_COORD_BASE*3;
+    digits= c;
+  }
+};
+
+
 void gcalc_mul_coord(Gcalc_internal_coord *result,
                      const Gcalc_internal_coord *a,
                      const Gcalc_internal_coord *b);
@@ -192,41 +206,71 @@ typedef uint gcalc_shape_info;
 class Gcalc_heap : public Gcalc_dyn_list
 {
 public:
-  class Info : public Gcalc_dyn_list::Item
+  enum node_type
   {
-  public:
-    gcalc_shape_info shape;
-    Info *left;
-    Info *right;
-    double x,y;
-    Gcalc_coord1 ix, iy;
-
-    inline bool is_bottom() const { return !left; }
-    inline Info *get_next() { return (Info *)next; }
-    inline const Info *get_next() const { return (const Info *)next; }
+    nt_shape_node,
+    nt_intersection,
+    nt_eq_node
   };
-  class Intersection_info : public Gcalc_dyn_list::Item
+  class Info : public Gcalc_dyn_list::Item
   {
   public:
-    /* Line p1-p2 supposed to intersect line p3-p4 */
-    const Info *p1;
-    const Info *p2;
-    const Info *p3;
-    const Info *p4;
+    node_type type;
+    union
+    {
+      struct
+      {
+        /* nt_shape_node */
+        gcalc_shape_info shape;
+        Info *left;
+        Info *right;
+        double x,y;
+        Gcalc_coord1 ix, iy;
+        int top_node;
+      };
+      struct
+      {
+        /* nt_intersection */
+        /* Line p1-p2 supposed to intersect line p3-p4 */
+        const Info *p1;
+        const Info *p2;
+        const Info *p3;
+        const Info *p4;
+        void *intersection_data;
+        int equal_intersection;
+      };
+      struct
+      {
+        /* nt_eq_node */
+        const Info *node;
+        void *eq_data;
+      };
+    };
+
+    bool is_bottom() const
+      { GCALC_DBUG_ASSERT(type == nt_shape_node); return !left; }
+    bool is_top() const
+      { GCALC_DBUG_ASSERT(type == nt_shape_node); return top_node; }
+    bool is_single_node() const
+      { return is_bottom() && is_top(); }
+
     void calc_xy(double *x, double *y) const;
+    int equal_pi(const Info *pi) const;
 #ifdef GCALC_CHECK_WITH_FLOAT
     void calc_xy_ld(long double *x, long double *y) const;
 #endif /*GCALC_CHECK_WITH_FLOAT*/
+
+    Info *get_next() { return (Info *)next; }
+    const Info *get_next() const { return (const Info *)next; }
   };
 
   Gcalc_heap(size_t blk_size=8192) :
     Gcalc_dyn_list(blk_size, sizeof(Info)),
-    m_hook(&m_first), m_n_points(0),
-    m_intersection_hook((Gcalc_dyn_list::Item **) &m_first_intersection)
+    m_hook(&m_first), m_n_points(0)
   {}
   Info *new_point_info(double x, double y, gcalc_shape_info shape);
-  Intersection_info *new_intersection(const Info *p1, const Info *p2,
-                                      const Info *p3, const Info *p4);
+  Info *new_intersection(const Info *p1, const Info *p2,
+                         const Info *p3, const Info *p4);
   void prepare_operation();
   inline bool ready() const { return m_hook == NULL; }
   Info *get_first() { return (Info *)m_first; }
@@ -240,8 +284,6 @@ private:
   Gcalc_dyn_list::Item *m_first;
   Gcalc_dyn_list::Item **m_hook;
   int m_n_points;
-  Intersection_info *m_first_intersection;
-  Gcalc_dyn_list::Item **m_intersection_hook;
   double coord_extent;
 };
 
@@ -345,7 +387,6 @@ enum Gcalc_scan_events
   scev_single_point= 64  /* Got single point */
 };
 
-typedef int sc_thread_id;
 
 /* 
    Gcalc_scan_iterator incapsulates the slisescan algorithm.
@@ -366,12 +407,11 @@ public:
     Gcalc_coord1 dy;
     Gcalc_heap::Info *pi;
     Gcalc_heap::Info *next_pi;
-    sc_thread_id thread;
+    Gcalc_heap::Info *ev_pi;
     const Gcalc_coord1 *l_border;
     const Gcalc_coord1 *r_border;
-    int always_on_left;
+    point *ev_next;
 
-    const point *intersection_link;
     Gcalc_scan_events event;
 
     inline const point *c_get_next() const
@@ -380,9 +420,6 @@ public:
     gcalc_shape_info get_shape() const { return pi->shape; }
     inline point *get_next() { return (point *)next; }
     inline const point *get_next() const { return (const point *)next; }
-    /* copies all but 'next' 'x' and 'precursor' */
-    void copy_core(const point *from);
-    void copy_all(const point *from);
     /* Compare the dx_dy parameters regarding the horiz_dir */
     /* returns -1 if less, 0 if equal, 1 if bigger          */
     static int cmp_dx_dy(const Gcalc_coord1 *dx_a,
@@ -394,48 +431,52 @@ public:
                          const Gcalc_heap::Info *p3,
                          const Gcalc_heap::Info *p4);
     int cmp_dx_dy(const point *p) const;
-    int simple_event() const
-    {
-      return !next ? (event & (scev_point | scev_end)) : 
-                     (!next->next && event == scev_two_ends);
-    }
-#ifndef DBUG_OFF
-    void dbug_print();
-#endif /*DBUG_OFF*/
+    point **next_ptr() { return (point **) &next; }
+#ifndef GCALC_DBUG_OFF
+    unsigned int thread;
+#endif /*GCALC_DBUG_OFF*/
 #ifdef GCALC_CHECK_WITH_FLOAT
     void calc_x(long double *x, long double y, long double ix) const;
 #endif /*GCALC_CHECK_WITH_FLOAT*/
   };
 
-  class intersection : public Gcalc_dyn_list::Item
+  /* That class introduced mostly for the 'typecontrol' reason.      */
+  /* only difference from the point classis the get_next() function. */
+  class event_point : public point
+  {
+  public:
+    inline const event_point *get_next() const
+    { return (const event_point*) ev_next; }
+    int simple_event() const
+    {
+      return !ev_next ? (event & (scev_point | scev_end)) : 
+        (!ev_next->ev_next && event == scev_two_ends);
+    }
+  };
+
+  class intersection_info : public Gcalc_dyn_list::Item
   {
   public:
-    int n_row;
-    sc_thread_id thread_a;
-    sc_thread_id thread_b;
-    const Gcalc_heap::Intersection_info *ii;
-    inline intersection *get_next() { return (intersection *)next; }
+    point *edge_a;
+    point *edge_b;
+
+    Gcalc_coord2 t_a;
+    Gcalc_coord2 t_b;
+    int t_calculated;
+    Gcalc_coord3 x_exp;
+    int x_calculated;
+    Gcalc_coord3 y_exp;
+    int y_calculated;
   };
 
+
   class slice_state
   {
   public:
     point *slice;
-    point *event_position;
-    Gcalc_dyn_list::Item **event_position_hook;
-    Gcalc_dyn_list::Item **event_end_hook;
-    int intersection_scan;
-    union
-    {
-      const Gcalc_heap::Info *pi;
-      const Gcalc_heap::Intersection_info *isc;
-    };
-    slice_state() : slice(NULL) {}
-    void clear_event_position()
-    {
-      event_position= NULL;
-      event_end_hook= (Gcalc_dyn_list::Item **) &event_position;
-    }
+    point **event_position_hook;
+    point *event_end;
+    const Gcalc_heap::Info *pi;
   };
 
 public:
@@ -443,68 +484,56 @@ public:
 
   void init(Gcalc_heap *points); /* Iterator can be reused */
   void reset();
-  int step()
-  {
-    DBUG_ASSERT(more_points());
-    return m_intersections ? intersection_scan() : normal_scan();
-  }
+  int step();
 
-  inline Gcalc_heap::Info *more_points() { return m_cur_pi; }
-  inline bool more_trapezoids()
+  Gcalc_heap::Info *more_points() { return m_cur_pi; }
+  bool more_trapezoids()
     { return m_cur_pi && m_cur_pi->next; }
 
-  inline const point *get_events() const
-    { return m_events; }
-  inline const point *get_event_position() const
-    { return current_state->event_position; }
-  inline const point *get_event_end() const
-    { return (point *) *current_state->event_end_hook; }
-  inline const point *get_b_slice() const { return current_state->slice; }
-  inline const point *get_t_slice() const { return next_state->slice; }
+  const point *get_bottom_points() const
+    { return m_bottom_points; }
+  const point *get_event_position() const
+    { return *state.event_position_hook; }
+  const point *get_event_end() const
+    { return state.event_end; }
+  const event_point *get_events() const
+    { return (const event_point *)
+        (*state.event_position_hook == state.event_end ?
+            m_bottom_points : *state.event_position_hook); }
+  const point *get_b_slice() const { return state.slice; }
   double get_h() const;
   double get_y() const;
   double get_event_x() const;
   double get_sp_x(const point *sp) const;
-  int intersection_step() const { return current_state->intersection_scan; }
+  int intersection_step() const
+    { return state.pi->type == Gcalc_heap::nt_intersection; }
   const Gcalc_heap::Info *get_cur_pi() const
   {
-    DBUG_ASSERT(!intersection_step());
-    return current_state->pi;
-  }
-  const Gcalc_heap::Intersection_info *get_cur_ii() const
-  {
-    DBUG_ASSERT(intersection_step());
-    return current_state->isc;
+    return state.pi;
   }
 
 private:
   Gcalc_heap *m_heap;
   Gcalc_heap::Info *m_cur_pi;
-  slice_state state0, state1, state_s;
-  slice_state *current_state;
-  slice_state *next_state;
-  slice_state *saved_state;
-
-  intersection *m_intersections;
-  int m_n_intersections;
-  intersection *m_cur_intersection;
-  bool m_next_is_top_point;
-  sc_thread_id m_cur_thread;
-
-  point *m_events;
-  int normal_scan();
-  int intersection_scan();
-  void sort_intersections();
-  int handle_intersections();
-  int insert_top_point();
-  int add_intersection(int n_row, const point *a, const point *b,
-		       Gcalc_dyn_list::Item ***p_hook);
-  int find_intersections();
-
-  intersection *new_intersection()
-  {
-    return (intersection *)new_item();
-  }
+  slice_state state;
+
+#ifndef GCALC_DBUG_OFF
+  unsigned int m_cur_thread;
+#endif /*GCALC_DBUG_OFF*/
+
+  point *m_bottom_points;
+  point **m_bottom_hook;
+
+  int node_scan();
+  void eq_scan();
+  void intersection_scan();
+  void remove_bottom_node();
+  int insert_top_node();
+  int add_intersection(point *sp_a, point *sp_b,
+                       Gcalc_heap::Info *pi_from);
+  int add_eq_node(Gcalc_heap::Info *node, point *sp);
+  int add_events_for_node(point *sp_node);
+
   point *new_slice_point()
   {
     point *new_point= (point *)new_item();
@@ -512,9 +541,15 @@ private:
     new_point->dy.init();
     return new_point;
   }
-  point *new_slice(point *example);
-  int arrange_event();
-  void mark_event_position1(point *ep, Gcalc_dyn_list::Item **ep_hook);
+  intersection_info *new_intersection_info(point *a, point *b)
+  {
+    intersection_info *ii= (intersection_info *)new_item();
+    ii->edge_a= a;
+    ii->edge_b= b;
+    ii->t_calculated= ii->x_calculated= ii->y_calculated= 0;
+    return ii;
+  }
+  int arrange_event(int do_sorting, int n_intersections);
 };
 
 
@@ -525,6 +560,7 @@ private:
    previous and current slices.
 */
 
+#ifdef TMP_BLOCK
 class Gcalc_trapezoid_iterator
 {
 protected:
@@ -556,6 +592,7 @@ public:
     sp1= rt();
   }
 };
+#endif /*TMP_BLOCK*/
 
 
 /* 
diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc
index eabc42a6c51..f6203ba552f 100644
--- a/sql/gcalc_tools.cc
+++ b/sql/gcalc_tools.cc
@@ -192,7 +192,7 @@ int Gcalc_function::count_internal(const char *cur_func, uint set_type,
         result= result & !next_res;
         break;
       default:
-        DBUG_ASSERT(FALSE);
+        GCALC_DBUG_ASSERT(FALSE);
     };
   }
 
@@ -262,7 +262,8 @@ void Gcalc_function::reset()
 
 int Gcalc_function::check_function(Gcalc_scan_iterator &scan_it)
 {
-  const Gcalc_scan_iterator::point *eq_start, *cur_eq, *events;
+  const Gcalc_scan_iterator::point *eq_start, *cur_eq;
+  const Gcalc_scan_iterator::event_point *events;
   GCALC_DBUG_ENTER("Gcalc_function::check_function");
 
   while (scan_it.more_points())
@@ -502,7 +503,7 @@ int Gcalc_result_receiver::complete_shape()
   }
   else
   {
-    DBUG_ASSERT(cur_shape != Gcalc_function::shape_point);
+    GCALC_DBUG_ASSERT(cur_shape != Gcalc_function::shape_point);
     if (cur_shape == Gcalc_function::shape_hole)
     {
       shape_area+= prev_x*first_y - prev_y*first_x;
@@ -534,7 +535,7 @@ do_complete:
 
   if (!n_shapes++)
   {
-    DBUG_ASSERT(cur_shape != Gcalc_function::shape_hole);
+    GCALC_DBUG_ASSERT(cur_shape != Gcalc_function::shape_hole);
     common_shapetype= cur_shape;
   }
   else if (cur_shape == Gcalc_function::shape_hole)
@@ -587,7 +588,7 @@ int Gcalc_result_receiver::get_result_typeid()
       return (n_shapes == 1) ? Geometry::wkb_linestring :
                                Geometry::wkb_multilinestring;
     default:
-      DBUG_ASSERT(0);
+      GCALC_DBUG_ASSERT(0);
   }
   return 0;
 }
@@ -648,6 +649,7 @@ Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) :
 }
 
 
+#ifdef TMP_BLOCK
 void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si)
 {
   if ((intersection_point= si->intersection_step()))
@@ -655,6 +657,12 @@ void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si)
   else
     pi= si->get_cur_pi();
 }
+#endif /*TMP_BLOCK*/
+void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si)
+{
+  intersection_point= si->intersection_step();
+  pi= si->get_cur_pi();
+}
 
 
 Gcalc_operation_reducer::res_point *
@@ -726,7 +734,7 @@ int Gcalc_operation_reducer::continue_range(active_thread *t,
 
 
 inline int Gcalc_operation_reducer::continue_i_range(active_thread *t,
-			            const Gcalc_heap::Intersection_info *ii)
+			            const Gcalc_heap::Info *ii)
 {
   res_point *rp= add_res_point(t->rp->type);
   GCALC_DBUG_ENTER("Gcalc_operation_reducer::continue_i_range");
@@ -736,7 +744,7 @@ inline int Gcalc_operation_reducer::continue_i_range(active_thread *t,
   rp->down= t->rp;
   t->rp->up= rp;
   rp->intersection_point= true;
-  rp->ii= ii;
+  rp->pi= ii;
   t->rp= rp;
   GCALC_DBUG_RETURN(0);
 }
@@ -746,7 +754,7 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1,
 {
   res_point *rp0, *rp1;
   GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_couple");
-  DBUG_ASSERT(t0->rp->type == t1->rp->type);
+  GCALC_DBUG_ASSERT(t0->rp->type == t1->rp->type);
   if (!(rp0= add_res_point(t0->rp->type)) ||
       !(rp1= add_res_point(t0->rp->type)))
     GCALC_DBUG_RETURN(1);
@@ -769,7 +777,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si)
   int prev_state= 0;
   int sav_prev_state;
   active_thread *prev_range= NULL;
-  const Gcalc_scan_iterator::point *events;
+  const Gcalc_scan_iterator::event_point *events;
   const Gcalc_scan_iterator::point *eq_start;
   active_thread **cur_t_hook= &m_first_active_thread;
   active_thread **starting_t_hook;
@@ -834,7 +842,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si)
         break;
       }
       default:
-        DBUG_ASSERT(0);
+        GCALC_DBUG_ASSERT(0);
     }
     GCALC_DBUG_RETURN(0);
   }
@@ -875,7 +883,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si)
       {
         if (cur_t->rp->type == Gcalc_function::shape_line)
         {
-          DBUG_ASSERT(!prev_state);
+          GCALC_DBUG_ASSERT(!prev_state);
           add_line(1, cur_t, events);
         }
         else
@@ -971,7 +979,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si)
     {
       poly_border *pb1, *pb2;
       pb1= m_poly_borders;
-      DBUG_ASSERT(m_poly_borders->next);
+      GCALC_DBUG_ASSERT(m_poly_borders->next);
 
       pb2= get_pair_border(pb1);
       /* Remove pb1 from the list. The pb2 already removed in get_pair_border. */
@@ -1098,7 +1106,7 @@ int Gcalc_operation_reducer::connect_threads(
   if (incoming_a && incoming_b)
   {
     res_point *rpa, *rpb;
-    DBUG_ASSERT(ta->rp->type == tb->rp->type);
+    GCALC_DBUG_ASSERT(ta->rp->type == tb->rp->type);
     if (!(rpa= add_res_point(ta->rp->type)) ||
         !(rpb= add_res_point(ta->rp->type)))
       GCALC_DBUG_RETURN(1);
@@ -1116,7 +1124,7 @@ int Gcalc_operation_reducer::connect_threads(
   }
   if (!incoming_a)
   {
-    DBUG_ASSERT(!incoming_b);
+    GCALC_DBUG_ASSERT(!incoming_b);
 
     res_point *rp0, *rp1;
     if (!(rp0= add_res_point(s_t)) || !(rp1= add_res_point(s_t)))
@@ -1152,14 +1160,14 @@ int Gcalc_operation_reducer::connect_threads(
   }
   /* else, if only ta is incoming */
 
-  DBUG_ASSERT(tb != ta);
+  GCALC_DBUG_ASSERT(tb != ta);
   tb->rp= ta->rp;
   tb->thread_start= ta->thread_start;
   if (Gcalc_scan_iterator::point::
       cmp_dx_dy(ta->p1, ta->p2, pb->pi, pb->next_pi) != 0)
   {
     if (si->intersection_step() ?
-          continue_i_range(tb, si->get_cur_ii()) :
+          continue_i_range(tb, si->get_cur_pi()) :
           continue_range(tb, si->get_cur_pi(), pb->next_pi))
       GCALC_DBUG_RETURN(1);
   }
@@ -1191,7 +1199,7 @@ int Gcalc_operation_reducer::end_line(active_thread *t,
                                       const Gcalc_scan_iterator *si)
 {
   GCALC_DBUG_ENTER("Gcalc_operation_reducer::end_line");
-  DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line);
+  GCALC_DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line);
   res_point *rp= add_res_point(Gcalc_function::shape_line);
   if (!rp)
     GCALC_DBUG_RETURN(1);
@@ -1237,7 +1245,7 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res,
   if (res->intersection_point)
   {
     double x, y;
-    res->ii->calc_xy(&x, &y);
+    res->pi->calc_xy(&x, &y);
     if (storage->single_point(x,y))
       GCALC_DBUG_RETURN(1);
   }
@@ -1264,7 +1272,7 @@ int Gcalc_operation_reducer::get_result_thread(res_point *cur,
     {
       if (cur->intersection_point)
       {
-        cur->ii->calc_xy(&x, &y);
+        cur->pi->calc_xy(&x, &y);
       }
       else
       {
@@ -1368,7 +1376,7 @@ int Gcalc_operation_reducer::get_result(Gcalc_result_receiver *storage)
         uint32 insert_position, hole_position, position_shift;
         poly_instance *cur_poly;
         insert_position= m_result->outer_poly->first_poly_node->poly_position;
-        DBUG_ASSERT(insert_position);
+        GCALC_DBUG_ASSERT(insert_position);
         hole_position= storage->position();
         storage->start_shape(Gcalc_function::shape_hole);
         if (get_polygon_result(m_result, storage,
diff --git a/sql/gcalc_tools.h b/sql/gcalc_tools.h
index ca740dcdc11..b89a9a45e07 100644
--- a/sql/gcalc_tools.h
+++ b/sql/gcalc_tools.h
@@ -233,7 +233,6 @@ public:
     union
     {
       const Gcalc_heap::Info *pi;
-      const Gcalc_heap::Intersection_info *ii;
       res_point *first_poly_node;
     };
     union
@@ -331,7 +330,7 @@ private:
   int continue_range(active_thread *t, const Gcalc_heap::Info *p,
                      const Gcalc_heap::Info *p_next);
   int continue_i_range(active_thread *t,
-                       const Gcalc_heap::Intersection_info *ii);
+                       const Gcalc_heap::Info *ii);
   int end_couple(active_thread *t0, active_thread *t1, const Gcalc_heap::Info *p);
   int get_single_result(res_point *res, Gcalc_result_receiver *storage);
   int get_result_thread(res_point *cur, Gcalc_result_receiver *storage,
diff --git a/sql/item_geofunc.cc b/sql/item_geofunc.cc
index dd6914e5d66..c62978f37e2 100644
--- a/sql/item_geofunc.cc
+++ b/sql/item_geofunc.cc
@@ -1445,7 +1445,7 @@ longlong Item_func_issimple::val_int()
   Gcalc_operation_transporter trn(&func, &collector);
   Geometry *g;
   int result= 1;
-  const Gcalc_scan_iterator::point *ev;
+  const Gcalc_scan_iterator::event_point *ev;
 
   DBUG_ENTER("Item_func_issimple::val_int");
   DBUG_ASSERT(fixed == 1);
@@ -1669,7 +1669,7 @@ double Item_func_distance::val_real()
   bool above_cur_point, cur_point_edge;
   const Gcalc_scan_iterator::point *evpos;
   const Gcalc_heap::Info *cur_point, *dist_point;
-  const Gcalc_scan_iterator::point *ev;
+  const Gcalc_scan_iterator::event_point *ev;
   double t, distance, cur_distance;
   double x1, x2, y1, y2;
   double ex, ey, vx, vy, e_sqrlen;