Update to latest tip (trunk r13432)

(bzr r13341.1.62)

3 files changed, 44 insertions, 10 deletions

diff --git a/src/2geom/crossing.cpp b/src/2geom/crossing.cpp
index 13affa8e9..513327271 100644
--- a/src/2geom/crossing.cpp
+++ b/src/2geom/crossing.cpp
@@ -154,7 +154,6 @@ Crossings reverse_tb(Crossings const &cr, unsigned split, std::vector<double> ma
     Crossings ret;
     for(Crossings::const_iterator i = cr.begin(); i != cr.end(); ++i) {
         double mx = max[i->b - split];
-        std::cout << i->b << "\n";
         ret.push_back(Crossing(i->ta, i->tb > mx+0.01 ? (1 - (i->tb - mx) + mx) : mx - i->tb,
                                !i->dir));
     }
@@ -181,6 +180,25 @@ CrossingSet reverse_tb(CrossingSet const &cr, unsigned split, std::vector<double
     return ret;
 }
 
+// Delete any duplicates in a vector of crossings
+// A crossing is considered to be a duplicate when it has both t_a and t_b near to another crossing's t_a and t_b
+// For example, duplicates will be found when calculating the intersections of a linesegment with a polygon, if the
+// endpoint of that line coincides with a cusp node of the polygon. In that case, an intersection will be found of
+// the linesegment with each of the polygon's linesegments extending from the cusp node (i.e. two intersections)
+void delete_duplicates(Crossings &crs) {
+    Crossings::reverse_iterator rit = crs.rbegin();
+
+    for (rit = crs.rbegin(); rit!= crs.rend(); ++rit) {
+        Crossings::reverse_iterator rit2 = rit;
+        while (++rit2 != crs.rend()) {
+            if (Geom::are_near((*rit).ta, (*rit2).ta) && Geom::are_near((*rit).tb, (*rit2).tb)) {
+                crs.erase((rit + 1).base()); // This +1 and .base() construction is needed to convert to a regular iterator
+                break; // out of while loop, and continue with next iteration of for loop
+            }
+        }
+    }
+}
+
 void clean(Crossings &/*cr_a*/, Crossings &/*cr_b*/) {
 /*    if(cr_a.empty()) return;
     
diff --git a/src/2geom/crossing.h b/src/2geom/crossing.h
index 75c75fc24..d5012ae2b 100644
--- a/src/2geom/crossing.h
+++ b/src/2geom/crossing.h
@@ -183,6 +183,7 @@ CrossingSet reverse_ta(CrossingSet const &cr, unsigned split, std::vector<double
 CrossingSet reverse_tb(CrossingSet const &cr, unsigned split, std::vector<double> max);
 
 void clean(Crossings &cr_a, Crossings &cr_b);
+void delete_duplicates(Crossings &crs);
 
 }
 
diff --git a/src/2geom/path-intersection.cpp b/src/2geom/path-intersection.cpp
index ff24b92eb..63a29423d 100644
--- a/src/2geom/path-intersection.cpp
+++ b/src/2geom/path-intersection.cpp
@@ -164,20 +164,35 @@ void append(T &a, T const &b) {
 bool
 linear_intersect(Point A0, Point A1, Point B0, Point B1,
                  double &tA, double &tB, double &det) {
-    // kramers rule as cross products
+    bool both_lines_non_zero = (!are_near(A0, A1)) && (!are_near(B0, B1));
+
+    // Cramer's rule as cross products
     Point Ad = A1 - A0,
           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.;
+
+    double det_rel = det; // Calculate the determinant of the normalized vectors
+    if (both_lines_non_zero) {
+        det_rel /= Ad.length();
+        det_rel /= Bd.length();
     }
+
+    if( fabs(det_rel) < 1e-12 ) { // If the cross product is NEARLY zero,
+        // Then one of the linesegments might have length zero
+        if (both_lines_non_zero) {
+            // 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 be able to calculate a single intersection point
+    } // Else we haven't bailed out, and we'll try to calculate the intersections
+
+    double detinv = 1.0 / det;
+    tA = cross(d, Bd) * detinv;
+    tB = cross(d, Ad) * detinv;
+    return (tA >= 0.) && (tA <= 1.) && (tB >= 0.) && (tB <= 1.);
 }