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.

1 files changed, 27 insertions, 12 deletions

diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
index 10a65159c..14913fd09 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