Re: [Lib2geom-devel] Intersection of parallel line segments

[Nathan H. <nj...@nj...>]

I wonder whether it would work better if you used relative error
rather than absolute?  Really what you're trying to do is put an error
bound around the line and call lines parallel if their error windows
overlap over the length of the segment.  The error bound for floating
point is relative (typically 2^-23/-53 of the value).  This might be
enough to make the problem go away.  Because the cross product is
O(x^2) your relative error should be more like 2^-26 (1e-8) for double,
I think.

njh


On Wed, May 14, 2014 at 11:06:10PM +0200, Johan Engelen wrote:
> Hi Diederik,
>   Great that you are working on this.
> I can't judge the technical side too well. Some code style comments:
> - remove / comment out the std::cout reporting
> - can you add parenthesis in the final boolean expression (to not
> rely on operator precedence)
> 
> cheers,
>   Johan
> 
> 
> On 14-5-2014 21:03, Diederik van Lierop wrote:
> >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.;
> > }
> >
> >
> >
> >
> >------------------------------------------------------------------------------
> >"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> >Instantly run your Selenium tests across 300+ browser/OS combos.
> >Get unparalleled scalability from the best Selenium testing platform available
> >Simple to use. Nothing to install. Get started now for free."
> >http://p.sf.net/sfu/SauceLabs
> >
> >
> >_______________________________________________
> >Lib2geom-devel mailing list
> >Lib...@li...
> >https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
> 

> ------------------------------------------------------------------------------
> "Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
> Instantly run your Selenium tests across 300+ browser/OS combos.
> Get unparalleled scalability from the best Selenium testing platform available
> Simple to use. Nothing to install. Get started now for free."
> http://p.sf.net/sfu/SauceLabs

> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel