Intersect.cs

        /// <summary>
        /// Faster version of intersect than the eyeshot code.
        /// </summary>
        /// <param name="this"></param>
        /// <param name="other"></param>
        /// <param name="intersection"></param>
        /// <returns>Returns true if there is an intersection. Returns false if it is colinear.</returns>
        public static bool Intersect(this Segment2D @this, Segment2D other, out Point2D intersection)
        {
            intersection = null;

            var p = @this;
            var q = other;

            // Solving equation
            //
            // P0 + t(P1 - P0) = Q0 + r(Q1 - Q0)
            //
            // if there is a solution for t and r and both lie between
            // zero and one then there is an intersection. Otherwise
            // there are none. Coliniearity is explicity not handled.

            // a-d are the entries of a 2x2 matrix
            var pP0X = p.P0.X;
            var pP0Y = p.P0.Y;
            var qP0Y = q.P0.Y;
            var qP0X = q.P0.X;

            var a = p.P1.X - pP0X;
            var b = -q.P1.X + qP0X;
            var c = p.P1.Y - pP0Y;
            var d = -q.P1.Y + qP0Y;

            var det = a*d - b*c;
            if (Math.Abs(det) < Utility.ZERO_TOLERANCE)
            {
                return false;
            }

            var x = qP0X - pP0X;
            var y = qP0Y - pP0Y;

            det = 1/det;

            var t = det*(d*x - b*y);
            if (!(t >= 0)
                || !(t <= 1))
                return false;

            var r = det*(-c*x + a*y);
            if (!(r >= 0) || !(r <= 1))
                return false;

            intersection = new Point2D(pP0X + t*a, pP0Y + t*c);
            return true;
        }

IntersectRef.cs

        /// <summary>
        /// Faster version of intersect than the eyeshot code.
        /// </summary>
        /// <param name="this"></param>
        /// <param name="other"></param>
        /// <param name="intersection"></param>
        /// <returns>Returns true if there is an intersection. Returns false if it is colinear.</returns>
        public static bool IntersectRef(this Segment2D @this, Segment2D other, ref Point2D intersection)
        {
            var p = @this;
            var q = other;

            // Solving equation
            //
            // P0 + t(P1 - P0) = Q0 + r(Q1 - Q0)
            //
            // if there is a solution for t and r and both lie between
            // zero and one then there is an intersection. Otherwise
            // there are none. Coliniearity is explicity not handled.

            // a-d are the entries of a 2x2 matrix
            var pP0X = p.P0.X;
            var pP0Y = p.P0.Y;
            var qP0Y = q.P0.Y;
            var qP0X = q.P0.X;

            var a = p.P1.X - pP0X;
            var b = -q.P1.X + qP0X;
            var c = p.P1.Y - pP0Y;
            var d = -q.P1.Y + qP0Y;

            var det = a*d - b*c;
            if (Math.Abs(det) < Utility.ZERO_TOLERANCE)
            {
                return false;
            }

            var x = qP0X - pP0X;
            var y = qP0Y - pP0Y;

            det = 1/det;

            var t = det*(d*x - b*y);
            if (!(t >= 0)
                || !(t <= 1))
                return false;

            var r = det*(-c*x + a*y);
            if (!(r >= 0) || !(r <= 1))
                return false;

            intersection.X = pP0X + t*a;
            intersection.Y = pP0Y + t*c;
            return true;
        }

testcase.cs

        [Fact]
        public void IntersectLinePerfTest()
        {
            var p1 = new Point2D(0, 0);
            var p2 = new Point2D(1, 1);
            var p3 = new Point2D(0, 1);
            var p4 = new Point2D(1, 0);
            var l1 = new Segment2D(p1, p2);
            var l2 = new Segment2D(p3, p4);

            var d = Math.Max( l1.Length, l2.Length );

            var s = 0.0;

            var n = 5000000;
            var r = new Random(0);
            var sw = Stopwatch.StartNew();

            var x1 = l1.P0.X;
            var y1 = l1.P0.Y;

            var x2 = l2.P0.X;
            var y2 = l2.P0.Y;

            const bool debug = false;
            const double delta = 0.01;
            for (int i = 0; i < n; i++)
            {

                {
                    l1.P0.X = x1 + r.NextDouble() * delta - delta/2;
                    l1.P0.Y = y1 + r.NextDouble() * delta - delta/2;
                    l2.P0.X = x2 + r.NextDouble() * delta - delta/2;
                    l2.P0.Y = y2 + r.NextDouble() * delta - delta/2;
                    if (l2.Intersect( l1, out var i0 ))
                    {

                        if(debug)
                            _Out.WriteLine( i0.ToString() );
                        s += i0.X;
                        s += i0.Y;
                    }
                    else
                    {
                        if(debug)
                            _Out.WriteLine( "No intersection" );
                        
                    }

                }
            }
            GC.Collect();
            _Out.WriteLine( $"WG - {sw.ElapsedMilliseconds}" );
            _Out.WriteLine( s.ToString() );


            s = 0.0;
            r = new Random(0);
            sw = Stopwatch.StartNew();
            {
                Point2D i0 = new Point2D();
                for (int i = 0; i < n; i++)
                {

                    {
                        l1.P0.X = x1 + r.NextDouble() * delta - delta / 2;
                        l1.P0.Y = y1 + r.NextDouble() * delta - delta / 2;
                        l2.P0.X = x2 + r.NextDouble() * delta - delta / 2;
                        l2.P0.Y = y2 + r.NextDouble() * delta - delta / 2;
                        if (l2.IntersectRef(l1, ref i0))
                        {

                            if (debug)
                                _Out.WriteLine(i0.ToString());
                            s += i0.X;
                            s += i0.Y;
                        }
                        else
                        {
                            if (debug)
                                _Out.WriteLine("No intersection");

                        }

                    }
                }
            }
            GC.Collect();
            _Out.WriteLine( $"WGRef - {sw.ElapsedMilliseconds}" );
            _Out.WriteLine( s.ToString() );


            s = 0.0;
            r = new Random(0);
            sw = Stopwatch.StartNew();
            for (int i = 0; i < n; i++)
            {
                {
                    l1.P0.X = x1 + r.NextDouble() * delta - delta/2;
                    l1.P0.Y = y1 + r.NextDouble() * delta - delta/2;
                    l2.P0.X = x2 + r.NextDouble() * delta - delta/2;
                    l2.P0.Y = y2 + r.NextDouble() * delta - delta/2;
                    if (Segment2D.Intersection( l1, l2, out var i0, out var i1, d ) != segmentIntersectionType.Disjoint)
                    {
                        if(debug)
                            _Out.WriteLine( i0.ToString());
                        s += i0.X;
                        s += i0.Y;
                    }else
                    {
                        if(debug)
                            _Out.WriteLine( "No intersection" );
                        
                    }
                }
            }
            GC.Collect();
            _Out.WriteLine( $"ES - {sw.ElapsedMilliseconds}" );
            _Out.WriteLine( s.ToString() );

        }