From c60e23feb16a8745eaa6d213a89f61ded5707731 Mon Sep 17 00:00:00 2001 From: Martin Robinson Date: Wed, 13 Mar 2013 17:19:19 -0700 Subject: path: Fix a bug in line intersection Before the intersection code was not taking into account that both quotients are required to be in the range (0,1) for the segments to intersect or handling the case of negative numerators and denominators. --- src/cairo-path-fixed.c | 39 +++++++++++++++++++++++++++------------ 1 file changed, 27 insertions(+), 12 deletions(-) diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c index 10a65159..14913fd0 100644 --- a/src/cairo-path-fixed.c +++ b/src/cairo-path-fixed.c @@ -1300,7 +1300,7 @@ _cairo_path_fixed_is_box (const cairo_path_fixed_t *path, } /* Determine whether two lines A->B and C->D intersect based on the - * algorithm described here: http://paulbourke.net/geometry/lineline2d/ */ + * algorithm described here: http://paulbourke.net/geometry/pointlineplane/ */ static inline cairo_bool_t _lines_intersect_or_are_coincident (cairo_point_t a, cairo_point_t b, @@ -1308,6 +1308,7 @@ _lines_intersect_or_are_coincident (cairo_point_t a, cairo_point_t d) { cairo_int64_t numerator_a, numerator_b, denominator; + cairo_bool_t denominator_negative; denominator = _cairo_int64_sub (_cairo_int32x32_64_mul (d.y - c.y, b.x - a.x), _cairo_int32x32_64_mul (d.x - c.x, b.y - a.y)); @@ -1327,20 +1328,34 @@ _lines_intersect_or_are_coincident (cairo_point_t a, return FALSE; } - /* If either division would produce a number between 0 and 1, i.e. - * the numerator is smaller than the denominator and their signs are - * the same, then the lines intersect. */ - if (_cairo_int64_lt (numerator_a, denominator) && - ! (_cairo_int64_negative (numerator_a) ^ _cairo_int64_negative(denominator))) { - return TRUE; - } + /* The lines intersect if both quotients are between 0 and 1 (exclusive). */ - if (_cairo_int64_lt (numerator_b, denominator) && - ! (_cairo_int64_negative (numerator_b) ^ _cairo_int64_negative(denominator))) { - return TRUE; + /* We first test whether either quotient is a negative number. */ + denominator_negative = _cairo_int64_negative (denominator); + if (_cairo_int64_negative (numerator_a) ^ denominator_negative) + return FALSE; + if (_cairo_int64_negative (numerator_b) ^ denominator_negative) + return FALSE; + + /* A zero quotient indicates an "intersection" at an endpoint, which + * we aren't considering a true intersection. */ + if (_cairo_int64_is_zero (numerator_a) || _cairo_int64_is_zero (numerator_b)) + return FALSE; + + /* If the absolute value of the numerator is larger than or equal to the + * denominator the result of the division would be greater than or equal + * to one. */ + if (! denominator_negative) { + if (! _cairo_int64_lt (numerator_a, denominator) || + ! _cairo_int64_lt (numerator_b, denominator)) + return FALSE; + } else { + if (! _cairo_int64_lt (denominator, numerator_a) || + ! _cairo_int64_lt (denominator, numerator_b)) + return FALSE; } - return FALSE; + return TRUE; } cairo_bool_t -- cgit v1.2.3