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

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

Hi Nathan and Johan,

Thanks for your feedback! It has been incorporated in the patches I just
commited

Kind regards,

Diederik


On Thu, May 15, 2014 at 12:49 AM, Nathan Hurst <nj...@nj...> wrote:

> 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
>
>
>
> ------------------------------------------------------------------------------
> "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
>