StrokeNodeOperations2.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / wpf / src / Core / CSharp / MS / Internal / Ink / StrokeNodeOperations2.cs / 1305600 / StrokeNodeOperations2.cs

                            //------------------------------------------------------------------------ 
// 
// Copyright (c) Microsoft Corporation. All rights reserved.
// 
//----------------------------------------------------------------------- 

using System; 
using System.Collections.Generic; 
using System.Windows;
using System.Windows.Media; 
using System.Windows.Input;

namespace MS.Internal.Ink
{ 
    /// 
    /// Static methods implementing generic hit-testing operations 
    ///  
    internal partial class StrokeNodeOperations
    { 
        #region enum HitResult

        ///  A set of possible results frequently used in StrokeNodeOperations and derived classes
        internal enum HitResult 
        {
            Hit, 
            Left, 
            Right,
            InFront, 
            Behind
        }

        #endregion 

        #region HitTestXxxYyy 
 
        /// 
        /// Hit-tests a linear segment against a convex polygon. 
        /// 
        /// Vertices of the polygon (in clockwise order)
        /// an end point of the hitting segment
        /// an end point of the hitting segment 
        /// true if hit; false otherwise
        internal static bool HitTestPolygonSegment(Vector[] vertices, Vector hitBegin, Vector hitEnd) 
        { 
            System.Diagnostics.Debug.Assert((null != vertices) && (2 < vertices.Length));
 
            HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
            int count = vertices.Length;
            Vector vertex = vertices[count - 1];
            for (int i = 0; i < count; i++) 
            {
                Vector nextVertex = vertices[i]; 
                hitResult = WhereIsSegmentAboutSegment(hitBegin, hitEnd, vertex, nextVertex); 
                if (HitResult.Hit == hitResult)
                { 
                    return true;
                }
                if (IsOutside(hitResult, prevResult))
                { 
                    return false;
                } 
                if (i == 0) 
                {
                    firstResult = hitResult; 
                }
                prevResult = hitResult;
                vertex = nextVertex;
            } 
            return (false == IsOutside(firstResult, hitResult));
        } 
 
        /// 
        /// This is a specialized version of HitTestPolygonSegment that takes 
        /// a Quad for a polygon. This method is called very intensively by
        /// hit-testing API and we don't want to create Vector[] for every quad it hit-tests.
        /// 
        /// the connecting quad to test against 
        /// begin point of the hitting segment
        /// end point of the hitting segment 
        /// true if hit, false otherwise 
        internal static bool HitTestQuadSegment(Quad quad, Point hitBegin, Point hitEnd)
        { 
            System.Diagnostics.Debug.Assert(quad.IsEmpty == false);

            HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
            int count = 4; 
            Vector zeroVector = new Vector(0, 0);
            Vector hitVector = hitEnd - hitBegin; 
            Vector vertex = quad[count - 1] - hitBegin; 

            for (int i = 0; i < count; i++) 
            {
                Vector nextVertex = quad[i] - hitBegin;
                hitResult = WhereIsSegmentAboutSegment(zeroVector, hitVector, vertex, nextVertex);
                if (HitResult.Hit == hitResult) 
                {
                    return true; 
                } 
                if (true == IsOutside(hitResult, prevResult))
                { 
                    return false;
                }
                if (i == 0)
                { 
                    firstResult = hitResult;
                } 
                prevResult = hitResult; 
                vertex = nextVertex;
            } 
            return (false == IsOutside(firstResult, hitResult));
        }

        ///  
        /// Hit-test a polygin against a circle
        ///  
        /// Vectors representing the vertices of the polygon, ordered in clockwise order 
        /// Vector representing the center of the circle
        /// Vector representing the radius of the circle 
        /// true if hit, false otherwise
        internal static bool HitTestPolygonCircle(Vector[] vertices, Vector center, Vector radius)
        {
            // NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext 
            throw new NotImplementedException();
            /* 
            System.Diagnostics.Debug.Assert((null != vertices) && (2 < vertices.Length)); 

            HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right; 
            int count = vertices.Length;
            Vector vertex = vertices[count - 1];

            for (int i = 0; i < count; i++) 
            {
                Vector nextVertex = vertices[i]; 
                hitResult = WhereIsCircleAboutSegment(center, radius, vertex, nextVertex); 
                if (HitResult.Hit == hitResult)
                { 
                    return true;
                }
                if (true == IsOutside(hitResult, prevResult))
                { 
                    return false;
                } 
                if (i == 0) 
                {
                    firstResult = hitResult; 
                }
                prevResult = hitResult;
                vertex = nextVertex;
            } 
            return (false == IsOutside(firstResult, hitResult));
            */ 
        } 

        ///  
        /// This is a specialized version of HitTestPolygonCircle that takes
        /// a Quad for a polygon. This method is called very intensively by
        /// hit-testing API and we don't want to create Vector[] for every quad it hit-tests.
        ///  
        /// the connecting quad
        /// center of the circle 
        /// radius of the circle  
        /// true if hit; false otherwise
        internal static bool HitTestQuadCircle(Quad quad, Point center, Vector radius) 
        {
            // NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
            throw new NotImplementedException();
            /* 
            System.Diagnostics.Debug.Assert(quad.IsEmpty == false);
 
            Vector centerVector = (Vector)center; 
            HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
            int count = 4; 
            Vector vertex = (Vector)quad[count - 1];

            for (int i = 0; i < count; i++)
            { 
                Vector nextVertex = (Vector)quad[i];
                hitResult = WhereIsCircleAboutSegment(centerVector, radius, vertex, nextVertex); 
                if (HitResult.Hit == hitResult) 
                {
                    return true; 
                }
                if (true == IsOutside(hitResult, prevResult))
                {
                    return false; 
                }
                if (i == 0) 
                { 
                    firstResult = hitResult;
                } 
                prevResult = hitResult;
                vertex = nextVertex;
            }
            return (false == IsOutside(firstResult, hitResult)); 
            */
        } 
 
        #endregion
 
        #region Whereabouts

        /// 
        /// Finds out where the segment [hitBegin, hitEnd] 
        /// is about the segment [orgBegin, orgEnd].
        ///  
        internal static HitResult WhereIsSegmentAboutSegment( 
            Vector hitBegin, Vector hitEnd, Vector orgBegin, Vector orgEnd)
        { 
            if (hitEnd == hitBegin)
            {
                return WhereIsCircleAboutSegment(hitBegin, new Vector(0, 0), 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,"
            //---------------------------------------------------------------------
            // The result tells where the segment CD is about the vector AB.
            // Return "Right" if either C or D is not on the left from AB. 
            HitResult result = HitResult.Right;
 
            // 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. 
                /*if (DoubleUtil.IsZero(Vector.Determinant(CD, CA))) 
                {
                    // The segments are collinear. 
                    // Check if their X and Y projections overlap.
                    if ((Math.Max(orgBegin.X, orgEnd.X) >= Math.Min(hitBegin.X, hitEnd.X)) &&
                        (Math.Min(orgBegin.X, orgEnd.X) <= Math.Max(hitBegin.X, hitEnd.X)) &&
                        (Math.Max(orgBegin.Y, orgEnd.Y) >= Math.Min(hitBegin.Y, hitEnd.Y)) && 
                        (Math.Min(orgBegin.Y, orgEnd.Y) <= Math.Max(hitBegin.Y, hitEnd.Y)))
                    { 
                        // The segments overlap. 
                        result = HitResult.Hit;
                    } 
                    else if (false == DoubleUtil.IsZero(AB.X))
                    {
                        result = ((AB.X * CA.X) > 0) ? HitResult.Behind : HitResult.InFront;
                    } 
                    else
                    { 
                        result = ((AB.Y * CA.Y) > 0) ? HitResult.Behind : HitResult.InFront; 
                    }
                } 
                else */
                if (DoubleUtil.IsZero(Vector.Determinant(CD, CA)) || DoubleUtil.GreaterThan(Vector.Determinant(AB, CA), 0))
                {
                    // C is on the left from AB, and, since the segments are parallel, D is also on the left. 
                    result = HitResult.Left;
                } 
            } 
            else
            { 
                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. 
                        result = HitResult.Hit;
                    }
                    else
                    { 
                        result = (0 < s) ? HitResult.InFront : HitResult.Behind;
                    } 
                } 
                else if ((WhereIsVectorAboutVector(hitBegin - orgBegin, AB) == HitResult.Left)
                    || (WhereIsVectorAboutVector(hitEnd - orgBegin, AB) == HitResult.Left)) 
                {
                    // The line defined AB doesn't cross the segment CD, and neither C nor D
                    // is on the right from AB
                    result = HitResult.Left; 
                }
            } 
 
            return result;
        } 

        /// 
        /// Find out the relative location of a circle relative to a line segment
        ///  
        /// center of the circle
        /// radius of the circle. center.radius is a point on the circle 
        /// begin point of the line segment 
        /// end point of the line segment
        /// test result 
        internal static HitResult WhereIsCircleAboutSegment(
            Vector center, Vector radius, Vector segBegin, Vector segEnd)
        {
            segBegin -= center; 
            segEnd -= center;
            double radiusSquared = radius.LengthSquared; 
 
            // This will find out the nearest path from center to a point on the segment
            double distanceSquared = GetNearest(segBegin, segEnd).LengthSquared; 

            // The segment must cross the circle, hit
            if (radiusSquared > distanceSquared)
            { 
                return HitResult.Hit;
            } 
 
            Vector segVector = segEnd - segBegin;
            HitResult result = HitResult.Right; 

            // NTRAID#Tablet PC bugs-26556-2004/10/19-xiaotu,resolved two issues with the original code:
            // 1. The local varial "normal" is assigned a value but it is never used afterwards. \
            // 2.  the code indicates that that only case result is HitResult.InFront or HitResult.Behind is 
            //  when WhereIsVectorAboutVector(-segBegin, segVector) == HitResult.Left.
 
            HitResult vResult = WhereIsVectorAboutVector(-segBegin, segVector); 

            //either front or behind 
            if (vResult == HitResult.Hit)
            {
                result = DoubleUtil.LessThan(segBegin.LengthSquared, segEnd.LengthSquared) ? HitResult.InFront :
                    HitResult.Behind; 
            }
            else 
            { 
                // Find the projection of center on the segment.
                double findex = GetProjectionFIndex(segBegin, segEnd); 

                // Get the normal vector, pointing from center to the projection point
                Vector normal = segBegin + (segVector * findex);
 
                // recalculate distanceSquared using normal
                distanceSquared = normal.LengthSquared; 
 
                // The extension of the segment won't hit the circle
                if (radiusSquared <= distanceSquared) 
                {
                    // either left or right
                    result = vResult;
                } 
                else
                { 
                    result = (findex > 0) ? HitResult.InFront : HitResult.Behind; 
                }
            } 

            return result;
        }
 
        /// 
        /// Finds out where the vector1 is about the vector2. 
        ///  
        internal static HitResult WhereIsVectorAboutVector(Vector vector1, Vector vector2)
        { 
            double determinant = Vector.Determinant(vector1, vector2);
            if (DoubleUtil.IsZero(determinant))
            {
                return HitResult.Hit;   // collinear 
            }
            return (0 < determinant) ? HitResult.Left : HitResult.Right; 
        } 

        ///  
        /// Tells whether the hitVector intersects the arc defined by two vectors.
        /// 
        internal static HitResult WhereIsVectorAboutArc(Vector hitVector, Vector arcBegin, Vector arcEnd)
        { 
            //HitResult result = HitResult.Right;
            if (arcBegin == arcEnd) 
            { 
                // full circle
                return HitResult.Hit; 
            }

            if (HitResult.Right == WhereIsVectorAboutVector(arcEnd, arcBegin))
            { 
                // small arc
                if ((HitResult.Left != WhereIsVectorAboutVector(hitVector, arcBegin)) && 
                    (HitResult.Right != WhereIsVectorAboutVector(hitVector, arcEnd))) 
                {
                    return HitResult.Hit; 
                }
            }
            else if ((HitResult.Left != WhereIsVectorAboutVector(hitVector, arcBegin)) ||
                    (HitResult.Right != WhereIsVectorAboutVector(hitVector, arcEnd))) 
            {
                return HitResult.Hit; 
            } 

            if ((WhereIsVectorAboutVector(hitVector - arcBegin, TurnLeft(arcBegin)) != HitResult.Left) || 
                (WhereIsVectorAboutVector(hitVector - arcEnd, TurnRight(arcEnd)) != HitResult.Right))
            {
                return HitResult.Left;
            } 

            return HitResult.Right; 
        } 

        #endregion 

        #region Misc. helpers

        ///  
        ///
        ///  
        ///  
        /// 
        internal static Vector TurnLeft(Vector vector) 
        {
            // NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
            throw new NotImplementedException();
            //return new Vector(-vector.Y, vector.X); 
        }
 
        ///  
        ///
        ///  
        /// 
        /// 
        internal static Vector TurnRight(Vector vector)
        { 
            // NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
            throw new NotImplementedException(); 
            //return new Vector(vector.Y, -vector.X); 
        }
 
        /// 
        ///
        /// 
        ///  
        /// 
        ///  
        internal static bool IsOutside(HitResult hitResult, HitResult prevHitResult) 
        {
            // ISSUE-2004/10/08-XiaoTu For Polygon and Circle, ((HitResult.Behind == hitResult) && (HitResult.InFront == prevHitResult)) 
            // cannot be true.
            return ((HitResult.Left == hitResult)
                || ((HitResult.Behind == hitResult) && (HitResult.InFront == prevHitResult)));
        } 

        ///  
        /// Internal helper function to find out the ratio of the distance from hitpoint to lineVector 
        /// and the distance from lineVector to (lineVector+nextLine)
        ///  
        /// This is one edge of a polygonal node
        /// The connection vector between the same edge on biginNode and ednNode
        /// a point
        /// the relative position of hitPoint 
        internal static double GetPositionBetweenLines(Vector linesVector, Vector nextLine, Vector hitPoint)
        { 
            Vector nearestOnFirst = GetProjection(-hitPoint, linesVector - hitPoint); 

            hitPoint = nextLine - hitPoint; 
            Vector nearestOnSecond = GetProjection(hitPoint, hitPoint + linesVector);

            Vector shortest = nearestOnFirst - nearestOnSecond;
            System.Diagnostics.Debug.Assert((false == DoubleUtil.IsZero(shortest.X)) || (false == DoubleUtil.IsZero(shortest.Y))); 

            //return DoubleUtil.IsZero(shortest.X) ? (nearestOnFirst.Y / shortest.Y) : (nearestOnFirst.X / shortest.X); 
            return Math.Sqrt(nearestOnFirst.LengthSquared / shortest.LengthSquared); 
        }
 
        /// 
        /// On a line defined buy two points finds the findex of the point
        /// nearest to the origin (0,0). Same as FindNearestOnLine just
        /// different output. 
        /// 
        /// A point on the line. 
        /// Another point on the line. 
        /// 
        internal static double GetProjectionFIndex(Vector begin, Vector end) 
        {
            Vector segment = end - begin;
            double lengthSquared = segment.LengthSquared;
 
            if (DoubleUtil.IsZero(lengthSquared))
            { 
                return 0; 
            }
 
            double dotProduct = -(begin * segment);
            return AdjustFIndex(dotProduct / lengthSquared);
        }
 
        /// 
        /// On a line defined buy two points finds the point nearest to the origin (0,0). 
        ///  
        /// A point on the line.
        /// Another point on the line. 
        /// 
        internal static Vector GetProjection(Vector begin, Vector end)
        {
            double findex = GetProjectionFIndex(begin, end); 
            return (begin + (end - begin) * findex);
        } 
 
        /// 
        /// On a given segment finds the point nearest to the origin (0,0). 
        /// 
        /// The segment's begin point.
        /// The segment's end point.
        ///  
        internal static Vector GetNearest(Vector begin, Vector end)
        { 
            double findex = GetProjectionFIndex(begin, end); 
            if (findex <= 0)
            { 
                return begin;
            }
            if (findex >= 1)
            { 
                return end;
            } 
            return (begin + ((end - begin) * findex)); 
        }
 
        /// 
        /// 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); 
        } 

        #endregion 
    }
}


// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//------------------------------------------------------------------------ 
// 
// Copyright (c) Microsoft Corporation. All rights reserved.
// 
//----------------------------------------------------------------------- 

using System; 
using System.Collections.Generic; 
using System.Windows;
using System.Windows.Media; 
using System.Windows.Input;

namespace MS.Internal.Ink
{ 
    /// 
    /// Static methods implementing generic hit-testing operations 
    ///  
    internal partial class StrokeNodeOperations
    { 
        #region enum HitResult

        ///  A set of possible results frequently used in StrokeNodeOperations and derived classes
        internal enum HitResult 
        {
            Hit, 
            Left, 
            Right,
            InFront, 
            Behind
        }

        #endregion 

        #region HitTestXxxYyy 
 
        /// 
        /// Hit-tests a linear segment against a convex polygon. 
        /// 
        /// Vertices of the polygon (in clockwise order)
        /// an end point of the hitting segment
        /// an end point of the hitting segment 
        /// true if hit; false otherwise
        internal static bool HitTestPolygonSegment(Vector[] vertices, Vector hitBegin, Vector hitEnd) 
        { 
            System.Diagnostics.Debug.Assert((null != vertices) && (2 < vertices.Length));
 
            HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
            int count = vertices.Length;
            Vector vertex = vertices[count - 1];
            for (int i = 0; i < count; i++) 
            {
                Vector nextVertex = vertices[i]; 
                hitResult = WhereIsSegmentAboutSegment(hitBegin, hitEnd, vertex, nextVertex); 
                if (HitResult.Hit == hitResult)
                { 
                    return true;
                }
                if (IsOutside(hitResult, prevResult))
                { 
                    return false;
                } 
                if (i == 0) 
                {
                    firstResult = hitResult; 
                }
                prevResult = hitResult;
                vertex = nextVertex;
            } 
            return (false == IsOutside(firstResult, hitResult));
        } 
 
        /// 
        /// This is a specialized version of HitTestPolygonSegment that takes 
        /// a Quad for a polygon. This method is called very intensively by
        /// hit-testing API and we don't want to create Vector[] for every quad it hit-tests.
        /// 
        /// the connecting quad to test against 
        /// begin point of the hitting segment
        /// end point of the hitting segment 
        /// true if hit, false otherwise 
        internal static bool HitTestQuadSegment(Quad quad, Point hitBegin, Point hitEnd)
        { 
            System.Diagnostics.Debug.Assert(quad.IsEmpty == false);

            HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
            int count = 4; 
            Vector zeroVector = new Vector(0, 0);
            Vector hitVector = hitEnd - hitBegin; 
            Vector vertex = quad[count - 1] - hitBegin; 

            for (int i = 0; i < count; i++) 
            {
                Vector nextVertex = quad[i] - hitBegin;
                hitResult = WhereIsSegmentAboutSegment(zeroVector, hitVector, vertex, nextVertex);
                if (HitResult.Hit == hitResult) 
                {
                    return true; 
                } 
                if (true == IsOutside(hitResult, prevResult))
                { 
                    return false;
                }
                if (i == 0)
                { 
                    firstResult = hitResult;
                } 
                prevResult = hitResult; 
                vertex = nextVertex;
            } 
            return (false == IsOutside(firstResult, hitResult));
        }

        ///  
        /// Hit-test a polygin against a circle
        ///  
        /// Vectors representing the vertices of the polygon, ordered in clockwise order 
        /// Vector representing the center of the circle
        /// Vector representing the radius of the circle 
        /// true if hit, false otherwise
        internal static bool HitTestPolygonCircle(Vector[] vertices, Vector center, Vector radius)
        {
            // NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext 
            throw new NotImplementedException();
            /* 
            System.Diagnostics.Debug.Assert((null != vertices) && (2 < vertices.Length)); 

            HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right; 
            int count = vertices.Length;
            Vector vertex = vertices[count - 1];

            for (int i = 0; i < count; i++) 
            {
                Vector nextVertex = vertices[i]; 
                hitResult = WhereIsCircleAboutSegment(center, radius, vertex, nextVertex); 
                if (HitResult.Hit == hitResult)
                { 
                    return true;
                }
                if (true == IsOutside(hitResult, prevResult))
                { 
                    return false;
                } 
                if (i == 0) 
                {
                    firstResult = hitResult; 
                }
                prevResult = hitResult;
                vertex = nextVertex;
            } 
            return (false == IsOutside(firstResult, hitResult));
            */ 
        } 

        ///  
        /// This is a specialized version of HitTestPolygonCircle that takes
        /// a Quad for a polygon. This method is called very intensively by
        /// hit-testing API and we don't want to create Vector[] for every quad it hit-tests.
        ///  
        /// the connecting quad
        /// center of the circle 
        /// radius of the circle  
        /// true if hit; false otherwise
        internal static bool HitTestQuadCircle(Quad quad, Point center, Vector radius) 
        {
            // NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
            throw new NotImplementedException();
            /* 
            System.Diagnostics.Debug.Assert(quad.IsEmpty == false);
 
            Vector centerVector = (Vector)center; 
            HitResult hitResult = HitResult.Right, firstResult = HitResult.Right, prevResult = HitResult.Right;
            int count = 4; 
            Vector vertex = (Vector)quad[count - 1];

            for (int i = 0; i < count; i++)
            { 
                Vector nextVertex = (Vector)quad[i];
                hitResult = WhereIsCircleAboutSegment(centerVector, radius, vertex, nextVertex); 
                if (HitResult.Hit == hitResult) 
                {
                    return true; 
                }
                if (true == IsOutside(hitResult, prevResult))
                {
                    return false; 
                }
                if (i == 0) 
                { 
                    firstResult = hitResult;
                } 
                prevResult = hitResult;
                vertex = nextVertex;
            }
            return (false == IsOutside(firstResult, hitResult)); 
            */
        } 
 
        #endregion
 
        #region Whereabouts

        /// 
        /// Finds out where the segment [hitBegin, hitEnd] 
        /// is about the segment [orgBegin, orgEnd].
        ///  
        internal static HitResult WhereIsSegmentAboutSegment( 
            Vector hitBegin, Vector hitEnd, Vector orgBegin, Vector orgEnd)
        { 
            if (hitEnd == hitBegin)
            {
                return WhereIsCircleAboutSegment(hitBegin, new Vector(0, 0), 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,"
            //---------------------------------------------------------------------
            // The result tells where the segment CD is about the vector AB.
            // Return "Right" if either C or D is not on the left from AB. 
            HitResult result = HitResult.Right;
 
            // 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. 
                /*if (DoubleUtil.IsZero(Vector.Determinant(CD, CA))) 
                {
                    // The segments are collinear. 
                    // Check if their X and Y projections overlap.
                    if ((Math.Max(orgBegin.X, orgEnd.X) >= Math.Min(hitBegin.X, hitEnd.X)) &&
                        (Math.Min(orgBegin.X, orgEnd.X) <= Math.Max(hitBegin.X, hitEnd.X)) &&
                        (Math.Max(orgBegin.Y, orgEnd.Y) >= Math.Min(hitBegin.Y, hitEnd.Y)) && 
                        (Math.Min(orgBegin.Y, orgEnd.Y) <= Math.Max(hitBegin.Y, hitEnd.Y)))
                    { 
                        // The segments overlap. 
                        result = HitResult.Hit;
                    } 
                    else if (false == DoubleUtil.IsZero(AB.X))
                    {
                        result = ((AB.X * CA.X) > 0) ? HitResult.Behind : HitResult.InFront;
                    } 
                    else
                    { 
                        result = ((AB.Y * CA.Y) > 0) ? HitResult.Behind : HitResult.InFront; 
                    }
                } 
                else */
                if (DoubleUtil.IsZero(Vector.Determinant(CD, CA)) || DoubleUtil.GreaterThan(Vector.Determinant(AB, CA), 0))
                {
                    // C is on the left from AB, and, since the segments are parallel, D is also on the left. 
                    result = HitResult.Left;
                } 
            } 
            else
            { 
                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. 
                        result = HitResult.Hit;
                    }
                    else
                    { 
                        result = (0 < s) ? HitResult.InFront : HitResult.Behind;
                    } 
                } 
                else if ((WhereIsVectorAboutVector(hitBegin - orgBegin, AB) == HitResult.Left)
                    || (WhereIsVectorAboutVector(hitEnd - orgBegin, AB) == HitResult.Left)) 
                {
                    // The line defined AB doesn't cross the segment CD, and neither C nor D
                    // is on the right from AB
                    result = HitResult.Left; 
                }
            } 
 
            return result;
        } 

        /// 
        /// Find out the relative location of a circle relative to a line segment
        ///  
        /// center of the circle
        /// radius of the circle. center.radius is a point on the circle 
        /// begin point of the line segment 
        /// end point of the line segment
        /// test result 
        internal static HitResult WhereIsCircleAboutSegment(
            Vector center, Vector radius, Vector segBegin, Vector segEnd)
        {
            segBegin -= center; 
            segEnd -= center;
            double radiusSquared = radius.LengthSquared; 
 
            // This will find out the nearest path from center to a point on the segment
            double distanceSquared = GetNearest(segBegin, segEnd).LengthSquared; 

            // The segment must cross the circle, hit
            if (radiusSquared > distanceSquared)
            { 
                return HitResult.Hit;
            } 
 
            Vector segVector = segEnd - segBegin;
            HitResult result = HitResult.Right; 

            // NTRAID#Tablet PC bugs-26556-2004/10/19-xiaotu,resolved two issues with the original code:
            // 1. The local varial "normal" is assigned a value but it is never used afterwards. \
            // 2.  the code indicates that that only case result is HitResult.InFront or HitResult.Behind is 
            //  when WhereIsVectorAboutVector(-segBegin, segVector) == HitResult.Left.
 
            HitResult vResult = WhereIsVectorAboutVector(-segBegin, segVector); 

            //either front or behind 
            if (vResult == HitResult.Hit)
            {
                result = DoubleUtil.LessThan(segBegin.LengthSquared, segEnd.LengthSquared) ? HitResult.InFront :
                    HitResult.Behind; 
            }
            else 
            { 
                // Find the projection of center on the segment.
                double findex = GetProjectionFIndex(segBegin, segEnd); 

                // Get the normal vector, pointing from center to the projection point
                Vector normal = segBegin + (segVector * findex);
 
                // recalculate distanceSquared using normal
                distanceSquared = normal.LengthSquared; 
 
                // The extension of the segment won't hit the circle
                if (radiusSquared <= distanceSquared) 
                {
                    // either left or right
                    result = vResult;
                } 
                else
                { 
                    result = (findex > 0) ? HitResult.InFront : HitResult.Behind; 
                }
            } 

            return result;
        }
 
        /// 
        /// Finds out where the vector1 is about the vector2. 
        ///  
        internal static HitResult WhereIsVectorAboutVector(Vector vector1, Vector vector2)
        { 
            double determinant = Vector.Determinant(vector1, vector2);
            if (DoubleUtil.IsZero(determinant))
            {
                return HitResult.Hit;   // collinear 
            }
            return (0 < determinant) ? HitResult.Left : HitResult.Right; 
        } 

        ///  
        /// Tells whether the hitVector intersects the arc defined by two vectors.
        /// 
        internal static HitResult WhereIsVectorAboutArc(Vector hitVector, Vector arcBegin, Vector arcEnd)
        { 
            //HitResult result = HitResult.Right;
            if (arcBegin == arcEnd) 
            { 
                // full circle
                return HitResult.Hit; 
            }

            if (HitResult.Right == WhereIsVectorAboutVector(arcEnd, arcBegin))
            { 
                // small arc
                if ((HitResult.Left != WhereIsVectorAboutVector(hitVector, arcBegin)) && 
                    (HitResult.Right != WhereIsVectorAboutVector(hitVector, arcEnd))) 
                {
                    return HitResult.Hit; 
                }
            }
            else if ((HitResult.Left != WhereIsVectorAboutVector(hitVector, arcBegin)) ||
                    (HitResult.Right != WhereIsVectorAboutVector(hitVector, arcEnd))) 
            {
                return HitResult.Hit; 
            } 

            if ((WhereIsVectorAboutVector(hitVector - arcBegin, TurnLeft(arcBegin)) != HitResult.Left) || 
                (WhereIsVectorAboutVector(hitVector - arcEnd, TurnRight(arcEnd)) != HitResult.Right))
            {
                return HitResult.Left;
            } 

            return HitResult.Right; 
        } 

        #endregion 

        #region Misc. helpers

        ///  
        ///
        ///  
        ///  
        /// 
        internal static Vector TurnLeft(Vector vector) 
        {
            // NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
            throw new NotImplementedException();
            //return new Vector(-vector.Y, vector.X); 
        }
 
        ///  
        ///
        ///  
        /// 
        /// 
        internal static Vector TurnRight(Vector vector)
        { 
            // NTRAID#WINDOWS-1448096-2006/1/9-SAMGEO, this code is not called, but will be in VNext
            throw new NotImplementedException(); 
            //return new Vector(vector.Y, -vector.X); 
        }
 
        /// 
        ///
        /// 
        ///  
        /// 
        ///  
        internal static bool IsOutside(HitResult hitResult, HitResult prevHitResult) 
        {
            // ISSUE-2004/10/08-XiaoTu For Polygon and Circle, ((HitResult.Behind == hitResult) && (HitResult.InFront == prevHitResult)) 
            // cannot be true.
            return ((HitResult.Left == hitResult)
                || ((HitResult.Behind == hitResult) && (HitResult.InFront == prevHitResult)));
        } 

        ///  
        /// Internal helper function to find out the ratio of the distance from hitpoint to lineVector 
        /// and the distance from lineVector to (lineVector+nextLine)
        ///  
        /// This is one edge of a polygonal node
        /// The connection vector between the same edge on biginNode and ednNode
        /// a point
        /// the relative position of hitPoint 
        internal static double GetPositionBetweenLines(Vector linesVector, Vector nextLine, Vector hitPoint)
        { 
            Vector nearestOnFirst = GetProjection(-hitPoint, linesVector - hitPoint); 

            hitPoint = nextLine - hitPoint; 
            Vector nearestOnSecond = GetProjection(hitPoint, hitPoint + linesVector);

            Vector shortest = nearestOnFirst - nearestOnSecond;
            System.Diagnostics.Debug.Assert((false == DoubleUtil.IsZero(shortest.X)) || (false == DoubleUtil.IsZero(shortest.Y))); 

            //return DoubleUtil.IsZero(shortest.X) ? (nearestOnFirst.Y / shortest.Y) : (nearestOnFirst.X / shortest.X); 
            return Math.Sqrt(nearestOnFirst.LengthSquared / shortest.LengthSquared); 
        }
 
        /// 
        /// On a line defined buy two points finds the findex of the point
        /// nearest to the origin (0,0). Same as FindNearestOnLine just
        /// different output. 
        /// 
        /// A point on the line. 
        /// Another point on the line. 
        /// 
        internal static double GetProjectionFIndex(Vector begin, Vector end) 
        {
            Vector segment = end - begin;
            double lengthSquared = segment.LengthSquared;
 
            if (DoubleUtil.IsZero(lengthSquared))
            { 
                return 0; 
            }
 
            double dotProduct = -(begin * segment);
            return AdjustFIndex(dotProduct / lengthSquared);
        }
 
        /// 
        /// On a line defined buy two points finds the point nearest to the origin (0,0). 
        ///  
        /// A point on the line.
        /// Another point on the line. 
        /// 
        internal static Vector GetProjection(Vector begin, Vector end)
        {
            double findex = GetProjectionFIndex(begin, end); 
            return (begin + (end - begin) * findex);
        } 
 
        /// 
        /// On a given segment finds the point nearest to the origin (0,0). 
        /// 
        /// The segment's begin point.
        /// The segment's end point.
        ///  
        internal static Vector GetNearest(Vector begin, Vector end)
        { 
            double findex = GetProjectionFIndex(begin, end); 
            if (findex <= 0)
            { 
                return begin;
            }
            if (findex >= 1)
            { 
                return end;
            } 
            return (begin + ((end - begin) * findex)); 
        }
 
        /// 
        /// 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); 
        } 

        #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