Lasso.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / wpf / src / Core / CSharp / MS / Internal / Ink / Lasso.cs / 1 / Lasso.cs

                            //------------------------------------------------------------------------ 
// 
// Copyright (c) Microsoft Corporation. All rights reserved.
// 
//----------------------------------------------------------------------- 
//#define TRACE
 
using System; 
using System.Windows;
using System.Windows.Ink; 
using System.Windows.Media;
using System.Collections.Generic;
using System.Globalization;
 
namespace MS.Internal.Ink
{ 
    #region Lasso 

    ///  
    /// Represents a lasso for selecting/cutting ink strokes with.
    /// Lasso is a sequence of points defining a complex region (polygon)
    /// 
    internal class Lasso 
    {
        #region Constructors 
 
        /// 
        /// Default c-tor. Used in incremental hit-testing. 
        /// 
        internal Lasso()
        {
            _points = new List(); 
        }
 
        #endregion 

        #region API 

        /// 
        /// Returns the bounds of the lasso
        ///  
        internal Rect Bounds
        { 
            get { return _bounds; } 
            set { _bounds = value;}
        } 

        /// 
        /// Tells whether the lasso captures any area
        ///  
        internal bool IsEmpty
        { 
            get 
            {
                System.Diagnostics.Debug.Assert(_points != null); 
                // The value is based on the assumption that the lasso is normalized
                // i.e. it has no duplicate points or collinear sibling segments.
                return (_points.Count < 3);
            } 
        }
 
        ///  
        /// Returns the count of points in the lasso
        ///  
        internal int PointCount
        {
            get
            { 
                System.Diagnostics.Debug.Assert(_points != null);
                return _points.Count; 
            } 
        }
 
        /// 
        /// Index-based read-only accessor to lasso points
        /// 
        /// index of the point to return 
        /// a point in the lasso
        internal Point this[int index] 
        { 
            get
            { 
                System.Diagnostics.Debug.Assert(_points != null);
                System.Diagnostics.Debug.Assert((0 <= index) && (index < _points.Count));

                return _points[index]; 
            }
        } 
 
        /// 
        /// Extends the lasso by appending more points 
        /// 
        /// new points
        internal void AddPoints(IEnumerable points)
        { 
            System.Diagnostics.Debug.Assert(null != points);
 
            foreach (Point point in points) 
            {
                AddPoint(point); 
            }
        }

        ///  
        /// Appends a point to the lasso
        ///  
        /// new lasso point 
        internal void AddPoint(Point point)
        { 
            System.Diagnostics.Debug.Assert(_points != null);
            if (!Filter(point))
            {
                // The point is not filtered, add it to the lasso 
                AddPointImpl(point);
            } 
        } 

        ///  
        /// This method implement the core algorithm to check whether a point is within a polygon
        /// that are formed by the lasso points.
        /// 
        ///  
        /// true if the point is contained within the lasso; false otherwise 
        internal bool Contains(Point point) 
        { 
            System.Diagnostics.Debug.Assert(_points != null);
 
            if (false == _bounds.Contains(point))
            {
                return false;
            } 

            bool isHigher = false; 
            int last = _points.Count; 
            while (--last >= 0)
            { 
                if (!DoubleUtil.AreClose(_points[last].Y,point.Y))
                {
                    isHigher = (point.Y < _points[last].Y);
                    break; 
                }
            } 
 
            bool isInside = false;
            Point prevLassoPoint = _points[_points.Count - 1]; 
            for (int i = 0; i < _points.Count; i++)
            {
                Point lassoPoint = _points[i];
                if (DoubleUtil.AreClose(lassoPoint.Y, point.Y)) 
                {
                    if (DoubleUtil.AreClose(lassoPoint.X, point.X)) 
                    { 
                        isInside = true;
                        break; 
                    }
                    if ((0 != i) && DoubleUtil.AreClose(prevLassoPoint.Y, point.Y) &&
                        DoubleUtil.GreaterThanOrClose(point.X, Math.Min(prevLassoPoint.X, lassoPoint.X)) &&
                        DoubleUtil.LessThanOrClose(point.X, Math.Max(prevLassoPoint.X, lassoPoint.X))) 
                    {
                        isInside = true; 
                        break; 
                    }
                } 
                else if (isHigher != (point.Y < lassoPoint.Y))
                {
                    isHigher = !isHigher;
                    if (DoubleUtil.GreaterThanOrClose(point.X, Math.Max(prevLassoPoint.X, lassoPoint.X))) 
                    {
                        // there certainly is an intersection on the left 
                        isInside = !isInside; 
                    }
                    else if (DoubleUtil.GreaterThanOrClose(point.X, Math.Min(prevLassoPoint.X, lassoPoint.X))) 
                    {
                        // The X of the point lies within the x ranges for the segment.
                        // Calculate the x value of the point where the segment intersects with the line.
                        Vector lassoSegment = lassoPoint - prevLassoPoint; 
                        System.Diagnostics.Debug.Assert(lassoSegment.Y != 0);
                        double x = prevLassoPoint.X + (lassoSegment.X / lassoSegment.Y) * (point.Y - prevLassoPoint.Y); 
                        if (DoubleUtil.GreaterThanOrClose(point.X, x)) 
                        {
                            isInside = !isInside; 
                        }
                    }
                }
                prevLassoPoint = lassoPoint; 
            }
            return isInside; 
        } 

        internal StrokeIntersection[] HitTest(StrokeNodeIterator iterator) 
        {
            System.Diagnostics.Debug.Assert(_points != null);
            System.Diagnostics.Debug.Assert(iterator != null);
 
#if TRACE
            System.Diagnostics.Debug.WriteLine(String.Format("Lasso: start lasso histtesing a new stroke ...")); 
#endif 

            if (_points.Count < 3) 
            {
                //
                // it takes at least 3 points to create a lasso
                // 
#if TRACE
                System.Diagnostics.Debug.WriteLine(String.Format("Lasso:.............. done. Nothing hit because lasso lasso has only {0} points", _points.Count)); 
#endif 
                return new StrokeIntersection[0];
            } 

            //
            // We're about to perform hit testing with a lasso.
            // To do so we need to iterate through each StrokeNode. 
            // As we do, we calculate the bounding rect between it
            // and the previous StrokeNode and store this in 'currentStrokeSegmentBounds' 
            // 
            // Next, we check to see if that StrokeNode pair's bounding box intersects
            // with the bounding box of the Lasso points.  If not, we continue iterating through 
            // StrokeNode pairs.
            //
            // If it does, we do a more granular hit test by pairing points in the Lasso, getting
            // their bounding box and seeing if that bounding box intersects our current StrokeNode 
            // pair
            // 
 
            Point lastNodePosition = new Point();
            Point lassoLastPoint = _points[_points.Count - 1]; 
            Rect currentStrokeSegmentBounds = Rect.Empty;

            // Initilize the current crossing to be an empty one
            LassoCrossing currentCrossing = LassoCrossing.EmptyCrossing; 

            // Creat a list to hold all the crossings 
            List crossingList = new List(); 
            for (int i = 0; i < iterator.Count; i++)
            { 
                StrokeNode strokeNode = iterator[i];
                Rect nodeBounds = strokeNode.GetBounds();
                currentStrokeSegmentBounds.Union(nodeBounds);
 
                // Skip the node if it's outside of the lasso's bounds
                if (currentStrokeSegmentBounds.IntersectsWith(_bounds) == true) 
                { 
                    // currentStrokeSegmentBounds, made up of the bounding box of
                    // this StrokeNode unioned with the last StrokeNode, 
                    // intersects the lasso bounding box.
                    //
                    // Now we need to iterate through the lasso points and find out where they cross
                    // 
                    Point lastPoint = lassoLastPoint;
                    foreach (Point point in _points) 
                    { 
                        //
                        // calculate a segment of the lasso from the last point 
                        // to the current point
                        //
                        Rect lassoSegmentBounds = new Rect(lastPoint, point);
 
                        //
                        // see if this lasso segment intersects with the current stroke segment 
                        // 
                        if (!currentStrokeSegmentBounds.IntersectsWith(lassoSegmentBounds))
                        { 
                            lastPoint = point;
                            continue;
                        }
 
                        //
                        // the lasso segment DOES intersect with the current stroke segment 
                        // find out precisely where 
                        //
                        StrokeFIndices strokeFIndices = strokeNode.CutTest(lastPoint, point); 

#if TRACE
                        if (!strokeFIndices.IsEmpty)
                        { 
                            System.Diagnostics.Debug.WriteLine (String.Format("\t\tLasso: found nonempty StrokeFIndices {0} with points [{1}] and  [{2}] for strokeNode at {3}", strokeFIndices, lastPoint, point,strokeNode.Position));
                        } 
#endif 
                        lastPoint = point;
                        if (strokeFIndices.IsEmpty) 
                        {
                            // current lasso segment does not hit the stroke segment, continue with the next lasso point
                            continue;
                        } 

                        // Create a potentially new crossing for the current hit testing result. 
                        LassoCrossing potentialNewCrossing = new LassoCrossing(strokeFIndices, strokeNode); 

                        // Try to merge with the current crossing. If the merge is succussful (return true), the new crossing is actually 
                        // continueing the current crossing, so do not start a new crossing. Otherwise, start a new one and add the existing
                        // one to the list.
                        if (!currentCrossing.Merge(potentialNewCrossing))
                        { 
#if TRACE
                            System.Diagnostics.Debug.WriteLine(String.Format("\tLasso: adding {0}  to crossingList and starting a new crossing {1}", currentCrossing, potentialNewCrossing)); 
#endif 

                            // start a new crossing and add the existing on to the list 
                            crossingList.Add(currentCrossing);
                            currentCrossing = potentialNewCrossing;
                        }
                    } 

                } 
 
                // Continue with the next node
                currentStrokeSegmentBounds = nodeBounds; 
                lastNodePosition = strokeNode.Position;
            }

 
            // Adding the last crossing to the list, if valid
            if (!currentCrossing.IsEmpty) 
            { 
                crossingList.Add(currentCrossing);
#if TRACE 
                System.Diagnostics.Debug.WriteLine(String.Format("\tLasso: adding the last crossing {0}  to crossingList", currentCrossing));
#endif
            }
 
            // Handle the special case of no intersection at all
            if (crossingList.Count == 0) 
            { 
                // the stroke was either completely inside the lasso
                // or outside the lasso 
                if (this.Contains(lastNodePosition))
                {
                    StrokeIntersection[] strokeIntersections = new StrokeIntersection[1];
                    strokeIntersections[0] = StrokeIntersection.Full; 
                    return strokeIntersections;
                } 
                else 
                {
                    return new StrokeIntersection[0]; 
                }
            }

            // It is still possible that the current crossing list is not sorted or overlapping. 
            // Sort the list and merge the overlapping ones.
            SortAndMerge(ref crossingList); 
 
            // Produce the hit test results and store them in a list
            List strokeIntersectionList = new List(); 
            ProduceHitTestResults(crossingList, strokeIntersectionList);

#if TRACE
            System.Diagnostics.Debug.WriteLine(String.Format("Lasso:.............. done. Lasso hit {0} segments", strokeIntersectionList.Count)); 
#endif
            return strokeIntersectionList.ToArray(); 
        } 

        ///  
        /// Sort and merge the crossing list
        /// 
        /// The crossing list to sort/merge
        private static void SortAndMerge(ref List crossingList) 
        {
            // Sort the crossings based on the BeginFIndex values 
            crossingList.Sort(); 

            List mergedList = new List(); 
            LassoCrossing mcrossing = LassoCrossing.EmptyCrossing;
            foreach (LassoCrossing crossing in crossingList)
            {
                System.Diagnostics.Debug.Assert(!crossing.IsEmpty && crossing.StartNode.IsValid && crossing.EndNode.IsValid); 
                if (!mcrossing.Merge(crossing))
                { 
                    System.Diagnostics.Debug.Assert(!mcrossing.IsEmpty && mcrossing.StartNode.IsValid && mcrossing.EndNode.IsValid); 
                    mergedList.Add(mcrossing);
                    mcrossing = crossing; 
                }
            }
            if (!mcrossing.IsEmpty)
            { 
                System.Diagnostics.Debug.Assert(!mcrossing.IsEmpty && mcrossing.StartNode.IsValid && mcrossing.EndNode.IsValid);
                mergedList.Add(mcrossing); 
            } 
            crossingList = mergedList;
        } 


        /// 
        /// Helper function to find out whether a point is inside the lasso 
        /// 
        private bool SegmentWithinLasso(StrokeNode strokeNode, double fIndex) 
        { 
            bool currentSegmentWithinLasso;
            if (DoubleUtil.AreClose(fIndex, StrokeFIndices.BeforeFirst)) 
            {
                // This should check against the very first stroke node
                currentSegmentWithinLasso = this.Contains(strokeNode.GetPointAt(0f));
            } 
            else if (DoubleUtil.AreClose(fIndex, StrokeFIndices.AfterLast))
            { 
                // This should check against the last stroke node 
                currentSegmentWithinLasso = this.Contains(strokeNode.Position);
            } 
            else
            {
                currentSegmentWithinLasso = this.Contains(strokeNode.GetPointAt(fIndex));
            } 

            return currentSegmentWithinLasso; 
        } 

        ///  
        /// Helper function to find out the hit test result
        /// 
        private void ProduceHitTestResults(
                                List crossingList, List strokeIntersections) 
        {
            bool previousSegmentInsideLasso = false; 
            for (int x = 0; x <= crossingList.Count; x++) 
            {
                bool currentSegmentWithinLasso = false; 
                bool canMerge = true;
                StrokeIntersection si = new StrokeIntersection();
                if (x == 0)
                { 
                    si.HitBegin = StrokeFIndices.BeforeFirst;
                    si.InBegin = StrokeFIndices.BeforeFirst; 
                } 
                else
                { 
                    si.InBegin = crossingList[x - 1].FIndices.EndFIndex;
                    si.HitBegin = crossingList[x - 1].FIndices.BeginFIndex;
                    currentSegmentWithinLasso = SegmentWithinLasso(crossingList[x - 1].EndNode, si.InBegin);
                } 

                if (x == crossingList.Count) 
                { 
                    // NTRAID#WINOS-1132904-2005/04/27-XIAOTU: For a special case when the last intersection is something like (1.2, AL).
                    // As a result the last InSegment should be empty. 
                    if (DoubleUtil.AreClose(si.InBegin, StrokeFIndices.AfterLast))
                    {
                        si.InEnd = StrokeFIndices.BeforeFirst;
                    } 
                    else
                    { 
                        si.InEnd = StrokeFIndices.AfterLast; 
                    }
                    si.HitEnd = StrokeFIndices.AfterLast; 
                }
                else
                {
                    si.InEnd = crossingList[x].FIndices.BeginFIndex; 

                    // NTRAID#WINOS-1132904-2005/04/27-XIAOTU: For a speical case when the first intersection is something like (BF, 0.67). 
                    // As a result the first InSegment should be empty 
                    if (DoubleUtil.AreClose(si.InEnd, StrokeFIndices.BeforeFirst))
                    { 
                        System.Diagnostics.Debug.Assert(DoubleUtil.AreClose(si.InBegin, StrokeFIndices.BeforeFirst));
                        si.InBegin = StrokeFIndices.AfterLast;
                    }
 
                    si.HitEnd = crossingList[x].FIndices.EndFIndex;
                    currentSegmentWithinLasso = SegmentWithinLasso(crossingList[x].StartNode, si.InEnd); 
 
                    // NTRAID#WINOS-1141831-2005/04/27-XIAOTU: If both the start and end position of the current crossing is
                    // outside the lasso, the crossing is a hit-only intersection, i.e., the in-segment is empty. 
                    if (!currentSegmentWithinLasso && !SegmentWithinLasso(crossingList[x].EndNode, si.HitEnd))
                    {
                        currentSegmentWithinLasso = true;
                        si.HitBegin = crossingList[x].FIndices.BeginFIndex; 
                        si.InBegin = StrokeFIndices.AfterLast;
                        si.InEnd = StrokeFIndices.BeforeFirst; 
                        canMerge = false; 
                    }
                } 

                if (currentSegmentWithinLasso)
                {
                    if (x > 0 && previousSegmentInsideLasso && canMerge) 
                    {
                        // we need to consolidate with the previous segment 
                        StrokeIntersection previousIntersection = strokeIntersections[strokeIntersections.Count - 1]; 

                        // For example: previousIntersection = [BF, AL, BF, 0.0027], si = [BF, 0.0027, 0.049, 0.063] 
                        if (previousIntersection.InSegment.IsEmpty)
                        {
                            previousIntersection.InBegin = si.InBegin;
                        } 
                        previousIntersection.InEnd = si.InEnd;
                        previousIntersection.HitEnd = si.HitEnd; 
                        strokeIntersections[strokeIntersections.Count - 1] = previousIntersection; 
                    }
                    else 
                    {
                        strokeIntersections.Add(si);
                    }
 
                    if (DoubleUtil.AreClose(si.HitEnd, StrokeFIndices.AfterLast))
                    { 
                        // The strokeIntersections already cover the end of the stroke. No need to continue. 
                        return;
                    } 
                }
                previousSegmentInsideLasso = currentSegmentWithinLasso;
            }
        } 

        ///  
        /// This flag is set to true when a lasso point has been modified or removed 
        /// from the list, which will invalidate incremental lasso hitteting
        ///  
        internal bool IsIncrementalLassoDirty
        {
            get
            { 
                return _incrementalLassoDirty;
            } 
            set 
            {
                _incrementalLassoDirty = value; 
            }
        }

        ///  
        /// Get a reference to the lasso points store
        ///  
        protected List PointsList 
        {
            get 
            {
                return _points;
            }
        } 

        ///  
        /// Filter out duplicate points (and maybe in the futuer colinear points). 
        /// Return true if the point should be filtered
        ///  
        protected virtual bool Filter(Point point)
        {
            // First point should not be filtered
            if (0 == _points.Count) 
            {
                return false; 
            } 
            // ISSUE-2004/06/14-vsmirnov - If the new segment is collinear with the last one,
            // don't add the point but modify the last point instead. 
            Point lastPoint = _points[_points.Count - 1];
            Vector vector = point - lastPoint;

            // The point will be filtered out, i.e. not added to the list, if the distance to the previous point is 
            // within the tolerance
            return (Math.Abs(vector.X) < MinDistance && Math.Abs(vector.Y) < MinDistance); 
        } 

        ///  
        /// Implemtnation of add point
        /// 
        /// 
        protected virtual void AddPointImpl(Point point) 
        {
            _points.Add(point); 
            _bounds.Union(point); 
        }
        #endregion 

        #region Fields

        private List             _points; 
        private Rect                    _bounds                 = Rect.Empty;
        private bool                    _incrementalLassoDirty  = false; 
        private static readonly double  MinDistance             = 1.0; 

        #endregion 

        /// 
        /// Simple helper struct used to track where the lasso crosses a stroke
        /// we should consider making this a class if generics perf is bad for structs 
        /// 
        private struct LassoCrossing : IComparable 
        { 
            internal StrokeFIndices FIndices;
            internal StrokeNode StartNode; 
            internal StrokeNode EndNode;

            /// 
            /// Constructor 
            /// 
            ///  
            ///  
            public LassoCrossing(StrokeFIndices newFIndices, StrokeNode strokeNode)
            { 
                System.Diagnostics.Debug.Assert(!newFIndices.IsEmpty);
                System.Diagnostics.Debug.Assert(strokeNode.IsValid);
                FIndices = newFIndices;
                StartNode = EndNode = strokeNode; 
            }
 
            ///  
            /// ToString
            ///  
            public override string ToString()
            {
                return FIndices.ToString();
            } 

            ///  
            /// Construct an empty LassoCrossing 
            /// 
            public static LassoCrossing EmptyCrossing 
            {
                get
                {
                    LassoCrossing crossing = new LassoCrossing(); 
                    crossing.FIndices = StrokeFIndices.Empty;
                    return crossing; 
                } 
            }
 
            /// 
            /// Return true if this crossing is an empty one; false otherwise
            /// 
            public bool IsEmpty 
            {
                get { return FIndices.IsEmpty;} 
            } 

            ///  
            /// Implement the interface used for comparison
            /// 
            /// 
            ///  
            public int CompareTo(object obj)
            { 
                System.Diagnostics.Debug.Assert(obj is LassoCrossing); 
                LassoCrossing crossing = (LassoCrossing)obj;
                if (crossing.IsEmpty && this.IsEmpty) 
                {
                    return 0;
                }
                else if (crossing.IsEmpty) 
                {
                    return 1; 
                } 
                else if (this.IsEmpty)
                { 
                    return -1;
                }
                else
                { 
                    return FIndices.CompareTo(crossing.FIndices);
                } 
            } 

            ///  
            /// Merge two crossings into one.
            /// 
            /// 
            /// Return true if these two crossings are actually overlapping and merged; false otherwise 
            public bool Merge(LassoCrossing crossing)
            { 
                if (crossing.IsEmpty) 
                {
                    return false; 
                }

                if (FIndices.IsEmpty && !crossing.IsEmpty)
                { 
                    FIndices = crossing.FIndices;
                    StartNode = crossing.StartNode; 
                    EndNode = crossing.EndNode; 
                    return true;
                } 

                if(DoubleUtil.GreaterThanOrClose(crossing.FIndices.EndFIndex, FIndices.BeginFIndex) &&
                    DoubleUtil.GreaterThanOrClose(FIndices.EndFIndex, crossing.FIndices.BeginFIndex))
                { 
                    if (DoubleUtil.LessThan(crossing.FIndices.BeginFIndex, FIndices.BeginFIndex))
                    { 
                        FIndices.BeginFIndex = crossing.FIndices.BeginFIndex; 
                        StartNode = crossing.StartNode;
                    } 

                    if (DoubleUtil.GreaterThan(crossing.FIndices.EndFIndex, FIndices.EndFIndex))
                    {
                        FIndices.EndFIndex =  crossing.FIndices.EndFIndex; 
                        EndNode = crossing.EndNode;
                    } 
                    return true; 
                }
 
                return false;
            }
        }
    } 
    #endregion
 
 
    #region Single-Loop Lasso
 
    /// 
    /// Implement a special lasso that considers only the first loop
    /// 
    internal class SingleLoopLasso : Lasso 
    {
        ///  
        /// Default constructor 
        /// 
        internal SingleLoopLasso() : base(){} 

        /// 
        /// Return true if the point will be filtered out and should NOT be added to the list
        ///  
        protected override bool Filter(Point point)
        { 
            List points = PointsList; 

            // First point should not be filtered 
            if (0 == points.Count)
            {
                // Just add the new point to the lasso
                return false; 
            }
 
            // Don't add this point if the lasso already has a loop; or 
            // if it's filtered by base class's filter.
            if (true == _hasLoop || true == base.Filter(point)) 
            {
                // Don't add this point to the lasso.
                return true;
            } 

            double intersection = 0f; 
 
            // Now check whether the line lastPoint->point intersect with the
            // existing lasso. 

            if (true == GetIntersectionWithExistingLasso(point, ref intersection))
            {
                System.Diagnostics.Debug.Assert(intersection >= 0 && intersection <= points.Count - 2); 

                if (intersection == points.Count - 2) 
                { 
                    return true;
                } 

                // Adding the new point will form a loop
                int i = (int) intersection;
 
                if (!DoubleUtil.AreClose(i, intersection))
                { 
                    // Move points[i] to the intersection position 
                    Point intersectionPoint = new Point(0, 0);
                    intersectionPoint.X = points[i].X + (intersection - i) * (points[i + 1].X - points[i].X); 
                    intersectionPoint.Y = points[i].Y + (intersection - i) * (points[i + 1].Y - points[i].Y);
                    points[i] = intersectionPoint;
                    IsIncrementalLassoDirty = true;
                } 

                // Since the lasso has a self loop and the loop starts at points[i], points[0] to 
                // points[i-1] should be removed 
                if (i > 0)
                { 
                    points.RemoveRange(0, i /*count*/);   // Remove points[0] to points[i-1]
                    IsIncrementalLassoDirty = true;
                }
 
                if (true == IsIncrementalLassoDirty)
                { 
                    // Update the bounds 
                    Rect bounds = Rect.Empty;
                    for (int j = 0; j < points.Count; j++) 
                    {
                        bounds.Union(points[j]);
                    }
                    Bounds = bounds; 
                }
 
                // The lasso has a self_loop, any more points will be neglected. 
                _hasLoop = true;
 
                // Don't add this point to the lasso.
                return true;
            }
 
            // Just add the new point to the lasso
            return false; 
        } 

        protected override void AddPointImpl(Point point) 
        {
            _prevBounds = Bounds;
            base.AddPointImpl(point);
        } 

        ///  
        /// If the line _points[Count -1]->point insersect with the existing lasso, return true 
        /// and bIndex value is set to a doulbe value representing position of the intersection.
        ///  
        private bool GetIntersectionWithExistingLasso(Point point, ref double bIndex)
        {
            List points = PointsList;
            int count = points.Count; 

            Rect newRect = new Rect(points[count - 1], point); 
 
            if (false == _prevBounds.IntersectsWith(newRect))
            { 
                // The point is not contained in the bound of the existing lasso, no intersection.
                return false;
            }
 
            for (int i = 0; i < count -2; i++)
            { 
                Rect currRect = new Rect(points[i], points[i+1]); 
                if (!currRect.IntersectsWith(newRect))
                { 
                    continue;
                }

                double s = FindIntersection(points[count-1] - points[i],            /*hitBegin*/ 
                                                    point - points[i],              /*hitEnd*/
                                                    new Vector(0, 0),               /*orgBegin*/ 
                                                    points[i+1] - points[i]         /*orgEnd*/); 
                if (s >=0 && s <= 1)
                { 
                    // Intersection found, adjust the fIndex
                    bIndex = i + s;
                    return true;
                } 
            }
 
            // No intersection 
            return false;
        } 


        /// 
        /// Finds the intersection between the segment [hitBegin, hitEnd] and the segment [orgBegin, orgEnd]. 
        /// 
        private static double FindIntersection(Vector hitBegin, Vector hitEnd, Vector orgBegin, Vector orgEnd) 
        { 
            System.Diagnostics.Debug.Assert(hitEnd != hitBegin && orgBegin != orgEnd);
 
            //---------------------------------------------------------------------
            // Source: http://isc.faqs.org/faqs/graphics/algorithms-faq/
            // Subject 1.03: How do I find intersections of 2 2D line segments?
            // 
            // Let A,B,C,D be 2-space position vectors.  Then the directed line
            // segments AB & CD are given by: 
            // 
            // AB=A+r(B-A), r in [0,1]
            // CD=C+s(D-C), s in [0,1] 
            //
            // If AB & CD intersect, then
            //
            // A+r(B-A)=C+s(D-C), or  Ax+r(Bx-Ax)=Cx+s(Dx-Cx) 
            // Ay+r(By-Ay)=Cy+s(Dy-Cy)  for some r,s in [0,1]
            // 
            // Solving the above for r and s yields 
            //
            //      (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy) 
            //  r = -----------------------------  (eqn 1)
            //      (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
            //
            //      (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay) 
            //  s = -----------------------------  (eqn 2)
            //      (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx) 
            // 
            // Let P be the position vector of the intersection point, then
            // 
            //  P=A+r(B-A) or Px=Ax+r(Bx-Ax) and Py=Ay+r(By-Ay)
            //
            // By examining the values of r & s, you can also determine some
            // other limiting conditions: 
            //  If 0 <= r <= 1 && 0 <= s <= 1, intersection exists
            //  r < 0 or r > 1 or s < 0 or s > 1 line segments do not intersect 
            //  If the denominator in eqn 1 is zero, AB & CD are parallel 
            //  If the numerator in eqn 1 is also zero, AB & CD are collinear.
            //  If they are collinear, then the segments may be projected to the x- 
            //  or y-axis, and overlap of the projected intervals checked.
            //
            // If the intersection point of the 2 lines are needed (lines in this
            // context mean infinite lines) regardless whether the two line 
            // segments intersect, then
            //  If r > 1, P is located on extension of AB 
            //  If r < 0, P is located on extension of BA 
            //  If s > 1, P is located on extension of CD
            //  If s < 0, P is located on extension of DC 
            // Also note that the denominators of eqn 1 & 2 are identical.
            //
            // References:
            // [O'Rourke (C)] pp. 249-51 
            // [Gems III] pp. 199-202 "Faster Line Segment Intersection,"
            //--------------------------------------------------------------------- 
 
            // Calculate the vectors.
            Vector AB = orgEnd - orgBegin;          // B - A 
            Vector CA = orgBegin - hitBegin;        // A - C
            Vector CD = hitEnd - hitBegin;          // D - C
            double det = Vector.Determinant(AB, CD);
 
            if (DoubleUtil.IsZero(det))
            { 
                // The segments are parallel. no intersection 
                return NoIntersection;
            } 

            double r = AdjustFIndex(Vector.Determinant(AB, CA) / det);

            if (r >= 0 && r <= 1) 
            {
                // The line defined AB does cross the segment CD. 
                double s = AdjustFIndex(Vector.Determinant(CD, CA) / det); 
                if (s >= 0 && s <= 1)
                { 
                    // The crossing point is on the segment AB as well.
                    // Intersection found.
                    return s;
                } 
            }
 
            // No intersection found 
            return NoIntersection;
        } 

        /// 
        /// Clears double's computation fuzz around 0 and 1
        ///  
        internal static double AdjustFIndex(double findex)
        { 
            return DoubleUtil.IsZero(findex) ? 0 : (DoubleUtil.IsOne(findex) ? 1 : findex); 
        }
 
        private bool _hasLoop                           = false;
        private Rect _prevBounds                        = Rect.Empty;
        private static readonly double NoIntersection   = StrokeFIndices.BeforeFirst;
    } 
    #endregion
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//------------------------------------------------------------------------ 
// 
// Copyright (c) Microsoft Corporation. All rights reserved.
// 
//----------------------------------------------------------------------- 
//#define TRACE
 
using System; 
using System.Windows;
using System.Windows.Ink; 
using System.Windows.Media;
using System.Collections.Generic;
using System.Globalization;
 
namespace MS.Internal.Ink
{ 
    #region Lasso 

    ///  
    /// Represents a lasso for selecting/cutting ink strokes with.
    /// Lasso is a sequence of points defining a complex region (polygon)
    /// 
    internal class Lasso 
    {
        #region Constructors 
 
        /// 
        /// Default c-tor. Used in incremental hit-testing. 
        /// 
        internal Lasso()
        {
            _points = new List(); 
        }
 
        #endregion 

        #region API 

        /// 
        /// Returns the bounds of the lasso
        ///  
        internal Rect Bounds
        { 
            get { return _bounds; } 
            set { _bounds = value;}
        } 

        /// 
        /// Tells whether the lasso captures any area
        ///  
        internal bool IsEmpty
        { 
            get 
            {
                System.Diagnostics.Debug.Assert(_points != null); 
                // The value is based on the assumption that the lasso is normalized
                // i.e. it has no duplicate points or collinear sibling segments.
                return (_points.Count < 3);
            } 
        }
 
        ///  
        /// Returns the count of points in the lasso
        ///  
        internal int PointCount
        {
            get
            { 
                System.Diagnostics.Debug.Assert(_points != null);
                return _points.Count; 
            } 
        }
 
        /// 
        /// Index-based read-only accessor to lasso points
        /// 
        /// index of the point to return 
        /// a point in the lasso
        internal Point this[int index] 
        { 
            get
            { 
                System.Diagnostics.Debug.Assert(_points != null);
                System.Diagnostics.Debug.Assert((0 <= index) && (index < _points.Count));

                return _points[index]; 
            }
        } 
 
        /// 
        /// Extends the lasso by appending more points 
        /// 
        /// new points
        internal void AddPoints(IEnumerable points)
        { 
            System.Diagnostics.Debug.Assert(null != points);
 
            foreach (Point point in points) 
            {
                AddPoint(point); 
            }
        }

        ///  
        /// Appends a point to the lasso
        ///  
        /// new lasso point 
        internal void AddPoint(Point point)
        { 
            System.Diagnostics.Debug.Assert(_points != null);
            if (!Filter(point))
            {
                // The point is not filtered, add it to the lasso 
                AddPointImpl(point);
            } 
        } 

        ///  
        /// This method implement the core algorithm to check whether a point is within a polygon
        /// that are formed by the lasso points.
        /// 
        ///  
        /// true if the point is contained within the lasso; false otherwise 
        internal bool Contains(Point point) 
        { 
            System.Diagnostics.Debug.Assert(_points != null);
 
            if (false == _bounds.Contains(point))
            {
                return false;
            } 

            bool isHigher = false; 
            int last = _points.Count; 
            while (--last >= 0)
            { 
                if (!DoubleUtil.AreClose(_points[last].Y,point.Y))
                {
                    isHigher = (point.Y < _points[last].Y);
                    break; 
                }
            } 
 
            bool isInside = false;
            Point prevLassoPoint = _points[_points.Count - 1]; 
            for (int i = 0; i < _points.Count; i++)
            {
                Point lassoPoint = _points[i];
                if (DoubleUtil.AreClose(lassoPoint.Y, point.Y)) 
                {
                    if (DoubleUtil.AreClose(lassoPoint.X, point.X)) 
                    { 
                        isInside = true;
                        break; 
                    }
                    if ((0 != i) && DoubleUtil.AreClose(prevLassoPoint.Y, point.Y) &&
                        DoubleUtil.GreaterThanOrClose(point.X, Math.Min(prevLassoPoint.X, lassoPoint.X)) &&
                        DoubleUtil.LessThanOrClose(point.X, Math.Max(prevLassoPoint.X, lassoPoint.X))) 
                    {
                        isInside = true; 
                        break; 
                    }
                } 
                else if (isHigher != (point.Y < lassoPoint.Y))
                {
                    isHigher = !isHigher;
                    if (DoubleUtil.GreaterThanOrClose(point.X, Math.Max(prevLassoPoint.X, lassoPoint.X))) 
                    {
                        // there certainly is an intersection on the left 
                        isInside = !isInside; 
                    }
                    else if (DoubleUtil.GreaterThanOrClose(point.X, Math.Min(prevLassoPoint.X, lassoPoint.X))) 
                    {
                        // The X of the point lies within the x ranges for the segment.
                        // Calculate the x value of the point where the segment intersects with the line.
                        Vector lassoSegment = lassoPoint - prevLassoPoint; 
                        System.Diagnostics.Debug.Assert(lassoSegment.Y != 0);
                        double x = prevLassoPoint.X + (lassoSegment.X / lassoSegment.Y) * (point.Y - prevLassoPoint.Y); 
                        if (DoubleUtil.GreaterThanOrClose(point.X, x)) 
                        {
                            isInside = !isInside; 
                        }
                    }
                }
                prevLassoPoint = lassoPoint; 
            }
            return isInside; 
        } 

        internal StrokeIntersection[] HitTest(StrokeNodeIterator iterator) 
        {
            System.Diagnostics.Debug.Assert(_points != null);
            System.Diagnostics.Debug.Assert(iterator != null);
 
#if TRACE
            System.Diagnostics.Debug.WriteLine(String.Format("Lasso: start lasso histtesing a new stroke ...")); 
#endif 

            if (_points.Count < 3) 
            {
                //
                // it takes at least 3 points to create a lasso
                // 
#if TRACE
                System.Diagnostics.Debug.WriteLine(String.Format("Lasso:.............. done. Nothing hit because lasso lasso has only {0} points", _points.Count)); 
#endif 
                return new StrokeIntersection[0];
            } 

            //
            // We're about to perform hit testing with a lasso.
            // To do so we need to iterate through each StrokeNode. 
            // As we do, we calculate the bounding rect between it
            // and the previous StrokeNode and store this in 'currentStrokeSegmentBounds' 
            // 
            // Next, we check to see if that StrokeNode pair's bounding box intersects
            // with the bounding box of the Lasso points.  If not, we continue iterating through 
            // StrokeNode pairs.
            //
            // If it does, we do a more granular hit test by pairing points in the Lasso, getting
            // their bounding box and seeing if that bounding box intersects our current StrokeNode 
            // pair
            // 
 
            Point lastNodePosition = new Point();
            Point lassoLastPoint = _points[_points.Count - 1]; 
            Rect currentStrokeSegmentBounds = Rect.Empty;

            // Initilize the current crossing to be an empty one
            LassoCrossing currentCrossing = LassoCrossing.EmptyCrossing; 

            // Creat a list to hold all the crossings 
            List crossingList = new List(); 
            for (int i = 0; i < iterator.Count; i++)
            { 
                StrokeNode strokeNode = iterator[i];
                Rect nodeBounds = strokeNode.GetBounds();
                currentStrokeSegmentBounds.Union(nodeBounds);
 
                // Skip the node if it's outside of the lasso's bounds
                if (currentStrokeSegmentBounds.IntersectsWith(_bounds) == true) 
                { 
                    // currentStrokeSegmentBounds, made up of the bounding box of
                    // this StrokeNode unioned with the last StrokeNode, 
                    // intersects the lasso bounding box.
                    //
                    // Now we need to iterate through the lasso points and find out where they cross
                    // 
                    Point lastPoint = lassoLastPoint;
                    foreach (Point point in _points) 
                    { 
                        //
                        // calculate a segment of the lasso from the last point 
                        // to the current point
                        //
                        Rect lassoSegmentBounds = new Rect(lastPoint, point);
 
                        //
                        // see if this lasso segment intersects with the current stroke segment 
                        // 
                        if (!currentStrokeSegmentBounds.IntersectsWith(lassoSegmentBounds))
                        { 
                            lastPoint = point;
                            continue;
                        }
 
                        //
                        // the lasso segment DOES intersect with the current stroke segment 
                        // find out precisely where 
                        //
                        StrokeFIndices strokeFIndices = strokeNode.CutTest(lastPoint, point); 

#if TRACE
                        if (!strokeFIndices.IsEmpty)
                        { 
                            System.Diagnostics.Debug.WriteLine (String.Format("\t\tLasso: found nonempty StrokeFIndices {0} with points [{1}] and  [{2}] for strokeNode at {3}", strokeFIndices, lastPoint, point,strokeNode.Position));
                        } 
#endif 
                        lastPoint = point;
                        if (strokeFIndices.IsEmpty) 
                        {
                            // current lasso segment does not hit the stroke segment, continue with the next lasso point
                            continue;
                        } 

                        // Create a potentially new crossing for the current hit testing result. 
                        LassoCrossing potentialNewCrossing = new LassoCrossing(strokeFIndices, strokeNode); 

                        // Try to merge with the current crossing. If the merge is succussful (return true), the new crossing is actually 
                        // continueing the current crossing, so do not start a new crossing. Otherwise, start a new one and add the existing
                        // one to the list.
                        if (!currentCrossing.Merge(potentialNewCrossing))
                        { 
#if TRACE
                            System.Diagnostics.Debug.WriteLine(String.Format("\tLasso: adding {0}  to crossingList and starting a new crossing {1}", currentCrossing, potentialNewCrossing)); 
#endif 

                            // start a new crossing and add the existing on to the list 
                            crossingList.Add(currentCrossing);
                            currentCrossing = potentialNewCrossing;
                        }
                    } 

                } 
 
                // Continue with the next node
                currentStrokeSegmentBounds = nodeBounds; 
                lastNodePosition = strokeNode.Position;
            }

 
            // Adding the last crossing to the list, if valid
            if (!currentCrossing.IsEmpty) 
            { 
                crossingList.Add(currentCrossing);
#if TRACE 
                System.Diagnostics.Debug.WriteLine(String.Format("\tLasso: adding the last crossing {0}  to crossingList", currentCrossing));
#endif
            }
 
            // Handle the special case of no intersection at all
            if (crossingList.Count == 0) 
            { 
                // the stroke was either completely inside the lasso
                // or outside the lasso 
                if (this.Contains(lastNodePosition))
                {
                    StrokeIntersection[] strokeIntersections = new StrokeIntersection[1];
                    strokeIntersections[0] = StrokeIntersection.Full; 
                    return strokeIntersections;
                } 
                else 
                {
                    return new StrokeIntersection[0]; 
                }
            }

            // It is still possible that the current crossing list is not sorted or overlapping. 
            // Sort the list and merge the overlapping ones.
            SortAndMerge(ref crossingList); 
 
            // Produce the hit test results and store them in a list
            List strokeIntersectionList = new List(); 
            ProduceHitTestResults(crossingList, strokeIntersectionList);

#if TRACE
            System.Diagnostics.Debug.WriteLine(String.Format("Lasso:.............. done. Lasso hit {0} segments", strokeIntersectionList.Count)); 
#endif
            return strokeIntersectionList.ToArray(); 
        } 

        ///  
        /// Sort and merge the crossing list
        /// 
        /// The crossing list to sort/merge
        private static void SortAndMerge(ref List crossingList) 
        {
            // Sort the crossings based on the BeginFIndex values 
            crossingList.Sort(); 

            List mergedList = new List(); 
            LassoCrossing mcrossing = LassoCrossing.EmptyCrossing;
            foreach (LassoCrossing crossing in crossingList)
            {
                System.Diagnostics.Debug.Assert(!crossing.IsEmpty && crossing.StartNode.IsValid && crossing.EndNode.IsValid); 
                if (!mcrossing.Merge(crossing))
                { 
                    System.Diagnostics.Debug.Assert(!mcrossing.IsEmpty && mcrossing.StartNode.IsValid && mcrossing.EndNode.IsValid); 
                    mergedList.Add(mcrossing);
                    mcrossing = crossing; 
                }
            }
            if (!mcrossing.IsEmpty)
            { 
                System.Diagnostics.Debug.Assert(!mcrossing.IsEmpty && mcrossing.StartNode.IsValid && mcrossing.EndNode.IsValid);
                mergedList.Add(mcrossing); 
            } 
            crossingList = mergedList;
        } 


        /// 
        /// Helper function to find out whether a point is inside the lasso 
        /// 
        private bool SegmentWithinLasso(StrokeNode strokeNode, double fIndex) 
        { 
            bool currentSegmentWithinLasso;
            if (DoubleUtil.AreClose(fIndex, StrokeFIndices.BeforeFirst)) 
            {
                // This should check against the very first stroke node
                currentSegmentWithinLasso = this.Contains(strokeNode.GetPointAt(0f));
            } 
            else if (DoubleUtil.AreClose(fIndex, StrokeFIndices.AfterLast))
            { 
                // This should check against the last stroke node 
                currentSegmentWithinLasso = this.Contains(strokeNode.Position);
            } 
            else
            {
                currentSegmentWithinLasso = this.Contains(strokeNode.GetPointAt(fIndex));
            } 

            return currentSegmentWithinLasso; 
        } 

        ///  
        /// Helper function to find out the hit test result
        /// 
        private void ProduceHitTestResults(
                                List crossingList, List strokeIntersections) 
        {
            bool previousSegmentInsideLasso = false; 
            for (int x = 0; x <= crossingList.Count; x++) 
            {
                bool currentSegmentWithinLasso = false; 
                bool canMerge = true;
                StrokeIntersection si = new StrokeIntersection();
                if (x == 0)
                { 
                    si.HitBegin = StrokeFIndices.BeforeFirst;
                    si.InBegin = StrokeFIndices.BeforeFirst; 
                } 
                else
                { 
                    si.InBegin = crossingList[x - 1].FIndices.EndFIndex;
                    si.HitBegin = crossingList[x - 1].FIndices.BeginFIndex;
                    currentSegmentWithinLasso = SegmentWithinLasso(crossingList[x - 1].EndNode, si.InBegin);
                } 

                if (x == crossingList.Count) 
                { 
                    // NTRAID#WINOS-1132904-2005/04/27-XIAOTU: For a special case when the last intersection is something like (1.2, AL).
                    // As a result the last InSegment should be empty. 
                    if (DoubleUtil.AreClose(si.InBegin, StrokeFIndices.AfterLast))
                    {
                        si.InEnd = StrokeFIndices.BeforeFirst;
                    } 
                    else
                    { 
                        si.InEnd = StrokeFIndices.AfterLast; 
                    }
                    si.HitEnd = StrokeFIndices.AfterLast; 
                }
                else
                {
                    si.InEnd = crossingList[x].FIndices.BeginFIndex; 

                    // NTRAID#WINOS-1132904-2005/04/27-XIAOTU: For a speical case when the first intersection is something like (BF, 0.67). 
                    // As a result the first InSegment should be empty 
                    if (DoubleUtil.AreClose(si.InEnd, StrokeFIndices.BeforeFirst))
                    { 
                        System.Diagnostics.Debug.Assert(DoubleUtil.AreClose(si.InBegin, StrokeFIndices.BeforeFirst));
                        si.InBegin = StrokeFIndices.AfterLast;
                    }
 
                    si.HitEnd = crossingList[x].FIndices.EndFIndex;
                    currentSegmentWithinLasso = SegmentWithinLasso(crossingList[x].StartNode, si.InEnd); 
 
                    // NTRAID#WINOS-1141831-2005/04/27-XIAOTU: If both the start and end position of the current crossing is
                    // outside the lasso, the crossing is a hit-only intersection, i.e., the in-segment is empty. 
                    if (!currentSegmentWithinLasso && !SegmentWithinLasso(crossingList[x].EndNode, si.HitEnd))
                    {
                        currentSegmentWithinLasso = true;
                        si.HitBegin = crossingList[x].FIndices.BeginFIndex; 
                        si.InBegin = StrokeFIndices.AfterLast;
                        si.InEnd = StrokeFIndices.BeforeFirst; 
                        canMerge = false; 
                    }
                } 

                if (currentSegmentWithinLasso)
                {
                    if (x > 0 && previousSegmentInsideLasso && canMerge) 
                    {
                        // we need to consolidate with the previous segment 
                        StrokeIntersection previousIntersection = strokeIntersections[strokeIntersections.Count - 1]; 

                        // For example: previousIntersection = [BF, AL, BF, 0.0027], si = [BF, 0.0027, 0.049, 0.063] 
                        if (previousIntersection.InSegment.IsEmpty)
                        {
                            previousIntersection.InBegin = si.InBegin;
                        } 
                        previousIntersection.InEnd = si.InEnd;
                        previousIntersection.HitEnd = si.HitEnd; 
                        strokeIntersections[strokeIntersections.Count - 1] = previousIntersection; 
                    }
                    else 
                    {
                        strokeIntersections.Add(si);
                    }
 
                    if (DoubleUtil.AreClose(si.HitEnd, StrokeFIndices.AfterLast))
                    { 
                        // The strokeIntersections already cover the end of the stroke. No need to continue. 
                        return;
                    } 
                }
                previousSegmentInsideLasso = currentSegmentWithinLasso;
            }
        } 

        ///  
        /// This flag is set to true when a lasso point has been modified or removed 
        /// from the list, which will invalidate incremental lasso hitteting
        ///  
        internal bool IsIncrementalLassoDirty
        {
            get
            { 
                return _incrementalLassoDirty;
            } 
            set 
            {
                _incrementalLassoDirty = value; 
            }
        }

        ///  
        /// Get a reference to the lasso points store
        ///  
        protected List PointsList 
        {
            get 
            {
                return _points;
            }
        } 

        ///  
        /// Filter out duplicate points (and maybe in the futuer colinear points). 
        /// Return true if the point should be filtered
        ///  
        protected virtual bool Filter(Point point)
        {
            // First point should not be filtered
            if (0 == _points.Count) 
            {
                return false; 
            } 
            // ISSUE-2004/06/14-vsmirnov - If the new segment is collinear with the last one,
            // don't add the point but modify the last point instead. 
            Point lastPoint = _points[_points.Count - 1];
            Vector vector = point - lastPoint;

            // The point will be filtered out, i.e. not added to the list, if the distance to the previous point is 
            // within the tolerance
            return (Math.Abs(vector.X) < MinDistance && Math.Abs(vector.Y) < MinDistance); 
        } 

        ///  
        /// Implemtnation of add point
        /// 
        /// 
        protected virtual void AddPointImpl(Point point) 
        {
            _points.Add(point); 
            _bounds.Union(point); 
        }
        #endregion 

        #region Fields

        private List             _points; 
        private Rect                    _bounds                 = Rect.Empty;
        private bool                    _incrementalLassoDirty  = false; 
        private static readonly double  MinDistance             = 1.0; 

        #endregion 

        /// 
        /// Simple helper struct used to track where the lasso crosses a stroke
        /// we should consider making this a class if generics perf is bad for structs 
        /// 
        private struct LassoCrossing : IComparable 
        { 
            internal StrokeFIndices FIndices;
            internal StrokeNode StartNode; 
            internal StrokeNode EndNode;

            /// 
            /// Constructor 
            /// 
            ///  
            ///  
            public LassoCrossing(StrokeFIndices newFIndices, StrokeNode strokeNode)
            { 
                System.Diagnostics.Debug.Assert(!newFIndices.IsEmpty);
                System.Diagnostics.Debug.Assert(strokeNode.IsValid);
                FIndices = newFIndices;
                StartNode = EndNode = strokeNode; 
            }
 
            ///  
            /// ToString
            ///  
            public override string ToString()
            {
                return FIndices.ToString();
            } 

            ///  
            /// Construct an empty LassoCrossing 
            /// 
            public static LassoCrossing EmptyCrossing 
            {
                get
                {
                    LassoCrossing crossing = new LassoCrossing(); 
                    crossing.FIndices = StrokeFIndices.Empty;
                    return crossing; 
                } 
            }
 
            /// 
            /// Return true if this crossing is an empty one; false otherwise
            /// 
            public bool IsEmpty 
            {
                get { return FIndices.IsEmpty;} 
            } 

            ///  
            /// Implement the interface used for comparison
            /// 
            /// 
            ///  
            public int CompareTo(object obj)
            { 
                System.Diagnostics.Debug.Assert(obj is LassoCrossing); 
                LassoCrossing crossing = (LassoCrossing)obj;
                if (crossing.IsEmpty && this.IsEmpty) 
                {
                    return 0;
                }
                else if (crossing.IsEmpty) 
                {
                    return 1; 
                } 
                else if (this.IsEmpty)
                { 
                    return -1;
                }
                else
                { 
                    return FIndices.CompareTo(crossing.FIndices);
                } 
            } 

            ///  
            /// Merge two crossings into one.
            /// 
            /// 
            /// Return true if these two crossings are actually overlapping and merged; false otherwise 
            public bool Merge(LassoCrossing crossing)
            { 
                if (crossing.IsEmpty) 
                {
                    return false; 
                }

                if (FIndices.IsEmpty && !crossing.IsEmpty)
                { 
                    FIndices = crossing.FIndices;
                    StartNode = crossing.StartNode; 
                    EndNode = crossing.EndNode; 
                    return true;
                } 

                if(DoubleUtil.GreaterThanOrClose(crossing.FIndices.EndFIndex, FIndices.BeginFIndex) &&
                    DoubleUtil.GreaterThanOrClose(FIndices.EndFIndex, crossing.FIndices.BeginFIndex))
                { 
                    if (DoubleUtil.LessThan(crossing.FIndices.BeginFIndex, FIndices.BeginFIndex))
                    { 
                        FIndices.BeginFIndex = crossing.FIndices.BeginFIndex; 
                        StartNode = crossing.StartNode;
                    } 

                    if (DoubleUtil.GreaterThan(crossing.FIndices.EndFIndex, FIndices.EndFIndex))
                    {
                        FIndices.EndFIndex =  crossing.FIndices.EndFIndex; 
                        EndNode = crossing.EndNode;
                    } 
                    return true; 
                }
 
                return false;
            }
        }
    } 
    #endregion
 
 
    #region Single-Loop Lasso
 
    /// 
    /// Implement a special lasso that considers only the first loop
    /// 
    internal class SingleLoopLasso : Lasso 
    {
        ///  
        /// Default constructor 
        /// 
        internal SingleLoopLasso() : base(){} 

        /// 
        /// Return true if the point will be filtered out and should NOT be added to the list
        ///  
        protected override bool Filter(Point point)
        { 
            List points = PointsList; 

            // First point should not be filtered 
            if (0 == points.Count)
            {
                // Just add the new point to the lasso
                return false; 
            }
 
            // Don't add this point if the lasso already has a loop; or 
            // if it's filtered by base class's filter.
            if (true == _hasLoop || true == base.Filter(point)) 
            {
                // Don't add this point to the lasso.
                return true;
            } 

            double intersection = 0f; 
 
            // Now check whether the line lastPoint->point intersect with the
            // existing lasso. 

            if (true == GetIntersectionWithExistingLasso(point, ref intersection))
            {
                System.Diagnostics.Debug.Assert(intersection >= 0 && intersection <= points.Count - 2); 

                if (intersection == points.Count - 2) 
                { 
                    return true;
                } 

                // Adding the new point will form a loop
                int i = (int) intersection;
 
                if (!DoubleUtil.AreClose(i, intersection))
                { 
                    // Move points[i] to the intersection position 
                    Point intersectionPoint = new Point(0, 0);
                    intersectionPoint.X = points[i].X + (intersection - i) * (points[i + 1].X - points[i].X); 
                    intersectionPoint.Y = points[i].Y + (intersection - i) * (points[i + 1].Y - points[i].Y);
                    points[i] = intersectionPoint;
                    IsIncrementalLassoDirty = true;
                } 

                // Since the lasso has a self loop and the loop starts at points[i], points[0] to 
                // points[i-1] should be removed 
                if (i > 0)
                { 
                    points.RemoveRange(0, i /*count*/);   // Remove points[0] to points[i-1]
                    IsIncrementalLassoDirty = true;
                }
 
                if (true == IsIncrementalLassoDirty)
                { 
                    // Update the bounds 
                    Rect bounds = Rect.Empty;
                    for (int j = 0; j < points.Count; j++) 
                    {
                        bounds.Union(points[j]);
                    }
                    Bounds = bounds; 
                }
 
                // The lasso has a self_loop, any more points will be neglected. 
                _hasLoop = true;
 
                // Don't add this point to the lasso.
                return true;
            }
 
            // Just add the new point to the lasso
            return false; 
        } 

        protected override void AddPointImpl(Point point) 
        {
            _prevBounds = Bounds;
            base.AddPointImpl(point);
        } 

        ///  
        /// If the line _points[Count -1]->point insersect with the existing lasso, return true 
        /// and bIndex value is set to a doulbe value representing position of the intersection.
        ///  
        private bool GetIntersectionWithExistingLasso(Point point, ref double bIndex)
        {
            List points = PointsList;
            int count = points.Count; 

            Rect newRect = new Rect(points[count - 1], point); 
 
            if (false == _prevBounds.IntersectsWith(newRect))
            { 
                // The point is not contained in the bound of the existing lasso, no intersection.
                return false;
            }
 
            for (int i = 0; i < count -2; i++)
            { 
                Rect currRect = new Rect(points[i], points[i+1]); 
                if (!currRect.IntersectsWith(newRect))
                { 
                    continue;
                }

                double s = FindIntersection(points[count-1] - points[i],            /*hitBegin*/ 
                                                    point - points[i],              /*hitEnd*/
                                                    new Vector(0, 0),               /*orgBegin*/ 
                                                    points[i+1] - points[i]         /*orgEnd*/); 
                if (s >=0 && s <= 1)
                { 
                    // Intersection found, adjust the fIndex
                    bIndex = i + s;
                    return true;
                } 
            }
 
            // No intersection 
            return false;
        } 


        /// 
        /// Finds the intersection between the segment [hitBegin, hitEnd] and the segment [orgBegin, orgEnd]. 
        /// 
        private static double FindIntersection(Vector hitBegin, Vector hitEnd, Vector orgBegin, Vector orgEnd) 
        { 
            System.Diagnostics.Debug.Assert(hitEnd != hitBegin && orgBegin != orgEnd);
 
            //---------------------------------------------------------------------
            // Source: http://isc.faqs.org/faqs/graphics/algorithms-faq/
            // Subject 1.03: How do I find intersections of 2 2D line segments?
            // 
            // Let A,B,C,D be 2-space position vectors.  Then the directed line
            // segments AB & CD are given by: 
            // 
            // AB=A+r(B-A), r in [0,1]
            // CD=C+s(D-C), s in [0,1] 
            //
            // If AB & CD intersect, then
            //
            // A+r(B-A)=C+s(D-C), or  Ax+r(Bx-Ax)=Cx+s(Dx-Cx) 
            // Ay+r(By-Ay)=Cy+s(Dy-Cy)  for some r,s in [0,1]
            // 
            // Solving the above for r and s yields 
            //
            //      (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy) 
            //  r = -----------------------------  (eqn 1)
            //      (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
            //
            //      (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay) 
            //  s = -----------------------------  (eqn 2)
            //      (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx) 
            // 
            // Let P be the position vector of the intersection point, then
            // 
            //  P=A+r(B-A) or Px=Ax+r(Bx-Ax) and Py=Ay+r(By-Ay)
            //
            // By examining the values of r & s, you can also determine some
            // other limiting conditions: 
            //  If 0 <= r <= 1 && 0 <= s <= 1, intersection exists
            //  r < 0 or r > 1 or s < 0 or s > 1 line segments do not intersect 
            //  If the denominator in eqn 1 is zero, AB & CD are parallel 
            //  If the numerator in eqn 1 is also zero, AB & CD are collinear.
            //  If they are collinear, then the segments may be projected to the x- 
            //  or y-axis, and overlap of the projected intervals checked.
            //
            // If the intersection point of the 2 lines are needed (lines in this
            // context mean infinite lines) regardless whether the two line 
            // segments intersect, then
            //  If r > 1, P is located on extension of AB 
            //  If r < 0, P is located on extension of BA 
            //  If s > 1, P is located on extension of CD
            //  If s < 0, P is located on extension of DC 
            // Also note that the denominators of eqn 1 & 2 are identical.
            //
            // References:
            // [O'Rourke (C)] pp. 249-51 
            // [Gems III] pp. 199-202 "Faster Line Segment Intersection,"
            //--------------------------------------------------------------------- 
 
            // Calculate the vectors.
            Vector AB = orgEnd - orgBegin;          // B - A 
            Vector CA = orgBegin - hitBegin;        // A - C
            Vector CD = hitEnd - hitBegin;          // D - C
            double det = Vector.Determinant(AB, CD);
 
            if (DoubleUtil.IsZero(det))
            { 
                // The segments are parallel. no intersection 
                return NoIntersection;
            } 

            double r = AdjustFIndex(Vector.Determinant(AB, CA) / det);

            if (r >= 0 && r <= 1) 
            {
                // The line defined AB does cross the segment CD. 
                double s = AdjustFIndex(Vector.Determinant(CD, CA) / det); 
                if (s >= 0 && s <= 1)
                { 
                    // The crossing point is on the segment AB as well.
                    // Intersection found.
                    return s;
                } 
            }
 
            // No intersection found 
            return NoIntersection;
        } 

        /// 
        /// Clears double's computation fuzz around 0 and 1
        ///  
        internal static double AdjustFIndex(double findex)
        { 
            return DoubleUtil.IsZero(findex) ? 0 : (DoubleUtil.IsOne(findex) ? 1 : findex); 
        }
 
        private bool _hasLoop                           = false;
        private Rect _prevBounds                        = Rect.Empty;
        private static readonly double NoIntersection   = StrokeFIndices.BeforeFirst;
    } 
    #endregion
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK