ConnectorRouter.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / cdf / src / NetFx40 / Tools / System.Activities.Core.Presentation / System / Activities / Core / Presentation / ConnectorRouter.cs / 1305376 / ConnectorRouter.cs

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

namespace System.Activities.Core.Presentation 
{
    using System.Collections.Generic; 
    using System.Windows; 
    using System.Windows.Controls;
    using System.Windows.Shapes; 
    using System.Globalization;
    using System.Diagnostics.CodeAnalysis;

    internal static class ConnectorRouter 
    {
        const int connectorMargin = 30; 
 
        [Flags]
        enum DesignerEdges 
        {
            None = 0,
            Left = 1,
            Top = 2, 
            Right = 4,
            Bottom = 8, 
            All = 15 
        }
 
        //This is used for link creation gesture to show the adorner.(In this case we know only the source connection point).
        internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint, Point end)
        {
            return Route(panel, srcConnPoint.Location, end, srcConnPoint.Edge, null); 
        }
 
        //This is used when we know both the source and destination connection points. 
        internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint , ConnectionPoint destConnPoint)
        { 
            return Route(panel, srcConnPoint.Location, destConnPoint.Location, srcConnPoint.Edge, destConnPoint.Edge);
        }

        //This is used when we move the end connection point. 
        internal static Point[] Route(FreeFormPanel panel, Point begin, Point end)
        { 
            return Route(panel, begin, end, null, null); 
        }
 
        internal static bool AreAllSegmentsVerticalOrHorizontal(Point[] segments)
        {
            if (segments == null || segments.Length == 0)
            { 
                return false;
            } 
 
            for (int i = 1; i < segments.Length; i++)
            { 
                if (segments[i - 1].X != segments[i].X && segments[i - 1].Y != segments[i].Y)
                {
                    return false;
                } 
            }
 
            return true; 
        }
 
        static ConnectorSegment SrcEdge;
        static ConnectorSegment DestEdge;

        //This method is the wrapper over the routing logic taken from Workflow V1. 
        static Point[] Route(FreeFormPanel panel, Point begin, Point end, List srcEdge, List destEdge)
        { 
            Point[] segments; 
            if (panel == null)
            { 
                throw FxTrace.Exception.AsError(new ArgumentNullException("panel"));
            }
            List < Rect > excludedRects = new List < Rect >();
            List < Point > excludedLines = new List < Point >(); 
            foreach (UIElement child in panel.Children)
            { 
                if (child.GetType() == typeof(Connector)) 
                {
                    for (int i = 0; i < (((Connector)child).Points.Count) - 1; i++) 
                    {
                        excludedLines.Add(new Point(((Connector)child).Points[i].X, ((Connector)child).Points[i].Y));
                        excludedLines.Add(new Point(((Connector)child).Points[i + 1].X, ((Connector)child).Points[i + 1].Y));
                    } 
                }
                else 
                { 
                    //Since the connectors will touch the UIElement, they will pass through the margin around the UIElement.
                    //Hence excluding the margin in excludedRects. 
                    Thickness margin = new Thickness(0);
                    Point origin = FreeFormPanel.GetLocation(child);
                    FrameworkElement frameworkChild = child as FrameworkElement;
                    if (frameworkChild != null) 
                    {
                        margin = frameworkChild.Margin; 
                    } 
                    Size childSize = new Size(frameworkChild.DesiredSize.Width - margin.Left - margin.Right, frameworkChild.DesiredSize.Height - margin.Top - margin.Bottom);
                    excludedRects.Add(new Rect(Point.Add(FreeFormPanel.GetLocation(child), new Vector(margin.Left, margin.Top)), childSize)); 
                }
            }

            ConnectorRouter.SrcEdge = null; 
            ConnectorRouter.DestEdge = null;
            if (srcEdge != null) 
            { 
                //ConnectorSegment should only be a segment from left to right or top to bottom.
                int smallerIndex = (srcEdge[0].X < srcEdge[1].X || srcEdge[0].Y < srcEdge[1].Y) ? 0 : 1; 
                ConnectorRouter.SrcEdge = new ConnectorSegment(srcEdge[smallerIndex], srcEdge[1 - smallerIndex]);
            }
            if (destEdge != null)
            { 
                int smallerIndex = (destEdge[0].X < destEdge[1].X || destEdge[0].Y < destEdge[1].Y) ? 0 : 1;
                ConnectorRouter.DestEdge = new ConnectorSegment(destEdge[smallerIndex], destEdge[1 - smallerIndex]); 
            } 

            segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), excludedLines.ToArray()); 

            //WE NEED TO INCLUDE THESE FALLBACKS DUE TO A

 
            if (!AreAllSegmentsVerticalOrHorizontal(segments))
            { 
                segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), new Point[] { }); 
                //segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), new Rect[] { }, excludedLines.ToArray());
            } 

            //DIRECT PATH
            if (!AreAllSegmentsVerticalOrHorizontal(segments))
            { 
                double slope = DesignerGeometryHelper.SlopeOfLineSegment(begin, end);
                Point intermediatePoint = (slope < 1) ? new Point(end.X, begin.Y) : new Point(begin.X, end.Y); 
                segments = new Point[] { begin, intermediatePoint, end }; 
            }
            segments = RemoveRedundantPoints(new List(segments)); 
            return segments;
        }

        //In a list of points specifying a connector, remove consecutive equal points. 
        static Point[] RemoveRedundantPoints(List points)
        { 
            for (int i = points.Count - 1; i > 0; i--) 
            {
                if (points[i].Equals(points[i - 1])) 
                {
                    points.RemoveAt(i);
                }
            } 
            return points.ToArray();
        } 
 

        static void AddBoundPoint(ref List < DistanceFromPoint > extremitiesList, Point p, ConnectorSegment segment, Point Z) 
        {
            if (p.X != int.MinValue && p.X != int.MaxValue && p.Y != int.MinValue && p.Y != int.MaxValue)
            {
                extremitiesList.Add(new DistanceFromPoint(segment, Z, p)); 
            }
        } 
 
        //Escape Algorithm
        static Nullable < Point > EscapeAlgorithm(CoverSet coverSet, Point Z, 
            ref List < Point > LeA, ref List < ConnectorSegment > LhA, ref List < ConnectorSegment > LvA, ref List < ConnectorSegment > LhB, ref List < ConnectorSegment > LvB,
            ref Orientation orientationA, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB, Size margin, ref bool noEscapeA)
        {
            Nullable < Point > intersection = null; 
            intersectionSegmentA = null;
            intersectionSegmentB = null; 
 
            ConnectorSegment leftCover = coverSet.GetCover(Z, DesignerEdges.Left);
            ConnectorSegment rightCover = coverSet.GetCover(Z, DesignerEdges.Right); 
            ConnectorSegment bottomCover = coverSet.GetCover(Z, DesignerEdges.Bottom);
            ConnectorSegment topCover = coverSet.GetCover(Z, DesignerEdges.Top);

            //P1: construct escape line(s) - on the beginning of the algorithm it will create two lines 
            ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, Z);
            //We do not want the routed line to coincide with the source or dest edge. 
            //Hence the edge should never be an escape line. 
            if (h.Equals(ConnectorRouter.SrcEdge) || h.Equals(ConnectorRouter.DestEdge))
            { 
                h = null;
            }
            else
            { 
                LhA.Add(h);
            } 
 
            ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, Z);
            if (v.Equals(ConnectorRouter.SrcEdge) || v.Equals(ConnectorRouter.DestEdge)) 
            {
                v = null;
            }
            else 
            {
                LvA.Add(v); 
            } 

 
            //P2 check if the new escape line(s) intersect with the existing ones
            if (h != null)
            {
                for (int i = 0; i < LvB.Count; i++) 
                {
                    ConnectorSegment segment = LvB[i]; 
                    intersection = h.Intersect(segment); 
                    if (intersection != null)
                    { 
                        intersectionSegmentA = h;
                        intersectionSegmentB = segment;
                        return intersection;
                    } 
                }
            } 
 
            if (v != null)
            { 
                for (int i = 0; i < LhB.Count; i++)
                {
                    ConnectorSegment segment = LhB[i];
                    intersection = v.Intersect(segment); 
                    if (intersection != null)
                    { 
                        intersectionSegmentA = v; 
                        intersectionSegmentB = segment;
                        return intersection; 
                    }
                }
            }
 
            //there was no intersection found above, continue on
 
            //P3 find an escape point 

            //Call Escape Process I 
            //Escape process I P1
            Nullable escapePoint = null;
            if (v != null)
            { 
                escapePoint = EscapeProcessI(coverSet, Z, v, Orientation.Horizontal, margin);
                if (escapePoint != null) 
                { 
                    orientationA = Orientation.Vertical;
                    LeA.Add((Point)escapePoint); 
                    return null;
                }
            }
 
            //Escape process I P2
            if (h != null) 
            { 
                escapePoint = EscapeProcessI(coverSet, Z, h, Orientation.Vertical, margin);
                if (escapePoint != null) 
                {
                    orientationA = Orientation.Horizontal;
                    LeA.Add((Point)escapePoint);
                    return null; 
                }
            } 
 
            //Call Escape process II
            bool intersectionFlag = false; 
            //flags indicating if we can still continue in the given directions
            bool continue1, continue2, continue3, continue4;
            //CHANGE THIS.
            Point r1 = new Point(), r2 = new Point(), r3 = new Point(), r4 = new Point(); 

            if (topCover != null) 
            { 
                r1 = new Point(Z.X, topCover.A.Y);
            } 
            if (rightCover != null)
            {
                r2 = new Point(rightCover.A.X, Z.Y);
            } 
            if (bottomCover != null)
            { 
                r3 = new Point(Z.X, bottomCover.A.Y); 
            }
            if (leftCover != null) 
            {
                r4 = new Point(leftCover.A.X, Z.Y);
            }
            do 
            {
                continue1 = continue2 = continue3 = continue4 = false; 
                if (topCover != null && v != null) 
                {
                    r1.Y -= margin.Height; 
                    if (r1.Y > Z.Y)
                    {
                        continue1 = true;
                        Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Vertical, 
                            ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r1, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
                        if (escape != null) 
                        { 
                            LvA.Add(v);
                            if (intersectionFlag) 
                            {
                                return escape;
                            }
 
                            orientationA = Orientation.Horizontal;
                            coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r1)); 
                            coverSet.AddUsedEscapeLine(new ConnectorSegment(r1, (Point)escape)); 
                            LeA.Add((Point)escape);
                            return null; 
                        }
                    }
                }
 
                if (rightCover != null && h != null)
                { 
                    r2.X -= margin.Width; 
                    if (r2.X > Z.X)
                    { 
                        continue2 = true;
                        Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Horizontal,
                            ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r2, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
                        if (escape != null) 
                        {
                            LhA.Add(h); 
                            if (intersectionFlag) 
                            {
                                return escape; 
                            }

                            orientationA = Orientation.Vertical;
                            coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r2)); 
                            coverSet.AddUsedEscapeLine(new ConnectorSegment(r2, (Point)escape));
                            LeA.Add((Point)escape); 
                            return null; 
                        }
                    } 
                }

                if (bottomCover != null && v != null)
                { 
                    r3.Y += margin.Height;
                    if (r3.Y < Z.Y) 
                    { 
                        continue3 = true;
                        Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Vertical, 
                            ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r3, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
                        if (escape != null)
                        {
                            LvA.Add(v); 
                            if (intersectionFlag)
                            { 
                                return escape; 
                            }
 
                            orientationA = Orientation.Horizontal;
                            coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r3));
                            coverSet.AddUsedEscapeLine(new ConnectorSegment(r3, (Point)escape));
                            LeA.Add((Point)escape); 
                            return null;
                        } 
                    } 
                }
 
                if (leftCover != null && h!= null)
                {
                    r4.X += margin.Width;
                    if (r4.X < Z.X) 
                    {
                        continue4 = true; 
                        Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Horizontal, 
                            ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r4, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
                        if (escape != null) 
                        {
                            LhA.Add(h);
                            if (intersectionFlag)
                            { 
                                return escape;
                            } 
 
                            orientationA = Orientation.Vertical;
                            coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r4)); 
                            coverSet.AddUsedEscapeLine(new ConnectorSegment(r4, (Point)escape));
                            LeA.Add((Point)escape);
                            return null;
                        } 
                    }
                } 
                //continue the loop until there is a place to go in either of the directions 
            } while (continue1 || continue2 || continue3 || continue4);
 
            noEscapeA = true;
            return null;
        }
 
        //Escape Process I
        static Nullable < Point > EscapeProcessI(CoverSet coverSet, Point Z, 
            ConnectorSegment escapeLine, Orientation orientation, Size margin) 
        {
            //perform extremity point permutation by the distance from the object point 
            //when sorting points store to which segments they belong (this is needed further when
            //deciding to side of the point to move if the extremity coincide with the object point
            //on abscissa or ordinata axis)
            List < DistanceFromPoint > extremitiesList = new List < DistanceFromPoint >(4); //at most four points 

            ConnectorSegment lesserCover = coverSet.GetCover(Z, (orientation == Orientation.Horizontal) ? DesignerEdges.Left : DesignerEdges.Bottom); 
            if (lesserCover != null) 
            {
                AddBoundPoint(ref extremitiesList, lesserCover.A, lesserCover, Z); 
                AddBoundPoint(ref extremitiesList, lesserCover.B, lesserCover, Z);
            }

            ConnectorSegment higherCover = coverSet.GetCover(Z, (orientation == Orientation.Horizontal) ? DesignerEdges.Right : DesignerEdges.Top); 
            if (higherCover != null)
            { 
                AddBoundPoint(ref extremitiesList, higherCover.A, higherCover, Z); 
                AddBoundPoint(ref extremitiesList, higherCover.B, higherCover, Z);
            } 

            if (extremitiesList.Count == 0)
            {
                return null; 
            }
 
            DistanceSorter.Sort(ref extremitiesList); 
            for (int i = 0; i < extremitiesList.Count; i++)
            { 
                Point p = extremitiesList[i].P;
                Point direction = new Point(Math.Sign(p.X - Z.X), Math.Sign(p.Y - Z.Y));
                if (((orientation == Orientation.Vertical) ? direction.X : direction.Y) == 0)
                { 
                    //if extremity is on the same abscissa(ordinata) line with the object point, need to be more careful
                    ConnectorSegment segment = extremitiesList[i].ConnectorSegment; 
                    p = segment.ExtendPointOutwards(p); 
                    direction = new Point(Math.Sign(p.X - Z.X), Math.Sign(p.Y - Z.Y));
                    p = extremitiesList[i].P; 
                }

                DesignerEdges side; //which side is the cover we are trying to escape
                if (orientation == Orientation.Vertical) 
                {
                    //we are escaping either top or bottom 
                    side = (direction.Y < 0) ? DesignerEdges.Bottom : DesignerEdges.Top; 
                }
                else 
                {
                    //we are escaping either left or right
                    side = (direction.X < 0) ? DesignerEdges.Left : DesignerEdges.Right;
                } 

                Point escapePoint; 
                if ((orientation == Orientation.Vertical)) 
                {
                    escapePoint = new Point(p.X + direction.X * margin.Width, Z.Y); 
                }
                else
                {
                    escapePoint = new Point(Z.X, p.Y + direction.Y * margin.Height); 
                }
 
                //the new escape point should 
                //1) lay on the given escape line (except the bounding points since they belong to covers)
                //2) not lay on any of the already tested escape segments - all points belonging to them are already worthless 
                ConnectorSegment newEscapeLine = new ConnectorSegment(Z, escapePoint);
                if (!coverSet.EscapeLineHasBeenUsed(escapePoint) &&
                    escapeLine.IsPointOnSegment(escapePoint) && escapeLine.A != escapePoint && escapeLine.B != escapePoint &&
                    coverSet.IsEscapePoint(Z, escapePoint, side)) 
                {
                    coverSet.AddUsedEscapeLine(newEscapeLine); 
                    return escapePoint; 
                }
            } 

            return null;
        }
 

        //Escape Process II 
        static Nullable < Point > EscapeProcessII(CoverSet coverSet, Orientation orientation, ref List < Point > LeA, 
            ref List < ConnectorSegment > LhA, ref List < ConnectorSegment > LvA, ref List < ConnectorSegment > LhB, ref List < ConnectorSegment > LvB,
            Point R, Size margin, out bool intersectionFlag, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB) 
        {
            intersectionFlag = false;
            intersectionSegmentA = null;
            intersectionSegmentB = null; 

            //rebuild invalidated covers 
            ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, R); 
            ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, R);
 
            //check intersections
            for (int i = 0; i < LvB.Count; i++)
            {
                ConnectorSegment segment = LvB[i]; 
                Nullable < Point > itersection = h.Intersect(segment);
                if (itersection != null) 
                { 
                    intersectionFlag = true;
                    intersectionSegmentA = h; 
                    intersectionSegmentB = segment;
                    LeA.Add(R);
                    return itersection;
                } 
            }
            for (int i = 0; i < LhB.Count; i++) 
            { 
                ConnectorSegment segment = LhB[i];
                Nullable < Point > itersection = v.Intersect(segment); 
                if (itersection != null)
                {
                    intersectionFlag = true;
                    intersectionSegmentA = v; 
                    intersectionSegmentB = segment;
                    LeA.Add(R); 
                    return itersection; 
                }
            } 

            Nullable < Point > escapePointI = null;

            //now do both horizontal and vertical escape processes I from that point... 
            //the order is important based on 'orientation' argument
            if (orientation == Orientation.Horizontal) 
            { 
                escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin);
                if (escapePointI != null) 
                {
                    LvA.Add(v);
                    LeA.Add(R);
                    return escapePointI; 
                }
 
                escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin); 
                if (escapePointI != null)
                { 
                    LhA.Add(h);
                    LeA.Add(R);
                    return escapePointI;
                } 
            }
            else 
            { 
                escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin);
                if (escapePointI != null) 
                {
                    LhA.Add(h);
                    LeA.Add(R);
                    return escapePointI; 
                }
 
                escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin); 
                if (escapePointI != null)
                { 
                    LvA.Add(v);
                    LeA.Add(R);
                    return escapePointI;
                } 
            }
 
            return null; 
        }
 


        //remove all non-corner points
        static List < Point > FirstRefinementAlgorithm(List < Point > Le, ConnectorSegment intersectionSegment) 
        {
            List < Point > refinedSet = new List < Point >(); 
            ConnectorSegment k = intersectionSegment; 

            while (Le.Count > 0) 
            {
                Point pi;
                int i = Le.Count - 1;
 
                //find the first point that lies on k
                while (!k.PointLiesOnThisLine(Le[i]) && i > 0) 
                { 
                    i--;
                } 

                //find the least point that lies on k
                while (i > 0 && k.PointLiesOnThisLine(Le[i - 1]))
                { 
                    i--;
                } 
                //save the point 
                pi = Le[i];
                refinedSet.Add(pi); 

                //remove all the points up to the found one from the original list
                while (Le.Count > i)
                { 
                    Le.RemoveAt(i);
                } 
 
                //continue with the points lying on the line perpendecular to the previous one and passing through the
                //found point 
                k = k.PeprendecularThroughPoint(pi);
            }

            return refinedSet; 
        }
 
        [SuppressMessage("Microsoft.Design", "CA1031:DoNotCatchGeneralExceptionTypes", 
            Justification = "Catch all exceptions to prevent crash.")]
        [SuppressMessage("Reliability", "Reliability108:IsFatalRule", 
            Justification = "Catch all exceptions to prevent crash.")]
        static Point[] GetRoutedLineSegments(Point begin, Point end, Size margin, Rect[] rectanglesToExclude, Point[] linesToExclude)
        {
            if (rectanglesToExclude == null) 
            {
                throw FxTrace.Exception.AsError(new ArgumentNullException("rectanglesToExclude")); 
            } 

            if (linesToExclude == null) 
            {
                throw FxTrace.Exception.AsError(new ArgumentNullException("linesToExclude"));
            }
 
            if ((linesToExclude.Length % 2) > 0)
            { 
                throw FxTrace.Exception.AsError(new ArgumentException("Error")); 
            }
 

            CoverSet coverSet = new CoverSet(rectanglesToExclude, linesToExclude);
            coverSet.ClearUsedLines();
 
            Point A = begin;
            Point B = end; 
 
            //escape points
            List < Point > LeA = new List < Point >(); //escape points from begin to end 
            List < Point > LeB = new List < Point >(); //escape points from end to begin

            //horizontal/vertical escape segments from A
            List < ConnectorSegment > LhA = new List < ConnectorSegment >(); 
            List < ConnectorSegment > LvA = new List < ConnectorSegment >();
 
            //horizontal/vertical escape segments from B 
            List < ConnectorSegment > LhB = new List < ConnectorSegment >();
            List < ConnectorSegment > LvB = new List < ConnectorSegment >(); 

            Orientation orientationA = Orientation.Horizontal;
            Orientation orientationB = Orientation.Horizontal;
 
            //P0
            LeA.Add(begin); 
            LeB.Add(end); 

            bool noEscapeA = false; 
            bool noEscapeB = false;

            Nullable < Point > intersection = null;
            ConnectorSegment intersectionSegmentA = null; 
            ConnectorSegment intersectionSegmentB = null;
 
            try 
            {
                do 
                {
                    //P1
                    if (noEscapeA)
                    { 
                        if (noEscapeB)
                        { 
                            //we failed to find the point 
                            break;
                        } 
                        else
                        {
                            //P2
                            //swap A and B (with all appropriate lists and flags...) 
                            List < Point > tempList = LeA;
                            LeA = LeB; 
                            LeB = tempList; 

                            Point tempPoint = A; 
                            A = B;
                            B = tempPoint;

                            bool tempBool = noEscapeA; 
                            noEscapeA = noEscapeB;
                            noEscapeB = tempBool; 
 
                            Orientation tempOrientation = orientationA;
                            orientationA = orientationB; 
                            orientationB = tempOrientation;

                            List < ConnectorSegment > tempListSegm = LhA;
                            LhA = LhB; 
                            LhB = tempListSegm;
 
                            tempListSegm = LvA; 
                            LvA = LvB;
                            LvB = tempListSegm; 

                            continue;
                        }
                    } 

                    Point objectPoint = LeA[LeA.Count - 1]; 
                    Point targetPoint = B; 

                    intersection = EscapeAlgorithm(coverSet, objectPoint, 
                        ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, ref orientationA,
                        out intersectionSegmentA, out intersectionSegmentB, margin, ref noEscapeA);
                    if (intersection != null)
                    { 
                        break;
                    } 
                    else 
                    {
                        //swap A and B (with all appropriate lists and flags...) 
                        List < Point > tempList = LeA;
                        LeA = LeB;
                        LeB = tempList;
 
                        Point tempPoint = A;
                        A = B; 
                        B = tempPoint; 

                        bool tempBool = noEscapeA; 
                        noEscapeA = noEscapeB;
                        noEscapeB = tempBool;

                        Orientation tempOrientation = orientationA; 
                        orientationA = orientationB;
                        orientationB = tempOrientation; 
 
                        List < ConnectorSegment > tempListSegm = LhA;
                        LhA = LhB; 
                        LhB = tempListSegm;

                        tempListSegm = LvA;
                        LvA = LvB; 
                        LvB = tempListSegm;
                    } 
 
                } while (true);
 
                //we failed
                if (intersection == null)
                {
                    return null; 
                }
 
                List < Point > refinedPath = new List < Point >(); 

                //P3 apply refinement algorithms 
                //first refinement algorithm
                LeA = FirstRefinementAlgorithm(LeA, intersectionSegmentA);
                LeB = FirstRefinementAlgorithm(LeB, intersectionSegmentB);
 
                //before going into the second refinement, construct the full path
                for (int j = LeA.Count - 1; j >= 0; j--) 
                { 
                    refinedPath.Add(LeA[j]);
                } 
                refinedPath.Add((Point)intersection);
                for (int j = 0; j < LeB.Count; j++)
                {
                    refinedPath.Add(LeB[j]); 
                }
 
                //perform second refinement algorithm on the full path 
                SecondRefinementAlgorithm(coverSet, ref refinedPath, margin);
 
                if (refinedPath.Count > 1 && refinedPath[refinedPath.Count - 1] == begin)
                {
                    refinedPath.Reverse();
                } 

                return refinedPath.ToArray(); 
            } 
            catch (Exception)
            { 
                //Debug.Assert(false, "Investigate if we ever get here. got an exception:\n" + ex.Message);
                return null;
            }
        } 

        //remove superflous parts from the path 
        static void SecondRefinementAlgorithm(CoverSet coverSet, ref List < Point > refinedPath, Size margin) 
        {
            List < Point > newPath = new List < Point >(); 

            //Part I: extend every segment in the path to see if it intersects any other segment
            int currentSegment = 0;
            while (currentSegment < refinedPath.Count - 1) 
            {
                Point a1 = refinedPath[currentSegment]; 
                Point a2 = refinedPath[currentSegment + 1]; 

                //need to construct a segment through the points that is limited by the covers 
                ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2);

                //try to intersect it with every segment after the current one
                //and the next one (which we know does intersect with the current one) 
                int intersectingSegment = currentSegment + 2;
                while (intersectingSegment < refinedPath.Count - 1) 
                { 
                    Point b1 = refinedPath[intersectingSegment];
                    Point b2 = refinedPath[intersectingSegment + 1]; 
                    ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, b1, b2);

                    Nullable < Point > intersection = a.Intersect(b);
                    if (intersection != null) 
                    {
                        newPath.Clear(); 
                        //need to remove all points between a1 and b2 and insert the point of intersectin there 
                        for (int i = 0; i <= currentSegment; i++)
                        { 
                            newPath.Add(refinedPath[i]);
                        }
                        newPath.Add((Point)intersection);
                        for (int i = intersectingSegment + 1; i < refinedPath.Count; i++) 
                        {
                            newPath.Add(refinedPath[i]); 
                        } 

                        List < Point > temp = refinedPath; 
                        refinedPath = newPath;
                        newPath = temp;
                        newPath.Clear();
 
                        //reset the second segment number and go through all segments once more
                        //until there are no intersections left 
                        intersectingSegment = currentSegment + 2; 
                    }
                    else 
                    {
                        intersectingSegment++;
                    }
                } 

                //we need to keep looking for intersections until we reach the very last one 
                currentSegment++; 
            }
 
            //Part II: construct segments perpendecular to every segment and see if they intersect any other segment
            currentSegment = 0;
            while (currentSegment < refinedPath.Count - 1)
            { 
                Point a1 = refinedPath[currentSegment];
                Point a2 = refinedPath[currentSegment + 1]; 
 
                //need to construct a segment through the points that is limited by the covers
                bool intersected = false; 
                ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2);
                if (a != null)
                {
                    Point direction = new Point(a2.X - a1.X, a2.Y - a1.Y); 

                    //see how many intemediate points we can construct 
                    int steps = (int)Math.Max(Math.Abs(direction.X / margin.Width), Math.Abs(direction.Y / margin.Height)); //one of the values will be null 
                    direction.X = (int)Math.Sign(direction.X);
                    direction.Y = (int)Math.Sign(direction.Y); 

                    for (int i = 1; i <= steps; i++)
                    {
                        Point k = new Point(a1.X + i * margin.Width * direction.X, a1.Y + i * margin.Height * direction.Y); 
                        if (k == a2)
                        { 
                            break; 
                        }
 
                        ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, k, (a.Orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal);
                        //now try to intersect that segment with every segment after the current one and the one after it
                        int intersectingSegment = currentSegment + 2;
                        while (intersectingSegment < refinedPath.Count - 1 && !intersected) 
                        {
                            Point c1 = refinedPath[intersectingSegment]; 
                            Point c2 = refinedPath[intersectingSegment + 1]; 
                            ConnectorSegment c = new ConnectorSegment(c1, c2);
 
                            Nullable < Point > intersection = b.Intersect(c);
                            if (intersection != null && c.IsPointOnSegment((Point)intersection))
                            {
                                intersected = true; 

                                newPath.Clear(); 
                                //need to remove all points between a1 and b2 and insert k and the point of intersection there 
                                for (int j = 0; j <= currentSegment; j++)
                                { 
                                    newPath.Add(refinedPath[j]);
                                }
                                newPath.Add(k);
                                newPath.Add((Point)intersection); 
                                for (int j = intersectingSegment + 1; j < refinedPath.Count; j++)
                                { 
                                    newPath.Add(refinedPath[j]); 
                                }
                                List < Point > temp = refinedPath; 
                                refinedPath = newPath;
                                newPath = temp;
                                newPath.Clear();
                                break; 
                            }
 
                            intersectingSegment++; 
                        }
 
                        //if there was an intersection, exit the for loop
                        if (intersected)
                        {
                            break; 
                        }
                    } 
                } 

                //if there was an intersection, run the same segment again to see if there are other intersecting segments 
                if (!intersected)
                {
                    currentSegment++;
                } 
            }
        } 
 
        //Struct DistanceFromPoint
        //sorting of extremities by closedness to point Z 
        struct DistanceFromPoint
        {
            public ConnectorSegment ConnectorSegment;
            public double Distance; 
            public Point P;
 
            public DistanceFromPoint(ConnectorSegment segment, Point z, Point p) 
            {
                this.ConnectorSegment = segment; 
                this.P = p;
                this.Distance = ConnectorSegment.DistanceBetweenPoints(z, p);
            }
        } 

 
 
        // represents a segment - the main entity in the routing algorithm
        sealed class ConnectorSegment 
        {
            Orientation orientation;
            Point point1;
            Point point2; 

            public ConnectorSegment(Point point1, Point point2) 
            { 
                if (point1.X != point2.X && point1.Y != point2.Y)
                { 
                    throw FxTrace.Exception.AsError(new InvalidOperationException(string.Format(CultureInfo.InvariantCulture,
                        SR.CannotConstructConnectionSegment, point1.ToString(), point2.ToString())));
                }
 
                this.point1 = point1;
                this.point2 = point2; 
                this.orientation = ((this.point1.X == this.point2.X) ? Orientation.Vertical : Orientation.Horizontal); 
            }
 
            public Point A
            {
                get
                { 
                    return this.point1;
                } 
            } 

            public Point B 
            {
                get
                {
                    return this.point2; 
                }
            } 
 
            public Orientation Orientation
            { 
                get
                {
                    return this.orientation;
                } 
            }
 
            //given two points construct a segment through them from lesser cover to higher 
            public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Point b)
            { 
                //Debug.Assert(!(a.X != b.X && a.Y != b.Y), "arbitrary segment, only horizontal or vertical ones are allowed!");
                if (a.X != b.X && a.Y != b.Y)
                {
                    return null; 
                }
 
                return ConstructBoundSegment(coverSet, a, (a.X == b.X) ? Orientation.Vertical : Orientation.Horizontal); 
            }
 
            public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Orientation orientation)
            {
                return (orientation == Orientation.Horizontal) ? SegmentFromLeftToRightCover(coverSet, a) : SegmentFromBottomToTopCover(coverSet, a);
            } 

            public static double DistanceBetweenPoints(Point p, Point q) 
            { 
                return Math.Sqrt((double)(p.X - q.X) * (p.X - q.X) + (double)(p.Y - q.Y) * (p.Y - q.Y));
            } 

            public static ConnectorSegment SegmentFromBottomToTopCover(CoverSet coverSet, Point p)
            {
                ConnectorSegment bottomCover = coverSet.GetCover(p, DesignerEdges.Bottom); 
                ConnectorSegment topCover = coverSet.GetCover(p, DesignerEdges.Top);
 
                //construct vertical escape segment 
                Point bottom = new Point(p.X, (bottomCover != null) ? bottomCover.A.Y : int.MinValue);
                Point top = new Point(p.X, (topCover != null) ? topCover.A.Y : int.MaxValue); 
                ConnectorSegment v = new ConnectorSegment(bottom, top);
                return v;
            }
 
            public static ConnectorSegment SegmentFromLeftToRightCover(CoverSet coverSet, Point p)
            { 
                ConnectorSegment leftCover = coverSet.GetCover(p, DesignerEdges.Left); 
                ConnectorSegment rightCover = coverSet.GetCover(p, DesignerEdges.Right);
 
                //construct horizontal escape segment
                Point left = new Point((leftCover != null) ? leftCover.A.X : int.MinValue, p.Y);
                Point right = new Point((rightCover != null) ? rightCover.A.X : int.MaxValue, p.Y);
                ConnectorSegment h = new ConnectorSegment(left, right); 
                return h;
            } 
 
            //"segment l covers a point p, if the perpendicular from p to the line of which l is a segment intersects l"
            //since a) we only have horizotal or vertical segments and b) some segments will be unbound, we have to store and use orientation 
            //flag to do analyzis
            public bool Covers(Point p)
            {
                return (this.orientation == Orientation.Horizontal) ? (p.X >= Math.Min(this.point1.X, this.point2.X) && p.X <= Math.Max(this.point1.X, this.point2.X)) : (p.Y >= Math.Min(this.point1.Y, this.point2.Y) && p.Y <= Math.Max(this.point1.Y, this.point2.Y)); 
            }
 
            public override bool Equals(object obj) 
            {
                ConnectorSegment segment = obj as ConnectorSegment; 
                if (segment == null)
                {
                    return false;
                } 
                return (this.point1 == segment.A && this.point2 == segment.B && Orientation == segment.Orientation);
            } 
 
            public Point ExtendPointOutwards(Point p)
            { 
                if (p != this.point1 && p != this.point2)
                {
                    return p;
                } 

                int k = (int)((this.orientation == Orientation.Horizontal) ? p.X : p.Y); 
                int k1 = (int)((this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y); 
                int k2 = (int)((this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y);
 
                if (k == Math.Min(k1, k2))
                {
                    k--;
                } 
                else
                { 
                    k++; 
                }
 
                return new Point((this.orientation == Orientation.Horizontal) ? k : p.X, (this.orientation == Orientation.Horizontal) ? p.Y : k);
            }

            public override int GetHashCode() 
            {
                return this.point1.GetHashCode() ^ this.point2.GetHashCode() ^ Orientation.GetHashCode(); 
            } 

            //see if the two segments intersect 
            //greatly simplified by the fact that we only have vertical or horizontal segments
            //should work fine with {Max, Min}Value values
            public Nullable < Point > Intersect(ConnectorSegment segment)
            { 
                if (this.orientation == segment.Orientation)
                { 
                    return null; 
                }
 
                ConnectorSegment vertical = (this.orientation == Orientation.Vertical) ? this : segment;
                ConnectorSegment horizontal = (this.orientation == Orientation.Vertical) ? segment : this;

                if (vertical.A.X < Math.Min(horizontal.A.X, horizontal.B.X) || vertical.A.X > Math.Max(horizontal.A.X, horizontal.B.X)) 
                {
                    return null; 
                } 

                if (horizontal.A.Y < Math.Min(vertical.A.Y, vertical.B.Y) || horizontal.A.Y > Math.Max(vertical.A.Y, vertical.B.Y)) 
                {
                    return null;
                }
 
                return new Point(vertical.A.X, horizontal.A.Y);
            } 
 
            //we consider just the segment for this test
            public bool IsPointOnSegment(Point p) 
            {
                if ((this.orientation == Orientation.Horizontal && p.Y != this.point1.Y) || (this.orientation == Orientation.Vertical && p.X != this.point1.X))
                {
                    return false; 
                }
 
                int k = (int)((this.orientation == Orientation.Horizontal) ? p.X : p.Y); 
                int k1 = (int)((this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y);
                int k2 = (int)((this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y); 
                return k >= Math.Min(k1, k2) && k <= Math.Max(k1, k2);
            }

 
            public ConnectorSegment PeprendecularThroughPoint(Point p)
            { 
                Orientation newOrientation = (this.orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal; 
                Point newPoint = new Point(p.X, p.Y);
                if (newOrientation == Orientation.Horizontal) 
                {
                    newPoint.X = int.MaxValue;
                }
                else 
                {
                    newPoint.Y = int.MaxValue; 
                } 

                return new ConnectorSegment(p, newPoint); 
            }

            //we consider the whole line to which this segment belongs for this test
            public bool PointLiesOnThisLine(Point p) 
            {
                return (this.orientation == Orientation.Horizontal) ? p.Y == this.point1.Y : p.X == this.point1.X; 
            } 
        }
 
        //Class CoverSet (Set of vertical and horizontal covers)
        sealed class CoverSet
        {
            List < ConnectorSegment > horizontalCovers = new List < ConnectorSegment >(); 
            List < ConnectorSegment > usedEscapeLine = new List < ConnectorSegment >();
            List < ConnectorSegment > verticalCovers = new List < ConnectorSegment >(); 
 
            public CoverSet(Rect[] rectanglesToExclude, Point[] linesToExclude)
            { 
                foreach (Rect rectangle in rectanglesToExclude)
                {
                    AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Top), new Point(rectangle.Left, rectangle.Bottom)));
                    AddCover(new ConnectorSegment(new Point(rectangle.Right, rectangle.Top), new Point(rectangle.Right, rectangle.Bottom))); 
                    AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Top), new Point(rectangle.Right, rectangle.Top)));
                    AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Bottom), new Point(rectangle.Right, rectangle.Bottom))); 
                } 

                //Add the linesegments to cover 
                for (int i = 0; i < linesToExclude.Length / 2; i++)
                {
                    AddCover(new ConnectorSegment(linesToExclude[i * 2], linesToExclude[(i * 2) + 1]));
                } 
            }
 
            public void AddCover(ConnectorSegment cover) 
            {
                List < ConnectorSegment > covers = (cover.Orientation == Orientation.Vertical) ? this.verticalCovers : this.horizontalCovers; 

                for (int i = 0; i < covers.Count; i++)
                {
                    ConnectorSegment existingCover = covers[i]; 
                    if (cover.IsPointOnSegment(existingCover.A) && cover.IsPointOnSegment(existingCover.B))
                    { 
                        //both points of vertical are on the new segment, delete the vertical and add the new one instead 
                        covers.RemoveAt(i);
                        break; 
                    }
                    else if (existingCover.IsPointOnSegment(cover.A) && existingCover.IsPointOnSegment(cover.B))
                    {
                        //both points of the new segment are on an existing segment already - skip this one 
                        return;
                    } 
                } 

                covers.Add(cover); 
            }


            public void AddUsedEscapeLine(ConnectorSegment segment) 
            {
                this.usedEscapeLine.Add(segment); 
            } 

            public void ClearUsedLines() 
            {
                this.usedEscapeLine.Clear();
            }
 
            //the new escape point should not lay on any of the already used escape segments
            public bool EscapeLineHasBeenUsed(Point escapePoint) 
            { 
                for (int i = 0; i < this.usedEscapeLine.Count; i++)
                { 
                    ConnectorSegment usedSegment = this.usedEscapeLine[i];
                    if (usedSegment.IsPointOnSegment(escapePoint))
                    {
                        return true; 
                    }
                } 
                return false; 
            }
 

            //get the cover on the given side (closest cover to the given side) for the point out of all stored segments
            public ConnectorSegment GetCover(Point p, DesignerEdges side)
            { 
                ConnectorSegment cover = null;
                int distance = 0; 
 
                if (side == DesignerEdges.Left || side == DesignerEdges.Right)
                { 
                    for (int i = 0; i < this.verticalCovers.Count; i++)
                    {
                        ConnectorSegment segment = this.verticalCovers[i];
                        int currentDistance = (int)((side == DesignerEdges.Left) ? p.X - segment.A.X : segment.A.X - p.X); 
                        if (currentDistance > 0 && segment.Covers(p))
                        { 
                            if (cover == null || distance > currentDistance) 
                            {
                                cover = segment; 
                                distance = currentDistance;
                            }
                        }
                    } 
                }
                else 
                { 
                    for (int i = 0; i < this.horizontalCovers.Count; i++)
                    { 
                        ConnectorSegment segment = this.horizontalCovers[i];
                        int currentDistance = (int)((side == DesignerEdges.Bottom) ? p.Y - segment.A.Y : segment.A.Y - p.Y);
                        if (currentDistance > 0 && segment.Covers(p))
                        { 
                            if (cover == null || distance > currentDistance)
                            { 
                                cover = segment; 
                                distance = currentDistance;
                            } 
                        }
                    }
                }
 
                return cover;
            } 
 
            //get the cover on the given side (closest cover to the given side) for the point out of all stored segments
            public List < ConnectorSegment > GetCovers(Point p, DesignerEdges side) 
            {
                List < ConnectorSegment > covers = new List < ConnectorSegment >();

                if (side == DesignerEdges.Left || side == DesignerEdges.Right) 
                {
                    for (int i = 0; i < this.verticalCovers.Count; i++) 
                    { 
                        ConnectorSegment segment = this.verticalCovers[i];
                        int currentDistance = (int)((side == DesignerEdges.Left) ? p.X - segment.A.X : segment.A.X - p.X); 
                        if (currentDistance > 0 && segment.Covers(p))
                        {
                            covers.Add(segment);
                        } 
                    }
                } 
                else 
                {
                    for (int i = 0; i < this.horizontalCovers.Count; i++) 
                    {
                        ConnectorSegment segment = this.horizontalCovers[i];
                        int currentDistance = (int)((side == DesignerEdges.Bottom) ? p.Y - segment.A.Y : segment.A.Y - p.Y);
                        if (currentDistance > 0 && segment.Covers(p)) 
                        {
                            covers.Add(segment); 
                        } 
                    }
                } 

                return covers;
            }
 
            public bool IsEscapePoint(Point origin, Point escape, DesignerEdges side)
            { 
                //get the original cover 
                ConnectorSegment originalCover = this.GetCover(origin, side);
                int originalDistance; 
                if (side == DesignerEdges.Left || side == DesignerEdges.Right)
                {
                    originalDistance = (int)(originalCover.A.X - escape.X);
                } 
                else
                { 
                    originalDistance = (int)(originalCover.A.Y - escape.Y); 
                }
 
                // the escape point should not be covered by the the original cover
                if (originalCover.Covers(escape))
                {
                    return false; 
                }
 
                //it should not also be covered by any member of other segments between the original cover and the original point 
                List < ConnectorSegment > newCovers = this.GetCovers(escape, side);
                for (int i = 0; i < newCovers.Count; i++) 
                {
                    ConnectorSegment newCover = newCovers[i];
                    //should never happen, just in case...
                    if (newCover == originalCover) 
                    {
                        return false; 
                    } 

                    int newDistance; 
                    if (side == DesignerEdges.Left || side == DesignerEdges.Right)
                    {
                        newDistance = (int)Math.Abs(newCover.A.X - escape.X);
                    } 
                    else
                    { 
                        newDistance = (int)Math.Abs(newCover.A.Y - escape.Y); 
                    }
 
                    if (Math.Sign(newDistance) == Math.Sign(originalDistance) && Math.Abs(newDistance) < Math.Abs(originalDistance))
                    {
                        return false;
                    } 
                }
 
                return true; 
            }
        } 

        sealed class DistanceSorter : IComparer < DistanceFromPoint >
        {
            DistanceSorter() 
            {
            } 
 
            public static void Sort(ref List < DistanceFromPoint > distances)
            { 
                DistanceSorter sorter = new DistanceSorter();
                distances.Sort(sorter);
            }
 
            int IComparer < DistanceFromPoint >.Compare(DistanceFromPoint lhs, DistanceFromPoint rhs)
            { 
                if (lhs.Distance == rhs.Distance) 
                {
                    return 0; 
                }
                else if (lhs.Distance > rhs.Distance)
                {
                    return 1; 
                }
                else 
                { 
                    return -1;
                } 
            }
        }

    } 

} 

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