[Lib2geom-devel] Intersection of parallel line segments

[Diederik v. L. <ma...@di...>]

Hi everyone,

When looking into this bug in Inkscape's measure tool:

https://bugs.launchpad.net/inkscape/+bug/1022733

I found out that intersecting two parallel line segments typically produces
50 - 100 crossings. This should either be zero or infinite (or maybe one if
one line segment is just a point).

The original code checked for a cross product being exactly zero as a
measure for line segments being parallel, but that's obviously a bad idea.
I've found the error to be < 1e-13, so I propose checking for a cross
product of < 1e-12.

This solves the bug I was trying to squash, but I'm not too familiar with
the crossers code. If someone objects to this fix, then just speak up!

Thanks,

Diederik

=== modified file 'src/2geom/path-intersection.cpp'
--- src/2geom/path-intersection.cpp    2014-03-27 01:33:44 +0000
+++ src/2geom/path-intersection.cpp    2014-05-14 18:47:54 +0000
@@ -169,15 +169,21 @@
           Bd = B1 - B0,
            d = B0 - A0;
     det = cross(Ad, Bd);
-    if( 1.0 + det == 1.0 )
-        return false;
-    else
-    {
-        double detinv = 1.0 / det;
-        tA = cross(d, Bd) * detinv;
-        tB = cross(d, Ad) * detinv;
-        return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
-    }
+    if( fabs(det) < 1e-12 ) {// If the cross product is NEARLY zero,
+        // Then one of the linesegments might have length zero
+        if (!are_near(A0, A1) && !are_near(B0, B1)) {
+            // If that's not the case, then we must have either:
+            // - parallel lines, with no intersections, or
+            // - coincident lines, with an infinite number of intersections
+            // Either is quite useless, so we'll just bail out
+            return false;
+        } // Else, one of the linesegments is zero, and we might still
find a single intersection point
+    } // Else we haven't bailed out, and we'll try to calculate the
intersections
+    std::cout << "det = cross = " << det << std::endl;
+    double detinv = 1.0 / det;
+    tA = cross(d, Bd) * detinv;
+    tB = cross(d, Ad) * detinv;
+    return tA >= 0. && tA <= 1. && tB >= 0. && tB <= 1.;
 }