From c8162ae7a5692e0aa91de4c08fa4bd8a47cc54a8 Mon Sep 17 00:00:00 2001
From: "Johan B. C. Engelen" <jbc.engelen@swissonline.ch>
Date: Sun, 11 May 2014 23:13:23 +0200
Subject: fix 2geom build for newer compilers (assert can be
 disabled/overridden, i suppose)

(bzr r13355)
---
 src/2geom/toposweep.cpp | 1 +
 1 file changed, 1 insertion(+)

(limited to 'src/2geom')

diff --git a/src/2geom/toposweep.cpp b/src/2geom/toposweep.cpp
index cfb91857c..9316669f5 100644
--- a/src/2geom/toposweep.cpp
+++ b/src/2geom/toposweep.cpp
@@ -53,6 +53,7 @@ TopoGraph::Edge TopoGraph::remove_edge(unsigned ix, unsigned jx) {
         }
     }
     assert(0);
+    return Edge; // if assert is disabled, return empty Edge.
 }
 
 void TopoGraph::cannonize() {
-- 
cgit v1.2.3


From a596a3e08e0f11e3d8d6a3107fc897c2cd729b1d Mon Sep 17 00:00:00 2001
From: "Johan B. C. Engelen" <jbc.engelen@swissonline.ch>
Date: Sun, 11 May 2014 23:18:22 +0200
Subject: correctly fix rev. 13355

(bzr r13356)
---
 src/2geom/toposweep.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'src/2geom')

diff --git a/src/2geom/toposweep.cpp b/src/2geom/toposweep.cpp
index 9316669f5..4da3f6922 100644
--- a/src/2geom/toposweep.cpp
+++ b/src/2geom/toposweep.cpp
@@ -53,7 +53,7 @@ TopoGraph::Edge TopoGraph::remove_edge(unsigned ix, unsigned jx) {
         }
     }
     assert(0);
-    return Edge; // if assert is disabled, return empty Edge.
+    return v[0]; // if assert is disabled, return first Edge.
 }
 
 void TopoGraph::cannonize() {
-- 
cgit v1.2.3


From 67e3a25d12d9a273afb1b8f9f3258b232989c660 Mon Sep 17 00:00:00 2001
From: Diederik van Lierop <mail@diedenrezi.nl>
Date: Fri, 23 May 2014 22:52:32 +0200
Subject: Fix flakiness of measurement tool (due to issues with parallel lines,
 duplicate intersections, and faulty sorting of intersections)

Fixed bugs:
  - https://launchpad.net/bugs/1022733

(bzr r13397)
---
 src/2geom/crossing.cpp          | 20 +++++++++++++++++++-
 src/2geom/crossing.h            |  1 +
 src/2geom/path-intersection.cpp | 33 ++++++++++++++++++++++++---------
 3 files changed, 44 insertions(+), 10 deletions(-)

(limited to 'src/2geom')

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.);
 }
 
 
-- 
cgit v1.2.3