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)

4 files changed, 68 insertions, 45 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.);
 }
 
 
diff --git a/src/ui/tools/measure-tool.cpp b/src/ui/tools/measure-tool.cpp
index 2c85874bc..feeb68288 100644
--- a/src/ui/tools/measure-tool.cpp
+++ b/src/ui/tools/measure-tool.cpp
@@ -277,21 +277,13 @@ void MeasureTool::finish() {
 //    return ret;
 //}
 
-static bool GeomPointSortPredicate(const Geom::Point& p1, const Geom::Point& p2)
+static void calculate_intersections(SPDesktop * /*desktop*/, SPItem* item, Geom::PathVector const &lineseg, SPCurve *curve, std::vector<double> &intersections)
 {
-    if (p1[Geom::Y] == p2[Geom::Y]) {
-        return p1[Geom::X] < p2[Geom::X];
-    } else {
-        return p1[Geom::Y] < p2[Geom::Y];
-    }
-}
 
-static void calculate_intersections(SPDesktop * /*desktop*/, SPItem* item, Geom::PathVector const &lineseg, SPCurve *curve, std::vector<Geom::Point> &intersections)
-{
     curve->transform(item->i2doc_affine());
-
     // Find all intersections of the control-line with this shape
     Geom::CrossingSet cs = Geom::crossings(lineseg, curve->get_pathvector());
+    Geom::delete_duplicates(cs[0]);
 
     // Reconstruct and store the points of intersection
     for (Geom::Crossings::const_iterator m = cs[0].begin(); m != cs[0].end(); ++m) {
@@ -304,10 +296,11 @@ static void calculate_intersections(SPDesktop * /*desktop*/, SPItem* item, Geom:
              item == doc->getItemAtPoint(desktop->dkey, lineseg[0].pointAt((*m).ta - eps), false, NULL)) ||
             ((*m).ta + eps < 1 &&
              item == doc->getItemAtPoint(desktop->dkey, lineseg[0].pointAt((*m).ta + eps), false, NULL)) ) {
-            intersections.push_back(intersection);
+            intersections.push_back((*m).ta);
         }
 #else
-        intersections.push_back(lineseg[0].pointAt((*m).ta));
+        intersections.push_back((*m).ta);
+
 #endif
     }
 }
@@ -441,28 +434,20 @@ bool MeasureTool::root_handler(GdkEvent* event) {
                     points.push_back(desktop->d2w(start_point + (i / NPOINTS) * (end_point - start_point)));
                 }
 
-// TODO: Felipe, why don't you simply iterate over all items, and test whether their bounding boxes intersect
-// with the measurement line, instead of interpolating? E.g. bbox_of_measurement_line.intersects(*bbox_of_item).
-// That's also how the object-snapper works, see _findCandidates() in object-snapper.cpp.
+                // TODO: Felipe, why don't you simply iterate over all items, and test whether their bounding boxes intersect
+                // with the measurement line, instead of interpolating over 800 points? E.g. bbox_of_measurement_line.intersects(*bbox_of_item).
+                // That's also how the object-snapper works, see _findCandidates() in object-snapper.cpp.
+
+                // TODO switch to a different variable name. The single letter 'l' is easy to misread.
 
                 //select elements crossed by line segment:
                 GSList *items = sp_desktop_document(desktop)->getItemsAtPoints(desktop->dkey, points);
-                std::vector<Geom::Point> intersections;
-                Inkscape::Preferences *prefs = Inkscape::Preferences::get();
-                bool ignore_1st_and_last = prefs->getBool("/tools/measure/ignore_1st_and_last", true);
-
-                if (!ignore_1st_and_last) {
-                    intersections.push_back(desktop->dt2doc(start_point));
-                }
-
-                std::vector<LabelPlacement> placements;
-
-                // TODO switch to a different variable name. The single letter 'l' is easy to misread.
+                std::vector<double> intersection_times;
                 for (GSList *l = items; l != NULL; l = l->next) {
                     SPItem *item = static_cast<SPItem*>(l->data);
 
                     if (SP_IS_SHAPE(item)) {
-                       calculate_intersections(desktop, item, lineseg, SP_SHAPE(item)->getCurve(), intersections);
+                       calculate_intersections(desktop, item, lineseg, SP_SHAPE(item)->getCurve(), intersection_times);
                     } else {
                         if (SP_IS_TEXT(item) || SP_IS_FLOWTEXT(item)) {
                             Inkscape::Text::Layout::iterator iter = te_get_layout(item)->begin();
@@ -486,7 +471,7 @@ bool MeasureTool::root_handler(GdkEvent* event) {
 
                                 curve->transform(item->i2doc_affine());
 
-                                calculate_intersections(desktop, item, lineseg, curve, intersections);
+                                calculate_intersections(desktop, item, lineseg, curve, intersection_times);
 
                                 if (iter == te_get_layout(item)->end()) {
                                     break;
@@ -496,13 +481,10 @@ bool MeasureTool::root_handler(GdkEvent* event) {
                     }
                 }
 
-                if (!ignore_1st_and_last) {
-                    intersections.push_back(desktop->dt2doc(end_point));
-                }
-
-                //sort intersections
-                if (intersections.size() > 2) {
-                    std::sort(intersections.begin(), intersections.end(), GeomPointSortPredicate);
+                Inkscape::Preferences *prefs = Inkscape::Preferences::get();
+                if (!prefs->getBool("/tools/measure/ignore_1st_and_last", true)) {
+                    intersection_times.push_back(0);
+                    intersection_times.push_back(1);
                 }
 
                 Glib::ustring unit_name = prefs->getString("/tools/measure/unit");
@@ -516,6 +498,13 @@ bool MeasureTool::root_handler(GdkEvent* event) {
                 Geom::Point windowNormal = Geom::unit_vector(Geom::rot90(desktop->d2w(end_point - start_point)));
                 Geom::Point normal = desktop->w2d(windowNormal);
 
+                std::vector<Geom::Point> intersections;
+                std::sort(intersection_times.begin(), intersection_times.end());
+                for (std::vector<double>::iterator iter_t = intersection_times.begin(); iter_t != intersection_times.end(); iter_t++) {
+                    intersections.push_back(lineseg[0].pointAt(*iter_t));
+                }
+
+                std::vector<LabelPlacement> placements;
                 for (size_t idx = 1; idx < intersections.size(); ++idx) {
                     LabelPlacement placement;
                     placement.lengthVal = (intersections[idx] - intersections[idx - 1]).length();