diff options
| -rw-r--r-- | mysql-test/r/gis-precise.result | 12 | ||||
| -rw-r--r-- | mysql-test/r/gis.result | 4 | ||||
| -rw-r--r-- | sql/gcalc_slicescan.cc | 1326 | ||||
| -rw-r--r-- | sql/gcalc_slicescan.h | 179 | ||||
| -rw-r--r-- | sql/gcalc_tools.cc | 293 | ||||
| -rw-r--r-- | sql/gcalc_tools.h | 83 | ||||
| -rw-r--r-- | sql/item_geofunc.cc | 3 | ||||
| -rw-r--r-- | sql/spatial.cc | 2 |
8 files changed, 1572 insertions, 330 deletions
diff --git a/mysql-test/r/gis-precise.result b/mysql-test/r/gis-precise.result index c3f77f6680f..5adecfb5a35 100644 --- a/mysql-test/r/gis-precise.result +++ b/mysql-test/r/gis-precise.result @@ -189,7 +189,7 @@ st_touches(geomfromtext('polygon((0 0, 2 2, 0 4, 0 0))'), geomfromtext('point(1 0 select st_touches(geomfromtext('polygon((0 0, 2 2, 0 4, 0 0))'), geomfromtext('polygon((1 1.2, 1 0, 2 0, 1 1.2))')); st_touches(geomfromtext('polygon((0 0, 2 2, 0 4, 0 0))'), geomfromtext('polygon((1 1.2, 1 0, 2 0, 1 1.2))')) -1 +0 select st_touches(geomfromtext('polygon((0 0, 2 2, 0 4, 0 0))'), geomfromtext('polygon((1 1, 1 0, 2 0, 1 1))')); st_touches(geomfromtext('polygon((0 0, 2 2, 0 4, 0 0))'), geomfromtext('polygon((1 1, 1 0, 2 0, 1 1))')) 1 @@ -257,7 +257,7 @@ ST_NUMGEOMETRIES((ST_UNION(ST_UNION( MULTILINESTRINGFROMTEXT('MULTILINESTRING((2 0,4 2,0 2,1 5,0 3,7 0,8 5,5 8), (6 2,4 0,3 5,3 6,4 3,6 4,3 9,0 7,3 7,8 4,2 9,5 0), -176 +185 SELECT Round(ST_AREA(ST_BUFFER( ST_UNION( POLYGONFROMTEXT('POLYGON((7 7, 7 7, 7 4, 7 7, 7 7))'), POLYGONFROMTEXT('POLYGON((7 7, 4 7, 2 9, 7 6, 7 7))')), 1)), 6); @@ -338,7 +338,7 @@ MULTILINESTRINGFROMTEXT('MULTILINESTRING((3 4, 3 1, 2 7, 4 2, 6 2, 1 5))') ST_NUMPOINTS(ST_EXTERIORRING(ST_BUFFER(ST_UNION( MULTILINESTRINGFROMTEXT('MULTILINESTRING((3 4, 2 5, 7 6, 1 8),(0 0 ,1 6 ,0 1, 8 9, 2 4, 6 1, 3 5, 4 8), (9 3, 5 4, 1 8, 4 2, 5 8, 3 0))' ) , MULTILINESTRINGFROMTEXT('MULTILINESTRING((3 4, 3 1, 2 7, 4 2, 6 2 -280 +275 SELECT ST_NUMGEOMETRIES(ST_DIFFERENCE ( ST_UNION ( MULTILINESTRINGFROMTEXT( ' MULTILINESTRING( ( 2 4 , 5 0 , 2 9 , 6 2 , 0 2 ) , ( 4 3 , 5 6 , 9 4 , 0 7 , 7 2 , 2 0 , 8 2 ) , ( 5 0 , 1 5 , 3 7 , 7 7 ) , ( 2 3 , 9 5 , 2 0 , 8 1 ) , ( 0 9 , 9 3 , 2 8 , 8 1 , 9 4 ) ) ' ), @@ -354,7 +354,7 @@ MULTILINESTRINGFROMTEXT( ' MULTILINESTRING( ( 2 9 , 1 3 , 7 3 , 8 5 ) , ( 5 0 , ST_NUMGEOMETRIES(ST_DIFFERENCE ( ST_UNION ( MULTILINESTRINGFROMTEXT( ' MULTILINESTRING( ( 2 4 , 5 0 , 2 9 , 6 2 , 0 2 ) , ( 4 3 , 5 6 , 9 4 , 0 7 , 7 2 , 2 0 , 8 2 ) , ( 5 0 , 1 5 , 3 7 , 7 7 ) , ( 2 3 , 9 5 , 2 0 , 8 1 ) , ( 0 9 , 9 3 , 2 8 , 8 1 , 9 4 ) -126 +123 SELECT ST_NUMPOINTS(ST_EXTERIORRING(ST_BUFFER ( ST_UNION ( MULTILINESTRINGFROMTEXT( ' MULTILINESTRING( ( 7 3 , 1 8 , 4 0 , 7 9 ) , ( 5 4 , 9 8 , 7 4 , 3 7 ) , ( 5 8 , 5 4 , 9 2 , 5 6 ) , ( 4 0 , 3 2 , 0 1 , 3 9 ) , ( 2 0 , 3 5 , 9 5 , 0 9 ) ) ' ) , @@ -365,7 +365,7 @@ ST_NUMPOINTS(ST_EXTERIORRING(ST_BUFFER ( ST_UNION ( MULTILINESTRINGFROMTEXT( ' MULTILINESTRING( ( 7 3 , 1 8 , 4 0 , 7 9 ) , ( 5 4 , 9 8 , 7 4 , 3 7 ) , ( 5 8 , 5 4 , 9 2 , 5 6 ) , ( 4 0 , 3 2 , 0 1 , 3 9 ) , ( 2 0 , 3 5 , 9 5 , 0 9 ) ) ' ) , MULTILINESTRI -659 +653 SELECT ASTEXT(ST_DIFFERENCE ( POLYGONFROMTEXT( ' POLYGON( ( 2 2 , 2 8 , 8 8 , 8 2 , 2 2 ) , ( 4 4 , 4 6 , 6 6 , 6 4 , 4 4 ) ) ' ) , ST_UNION ( @@ -416,7 +416,7 @@ ST_DISTANCE ( ST_DIFFERENCE ( MULTIPOLYGONFR NULL SELECT ST_NUMGEOMETRIES( ST_SYMDIFFERENCE ( ST_SYMDIFFERENCE ( ST_INTERSECTION ( MULTILINESTRINGFROMTEXT( ' MULTILINESTRING( ( 6 4 , 3 7 , 9 4 , 3 8 ) , ( 2 2 , 2 9 , 1 2 , 9 8 ) ) ' ) , ST_SYMDIFFERENCE ( MULTIPOINTFROMTEXT( ' MULTIPOINT( 6 1 , 3 8 , 3 3 , 0 6 , 7 2 , 3 4 ) ' ) , ST_BUFFER ( ST_UNION ( MULTIPOLYGONFROMTEXT( ' MULTIPOLYGON( ( ( 2 2 , 6 2 , 1 3 , 2 2 , 2 2 ) ) ) ' ) , GEOMETRYFROMTEXT( ' MULTILINESTRING( ( 1 4 , 9 9 , 3 0 , 6 6 ) , ( 3 5 , 1 0 , 5 8 , 6 1 ) , ( 8 9 , 6 1 , 5 1 , 6 2 ) , ( 2 2 , 7 5 , 5 8 , 6 9 , 3 0 ) , ( 8 0 , 8 4 , 6 7 , 5 5 ) ) ' ) ) , NUMPOINTS( EXTERIORRING( POLYGONFROMTEXT( ' POLYGON( ( 0 0 , 2 1 , 8 2 , 0 0 ) ) ' ) ) ) ) ) ) , ST_INTERSECTION ( POLYGONFROMTEXT( ' POLYGON( ( 2 3, 5 7 , 3 7 , 4 1 , 0 5, 2 3 ) ) ' ) , MULTILINESTRINGFROMTEXT( ' MULTILINESTRING( ( 2 3 , 1 4 , 6 4 , 9 1 , 3 4 , 1 8 ) , ( 9 9 , 0 3 , 1 7 , 9 9 ) ) ' ) ) ) , POLYGONFROMTEXT( ' POLYGON( ( 1 3, 7 2 , 1 5 , 3 8 , 5 0, 1 3) ) ' ) ) ) ; ST_NUMGEOMETRIES( ST_SYMDIFFERENCE ( ST_SYMDIFFERENCE ( ST_INTERSECTION ( MULTILINESTRINGFROMTEXT( ' MULTILINESTRING( ( 6 4 , 3 7 , 9 4 , 3 8 ) , ( 2 2 , 2 9 , 1 2 , 9 8 ) ) ' ) , ST_SYMDIFFERENCE ( MULTIPOINTFROMTEXT( ' MULTIPOINT( 6 1 , 3 8 , 3 3 , 0 6 -27 +25 SELECT ASTEXT(ST_INTERSECTION( GEOMETRYFROMTEXT('GEOMETRYCOLLECTION(LINESTRING(7 7,5.33333333333333 7),LINESTRING(5.33333333333333 7,0 7,5 8,5.33333333333333 7),LINESTRING(5.33333333333333 7,7 2,7 7),POLYGON((0 5,3 5,3 2,1 2,1 1,3 1,3 0,0 0,0 3,2 3,2 4,0 4,0 5)))'), geomETRYFROMTEXT(' MULTILINESTRING( ( 5 1 , 3 7 , 6 1 , 7 0 ) , ( 1 6 , 8 5 , 7 5 , 5 6 ) )') )); ASTEXT(ST_INTERSECTION( GEOMETRYFROMTEXT('GEOMETRYCOLLECTION(LINESTRING(7 7,5.33333333333333 7),LINESTRING(5.33333333333333 7,0 7,5 8,5.33333333333333 7),LINESTRING(5.33333333333333 7,7 2,7 7),POLYGON((0 5,3 5,3 2,1 2,1 1,3 1,3 0,0 0,0 3,2 3,2 4,0 4,0 5)) MULTIPOINT(7 5,7 5.14285714285714,5.9 5.3,5.8 5.6,3 7) diff --git a/mysql-test/r/gis.result b/mysql-test/r/gis.result index b3993657182..190795855dd 100644 --- a/mysql-test/r/gis.result +++ b/mysql-test/r/gis.result @@ -850,7 +850,7 @@ mbroverlaps down,left,right,up SELECT GROUP_CONCAT(a2.name ORDER BY a2.name) AS mbrtouches FROM t1 a1 JOIN t1 a2 ON MBRTouches( a1.square, a2.square) WHERE a1.name = "center" GROUP BY a1.name; mbrtouches -big,center,down,down2,left,left2,right,right2,small,up,up2 +down2,left2,right2,up2 SELECT GROUP_CONCAT(a2.name ORDER BY a2.name) AS mbrwithin FROM t1 a1 JOIN t1 a2 ON MBRWithin( a1.square, a2.square) WHERE a1.name = "center" GROUP BY a1.name; mbrwithin big,center @@ -871,7 +871,7 @@ overlaps down,left,right,up SELECT GROUP_CONCAT(a2.name ORDER BY a2.name) AS touches FROM t1 a1 JOIN t1 a2 ON Touches( a1.square, a2.square) WHERE a1.name = "center" GROUP BY a1.name; touches -big,center,down,down2,left,left2,right,right2,small,up,up2 +down2,left2,right2,up2 SELECT GROUP_CONCAT(a2.name ORDER BY a2.name) AS within FROM t1 a1 JOIN t1 a2 ON Within( a1.square, a2.square) WHERE a1.name = "center" GROUP BY a1.name; within big,center diff --git a/sql/gcalc_slicescan.cc b/sql/gcalc_slicescan.cc index 6f41a5fc371..07120d2e87e 100644 --- a/sql/gcalc_slicescan.cc +++ b/sql/gcalc_slicescan.cc @@ -116,6 +116,450 @@ void Gcalc_dyn_list::reset() } +/* Internal coordinate operations implementations */ + +void Gcalc_internal_coord::set_zero() +{ + int n_res= 0; + do + { + digits[n_res++]= 0; + } while (n_res < n_digits); + sign= 0; +} + + +int Gcalc_internal_coord::is_zero() const +{ + int n_res= 0; + do + { + if (digits[n_res++] != 0) + return 0; + } while (n_res < n_digits); + return 1; +} + + +#ifdef GCALC_CHECK_WITH_FLOAT +long double Gcalc_internal_coord::get_double() const +{ + int n= 0; + long double res= 0.0; + do + { + res*= (long double) DIG_BASE; + res+= digits[n]; + } while(++n < n_digits); + + n= 0; + do + { + if (n & 1) + res/= (long double) C_SCALE; + } while(++n < n_digits); + + if (sign) + res*= -1.0; + return res; +} +#endif /*GCALC_CHECK_WITH_FLOAT*/ + + +static void do_add(Gcalc_internal_coord *result, + const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b) +{ + DBUG_ASSERT(a->n_digits == b->n_digits); + DBUG_ASSERT(a->n_digits == result->n_digits); + int n_digit= a->n_digits-1; + coord_digit_t carry= 0; + + do + { + if ((result->digits[n_digit]= + a->digits[n_digit] + b->digits[n_digit] + carry) >= DIG_BASE) + { + carry= 1; + result->digits[n_digit]-= DIG_BASE; + } + else + carry= 0; + } while (n_digit--); + DBUG_ASSERT(carry == 0); + result->sign= a->sign; +} + + +static void do_sub(Gcalc_internal_coord *result, + const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b) +{ + DBUG_ASSERT(a->n_digits == b->n_digits); + DBUG_ASSERT(a->n_digits == result->n_digits); + int n_digit= a->n_digits-1; + coord_digit_t carry= 0; + + do + { + if ((result->digits[n_digit]= + a->digits[n_digit] - b->digits[n_digit] - carry) < 0) + { + carry= 1; + result->digits[n_digit]+= DIG_BASE; + } + else + carry= 0; + } while (n_digit--); + DBUG_ASSERT(carry == 0); + if (a->sign && result->is_zero()) + result->sign= 0; + else + result->sign= a->sign; +} + + +static int do_cmp(const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b) +{ + DBUG_ASSERT(a->n_digits == b->n_digits); + int n_digit= 0; + + do + { + coord_digit_t d= a->digits[n_digit] - b->digits[n_digit]; + if (d > 0) + return 1; + if (d < 0) + return -1; + n_digit++; + } while (n_digit < a->n_digits); + + return 0; +} + + +#ifdef GCALC_CHECK_WITH_FLOAT +static int de_check(long double a, long double b) +{ + long double d= a - b; + if (d < (long double) 1e-6 && d > (long double) -1e-6) + return 1; + printf("xxx\n"); + return 0; +} + +static int de_check1(long double a, long double b) +{ + long double d= a - b; + if (d < (long double) 1e-6 && d > (long double) -1e-6) + return 1; + return 0; +} +static int de_weak(long double a, long double b) +{ + long double d= a - b; + if (d < (long double) 1 && d > (long double) -1) + return 1; + return 0; +} +#endif /*GCALC_CHECK_WITH_FLOAT*/ + + +void gcalc_mul_coord(Gcalc_internal_coord *result, + const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b) +{ + DBUG_ASSERT(result->n_digits == a->n_digits + b->n_digits); + int n_a, n_b, n_res; + coord_digit_t carry= 0; + + result->set_zero(); + if (a->is_zero() || b->is_zero()) + return; + + n_a= a->n_digits - 1; + do + { + n_b= b->n_digits - 1; + do + { + coord2 mul= ((coord2) a->digits[n_a]) * b->digits[n_b] + carry + + result->digits[n_a + n_b + 1]; + result->digits[n_a + n_b + 1]= mul % DIG_BASE; + carry= mul / DIG_BASE; + } while (n_b--); + if (carry) + { + for (n_res= n_a; (result->digits[n_res]+= carry) >= DIG_BASE; n_res--) + { + result->digits[n_res]-= DIG_BASE; + carry= 1; + } + carry= 0; + } + } while (n_a--); + result->sign= a->sign != b->sign; +#ifdef GCALC_CHECK_WITH_FLOAT + DBUG_ASSERT(de_check(a->get_double() * b->get_double(), + result->get_double())); +#endif /*GCALC_CHECK_WITH_FLOAT*/ +} + + +void gcalc_add_coord(Gcalc_internal_coord *result, + const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b) +{ + if (a->sign == b->sign) + do_add(result, a, b); + else + { + int cmp_res= do_cmp(a, b); + if (cmp_res == 0) + result->set_zero(); + else if (cmp_res > 0) + do_sub(result, a, b); + else + do_sub(result, b, a); + } +#ifdef GCALC_CHECK_WITH_FLOAT + DBUG_ASSERT(de_check(a->get_double() + b->get_double(), + result->get_double())); +#endif /*GCALC_CHECK_WITH_FLOAT*/ +} + + +void gcalc_sub_coord(Gcalc_internal_coord *result, + const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b) +{ + if (a->sign != b->sign) + do_add(result, a, b); + else + { + int cmp_res= do_cmp(a, b); + if (cmp_res == 0) + result->set_zero(); + else if (cmp_res > 0) + do_sub(result, a, b); + else + { + do_sub(result, b, a); + result->sign= 1 - result->sign; + } + } +#ifdef GCALC_CHECK_WITH_FLOAT + DBUG_ASSERT(de_check(a->get_double() - b->get_double(), + result->get_double())); +#endif /*GCALC_CHECK_WITH_FLOAT*/ +} + + +int gcalc_cmp_coord(const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b) +{ + int result; + if (a->sign != b->sign) + return a->sign ? -1 : 1; + result= a->sign ? do_cmp(b, a) : do_cmp(a, b); +#ifdef GCALC_CHECK_WITH_FLOAT + if (result == 0) + DBUG_ASSERT(de_check(a->get_double(), b->get_double())); + else if (result == 1) + DBUG_ASSERT(de_check1(a->get_double(), b->get_double()) || + a->get_double() > b->get_double()); + else + DBUG_ASSERT(de_check1(a->get_double(), b->get_double()) || + a->get_double() < b->get_double()); +#endif /*GCALC_CHECK_WITH_FLOAT*/ + return result; +} + + +int Gcalc_coord1::set_double(double d) +{ + double ds= d * C_SCALE; + init(); + if ((sign= ds < 0)) + ds= -ds; + c[0]= (coord_digit_t) (ds / (double) DIG_BASE); + c[1]= (coord_digit_t) (ds - ((double) c[0]) * DIG_BASE); +#ifdef GCALC_CHECK_WITH_FLOAT + DBUG_ASSERT(de_check(d, get_double())); +#endif /*GCALC_CHECK_WITH_FLOAT*/ + return 0; +} + + +void Gcalc_coord1::copy(const Gcalc_coord1 *from) +{ + c[0]= from->c[0]; + c[1]= from->c[1]; + sign= from->sign; +} + +/* Internal coordinates implementation end */ + + +Gcalc_heap::Info *Gcalc_heap::new_point_info(double x, double y, + gcalc_shape_info shape) +{ + Info *result= (Info *)new_item(); + if (!result) + return NULL; + *m_hook= result; + m_hook= &result->next; + m_n_points++; + result->x= x; + result->y= y; + result->shape= shape; + result->ix.set_double(x); + result->iy.set_double(y); + 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 +{ + coord_digit_t c[COORD_BASE*3]; + public: + void init() + { + n_digits= COORD_BASE*3; + digits= c; + } +}; + + +static void calc_t(Gcalc_coord2 *t_a, Gcalc_coord2 *t_b, + Gcalc_coord1 *b1x, + Gcalc_coord1 *b1y, + const Gcalc_heap::Info *p1, + const Gcalc_heap::Info *p2, + const Gcalc_heap::Info *p3, + const Gcalc_heap::Info *p4) +{ + Gcalc_coord1 a2_a1x, a2_a1y; + Gcalc_coord1 b2x, b2y; + Gcalc_coord2 x1y2, x2y1; + + a2_a1x.init(); + a2_a1y.init(); + x1y2.init(); + x2y1.init(); + t_a->init(); + t_b->init(); + b1y->init(); + b1x->init(); + b2x.init(); + b2y.init(); + + gcalc_sub_coord(&a2_a1x, &p3->ix, &p1->ix); + gcalc_sub_coord(&a2_a1y, &p3->iy, &p1->iy); + gcalc_sub_coord(b1x, &p2->ix, &p1->ix); + gcalc_sub_coord(b1y, &p2->iy, &p1->iy); + gcalc_sub_coord(&b2x, &p4->ix, &p3->ix); + gcalc_sub_coord(&b2y, &p4->iy, &p3->iy); + + gcalc_mul_coord(&x1y2, b1x, &b2y); + gcalc_mul_coord(&x2y1, &b2x, b1y); + gcalc_sub_coord(t_b, &x1y2, &x2y1); + + + gcalc_mul_coord(&x1y2, &a2_a1x, &b2y); + gcalc_mul_coord(&x2y1, &a2_a1y, &b2x); + gcalc_sub_coord(t_a, &x1y2, &x2y1); +} + + +inline void calc_t(Gcalc_coord2 *t_a, Gcalc_coord2 *t_b, + Gcalc_coord1 *b1x, + Gcalc_coord1 *b1y, + const Gcalc_heap::Intersection_info *isc) +{ + calc_t(t_a, t_b, b1x, b1y, isc->p1, isc->p2, isc->p3, isc->p4); +} + + +void Gcalc_heap::Intersection_info::calc_xy(double *x, double *y) const +{ + double b0_x= p2->x - p1->x; + double b0_y= p2->y - p1->y; + double b1_x= p4->x - p3->x; + double b1_y= p4->y - p3->y; + double b0xb1= b0_x * b1_y - b0_y * b1_x; + double t= (p3->x - p1->x) * b1_y - (p3->y - p1->y) * b1_x; + + t/= b0xb1; + + *x= p1->x + b0_x * t; + *y= p1->y + b0_y * t; +} + + +#ifdef GCALC_CHECK_WITH_FLOAT +void Gcalc_heap::Intersection_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; + long double b1_x= p4->x - p3->x; + long double b1_y= p4->y - p3->y; + long double b0xb1= b0_x * b1_y - b0_y * b1_x; + long double t= (p3->x - p1->x) * b1_y - (p3->y - p1->y) * b1_x; + long double cx, cy; + + t/= b0xb1; + + cx= (long double) p1->x + b0_x * t; + cy= (long double) p1->y + b0_y * t; + + Gcalc_coord2 t_a, t_b; + Gcalc_coord1 yb, xb; + Gcalc_coord3 m1, m2, sum; + + calc_t(&t_a, &t_b, &xb, &yb, this); + if (t_b.is_zero()) + { + *x= p1->x; + *y= p1->y; + return; + } + + m1.init(); + m2.init(); + sum.init(); + gcalc_mul_coord(&m1, &p1->ix, &t_b); + gcalc_mul_coord(&m2, &xb, &t_a); + gcalc_add_coord(&sum, &m1, &m2); + *x= sum.get_double() / t_b.get_double(); + + gcalc_mul_coord(&m1, &p1->iy, &t_b); + gcalc_mul_coord(&m2, &yb, &t_a); + gcalc_add_coord(&sum, &m1, &m2); + *y= sum.get_double() / t_b.get_double(); +} +#endif /*GCALC_CHECK_WITH_FLOAT*/ + + static inline void trim_node(Gcalc_heap::Info *node, Gcalc_heap::Info *prev_node) { if (!node) @@ -127,13 +571,21 @@ static inline void trim_node(Gcalc_heap::Info *node, Gcalc_heap::Info *prev_node } +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 int compare_point_info(const void *e0, const void *e1) { const Gcalc_heap::Info *i0= (const Gcalc_heap::Info *)e0; const Gcalc_heap::Info *i1= (const Gcalc_heap::Info *)e1; - if (!coord_eq(i0->y, i1->y)) - return i0->y > i1->y; - return i0->x > i1->x; + return cmp_point_info(i0, i1) > 0; } @@ -155,6 +607,7 @@ void Gcalc_heap::prepare_operation() void Gcalc_heap::reset() { +#ifdef TMP_BLOCK if (!m_hook) { m_hook= &m_first; @@ -164,10 +617,18 @@ void Gcalc_heap::reset() *m_hook= m_free; m_free= m_first; +#endif /*TMP_BLOCK*/ + if (m_n_points) + { + free_list(m_first); + free_list(m_first_intersection, m_intersection_hook); + m_intersection_hook= (Gcalc_dyn_list::Item **) &m_first_intersection; + m_n_points= 0; + } m_hook= &m_first; - m_n_points= 0; } + int Gcalc_shape_transporter::int_single_point(gcalc_shape_info Info, double x, double y) { @@ -229,6 +690,7 @@ void Gcalc_shape_transporter::int_complete() } +#ifdef TMP_BLOCK inline int GET_DX_DY(double *dxdy, const Gcalc_heap::Info *p0, const Gcalc_heap::Info *p1) { @@ -238,6 +700,13 @@ inline int GET_DX_DY(double *dxdy, (*dxdy/= dy)>DBL_MAX || (*dxdy)<-DBL_MAX; } +#endif /*TMP_BLOCK*/ +inline void calc_dx_dy(Gcalc_scan_iterator::point *p) +{ + gcalc_sub_coord(&p->dx, &p->next_pi->ix, &p->pi->ix); + gcalc_sub_coord(&p->dy, &p->next_pi->iy, &p->pi->iy); +} + Gcalc_scan_iterator::Gcalc_scan_iterator(size_t blk_size) : Gcalc_dyn_list(blk_size, @@ -268,14 +737,20 @@ void Gcalc_scan_iterator::init(Gcalc_heap *points) if (!(m_cur_pi= points->get_first())) return; + m_heap= points; 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; +#ifdef TMP_BLOCK next_state->y= m_cur_pi->y; +#endif /*TMP_BLOCK*/ + next_state->intersection_scan= 0; + next_state->pi= m_cur_pi; } void Gcalc_scan_iterator::reset() @@ -286,21 +761,36 @@ void Gcalc_scan_iterator::reset() } -void Gcalc_scan_iterator::point::copy_core(point *from) +void Gcalc_scan_iterator::point::copy_core(const point *from) { +#ifdef TMP_BLOCK dx_dy= from->dx_dy; horiz_dir= from->horiz_dir; +#endif /*TMP_BLOCK*/ pi= from->pi; next_pi= from->next_pi; thread= from->thread; + dx.copy(&from->dx); + dy.copy(&from->dy); #ifdef TO_REMOVE from->next_link= this; #endif /*TO_REMOVE*/ } -int Gcalc_scan_iterator::point::compare_dx_dy(int horiz_dir_a, double dx_dy_a, - int horiz_dir_b, double dx_dy_b) +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; +} +#ifdef TMP_BLOCK +int Gcalc_scan_iterator::point::cmp_dx_dy(int horiz_dir_a, double dx_dy_a, + int horiz_dir_b, double dx_dy_b) { if (!horiz_dir_a && !horiz_dir_b) { @@ -323,7 +813,169 @@ int Gcalc_scan_iterator::point::cmp_dx_dy(const point *p) const return p->is_bottom() ? 0 : -1; if (p->is_bottom()) return 1; - return compare_dx_dy(horiz_dir, dx_dy, p->horiz_dir, p->dx_dy); + return cmp_dx_dy(horiz_dir, dx_dy, p->horiz_dir, p->dx_dy); +} +#endif /*TMP_BLOCK*/ +int Gcalc_scan_iterator::point::cmp_dx_dy(const Gcalc_coord1 *dx_a, + const Gcalc_coord1 *dy_a, + const Gcalc_coord1 *dx_b, + const Gcalc_coord1 *dy_b) +{ + Gcalc_coord2 dx_a_dy_b; + Gcalc_coord2 dy_a_dx_b; + dx_a_dy_b.init(); + dy_a_dx_b.init(); + gcalc_mul_coord(&dx_a_dy_b, dx_a, dy_b); + gcalc_mul_coord(&dy_a_dx_b, dy_a, dx_b); + + return gcalc_cmp_coord(&dx_a_dy_b, &dy_a_dx_b); +} + + +int Gcalc_scan_iterator::point::cmp_dx_dy(const Gcalc_heap::Info *p1, + const Gcalc_heap::Info *p2, + const Gcalc_heap::Info *p3, + const Gcalc_heap::Info *p4) +{ + Gcalc_coord1 dx_a, dy_a, dx_b, dy_b; + dx_a.init(); + dx_b.init(); + dy_a.init(); + dy_b.init(); + gcalc_sub_coord(&dx_a, &p2->ix, &p1->ix); + gcalc_sub_coord(&dy_a, &p2->iy, &p1->iy); + gcalc_sub_coord(&dx_b, &p4->ix, &p3->ix); + gcalc_sub_coord(&dy_b, &p4->iy, &p3->iy); + return cmp_dx_dy(&dx_a, &dy_a, &dx_b, &dy_b); +} + + +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; + return cmp_dx_dy(&dx, &dy, &p->dx, &p->dy); +} + + +#ifdef GCALC_CHECK_WITH_FLOAT +void Gcalc_scan_iterator::point::calc_x(long double *x, long double y, + long double ix) const +{ + if (fabsl(dy.get_double()) < (long double) 1e-15) + { + *x= ix; + } + else + *x= (long double) pi->x + dx.get_double()/dy.get_double() * (y - pi->y); +} +#endif /*GCALC_CHECK_WITH_FLOAT*/ + + +static int cmp_sp_pi(const Gcalc_scan_iterator::point *sp, + const Gcalc_heap::Info *pi) +{ + 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) + DBUG_ASSERT(de_check1(sp->dy.get_double(), 0.0) || + de_check(sp_x, pi->x)); + if (result < 0) + DBUG_ASSERT(de_check1(sp->dy.get_double(), 0.0) || + de_check1(sp_x, pi->x) || + sp_x < pi->x); + if (result > 0) + DBUG_ASSERT(de_check1(sp->dy.get_double(), 0.0) || + de_check1(sp_x, pi->x) || + sp_x > pi->x); +#endif /*GCALC_CHECK_WITH_FLOAT*/ + return result; +} + + +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) +{ + Gcalc_coord2 x_dy, dx_ly, sum; + + x_dy.init(); + dx_ly.init(); + sum.init(); + result->init(); + + 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); +} + + +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; + + lya.init(); + lyb.init(); + gcalc_sub_coord(&lya, y, &a->pi->iy); + gcalc_sub_coord(&lyb, y, &b->pi->iy); + + calc_cmp_sp_sp_exp(&a_exp, a, b, &lya); + calc_cmp_sp_sp_exp(&b_exp, b, a, &lyb); + + 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) + DBUG_ASSERT(de_check(a_x, b_x)); + if (result < 0) + DBUG_ASSERT(de_check1(a_x, b_x) || a_x < b_x); + if (result > 0) + DBUG_ASSERT(de_check1(a_x, b_x) || a_x > b_x); +#endif /*GCALC_CHECK_WITH_FLOAT*/ + return result; +} + + +static int cmp_sp_sp(const Gcalc_scan_iterator::point *a, + const Gcalc_scan_iterator::point *b, + const Gcalc_heap::Info *pi) +{ + 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; } @@ -366,7 +1018,7 @@ int Gcalc_scan_iterator::arrange_event() continue; if (!(new_sp= new_slice_point())) return 1; - *new_sp= *sp; + new_sp->copy_all(sp); *ae_hook= new_sp; ae_hook= &new_sp->next; #ifdef TO_REMOVE @@ -420,10 +1072,12 @@ int Gcalc_scan_iterator::insert_top_point() sp0->pi= m_cur_pi; sp0->next_pi= m_cur_pi->left; sp0->thread= m_cur_thread++; +#ifdef TMP_BLOCK sp0->x= coord_to_float(m_cur_pi->x); +#endif /*TMP_BLOCK*/ if (m_cur_pi->left) { - sp0->horiz_dir= GET_DX_DY(&sp0->dx_dy, m_cur_pi, m_cur_pi->left); + calc_dx_dy(sp0); sp0->event= scev_thread; /*Now just to increase the size of m_slice0 to be same*/ @@ -436,15 +1090,13 @@ int Gcalc_scan_iterator::insert_top_point() if (!(sp1= new_slice_point())) return 1; sp1->event= sp0->event= scev_two_threads; -#ifdef TO_REMOVE - sp1->event_pair= sp0; - sp0->event_pair= sp1; -#endif /*TO_REMOVE*/ sp1->pi= m_cur_pi; sp1->next_pi= m_cur_pi->right; sp1->thread= m_cur_thread++; +#ifdef TMP_BLOCK sp1->x= sp0->x; - sp1->horiz_dir= GET_DX_DY(&sp1->dx_dy, m_cur_pi, m_cur_pi->right); +#endif /*TMP_BLOCK*/ + calc_dx_dy(sp1); /* We have two threads so should decide which one will be first */ if (sp0->cmp_dx_dy(sp1)>0) { @@ -463,17 +1115,20 @@ int Gcalc_scan_iterator::insert_top_point() else { sp0->event= scev_single_point; +#ifdef TMP_BLOCK sp0->horiz_dir= 0; sp0->dx_dy= 0.0; +#endif /*TMP_BLOCK*/ } /* We need to find the place to insert. */ - for (; sp && (sp->x < sp0->x); prev_hook= &sp->next, sp=sp->get_next()) + for (; sp && cmp_sp_pi(sp, m_cur_pi) < 0; + prev_hook= &sp->next, sp=sp->get_next()) {} next_state->event_position_hook= prev_hook; - if (sp && coord_eq(sp->x, sp0->x)) + if (sp && cmp_sp_pi(sp, m_cur_pi) == 0) { next_state->event_position= sp; do @@ -482,7 +1137,7 @@ int Gcalc_scan_iterator::insert_top_point() sp->event= scev_intersection; prev_hook= &sp->next; sp= sp->get_next(); - } while (sp && coord_eq(sp->x, sp0->x)); + } while (sp && cmp_sp_pi(sp, m_cur_pi) == 0); } else next_state->event_position= sp0; @@ -503,44 +1158,88 @@ int Gcalc_scan_iterator::insert_top_point() } +#ifndef NO_TESTING +const char *pev(int ev) +{ + switch (ev) + { + case scev_none: + return "n"; + case scev_thread: + return "t"; + case scev_two_threads: + return "tt"; + case scev_end: + return "e"; + case scev_two_ends: + return "ee"; + case scev_intersection: + return "i"; + case scev_point: + return "p"; + case scev_single_point: + return "sp"; + }; + return "fck"; +} +extern int ca_counter; +#endif /*NO_TESTING*/ int Gcalc_scan_iterator::normal_scan() { point *sp; Gcalc_dyn_list::Item **sp_hook; Gcalc_heap::Info *next_pi; - point *first_bottom_point= NULL; + point *first_bottom_point; if (m_next_is_top_point && insert_top_point()) return 1; for (next_pi= m_cur_pi->get_next(); - next_pi && - coord_eq(m_cur_pi->x, next_pi->x) && - coord_eq(m_cur_pi->y, next_pi->y); + next_pi && cmp_point_info(m_cur_pi, next_pi) == 0; next_pi= next_pi->get_next()) { - DBUG_ASSERT(coord_eq(next_state->event_position->x, next_pi->x)); 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()) { +#ifndef NO_TESTING + // if (ca_counter == 21) + printf("%s%d\t", pev(sp->event), sp->thread); +#endif /*NO_TESTING*/ if (sp->next_pi == next_pi) /* End of the segment */ { +#ifdef TMP_BLOCK sp->x= coord_to_float(next_pi->x); sp->pi= next_pi; +#endif /*TMP_BLOCK*/ + if (cmp_point_info(sp->pi, next_pi)) + sp->pi= next_pi; sp->next_pi= next_pi->left; m_next_is_top_point= false; if (next_pi->is_bottom()) { - if (first_bottom_point) + if (sp->event == scev_thread) + sp->event= scev_single_point; + else if (sp->event == scev_two_threads) + { + if (sp->get_next() && sp->get_next()->pi == sp->pi) + 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()); + DBUG_ASSERT(fnd_sp->pi == sp->pi); + fnd_sp->event= scev_thread; + } + sp->event= scev_single_point; + } + else if (first_bottom_point) { first_bottom_point->event= sp->event= scev_two_ends; -#ifdef TO_REMOVE - first_bottom_point->event_pair= sp; - sp->event_pair= first_bottom_point; -#endif /*TO_REMOVE*/ } else { @@ -550,21 +1249,52 @@ int Gcalc_scan_iterator::normal_scan() } else { - sp->event= scev_point; - sp->horiz_dir= GET_DX_DY(&sp->dx_dy, next_pi, next_pi->left); + 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 (coord_eq(sp->x, next_pi->x)) + else if (sp->event || (cmp_sp_pi(sp, next_pi) == 0)) { if (!sp->event) sp->event= scev_intersection; mark_event_position1(sp, sp_hook); } } +#ifndef NO_TESTING + //if (ca_counter == 21) + printf("\n"); +#endif /*NO_TESTING*/ m_cur_pi= next_pi; - if (m_next_is_top_point && insert_top_point()) - return 1; + if (m_next_is_top_point) + { + if (insert_top_point()) + 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); +#ifndef NO_TESTING + //if (ca_counter == 21) + printf("*%s%d\t", pev(next_state->slice->event), next_state->slice->thread); +#endif /*NO_TESTING*/ + for (sp= next_state->slice; sp->get_next(); sp= sp->get_next()) + { +#ifndef NO_TESTING + //if (ca_counter == 21) + printf("%s%d\t", pev(sp->get_next()->event), sp->get_next()->thread); +#endif /*NO_TESTING*/ + if (sp->get_next()->event) + mark_event_position1(sp->get_next(), &sp->next); + } +#ifndef NO_TESTING + //if (ca_counter == 21) + printf("\n"); +#endif /*NO_TESTING*/ + } } /* Swap current <-> next */ @@ -580,6 +1310,19 @@ int Gcalc_scan_iterator::normal_scan() point *sp0= current_state->slice; point *sp1= next_state->slice; point *prev_sp1= NULL; +#ifndef NO_TESTING + //if (ca_counter == 21) + { + point *sp= current_state->slice; + printf("After arrange\n"); + for (; sp; sp= sp->get_next()) + printf("%s%d\t", pev(sp->event), sp->thread); + printf("\nEvent\n"); + for (sp= m_events; sp; sp= sp->get_next()) + printf("%s%d\t", pev(sp->event), sp->thread); + printf("\n"); + } +#endif /*NO_TESTING*/ if (!(m_cur_pi= next_pi)) { @@ -592,8 +1335,12 @@ int Gcalc_scan_iterator::normal_scan() return 0; } + next_state->intersection_scan= 0; + next_state->pi= m_cur_pi; Gcalc_heap::Info *cur_pi= m_cur_pi; +#ifdef TMP_BLOCK next_state->y= coord_to_float(cur_pi->y); +#endif /*TMP_BLOCK*/ first_bottom_point= NULL; @@ -603,9 +1350,12 @@ int Gcalc_scan_iterator::normal_scan() for (; sp0; sp0= sp0->get_next()) { + DBUG_ASSERT(!sp0->is_bottom()); if (sp0->next_pi == cur_pi) /* End of the segment */ { +#ifdef TMP_BLOCK sp1->x= coord_to_float(cur_pi->x); +#endif /*TMP_BLOCK*/ sp1->pi= cur_pi; sp1->thread= sp0->thread; sp1->next_pi= cur_pi->left; @@ -625,16 +1375,12 @@ int Gcalc_scan_iterator::normal_scan() else { first_bottom_point->event= sp1->event= scev_two_ends; -#ifdef TO_REMOVE - sp1->event_pair= first_bottom_point; - first_bottom_point->event_pair= sp1; -#endif /*TO_REMOVE*/ } } else { sp1->event= scev_point; - sp1->horiz_dir= GET_DX_DY(&sp1->dx_dy, m_cur_pi, m_cur_pi->left); + calc_dx_dy(sp1); } mark_event_position1(sp1, prev_sp1 ? &prev_sp1->next : @@ -644,10 +1390,12 @@ int Gcalc_scan_iterator::normal_scan() { /* Cut current string with the height of the new point*/ sp1->copy_core(sp0); +#ifdef TMP_BLOCK sp1->x= sp1->horiz_dir ? coord_to_float(cur_pi->x) : (coord_to_float(sp1->pi->x) + (next_state->y-coord_to_float(sp1->pi->y)) * sp1->dx_dy); - if (coord_eq(sp1->x, cur_pi->x)) +#endif /*TMP_BLOCK*/ + if (cmp_sp_pi(sp1, cur_pi) == 0) { mark_event_position1(sp1, prev_sp1 ? &prev_sp1->next : @@ -659,7 +1407,7 @@ int Gcalc_scan_iterator::normal_scan() } intersections_found= intersections_found || - (prev_sp1 && prev_sp1->x > sp1->x); + (prev_sp1 && cmp_sp_sp(prev_sp1, sp1, cur_pi) > 0); prev_sp1= sp1; sp1= sp1->get_next(); @@ -674,6 +1422,16 @@ int Gcalc_scan_iterator::normal_scan() free_list(sp1); } +#ifndef NO_TESTING + //if (ca_counter == 21) + { + point *sp= next_state->slice; + printf("After slice\n"); + for (; sp; sp= sp->get_next()) + printf("%s%d\t", pev(sp->event), sp->thread); + printf("\n"); + } +#endif /*NO_TESTING*/ if (intersections_found) return handle_intersections(); @@ -681,16 +1439,20 @@ int Gcalc_scan_iterator::normal_scan() } -#define INTERSECTION_ZERO 0.000000000001 - +#ifndef NO_TESTING +int isc_counter= 0; +#endif /*NO_TESTING*/ 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(); if (!isc) return 1; + m_n_intersections++; **p_hook= isc; *p_hook= &isc->next; @@ -698,34 +1460,17 @@ int Gcalc_scan_iterator::add_intersection(int n_row, isc->thread_a= a->thread; isc->thread_b= b->thread; - /* intersection_normal */ - const point *a0= a->intersection_link; - const point *b0= b->intersection_link; - DBUG_ASSERT(!a0->horiz_dir || !b0->horiz_dir); - - if (!a0->horiz_dir && !b0->horiz_dir) + isc->ii= m_heap->new_intersection(a0->pi, a0->next_pi, + b0->pi, b0->next_pi); +#ifndef NO_TESTING + //if (isc_counter == 40) { - double b0_x= a0->next_pi->x - a0->pi->x; - double b0_y= a0->next_pi->y - a0->pi->y; - double b1_x= b0->next_pi->x - b0->pi->x; - double b1_y= b0->next_pi->y - b0->pi->y; - double b1xb0= b1_x * b0_y - b1_y * b0_x; - double t= (a0->pi->x - b0->pi->x) * b0_y - (a0->pi->y - b0->pi->y) * b0_x; - if (fabs(b1xb0) < INTERSECTION_ZERO) - { - isc->y= current_state->y; - isc->x= a0->x; - return 0; - } - - t/= b1xb0; - isc->x= b0->pi->x + b1_x*t; - isc->y= b0->pi->y + b1_y*t; - return 0; + long double ix, iy; + isc->ii->calc_xy_ld(&ix, &iy); + printf("%d\t%d\t%.20LG\t%.20LG\t%d\n", isc->thread_a, isc->thread_b, ix, iy, isc->n_row); } - isc->y= next_state->y; - isc->x= a0->horiz_dir ? b->x : a->x; - return 0; +#endif /*NO_TESTING*/ + return isc->ii == NULL; } @@ -733,6 +1478,10 @@ int Gcalc_scan_iterator::find_intersections() { Gcalc_dyn_list::Item **hook; +#ifndef NO_TESTING + ++isc_counter; + printf("Looking for intersections\n"); +#endif /*NO_TESTING*/ m_n_intersections= 0; { /* Set links between slicepoints */ @@ -743,6 +1492,15 @@ int Gcalc_scan_iterator::find_intersections() DBUG_ASSERT(!sp0->is_bottom()); DBUG_ASSERT(sp0->thread == sp1->thread); sp1->intersection_link= sp0; +#ifndef NO_TESTING + //if (isc_counter == 40) + { + long double spx, spx1; + sp0->calc_x(&spx, current_state->pi->y, current_state->pi->x); + sp1->calc_x(&spx1, m_cur_pi->y, m_cur_pi->x); + printf("%d\t%.20LG\t%.20LG\n", sp0->thread, spx, spx1); + } +#endif /*NO_TESTING*/ } } @@ -761,7 +1519,7 @@ int Gcalc_scan_iterator::find_intersections() point *s1= prev_s1->get_next(); if (!s1) break; - if (prev_s1->x <= s1->x) + if (cmp_sp_sp(prev_s1, s1, m_cur_pi) <= 0) { pprev_s1= (point **) &prev_s1->next; continue; @@ -783,19 +1541,250 @@ int Gcalc_scan_iterator::find_intersections() } -static int compare_intersections(const void *e0, const void *e1) +class Gcalc_coord4 : public Gcalc_internal_coord +{ + coord_digit_t c[COORD_BASE*4]; + public: + void init() + { + n_digits= COORD_BASE*4; + digits= c; + } +}; + +class Gcalc_coord5 : public Gcalc_internal_coord +{ + coord_digit_t c[COORD_BASE*5]; + public: + void init() + { + n_digits= 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); +} + + +#ifdef TMP_BLOCK +static void calc_aa1_b(Gcalc_coord2 *res, + const Gcalc_heap::Info *a0, + const Gcalc_heap::Info *a1, + const Gcalc_coord1 *xb, + const Gcalc_coord1 *yb) +{ + Gcalc_coord1 aa1_x, aa1_y; + Gcalc_coord2 p1, p2; + res->init(); + aa1_x.init(); + aa1_y.init(); + p1.init(); + p2.init(); + + gcalc_sub_coord(&aa1_x, &a1->ix, &a0->ix); + gcalc_sub_coord(&aa1_y, &a1->iy, &a0->iy); + gcalc_mul_coord(&p1, &aa1_x, yb); + gcalc_mul_coord(&p2, &aa1_y, xb); + gcalc_sub_coord(res, &p1, &p2); +} + + +static int cmp_intersections_y(const Gcalc_heap::Intersection_info *i1, + const Gcalc_heap::Intersection_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; + + 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); + + int 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) + DBUG_ASSERT(de_check(y1, y2)); + if (result < 0) + DBUG_ASSERT(de_check1(y1, y2) || y1 < y2); + if (result > 0) + DBUG_ASSERT(de_check1(y1, y2) || y1 > y2); +#endif /*GCALC_CHECK_WITH_FLOAT*/ + return result; +} + + +static int compare_intersections(const void *e1, const void *e2) { - Gcalc_scan_iterator::intersection *i0= (Gcalc_scan_iterator::intersection *)e0; Gcalc_scan_iterator::intersection *i1= (Gcalc_scan_iterator::intersection *)e1; + Gcalc_scan_iterator::intersection *i2= (Gcalc_scan_iterator::intersection *)e2; + int result= cmp_intersections_y(i1->ii, i2->ii); + if (result != 0) + return result > 0; + return (i1->n_row > i2->n_row); +} + +#endif /*TMP_BLOCK*/ + +#ifndef NO_TESTING +extern int ca_counter; +#endif /*NO_TESTING*/ +static int cmp_intersections(const Gcalc_heap::Intersection_info *i1, + const Gcalc_heap::Intersection_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) + DBUG_ASSERT(de_weak(y1, y2)); +#ifndef NO_TESTING + if (ca_counter == 7) + printf("77"); +#endif /*NO_TESTING*/ + if (result < 0) + DBUG_ASSERT(de_weak(y1, y2) || y1 < y2); + if (result > 0) + DBUG_ASSERT(de_weak(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) + DBUG_ASSERT(de_weak(x1, x2)); + if (result < 0) + DBUG_ASSERT(de_weak(x1, x2) || x1 < x2); + if (result > 0) + DBUG_ASSERT(de_weak(x1, x2) || x1 > x2); +#endif /*GCALC_CHECK_WITH_FLOAT*/ + return result; +} - if (fabs(i0->y - i1->y) > 0.00000000000001) - return i0->y > i1->y; +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); +} - if (i0->n_row != i1->n_row) - return i0->n_row > i1->n_row; - if (!coord_eq(i0->y, i1->y)) - return i0->y > i1->y; - return i0->x > i1->x; +inline int intersections_eq(const Gcalc_heap::Intersection_info *i1, + const Gcalc_heap::Intersection_info *i2) +{ + return cmp_intersections(i1, i2) == 0; +} + + +#ifdef TMP_BLOCK +static void calc_isc_sp_exp(Gcalc_coord4 *exp, + const Gcalc_coord2 *bb, + const Gcalc_coord1 *x1, + const Gcalc_coord1 *y1, + const Gcalc_coord1 *x2, + const Gcalc_coord1 *y2) +{ + Gcalc_coord2 p1, p2, sum; + p1.init(); + p2.init(); + sum.init(); + exp->init(); + + gcalc_mul_coord(&p1, x1, y1); + gcalc_mul_coord(&p2, x2, y2); + gcalc_add_coord(&sum, &p1, &p2); + gcalc_mul_coord(exp, bb, &sum); +} +#endif /*TMP_BLOCK*/ + + +static int sp_isc_eq(const Gcalc_scan_iterator::point *sp, + const Gcalc_heap::Intersection_info *isc) +{ + + Gcalc_coord4 exp_a, exp_b; + Gcalc_coord1 xb1, yb1; + Gcalc_coord2 t_a, t_b; + Gcalc_coord2 t_sp_a, t_sp_b; +#ifdef TMP_BLOCK + xa1a0.init(); + ya1a0.init(); + + gcalc_sub_coord(&xa1a0, &isc->p1->ix, &sp->pi->ix); + gcalc_sub_coord(&ya1a0, &isc->p1->iy, &sp->pi->iy); + calc_isc_sp_exp(&exp_a, &t_b, &sp->pi->ix, &ya1a0, &sp->pi->iy, &xa1a0); + calc_isc_sp_exp(&exp_b, &t_a, &sp->pi->iy, &isc->p1->ix, + &sp->pi->ix, &isc->p1->iy); + return gcalc_cmp_coord(&exp_a, &exp_b); +#endif /*TMP_BLOCK*/ + 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) + DBUG_ASSERT(de_check1(sp->dy.get_double(), 0.0) || + de_check(sp_x, int_x)); +#ifdef TMP_BLOCK + else + DBUG_ASSERT(!de_check1(sp_x, int_x)); +#endif /*TMP_BLOCK*/ +#endif /*GCALC_CHECK_WITH_FLOAT*/ + return result == 0; } @@ -823,6 +1812,18 @@ int Gcalc_scan_iterator::handle_intersections() /* We need the next slice to be just equal */ next_state->slice= new_slice(saved_state->slice); m_cur_intersection= m_intersections; +#ifndef NO_TESTING + //if (isc_counter == 40) + { + printf("Sorted\n"); + for (intersection *isc= m_intersections; isc; isc= isc->get_next()) + { + long double ix, iy; + isc->ii->calc_xy_ld(&ix, &iy); + printf("%d\t%d\t%.20LG\t%.20LG\t%d\n", isc->thread_a, isc->thread_b, ix, iy, isc->n_row); + } + } +#endif /*NO_TESTING*/ return intersection_scan(); } @@ -832,7 +1833,6 @@ int Gcalc_scan_iterator::intersection_scan() point *sp0, *sp1; Gcalc_dyn_list::Item **hook; intersection *next_intersection= NULL; - int met_equal= 0; if (m_cur_intersection != m_intersections) { @@ -846,31 +1846,72 @@ int Gcalc_scan_iterator::intersection_scan() if (arrange_event()) return 1; +#ifdef TMP_BLOCK if (!m_cur_intersection) { saved_state->event_position_hook= (Gcalc_dyn_list::Item **) &saved_state->slice; -#ifdef TO_REMOVE - for (sp0= current_state->slice, sp1= saved_state->slice; - sp0; - sp0= sp0->get_next(), sp1= sp1->get_next()) + + for (sp1= saved_state->slice; sp1; sp1= sp1->get_next()) { - sp0->next_link= sp1; if (sp1->get_next() == saved_state->event_position) saved_state->event_position_hook= &sp1->next; } -#endif /*TO_REMOVE*/ - for (sp1= saved_state->slice; sp1; sp1= sp1->get_next()) + /* Swap saved <-> next */ { - if (sp1->get_next() == saved_state->event_position) - saved_state->event_position_hook= &sp1->next; + slice_state *tmp= next_state; + next_state= saved_state; + saved_state= tmp; } + free_list(saved_state->slice); + saved_state->slice= NULL; + + free_list(m_intersections); + m_intersections= NULL; + return 0; + } +#endif /*TMP_BLOCK*/ + 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()); + 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 DBUG_OFF + sp0= current_state->slice; + sp1= next_state->slice; + for (; sp0; sp0= sp0->get_next(), sp1= sp1->get_next()) + DBUG_ASSERT(sp0->thread == sp1->thread); + DBUG_ASSERT(!sp1); +#endif /*DBUG_OFF*/ free_list(saved_state->slice); saved_state->slice= NULL; @@ -880,12 +1921,12 @@ int Gcalc_scan_iterator::intersection_scan() } } - next_state->y= m_cur_intersection->y; - 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()) @@ -893,27 +1934,20 @@ int Gcalc_scan_iterator::intersection_scan() if (sp0->thread == m_cur_intersection->thread_a || sp0->thread == m_cur_intersection->thread_b) { -#ifdef REACTIVATE_THIS DBUG_ASSERT(sp0->thread != m_cur_intersection->thread_a || - sp0->get_next()->thread == m_cur_intersection->thread_b); -#endif /*REACTIVATE_THIS*/ + sp0->get_next()->thread == m_cur_intersection->thread_b || + sp_isc_eq(sp0->get_next(), m_cur_intersection->ii)); sp1->copy_core(sp0); - sp1->x= m_cur_intersection->x; sp1->event= scev_intersection; mark_event_position1(sp1, hook); } else { sp1->copy_core(sp0); - sp1->x= sp1->horiz_dir ? - m_cur_intersection->x : - coord_to_float(sp1->pi->x) + - (next_state->y-coord_to_float(sp1->pi->y)) * sp1->dx_dy; - if (coord_eq(sp1->x, m_cur_intersection->x)) + if (sp_isc_eq(sp1, m_cur_intersection->ii)) { sp1->event= scev_intersection; mark_event_position1(sp1, hook); - met_equal= 1; } else sp1->event= scev_none; @@ -926,45 +1960,10 @@ int Gcalc_scan_iterator::intersection_scan() *hook= NULL; } - if (met_equal) - { - /* Remove superfluous intersections. */ - /* Double operations can produce unexact result, so it's needed. */ - for (sp0= next_state->event_position; - sp0 != *next_state->event_end_hook; - sp0= sp0->get_next()) - { - for (sp1= sp0->get_next(); - sp1 != *next_state->event_end_hook; - sp1= sp1->get_next()) - { - intersection *isc= m_cur_intersection; - while (isc->get_next()) - { - intersection *cur_isc= isc->get_next(); - if ((cur_isc->thread_a == sp0->thread && - cur_isc->thread_b == sp1->thread) || - (cur_isc->thread_a == sp1->thread && - cur_isc->thread_b == sp0->thread)) - { - /* The superfluous intersection should be close to the current. */ - DBUG_ASSERT(fabs(cur_isc->x-m_cur_intersection->x) + - fabs(cur_isc->y-m_cur_intersection->y) < - 0.00000000001); - isc->next= isc->next->next; - free_item(cur_isc); - } - else - isc= isc->get_next(); - } - } - } - } - + /* Now check equal intersections */ for (next_intersection= m_cur_intersection->get_next(); next_intersection && - coord_eq(next_intersection->x, m_cur_intersection->x) && - coord_eq(next_intersection->y, m_cur_intersection->y); + 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 */ @@ -990,5 +1989,58 @@ int Gcalc_scan_iterator::intersection_scan() return 0; } + +double Gcalc_scan_iterator::get_y() const +{ + if (current_state->intersection_scan) + { + double x, y; + current_state->isc->calc_xy(&x, &y); + return y; + } + else + return current_state->pi->y; +} + + +double Gcalc_scan_iterator::get_event_x() const +{ + if (current_state->intersection_scan) + { + double x, y; + current_state->isc->calc_xy(&x, &y); + return x; + } + else + return current_state->pi->x; +} + +double Gcalc_scan_iterator::get_h() const +{ + double cur_y= get_y(); + double next_y; + if (next_state->intersection_scan) + { + double x; + next_state->isc->calc_xy(&x, &next_y); + } + else + next_y= next_state->pi->y; + return next_y - cur_y; +} + + +double Gcalc_scan_iterator::get_sp_x(const point *sp) const +{ + double dy; + if (sp->event == scev_end | scev_two_ends | scev_point) + return sp->pi->x; + dy= sp->next_pi->y - sp->pi->y; + if (fabs(dy) < 1e-12) + return sp->pi->x; + return (sp->next_pi->x - sp->pi->x) * dy; +} + + #endif /* HAVE_SPATIAL */ diff --git a/sql/gcalc_slicescan.h b/sql/gcalc_slicescan.h index ebe2bcffe5c..d1c81ca4648 100644 --- a/sql/gcalc_slicescan.h +++ b/sql/gcalc_slicescan.h @@ -59,8 +59,11 @@ public: } inline void free_list(Item *list, Item **hook) { - *hook= m_free; - m_free= list; + if (*hook != list) + { + *hook= m_free; + m_free= list; + } } void free_list(Item *list) @@ -91,6 +94,79 @@ protected: } }; +/* Internal Gcalc coordinates to provide the precise calculations */ + +#define DIG_BASE 1000000000 +typedef int32 coord_digit_t; +typedef long long coord2; + +#define C_SCALE 1e13 +#define COORD_BASE 2 +#ifndef DBUG_OFF +//#define GCALC_CHECK_WITH_FLOAT +#define NO_TESTING +#else +#define NO_TESTING +#endif /*DBUG_OFF*/ + +class Gcalc_internal_coord +{ +public: + coord_digit_t *digits; + int sign; + int n_digits; + void set_zero(); + int is_zero() const; +#ifdef GCALC_CHECK_WITH_FLOAT + long double get_double() const; +#endif /*GCALC_CHECK_WITH_FLOAT*/ +}; + + +class Gcalc_coord1 : public Gcalc_internal_coord +{ + coord_digit_t c[COORD_BASE]; +public: + void init() + { + n_digits= COORD_BASE; + digits= c; + } + int set_double(double d); + void copy(const Gcalc_coord1 *from); +}; + + +class Gcalc_coord2 : public Gcalc_internal_coord +{ + coord_digit_t c[COORD_BASE*2]; +public: + void init() + { + n_digits= COORD_BASE*2; + digits= c; + } +}; + + +void gcalc_mul_coord(Gcalc_internal_coord *result, + const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b); + +void gcalc_add_coord(Gcalc_internal_coord *result, + const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b); + +void gcalc_sub_coord(Gcalc_internal_coord *result, + const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b); + +int gcalc_cmp_coord(const Gcalc_internal_coord *a, + const Gcalc_internal_coord *b); + +/* Internal coordinates declarations end. */ + + typedef uint gcalc_shape_info; /* @@ -114,27 +190,34 @@ public: 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; } }; + class Intersection_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; + void calc_xy(double *x, double *y) const; +#ifdef GCALC_CHECK_WITH_FLOAT + void calc_xy_ld(long double *x, long double *y) const; +#endif /*GCALC_CHECK_WITH_FLOAT*/ + }; Gcalc_heap(size_t blk_size=8192) : - Gcalc_dyn_list(blk_size, sizeof(Info)), m_hook(&m_first), m_n_points(0) {} - Info *new_point_info(double x, double y, gcalc_shape_info shape) - { - Info *result= (Info *)new_item(); - if (!result) - return NULL; - *m_hook= result; - m_hook= &result->next; - m_n_points++; - result->x= x; - result->y= y; - result->shape= shape; - return result; - } + 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) + {} + 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); void prepare_operation(); inline bool ready() const { return m_hook == NULL; } Info *get_first() { return (Info *)m_first; } @@ -145,6 +228,8 @@ 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; }; @@ -263,9 +348,13 @@ public: class point : public Gcalc_dyn_list::Item { public: +#ifdef TMP_BLOCK double x; double dx_dy; int horiz_dir; +#endif /*TMP_BLOCK*/ + Gcalc_coord1 dx; + Gcalc_coord1 dy; Gcalc_heap::Info *pi; Gcalc_heap::Info *next_pi; sc_thread_id thread; @@ -273,22 +362,32 @@ public: const point *intersection_link; Gcalc_scan_events event; #ifdef TO_REMOVE - const point *event_pair; point *next_link; #endif /*TO_REMOVE*/ inline const point *c_get_next() const { return (const point *)next; } - inline bool is_bottom() const { return pi->is_bottom(); } + inline bool is_bottom() const { return !next_pi; } 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(point *from); + 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 compare_dx_dy(int horiz_dir_a, double dx_dy_a, - int horiz_dir_b, double dx_dy_b); +#ifdef TMP_BLOCK + static int cmp_dx_dy(int horiz_dir_a, double dx_dy_a, + int horiz_dir_b, double dx_dy_b); +#endif /*TMP_BLOCK*/ + static int cmp_dx_dy(const Gcalc_coord1 *dx_a, + const Gcalc_coord1 *dy_a, + const Gcalc_coord1 *dx_b, + const Gcalc_coord1 *dy_b); + static int cmp_dx_dy(const Gcalc_heap::Info *p1, + const Gcalc_heap::Info *p2, + const Gcalc_heap::Info *p3, + const Gcalc_heap::Info *p4); int cmp_dx_dy(const point *p) const; int simple_event() const { @@ -298,6 +397,9 @@ public: #ifndef DBUG_OFF void dbug_print(); #endif /*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 @@ -306,8 +408,11 @@ public: int n_row; sc_thread_id thread_a; sc_thread_id thread_b; +#ifdef TMP_BLOCK double x; double y; +#endif /*TMP_BLOCK*/ + const Gcalc_heap::Intersection_info *ii; inline intersection *get_next() { return (intersection *)next; } }; @@ -318,7 +423,15 @@ public: 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; + }; +#ifdef TMP_BLOCK double y; +#endif /*TMP_BLOCK*/ slice_state() : slice(NULL) {} void clear_event_position() { @@ -350,10 +463,24 @@ public: { 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; } - inline double get_h() const { return current_state->y - next_state->y; } - inline double get_y() const { return current_state->y; } + 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; } + 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; + } private: + Gcalc_heap *m_heap; Gcalc_heap::Info *m_cur_pi; slice_state state0, state1, state_s; slice_state *current_state; @@ -382,7 +509,10 @@ private: } point *new_slice_point() { - return (point *)new_item(); + point *new_point= (point *)new_item(); + new_point->dx.init(); + new_point->dy.init(); + return new_point; } point *new_slice(point *example); int arrange_event(); @@ -450,7 +580,6 @@ public: inline const Gcalc_scan_iterator::point *point() const { return sp; } inline const Gcalc_heap::Info *get_pi() const { return sp->pi; } inline gcalc_shape_info get_shape() const { return sp->get_shape(); } - inline double get_x() const { return sp->x; } inline void restart(const Gcalc_scan_iterator *scan_i) { sp= scan_i->get_b_slice(); } }; diff --git a/sql/gcalc_tools.cc b/sql/gcalc_tools.cc index baff6278444..90c39f08d0b 100644 --- a/sql/gcalc_tools.cc +++ b/sql/gcalc_tools.cc @@ -347,6 +347,10 @@ int Gcalc_result_receiver::add_point(double x, double y) buffer.q_append(prev_y); prev_x= x; prev_y= y; +#ifndef NO_TESTING + if (n_points == 53) + printf("xxx\n"); +#endif /*NO_TESTING*/ return 0; } @@ -488,6 +492,9 @@ int Gcalc_result_receiver::move_hole(uint32 dest_position, uint32 source_positio Gcalc_operation_reducer::Gcalc_operation_reducer(size_t blk_size) : Gcalc_dyn_list(blk_size, sizeof(res_point)), +#ifndef DBUG_OFF + n_res_points(0), +#endif /*DBUG_OFF*/ m_res_hook((Gcalc_dyn_list::Item **)&m_result), m_first_active_thread(NULL) {} @@ -514,9 +521,73 @@ Gcalc_operation_reducer(Gcalc_function *fn, modes mode, size_t blk_size) : } -inline int Gcalc_operation_reducer::continue_range(active_thread *t, - const Gcalc_heap::Info *p, - int horiz_dir, double dx_dy) +void Gcalc_operation_reducer::res_point::set(const Gcalc_scan_iterator *si) +{ + if ((intersection_point= si->intersection_step())) + ii= si->get_cur_ii(); + else + pi= si->get_cur_pi(); +} + +#ifndef NO_TESTING +void call_checkpoint(int d) +{ + printf("%d\n", d); +} +#endif /*NO_TESTING*/ + +Gcalc_operation_reducer::res_point * + Gcalc_operation_reducer::add_res_point(Gcalc_function::shape_type type) +{ + res_point *result= (res_point *)new_item(); + *m_res_hook= result; + result->prev_hook= m_res_hook; + m_res_hook= &result->next; + result->type= type; +#ifndef DBUG_OFF + result->point_n= n_res_points++; +#endif /*DBUG_OFF*/ +#ifndef NO_TESTING + if (result->point_n == 74) + call_checkpoint(74); +#endif /*NO_TESTING*/ + return result; +} + +int Gcalc_operation_reducer::add_line(int incoming, active_thread *t, + const Gcalc_scan_iterator::point *p) +{ + line *l= new_line(); + if (!l) + return 1; + l->incoming= incoming; + l->t= t; + l->p= p; + *m_lines_hook= l; + m_lines_hook= &l->next; + return 0; +} + + +int Gcalc_operation_reducer::add_poly_border(int incoming, + active_thread *t, int prev_state, const Gcalc_scan_iterator::point *p) +{ + poly_border *b= new_poly_border(); + if (!b) + return 1; + b->incoming= incoming; + b->t= t; + b->prev_state= prev_state; + b->p= p; + *m_poly_borders_hook= b; + m_poly_borders_hook= &b->next; + return 0; +} + + +int Gcalc_operation_reducer::continue_range(active_thread *t, + const Gcalc_heap::Info *p, + const Gcalc_heap::Info *p_next) { res_point *rp= add_res_point(t->rp->type); if (!rp) @@ -527,15 +598,14 @@ inline int Gcalc_operation_reducer::continue_range(active_thread *t, rp->intersection_point= false; rp->pi= p; t->rp= rp; - t->horiz_dir= horiz_dir; - t->dx_dy= dx_dy; + t->p1= p; + t->p2= p_next; return 0; } inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, - double x, double y, - int horiz_dir, double dx_dy) + const Gcalc_heap::Intersection_info *ii) { res_point *rp= add_res_point(t->rp->type); if (!rp) @@ -544,11 +614,8 @@ inline int Gcalc_operation_reducer::continue_i_range(active_thread *t, rp->down= t->rp; t->rp->up= rp; rp->intersection_point= true; - rp->x= x; - rp->y= y; + rp->ii= ii; t->rp= rp; - t->horiz_dir= horiz_dir; - t->dx_dy= dx_dy; return 0; } @@ -573,6 +640,9 @@ int Gcalc_operation_reducer::end_couple(active_thread *t0, active_thread *t1, } +#ifndef NO_TESTING +int ca_counter= 0; +#endif /*NO_TESTING*/ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { Gcalc_point_iterator pi(si); @@ -587,8 +657,16 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) active_thread *bottom_threads= NULL; active_thread *eq_thread, *point_thread;; +#ifndef NO_TESTING + if (ca_counter == 11522) + call_checkpoint(89); +#endif /*NO_TESTING*/ m_fn->clear_state(); /* Walk to the event, remembering what is needed. */ +#ifndef NO_TESTING + if (si->get_event_position() == pi.point()) + printf("yyy\n"); +#endif /*NO_TESTING*/ for (; pi.point() != si->get_event_position(); ++pi, cur_t_hook= (active_thread **) &(*cur_t_hook)->next) { @@ -612,13 +690,13 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) case scev_point: { if (cur_t->enabled() && - continue_range(cur_t, events->pi, events->horiz_dir, events->dx_dy)) + continue_range(cur_t, events->pi, events->next_pi)) return 1; break; } case scev_end: { - if (cur_t->enabled() && end_line(cur_t, events->pi, si)) + if (cur_t->enabled() && end_line(cur_t, si)) return 1; *cur_t_hook= cur_t->get_next(); free_item(cur_t); @@ -635,8 +713,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) else if (cur_t->enabled() || cur_t->get_next()->enabled()) { /* Rare case when edges of a polygon coincide */ - if (end_line(cur_t->enabled() ? cur_t : cur_t->get_next(), - events->pi, si)) + if (end_line(cur_t->enabled() ? cur_t : cur_t->get_next(), si)) return 1; } *cur_t_hook= cur_t->get_next()->get_next(); @@ -647,6 +724,9 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) default: DBUG_ASSERT(0); } +#ifndef NO_TESTING + goto testing; +#endif /*NO_TESTING*/ return 0; } @@ -773,7 +853,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) for (events= si->get_events(); events; events= events->get_next()) m_fn->set_on_state(events->get_shape()); - return m_fn->count() ? add_single_point(event_point, si) : 0; + return m_fn->count() ? add_single_point(si) : 0; } if (m_poly_borders) @@ -783,6 +863,10 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { poly_border *pb1, *pb2; pb1= m_poly_borders; +#ifndef NO_TESTING + if (!m_poly_borders->next) + call_checkpoint(3); +#endif /*NO_TESTING*/ DBUG_ASSERT(m_poly_borders->next); pb2= get_pair_border(pb1); @@ -790,8 +874,7 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) m_poly_borders= pb1->get_next(); if (connect_threads(pb1->incoming, pb2->incoming, pb1->t, pb2->t, pb1->p, pb2->p, - prev_range, event_point, si, - Gcalc_function::shape_polygon)) + prev_range, si, Gcalc_function::shape_polygon)) return 1; free_item(pb1); @@ -809,8 +892,8 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { if (connect_threads(m_lines->incoming, m_lines->get_next()->incoming, m_lines->t, m_lines->get_next()->t, - m_lines->p, m_lines->get_next()->p, NULL, - event_point, si, Gcalc_function::shape_line)) + m_lines->p, m_lines->get_next()->p, + NULL, si, Gcalc_function::shape_line)) return 1; } else @@ -819,11 +902,11 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) { if (cur_line->incoming) { - if (end_line(cur_line->t, event_point, si)) + if (end_line(cur_line->t, si)) return 1; } else - start_line(cur_line->t, cur_line->p, event_point, si); + start_line(cur_line->t, cur_line->p, si); } } free_list(m_lines); @@ -834,28 +917,56 @@ int Gcalc_operation_reducer::count_slice(Gcalc_scan_iterator *si) if (bottom_threads) free_list(bottom_threads); +#ifndef NO_TESTING +testing: + { + Gcalc_point_iterator x_pi(si); + active_thread **x_cur_t_hook= &m_first_active_thread; + int x_prev_state= 0; + m_fn->save_states(); + m_fn->clear_state(); + if (ca_counter == /*11552*/90) + call_checkpoint(10); + for (; x_pi.point(); ++x_pi) + { + active_thread *cur_t= *x_cur_t_hook; + if (cur_t->enabled() && + cur_t->rp->type == Gcalc_function::shape_polygon) + x_prev_state^= 1; + int ppb= m_fn->count(); + if (m_fn->get_shape_kind(x_pi.get_shape()) == Gcalc_function::shape_polygon) + m_fn->invert_state(x_pi.get_shape()); + int ppa= m_fn->count(); + if (ppa != x_prev_state) + { + if (x_pi.point()->cmp_dx_dy(x_pi.point()->get_next()) != 0) + call_checkpoint(21); + } + if (cur_t->enabled()) + { + if (m_fn->get_shape_kind(x_pi.get_shape()) == Gcalc_function::shape_polygon) + if (ppa == ppb) + call_checkpoint(22); + else + if (ppa != 0 && ppb != 0) + call_checkpoint(23); + } + x_cur_t_hook= (active_thread **) &(*x_cur_t_hook)->next; + } + m_fn->restore_states(); + } +#endif /*NO_TESTING*/ return 0; } -int Gcalc_operation_reducer::add_single_point(const Gcalc_heap::Info *p, - const Gcalc_scan_iterator *si) +int Gcalc_operation_reducer::add_single_point(const Gcalc_scan_iterator *si) { res_point *rp= add_res_point(Gcalc_function::shape_point); if (!rp) return 1; rp->glue= rp->up= rp->down= NULL; - if (p) - { - rp->intersection_point= false; - rp->pi= p; - } - else - { - rp->intersection_point= true; - rp->y= si->get_y(); - rp->x= si->get_events()->x; - } + rp->set(si); return 0; } @@ -912,7 +1023,7 @@ int Gcalc_operation_reducer::connect_threads( int incoming_a, int incoming_b, active_thread *ta, active_thread *tb, const Gcalc_scan_iterator::point *pa, const Gcalc_scan_iterator::point *pb, - active_thread *prev_range, const Gcalc_heap::Info *ev_p, + active_thread *prev_range, const Gcalc_scan_iterator *si, Gcalc_function::shape_type s_t) { if (incoming_a && incoming_b) @@ -929,18 +1040,8 @@ int Gcalc_operation_reducer::connect_threads( rpa->up= rpb->up= NULL; ta->rp->up= rpa; tb->rp->up= rpb; - if (ev_p) - { - rpa->intersection_point= rpb->intersection_point= false; - rpa->pi= rpb->pi= ev_p; - } - else - { - rpa->intersection_point= rpb->intersection_point= true; - rpa->x= rpb->x= si->get_events()->x; - rpa->y= rpb->y= si->get_y(); - } - + rpa->set(si); + rpb->set(si); ta->rp= tb->rp= NULL; return 0; } @@ -953,35 +1054,30 @@ int Gcalc_operation_reducer::connect_threads( return 1; rp0->glue= rp1; rp1->glue= rp0; - if (ev_p) - { - rp0->intersection_point= rp1->intersection_point= false; - rp0->pi= rp1->pi= ev_p; - } - else - { - rp0->intersection_point= rp1->intersection_point= true; - rp0->x= rp1->x= si->get_events()->x; - rp0->y= rp1->y= si->get_y(); - } + rp0->set(si); + rp1->set(si); rp0->down= rp1->down= NULL; ta->rp= rp0; tb->rp= rp1; - ta->horiz_dir= pa->horiz_dir; - ta->dx_dy= pa->dx_dy; + ta->p1= pa->pi; + ta->p2= pa->next_pi; - tb->horiz_dir= pb->horiz_dir; - tb->dx_dy= pb->dx_dy; + tb->p1= pb->pi; + tb->p2= pb->next_pi; if (prev_range) { rp0->outer_poly= prev_range->thread_start; tb->thread_start= prev_range->thread_start; + /* Chack if needed */ + ta->thread_start= prev_range->thread_start; } else { rp0->outer_poly= 0; ta->thread_start= rp0; + /* Chack if needed */ + tb->thread_start= rp0; } return 0; } @@ -991,20 +1087,18 @@ int Gcalc_operation_reducer::connect_threads( tb->rp= ta->rp; tb->thread_start= ta->thread_start; if (Gcalc_scan_iterator::point:: - compare_dx_dy(ta->horiz_dir, ta->dx_dy, - pb->horiz_dir, pb->dx_dy) != 0) + cmp_dx_dy(ta->p1, ta->p2, pb->pi, pb->next_pi) != 0) { - if (ev_p ? continue_range(tb, ev_p, pb->horiz_dir, pb->dx_dy): - continue_i_range(tb, - si->get_events()->x, si->get_y(), - pb->horiz_dir, pb->dx_dy)) + if (si->intersection_step() ? + continue_i_range(tb, si->get_cur_ii()) : + continue_range(tb, si->get_cur_pi(), pb->next_pi)) +#ifdef TMP_BLOCK + continue_range(tb, si->get_cur_pi()) +#endif /*TMP_BLOCK*/ return 1; } - else - { - tb->horiz_dir= pb->horiz_dir; - tb->dx_dy= pb->dx_dy; - } + tb->p1= pb->pi; + tb->p2= pb->next_pi; return 0; } @@ -1012,33 +1106,21 @@ int Gcalc_operation_reducer::connect_threads( int Gcalc_operation_reducer::start_line(active_thread *t, const Gcalc_scan_iterator::point *p, - const Gcalc_heap::Info *ev_p, const Gcalc_scan_iterator *si) { res_point *rp= add_res_point(Gcalc_function::shape_line); if (!rp) return 1; rp->glue= rp->down= NULL; - if (ev_p) - { - rp->intersection_point= false; - rp->pi= ev_p; - } - else - { - rp->intersection_point= true; - rp->x= si->get_events()->x; - rp->y= si->get_y(); - } + rp->set(si); t->rp= rp; - t->horiz_dir= p->horiz_dir; - t->dx_dy= p->dx_dy; + t->p1= p->pi; + t->p2= p->next_pi; return 0; } int Gcalc_operation_reducer::end_line(active_thread *t, - const Gcalc_heap::Info *ev_p, const Gcalc_scan_iterator *si) { DBUG_ASSERT(t->rp->type == Gcalc_function::shape_line); @@ -1047,17 +1129,7 @@ int Gcalc_operation_reducer::end_line(active_thread *t, return 1; rp->glue= rp->up= NULL; rp->down= t->rp; - if (ev_p) - { - rp->intersection_point= false; - rp->pi= ev_p; - } - else - { - rp->intersection_point= true; - rp->x= si->get_events()->x; - rp->y= si->get_y(); - } + rp->set(si); t->rp->up= rp; t->rp= NULL; @@ -1071,6 +1143,11 @@ int Gcalc_operation_reducer::count_all(Gcalc_heap *hp) si.init(hp); while (si.more_points()) { +#ifndef NO_TESTING + printf("Point %d\n", ++ca_counter); + if (ca_counter == 12) + call_checkpoint(10); +#endif /*NO_TESTING*/ if (si.step()) return 1; if (count_slice(&si)) @@ -1094,8 +1171,9 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res, { if (res->intersection_point) { - if (storage->single_point(float_to_coord(res->x), - float_to_coord(res->y))) + double x, y; + res->ii->calc_xy(&x, &y); + if (storage->single_point(x,y)) return 1; } else @@ -1105,6 +1183,9 @@ inline int Gcalc_operation_reducer::get_single_result(res_point *res, return 0; } +#ifndef NO_TESTING +int pc_counter= 0; +#endif /*NO_TESTING*/ int Gcalc_operation_reducer::get_result_thread(res_point *cur, Gcalc_result_receiver *storage, @@ -1116,12 +1197,16 @@ int Gcalc_operation_reducer::get_result_thread(res_point *cur, double x, y; while (cur) { +#ifndef NO_TESTING + ++pc_counter; + if (pc_counter == 79) + call_checkpoint(79); +#endif /*NO_TESTING*/ if (!glue_step) { if (cur->intersection_point) { - x= float_to_coord(cur->x); - y= float_to_coord(cur->y); + cur->ii->calc_xy(&x, &y); } else { diff --git a/sql/gcalc_tools.h b/sql/gcalc_tools.h index da7be1d9fa7..39704dfeb56 100644 --- a/sql/gcalc_tools.h +++ b/sql/gcalc_tools.h @@ -206,26 +206,37 @@ public: int get_result(Gcalc_result_receiver *storage); void reset(); +#ifndef DBUG_OFF + int n_res_points; +#endif /*DBUG_OFF*/ class res_point : public Gcalc_dyn_list::Item { public: - bool intersection_point; - double x,y; - res_point *up; - res_point *down; - res_point *glue; - Gcalc_function::shape_type type; + int intersection_point; union { const Gcalc_heap::Info *pi; + const Gcalc_heap::Intersection_info *ii; res_point *first_poly_node; }; +#ifdef TMP_BLOCK union { +#endif /*TMP_BLOCK*/ res_point *outer_poly; uint32 poly_position; +#ifdef TMP_BLOCK }; +#endif /*TMP_BLOCK*/ + res_point *up; + res_point *down; + res_point *glue; + Gcalc_function::shape_type type; Gcalc_dyn_list::Item **prev_hook; +#ifndef DBUG_OFF + int point_n; +#endif /*DBUG_OFF*/ + void set(const Gcalc_scan_iterator *si); res_point *get_next() { return (res_point *)next; } }; @@ -233,9 +244,9 @@ public: { public: res_point *rp; - int horiz_dir; - double dx_dy; res_point *thread_start; + + const Gcalc_heap::Info *p1, *p2; res_point *enabled() { return rp; } active_thread *get_next() { return (active_thread *)next; } }; @@ -273,33 +284,9 @@ public: line *new_line() { return (line *) new_item(); } poly_border *new_poly_border() { return (poly_border *) new_item(); } int add_line(int incoming, active_thread *t, - const Gcalc_scan_iterator::point *p) - { - line *l= new_line(); - if (!l) - return 1; - l->incoming= incoming; - l->t= t; - l->p= p; - *m_lines_hook= l; - m_lines_hook= &l->next; - return 0; - } - + const Gcalc_scan_iterator::point *p); int add_poly_border(int incoming, active_thread *t, int prev_state, - const Gcalc_scan_iterator::point *p) - { - poly_border *b= new_poly_border(); - if (!b) - return 1; - b->incoming= incoming; - b->t= t; - b->prev_state= prev_state; - b->p= p; - *m_poly_borders_hook= b; - m_poly_borders_hook= &b->next; - return 0; - } + const Gcalc_scan_iterator::point *p); protected: Gcalc_function *m_fn; @@ -310,43 +297,29 @@ protected: res_point *result_heap; active_thread *m_first_active_thread; - res_point *add_res_point(Gcalc_function::shape_type type) - { - res_point *result= (res_point *)new_item(); - *m_res_hook= result; - result->prev_hook= m_res_hook; - m_res_hook= &result->next; - result->type= type; - return result; - } - + res_point *add_res_point(Gcalc_function::shape_type type); active_thread *new_active_thread() { return (active_thread *)new_item(); } poly_instance *new_poly() { return (poly_instance *) new_item(); } private: int start_line(active_thread *t, const Gcalc_scan_iterator::point *p, - const Gcalc_heap::Info *ev_p, const Gcalc_scan_iterator *si); - int end_line(active_thread *t, const Gcalc_heap::Info *ev_p, - const Gcalc_scan_iterator *si); + const Gcalc_scan_iterator *si); + int end_line(active_thread *t, const Gcalc_scan_iterator *si); int connect_threads(int incoming_a, int incoming_b, active_thread *ta, active_thread *tb, const Gcalc_scan_iterator::point *pa, const Gcalc_scan_iterator::point *pb, active_thread *prev_range, - const Gcalc_heap::Info *ev_p, const Gcalc_scan_iterator *si, Gcalc_function::shape_type s_t); - int add_single_point(const Gcalc_heap::Info *p, - const Gcalc_scan_iterator *si); + int add_single_point(const Gcalc_scan_iterator *si); poly_border *get_pair_border(poly_border *b1); int continue_range(active_thread *t, const Gcalc_heap::Info *p, - int horiz_dir, double dx_dy); - int continue_i_range(active_thread *t, double x, double y, - int horiz_dir, double dx_dy); + const Gcalc_heap::Info *p_next); + int continue_i_range(active_thread *t, + const Gcalc_heap::Intersection_info *ii); int end_couple(active_thread *t0, active_thread *t1, const Gcalc_heap::Info *p); - int add_single_point(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, int move_upward, res_point *first_poly_node); diff --git a/sql/item_geofunc.cc b/sql/item_geofunc.cc index 631b63812b5..2c3facb49c8 100644 --- a/sql/item_geofunc.cc +++ b/sql/item_geofunc.cc @@ -867,7 +867,8 @@ int Item_func_spatial_rel::func_touches() if (cur_func) { area= scan_it.get_h() * - ((ti.rb()->x - ti.lb()->x) + (ti.rt()->x - ti.lt()->x)); + ((scan_it.get_sp_x(ti.rb()) - scan_it.get_sp_x(ti.lb())) + + (scan_it.get_sp_x(ti.rt()) - scan_it.get_sp_x(ti.lt()))); if (area > GIS_ZERO) { result= 0; diff --git a/sql/spatial.cc b/sql/spatial.cc index 67e36ccb12b..0e535d11056 100644 --- a/sql/spatial.cc +++ b/sql/spatial.cc @@ -2230,6 +2230,8 @@ bool Gis_geometry_collection::get_mbr(MBR *mbr, const char **end) const return 1; n_objects= uint4korr(data); data+= 4; + if (n_objects == 0) + return 1; while (n_objects--) { |