mcs/class/referencesource/System.Activities.Presentation/System.Activities.Presentation/System/Activities/Presentation/FreeFormEditing/ConnectorRouter.cs

   1 //------------------------------------------------------------
   2 // Copyright (c) Microsoft Corporation.  All rights reserved.
   3 //------------------------------------------------------------
   4
   5 namespace System.Activities.Presentation.FreeFormEditing
   6 {
   7     using System;
   8     using System.Collections.Generic;
   9     using System.Diagnostics;
  10     using System.Diagnostics.CodeAnalysis;
  11     using System.Globalization;
  12     using System.Windows;
  13     using System.Windows.Controls;
  14     using System.Runtime;
  15     using System.Activities.Presentation.View;
  16     using System.Activities.Presentation.Internal.PropertyEditing;
  17     using System.Windows.Input;
  18
  19     //
  20     // ConnectorRouter class implements the cannonical Hightower's algorithm.
  21     // See reference paper: Hightower, "A solution to line-routing problem on the continuous plane", DAC-69.
  22     //
  23     // Algorithm advantages:
  24     //      1. Very fast.
  25     //      2. Low memory requirement.
  26     //      2. Very flexible.
  27     //
  28     // Algorithm disadvantages:
  29     //      1. Do not guarantee to generate the shortest path.
  30     //      2. May fail to find a route even if it does exist.
  31     //
  32
  33     internal static class ConnectorRouter
  34     {
  35         const int connectorMargin = 30;
  36         // Used for second refinement algorithm: prevent segment overlapping with the shape edge.
  37         const int lineMargin = 10;
  38         // Used for inner blockage of the source/destination shape.
  39         const double delta = 1;
  40         // The tolerance between the end point of the routed line and the source/destination ConnectionPoint.
  41         internal const double EndPointTolerance = 1;
  42
  43         [Flags]
  44         enum DesignerEdges
  45         {
  46             None = 0,
  47             Left = 1,
  48             Top = 2,
  49             Right = 4,
  50             Bottom = 8,
  51             All = 15
  52         }
  53
  54         //This is used for dragging source point of a connector.(In this case we know only the destination connection point).
  55         internal static Point[] Route(FreeFormPanel panel, Point srPoint, ConnectionPoint destConnPoint)
  56         {
  57             Fx.Assert(panel.IsOutmostPanel(), "panel should be the outmost FreeFormPanel");
  58             UIElement destElement = destConnPoint.ParentDesigner;
  59             return Route(panel, srPoint, FreeFormPanel.GetLocationRelativeToOutmostPanel(destConnPoint), null, FreeFormPanel.GetEdgeRelativeToOutmostPanel(destConnPoint), null, destElement);
  60         }
  61
  62         //This is used for link creation gesture to show the adorner.(In this case we know only the source connection point).
  63         internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint, Point destPoint)
  64         {
  65             Fx.Assert(panel.IsOutmostPanel(), "panel should be the outmost FreeFormPanel");
  66             UIElement srcElement = srcConnPoint.ParentDesigner;
  67             return Route(panel, FreeFormPanel.GetLocationRelativeToOutmostPanel(srcConnPoint), destPoint, FreeFormPanel.GetEdgeRelativeToOutmostPanel(srcConnPoint), null, srcElement, null);
  68         }
  69
  70         //This is used for link creation gesture to show the adorner.
  71         internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnectionPoint, MouseEventArgs e)
  72         {
  73             Fx.Assert(panel.IsOutmostPanel(), "panel should be the outmost FreeFormPanel");
  74             Point[] points = null;
  75             // Used to keep consistency between preview and actual result.
  76             // Check if we are hiting a connection point
  77             if (typeof(ConnectionPointsAdorner).IsAssignableFrom(Mouse.DirectlyOver.GetType()))
  78             {
  79                 ConnectionPointsAdorner destConnPtsAdorner = Mouse.DirectlyOver as ConnectionPointsAdorner;
  80                 ConnectionPoint destConnPoint = FreeFormPanel.ConnectionPointHitTest(e.GetPosition(panel), destConnPtsAdorner);
  81                 if (destConnPoint != null && !destConnPoint.Equals(srcConnectionPoint))
  82                 {
  83                     return Route(panel, FreeFormPanel.GetLocationRelativeToOutmostPanel(srcConnectionPoint), FreeFormPanel.GetLocationRelativeToOutmostPanel(destConnPoint),
  84                         FreeFormPanel.GetEdgeRelativeToOutmostPanel(srcConnectionPoint), FreeFormPanel.GetEdgeRelativeToOutmostPanel(destConnPoint), srcConnectionPoint.ParentDesigner, destConnPtsAdorner.AdornedElement);
  85                 }
  86                 else
  87                 {
  88                     return null;
  89                 }
  90             }
  91             else
  92             {
  93                 points = ConnectorRouter.Route(panel, srcConnectionPoint, e.GetPosition(panel));
  94             }
  95             return points;
  96         }
  97
  98         //This is used when we know both the source and destination connection points.
  99         internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint, ConnectionPoint destConnPoint)
 100         {
 101             Fx.Assert(panel.IsOutmostPanel(), "panel should be the outmost FreeFormPanel");
 102             UIElement srcElement = srcConnPoint.ParentDesigner;
 103             UIElement destElement = destConnPoint.ParentDesigner;
 104             return Route(panel, FreeFormPanel.GetLocationRelativeToOutmostPanel(srcConnPoint), FreeFormPanel.GetLocationRelativeToOutmostPanel(destConnPoint),
 105                 FreeFormPanel.GetEdgeRelativeToOutmostPanel(srcConnPoint), FreeFormPanel.GetEdgeRelativeToOutmostPanel(destConnPoint), srcElement, destElement);
 106         }
 107
 108         internal static Point GetDirection(Point from, Point to)
 109         {
 110             Vector vec = to - from;
 111             return new Point(
 112                 vec.X.IsEqualTo(0) ? 0 : Math.Sign(vec.X),
 113                 vec.Y.IsEqualTo(0) ? 0 : Math.Sign(vec.Y)
 114                 );
 115         }
 116
 117         static ConnectorSegment SrcEdge;
 118         static ConnectorSegment DestEdge;
 119
 120         static void AddExcludedAndSrcDestRects(FreeFormPanel outmostPanel, FreeFormPanel panel, Point srcPoint, Point destPoint, UIElement srcElement, UIElement destElement, List<Rect> excludedRects, List<Rect> srcDestRects)
 121         {
 122             foreach (UIElement child in panel.Children)
 123             {
 124                 if (!(child is Connector))
 125                 {
 126                     Thickness margin = new Thickness(0);
 127                     FrameworkElement frameworkChild = child as FrameworkElement;
 128                     if (frameworkChild != null)
 129                     {
 130                         margin = frameworkChild.Margin;
 131                     }
 132                     Size childSize = new Size(frameworkChild.DesiredSize.Width - margin.Left - margin.Right, frameworkChild.DesiredSize.Height - margin.Top - margin.Bottom);
 133                     Rect rect = new Rect(Point.Add(panel.TranslatePoint(FreeFormPanel.GetLocation(child), outmostPanel), new Vector(margin.Left, margin.Top)), childSize);
 134                     // We don't want to add containing rectangles to the exclusion list, otherwise the algorithm will fail to find a path
 135                     Rect shrunk = new Rect(rect.X + delta, rect.Y + delta, rect.Width - delta * 2, rect.Height - delta * 2);
 136                     if (!shrunk.Contains(srcPoint) && !shrunk.Contains(destPoint))
 137                     {
 138                         excludedRects.Add(rect);
 139                     }
 140
 141                     if (srcElement == child)
 142                     {
 143                         srcDestRects.Add(rect);
 144                     }
 145                     else if (destElement == child)
 146                     {
 147                         srcDestRects.Add(rect);
 148                     }
 149
 150                     UIElement element = VirtualizedContainerService.TryGetVirtualizedElement(child);
 151                     if (element != null && typeof(INestedFreeFormPanelContainer).IsAssignableFrom(element.GetType()))
 152                     {
 153                         FreeFormPanel childPanel = ((INestedFreeFormPanelContainer)element).GetChildFreeFormPanel();
 154                         if (childPanel != null)
 155                         {
 156                             AddExcludedAndSrcDestRects(outmostPanel, childPanel, srcPoint, destPoint, srcElement, destElement, excludedRects, srcDestRects);
 157                         }
 158                     }
 159                 }
 160             }
 161         }
 162
 163         internal static Point[] Route(FreeFormPanel panel, Point srcPoint, Point destPoint, List<Point> srcEdge, List<Point> destEdge, UIElement srcElement, UIElement destElement)
 164         {
 165             if (panel == null)
 166             {
 167                 throw FxTrace.Exception.AsError(new ArgumentNullException("panel"));
 168             }
 169             List<Rect> excludedRects = new List<Rect>();
 170             List<Rect> srcDestRects = new List<Rect>();
 171             List<Point> excludedLines = new List<Point>();
 172             foreach (UIElement child in panel.Children)
 173             {
 174                 if (child.GetType() == typeof(Connector))
 175                 {
 176                     Connector connector = (Connector)child;
 177                     for (int i = 0; i < connector.Points.Count - 1; i++)
 178                     {
 179                         excludedLines.Add(new Point(connector.Points[i].X, connector.Points[i].Y));
 180                         excludedLines.Add(new Point(connector.Points[i + 1].X, connector.Points[i + 1].Y));
 181                     }
 182                 }
 183             }
 184
 185             AddExcludedAndSrcDestRects(panel, panel, srcPoint, destPoint, srcElement, destElement, excludedRects, srcDestRects);
 186
 187             return Route(srcPoint, destPoint, srcEdge, destEdge, excludedRects, excludedLines, srcDestRects);
 188         }
 189
 190         internal static Point[] Route(Point srcPoint, Point destPoint, List<Point> srcEdge, List<Point> destEdge, List<Rect> excludedRects, List<Point> excludedLines, List<Rect> srcDestRects)
 191         {
 192             ConnectorRouter.SrcEdge = null;
 193             ConnectorRouter.DestEdge = null;
 194             if (srcEdge != null)
 195             {
 196                 //ConnectorSegment should only be a segment from left to right or top to bottom.
 197                 int smallerIndex = (srcEdge[0].X < srcEdge[1].X || srcEdge[0].Y < srcEdge[1].Y) ? 0 : 1;
 198                 ConnectorRouter.SrcEdge = new ConnectorSegment(srcEdge[smallerIndex], srcEdge[1 - smallerIndex]);
 199             }
 200             if (destEdge != null)
 201             {
 202                 int smallerIndex = (destEdge[0].X < destEdge[1].X || destEdge[0].Y < destEdge[1].Y) ? 0 : 1;
 203                 ConnectorRouter.DestEdge = new ConnectorSegment(destEdge[smallerIndex], destEdge[1 - smallerIndex]);
 204             }
 205
 206             Rect[] srcDestRectsCopy = srcDestRects.ToArray();
 207             foreach (Rect rect in srcDestRectsCopy)
 208             {
 209                 // Add shrunk rectangle to avoid connector passing through the inner area of the src/dest rectangle
 210                 Rect shrunk = new Rect(rect.X + delta, rect.Y + delta, rect.Width - delta * 2, rect.Height - delta * 2);
 211                 srcDestRects.Add(shrunk);
 212                 excludedRects.Add(shrunk);
 213             }
 214
 215             return TryRoute(srcPoint, destPoint, excludedRects, excludedLines, srcDestRects);
 216         }
 217
 218         static Point[] TryRoute(Point srcPoint, Point destPoint, List<Rect> excludedRects, List<Point> excludedLines, List<Rect> srcDestRects)
 219         {
 220             Point[] segments = GetRoutedLineSegments(srcPoint, destPoint, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), excludedLines.ToArray());
 221
 222             // If we failed to find a routed path, ignore all the lines and try again.
 223             if (!AreSegmentsValid(segments))
 224             {
 225                 segments = GetRoutedLineSegments(srcPoint, destPoint, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), new Point[] { });
 226             }
 227
 228             // If we failed to find a routed path, ignore all other shapes except the source and destination shape.
 229             if (!AreSegmentsValid(segments))
 230             {
 231                 segments = GetRoutedLineSegments(srcPoint, destPoint, new Size(connectorMargin, connectorMargin), srcDestRects.ToArray(), new Point[] { });
 232             }
 233
 234             // If we still don't find a routed path, return the direct path.
 235             if (!AreSegmentsValid(segments))
 236             {
 237                 double slope = DesignerGeometryHelper.SlopeOfLineSegment(srcPoint, destPoint);
 238                 Point intermediatePoint = (slope < 1) ? new Point(destPoint.X, srcPoint.Y) : new Point(srcPoint.X, destPoint.Y);
 239                 segments = new Point[] { srcPoint, intermediatePoint, destPoint };
 240             }
 241             segments = RemoveRedundantPoints(new List<Point>(segments));
 242             return segments;
 243         }
 244
 245         //In a list of points specifying a connector, remove consecutive equivalent points.
 246         internal static Point[] RemoveRedundantPoints(List<Point> points)
 247         {
 248             for (int i = points.Count - 1; i > 0; i--)
 249             {
 250                 if (points[i].IsEqualTo(points[i - 1]))
 251                 {
 252                     points.RemoveAt(i);
 253                 }
 254             }
 255
 256             List<int> toRemove = new List<int>();
 257             int index1 = 0;
 258             int index2 = 1;
 259             int index3 = 2;
 260             while (index3 < points.Count)
 261             {
 262                 if (points[index1].X.IsEqualTo(points[index3].X) ||
 263                     points[index1].Y.IsEqualTo(points[index3].Y))
 264                 {
 265                     toRemove.Add(index2);
 266                 }
 267                 else
 268                 {
 269                     index1 = index2;
 270                 }
 271                 ++index2;
 272                 ++index3;
 273             }
 274
 275             for (int i = points.Count - 1; i > 0; i--)
 276             {
 277                 if (toRemove.Contains(i))
 278                 {
 279                     points.RemoveAt(i);
 280                 }
 281             }
 282
 283             return points.ToArray();
 284         }
 285
 286         static void AddBoundPoint(ref List<DistanceFromPoint> extremitiesList, Point p, ConnectorSegment segment, Point Z)
 287         {
 288             if (p.X != int.MinValue && p.X != int.MaxValue && p.Y != int.MinValue && p.Y != int.MaxValue)
 289             {
 290                 extremitiesList.Add(new DistanceFromPoint(segment, Z, p));
 291             }
 292         }
 293
 294         internal static bool AreSegmentsValid(Point[] segments)
 295         {
 296             if (segments == null || segments.Length < 2)
 297             {
 298                 return false;
 299             }
 300
 301             for (int i = 1; i < segments.Length; i++)
 302             {
 303                 if (!segments[i - 1].X.IsEqualTo(segments[i].X) && !segments[i - 1].Y.IsEqualTo(segments[i].Y))
 304                 {
 305                     return false;
 306                 }
 307             }
 308
 309             return true;
 310         }
 311
 312         [SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity", Justification = "This is a legacy algorithm.")]
 313         static Nullable<Point> EscapeAlgorithm(CoverSet coverSet, Point Z,
 314             ref List<Point> escapePointsA, ref List<ConnectorSegment> horizontalSegmentsA, ref List<ConnectorSegment> verticalSegmentsA, ref List<ConnectorSegment> horizontalSegmentsB, ref List<ConnectorSegment> verticalSegmentsB,
 315             ref Orientation orientationA, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB, Size margin, ref bool noEscapeA)
 316         {
 317             Nullable<Point> intersection = null;
 318             intersectionSegmentA = null;
 319             intersectionSegmentB = null;
 320
 321             ConnectorSegment leftCover = coverSet.GetCover(Z, DesignerEdges.Left);
 322             ConnectorSegment rightCover = coverSet.GetCover(Z, DesignerEdges.Right);
 323             ConnectorSegment bottomCover = coverSet.GetCover(Z, DesignerEdges.Bottom);
 324             ConnectorSegment topCover = coverSet.GetCover(Z, DesignerEdges.Top);
 325
 326             ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, Z);
 327             // We do not want the routed line to coincide with the source or dest edge.
 328             // Hence the edge should never be an escape line.
 329             if (h.Overlaps(ConnectorRouter.SrcEdge) || h.Overlaps(ConnectorRouter.DestEdge))
 330             {
 331                 h = null;
 332             }
 333             else
 334             {
 335                 horizontalSegmentsA.Add(h);
 336             }
 337
 338             ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, Z);
 339             if (v.Overlaps(ConnectorRouter.SrcEdge) || v.Overlaps(ConnectorRouter.DestEdge))
 340             {
 341                 v = null;
 342             }
 343             else
 344             {
 345                 verticalSegmentsA.Add(v);
 346             }
 347
 348
 349             // Check if the new escape line(s) intersect with the existing ones
 350             if (h != null)
 351             {
 352                 for (int i = 0; i < verticalSegmentsB.Count; i++)
 353                 {
 354                     ConnectorSegment segment = verticalSegmentsB[i];
 355                     intersection = h.Intersect(segment);
 356                     if (intersection != null)
 357                     {
 358                         intersectionSegmentA = h;
 359                         intersectionSegmentB = segment;
 360                         return intersection;
 361                     }
 362                 }
 363             }
 364
 365             if (v != null)
 366             {
 367                 for (int i = 0; i < horizontalSegmentsB.Count; i++)
 368                 {
 369                     ConnectorSegment segment = horizontalSegmentsB[i];
 370                     intersection = v.Intersect(segment);
 371                     if (intersection != null)
 372                     {
 373                         intersectionSegmentA = v;
 374                         intersectionSegmentB = segment;
 375                         return intersection;
 376                     }
 377                 }
 378             }
 379
 380             Nullable<Point> escapePoint = null;
 381             if (v != null)
 382             {
 383                 escapePoint = EscapeProcessI(coverSet, Z, v, Orientation.Horizontal, margin);
 384                 if (escapePoint != null)
 385                 {
 386                     orientationA = Orientation.Vertical;
 387                     escapePointsA.Add((Point)escapePoint);
 388                     return null;
 389                 }
 390             }
 391
 392             if (h != null)
 393             {
 394                 escapePoint = EscapeProcessI(coverSet, Z, h, Orientation.Vertical, margin);
 395                 if (escapePoint != null)
 396                 {
 397                     orientationA = Orientation.Horizontal;
 398                     escapePointsA.Add((Point)escapePoint);
 399                     return null;
 400                 }
 401             }
 402
 403             bool intersectionFlag = false;
 404
 405             // Flags indicating if we can still continue in the given directions
 406             bool continue1, continue2, continue3, continue4;
 407
 408             Point r1 = new Point(), r2 = new Point(), r3 = new Point(), r4 = new Point();
 409
 410             if (topCover != null)
 411             {
 412                 r1 = new Point(Z.X, topCover.A.Y);
 413             }
 414             if (rightCover != null)
 415             {
 416                 r2 = new Point(rightCover.A.X, Z.Y);
 417             }
 418             if (bottomCover != null)
 419             {
 420                 r3 = new Point(Z.X, bottomCover.A.Y);
 421             }
 422             if (leftCover != null)
 423             {
 424                 r4 = new Point(leftCover.A.X, Z.Y);
 425             }
 426             do
 427             {
 428                 continue1 = continue2 = continue3 = continue4 = false;
 429                 if (topCover != null && v != null)
 430                 {
 431                     r1.Y -= margin.Height;
 432                     if (r1.Y > Z.Y)
 433                     {
 434                         continue1 = true;
 435                         Nullable<Point> escape = EscapeProcessII(coverSet, Orientation.Vertical,
 436                             ref escapePointsA, ref horizontalSegmentsA, ref verticalSegmentsA, ref horizontalSegmentsB, ref verticalSegmentsB, r1, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
 437                         if (escape != null)
 438                         {
 439                             verticalSegmentsA.Add(v);
 440                             if (intersectionFlag)
 441                             {
 442                                 return escape;
 443                             }
 444
 445                             orientationA = Orientation.Horizontal;
 446                             coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r1));
 447                             coverSet.AddUsedEscapeLine(new ConnectorSegment(r1, (Point)escape));
 448                             escapePointsA.Add((Point)escape);
 449                             return null;
 450                         }
 451                     }
 452                 }
 453
 454                 if (rightCover != null && h != null)
 455                 {
 456                     r2.X -= margin.Width;
 457                     if (r2.X > Z.X)
 458                     {
 459                         continue2 = true;
 460                         Nullable<Point> escape = EscapeProcessII(coverSet, Orientation.Horizontal,
 461                             ref escapePointsA, ref horizontalSegmentsA, ref verticalSegmentsA, ref horizontalSegmentsB, ref verticalSegmentsB, r2, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
 462                         if (escape != null)
 463                         {
 464                             horizontalSegmentsA.Add(h);
 465                             if (intersectionFlag)
 466                             {
 467                                 return escape;
 468                             }
 469
 470                             orientationA = Orientation.Vertical;
 471                             coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r2));
 472                             coverSet.AddUsedEscapeLine(new ConnectorSegment(r2, (Point)escape));
 473                             escapePointsA.Add((Point)escape);
 474                             return null;
 475                         }
 476                     }
 477                 }
 478
 479                 if (bottomCover != null && v != null)
 480                 {
 481                     r3.Y += margin.Height;
 482                     if (r3.Y < Z.Y)
 483                     {
 484                         continue3 = true;
 485                         Nullable<Point> escape = EscapeProcessII(coverSet, Orientation.Vertical,
 486                             ref escapePointsA, ref horizontalSegmentsA, ref verticalSegmentsA, ref horizontalSegmentsB, ref verticalSegmentsB, r3, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
 487                         if (escape != null)
 488                         {
 489                             verticalSegmentsA.Add(v);
 490                             if (intersectionFlag)
 491                             {
 492                                 return escape;
 493                             }
 494
 495                             orientationA = Orientation.Horizontal;
 496                             coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r3));
 497                             coverSet.AddUsedEscapeLine(new ConnectorSegment(r3, (Point)escape));
 498                             escapePointsA.Add((Point)escape);
 499                             return null;
 500                         }
 501                     }
 502                 }
 503
 504                 if (leftCover != null && h != null)
 505                 {
 506                     r4.X += margin.Width;
 507                     if (r4.X < Z.X)
 508                     {
 509                         continue4 = true;
 510                         Nullable<Point> escape = EscapeProcessII(coverSet, Orientation.Horizontal,
 511                             ref escapePointsA, ref horizontalSegmentsA, ref verticalSegmentsA, ref horizontalSegmentsB, ref verticalSegmentsB, r4, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
 512                         if (escape != null)
 513                         {
 514                             horizontalSegmentsA.Add(h);
 515                             if (intersectionFlag)
 516                             {
 517                                 return escape;
 518                             }
 519
 520                             orientationA = Orientation.Vertical;
 521                             coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r4));
 522                             coverSet.AddUsedEscapeLine(new ConnectorSegment(r4, (Point)escape));
 523                             escapePointsA.Add((Point)escape);
 524                             return null;
 525                         }
 526                     }
 527                 }
 528             } while (continue1 || continue2 || continue3 || continue4);
 529
 530             noEscapeA = true;
 531             return null;
 532         }
 533
 534         static Nullable<Point> EscapeProcessI(CoverSet coverSet, Point Z,
 535             ConnectorSegment escapeLine, Orientation orientation, Size margin)
 536         {
 537             List<DistanceFromPoint> extremitiesList = new List<DistanceFromPoint>(4);
 538
 539             ConnectorSegment lesserCover = coverSet.GetCover(Z, (orientation == Orientation.Horizontal) ? DesignerEdges.Left : DesignerEdges.Bottom);
 540             if (lesserCover != null)
 541             {
 542                 AddBoundPoint(ref extremitiesList, lesserCover.A, lesserCover, Z);
 543                 AddBoundPoint(ref extremitiesList, lesserCover.B, lesserCover, Z);
 544             }
 545
 546             ConnectorSegment higherCover = coverSet.GetCover(Z, (orientation == Orientation.Horizontal) ? DesignerEdges.Right : DesignerEdges.Top);
 547             if (higherCover != null)
 548             {
 549                 AddBoundPoint(ref extremitiesList, higherCover.A, higherCover, Z);
 550                 AddBoundPoint(ref extremitiesList, higherCover.B, higherCover, Z);
 551             }
 552
 553             if (extremitiesList.Count == 0)
 554             {
 555                 return null;
 556             }
 557
 558             DistanceSorter.Sort(ref extremitiesList);
 559             for (int i = 0; i < extremitiesList.Count; i++)
 560             {
 561                 Point p = extremitiesList[i].P;
 562                 Point direction = GetDirection(Z, p);
 563                 if (((orientation == Orientation.Vertical) ? direction.X : direction.Y).IsEqualTo(0))
 564                 {
 565                     ConnectorSegment segment = extremitiesList[i].ConnectorSegment;
 566                     p = segment.ExtendPointOutwards(p);
 567                     direction = GetDirection(Z, p);
 568                     p = extremitiesList[i].P;
 569                 }
 570
 571                 DesignerEdges side;
 572                 if (orientation == Orientation.Vertical)
 573                 {
 574                     side = (direction.Y < 0) ? DesignerEdges.Bottom : DesignerEdges.Top;
 575                 }
 576                 else
 577                 {
 578                     side = (direction.X < 0) ? DesignerEdges.Left : DesignerEdges.Right;
 579                 }
 580
 581                 Point escapePoint;
 582                 if ((orientation == Orientation.Vertical))
 583                 {
 584                     escapePoint = new Point(p.X + direction.X * margin.Width, Z.Y);
 585                 }
 586                 else
 587                 {
 588                     escapePoint = new Point(Z.X, p.Y + direction.Y * margin.Height);
 589                 }
 590
 591                 ConnectorSegment newEscapeLine = new ConnectorSegment(Z, escapePoint);
 592                 if (!coverSet.EscapeLineHasBeenUsed(escapePoint) &&
 593                     escapeLine.IsPointOnSegment(escapePoint) && !escapeLine.A.IsEqualTo(escapePoint) && !escapeLine.B.IsEqualTo(escapePoint) &&
 594                     coverSet.IsEscapePoint(Z, escapePoint, side))
 595                 {
 596                     coverSet.AddUsedEscapeLine(newEscapeLine);
 597                     return escapePoint;
 598                 }
 599             }
 600
 601             return null;
 602         }
 603
 604         static Nullable<Point> EscapeProcessII(CoverSet coverSet, Orientation orientation, ref List<Point> escapePointsA,
 605             ref List<ConnectorSegment> horizontalSegmentsA, ref List<ConnectorSegment> verticalSegmentsA, ref List<ConnectorSegment> horizontalSegmentsB, ref List<ConnectorSegment> verticalSegmentsB,
 606             Point R, Size margin, out bool intersectionFlag, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB)
 607         {
 608             intersectionFlag = false;
 609             intersectionSegmentA = null;
 610             intersectionSegmentB = null;
 611
 612             ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, R);
 613             ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, R);
 614
 615             for (int i = 0; i < verticalSegmentsB.Count; i++)
 616             {
 617                 ConnectorSegment segment = verticalSegmentsB[i];
 618                 Nullable<Point> intersection = h.Intersect(segment);
 619                 if (intersection != null)
 620                 {
 621                     intersectionFlag = true;
 622                     intersectionSegmentA = h;
 623                     intersectionSegmentB = segment;
 624                     escapePointsA.Add(R);
 625                     return intersection;
 626                 }
 627             }
 628             for (int i = 0; i < horizontalSegmentsB.Count; i++)
 629             {
 630                 ConnectorSegment segment = horizontalSegmentsB[i];
 631                 Nullable<Point> intersection = v.Intersect(segment);
 632                 if (intersection != null)
 633                 {
 634                     intersectionFlag = true;
 635                     intersectionSegmentA = v;
 636                     intersectionSegmentB = segment;
 637                     escapePointsA.Add(R);
 638                     return intersection;
 639                 }
 640             }
 641
 642             Nullable<Point> escapePointI = null;
 643
 644             if (orientation == Orientation.Horizontal)
 645             {
 646                 escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin);
 647                 if (escapePointI != null)
 648                 {
 649                     verticalSegmentsA.Add(v);
 650                     escapePointsA.Add(R);
 651                     return escapePointI;
 652                 }
 653
 654                 escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin);
 655                 if (escapePointI != null)
 656                 {
 657                     horizontalSegmentsA.Add(h);
 658                     escapePointsA.Add(R);
 659                     return escapePointI;
 660                 }
 661             }
 662             else
 663             {
 664                 escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin);
 665                 if (escapePointI != null)
 666                 {
 667                     horizontalSegmentsA.Add(h);
 668                     escapePointsA.Add(R);
 669                     return escapePointI;
 670                 }
 671
 672                 escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin);
 673                 if (escapePointI != null)
 674                 {
 675                     verticalSegmentsA.Add(v);
 676                     escapePointsA.Add(R);
 677                     return escapePointI;
 678                 }
 679             }
 680
 681             return null;
 682         }
 683
 684         static List<Point> FirstRefinementAlgorithm(List<Point> points, ConnectorSegment intersectionSegment)
 685         {
 686             List<Point> refinedSet = new List<Point>();
 687             ConnectorSegment k = intersectionSegment;
 688
 689             while (points.Count > 0)
 690             {
 691                 Point point;
 692                 int i = points.Count - 1;
 693
 694                 while (!k.PointLiesOnThisLine(points[i]) && i > 0)
 695                 {
 696                     i--;
 697                 }
 698
 699                 while (i > 0 && k.PointLiesOnThisLine(points[i - 1]))
 700                 {
 701                     i--;
 702                 }
 703                 point = points[i];
 704                 refinedSet.Add(point);
 705
 706                 while (points.Count > i)
 707                 {
 708                     points.RemoveAt(i);
 709                 }
 710
 711                 k = k.PerpendicularThroughPoint(point);
 712             }
 713
 714             return refinedSet;
 715         }
 716
 717         [SuppressMessage("Microsoft.Design", "CA1031:DoNotCatchGeneralExceptionTypes",
 718             Justification = "Catch all exceptions to prevent crash.")]
 719         [SuppressMessage("Reliability", "Reliability108:IsFatalRule",
 720             Justification = "Catch all exceptions to prevent crash.")]
 721         static Point[] GetRoutedLineSegments(Point begin, Point end, Size margin, Rect[] rectanglesToExclude, Point[] linesToExclude)
 722         {
 723             if (rectanglesToExclude == null)
 724             {
 725                 throw FxTrace.Exception.AsError(new ArgumentNullException("rectanglesToExclude"));
 726             }
 727
 728             if (linesToExclude == null)
 729             {
 730                 throw FxTrace.Exception.AsError(new ArgumentNullException("linesToExclude"));
 731             }
 732
 733             if ((linesToExclude.Length % 2) > 0)
 734             {
 735                 throw FxTrace.Exception.AsError(new ArgumentException("Error"));
 736             }
 737
 738
 739             CoverSet coverSet = new CoverSet(rectanglesToExclude, linesToExclude);
 740             coverSet.ClearUsedLines();
 741
 742             Point A = begin;
 743             Point B = end;
 744
 745             //escape points
 746             List<Point> escapePointsA = new List<Point>(); //escape points from begin to end
 747             List<Point> escapePointsB = new List<Point>(); //escape points from end to begin
 748
 749             //horizontal/vertical escape segments from A
 750             List<ConnectorSegment> horizontalEscapeSegmentsA = new List<ConnectorSegment>();
 751             List<ConnectorSegment> verticalEscapeSegmentsA = new List<ConnectorSegment>();
 752
 753             //horizontal/vertical escape segments from B
 754             List<ConnectorSegment> horizontalEscapeSegmentsB = new List<ConnectorSegment>();
 755             List<ConnectorSegment> verticalEscapeSegmentsB = new List<ConnectorSegment>();
 756
 757             Orientation orientationA = Orientation.Horizontal;
 758             Orientation orientationB = Orientation.Horizontal;
 759
 760             escapePointsA.Add(begin);
 761             escapePointsB.Add(end);
 762
 763             bool noEscapeA = false;
 764             bool noEscapeB = false;
 765
 766             Nullable<Point> intersection = null;
 767             ConnectorSegment intersectionSegmentA = null;
 768             ConnectorSegment intersectionSegmentB = null;
 769
 770             try
 771             {
 772                 do
 773                 {
 774                     if (noEscapeA)
 775                     {
 776                         if (noEscapeB)
 777                         {
 778                             break;
 779                         }
 780                         else
 781                         {
 782                             List<Point> tempList = escapePointsA;
 783                             escapePointsA = escapePointsB;
 784                             escapePointsB = tempList;
 785
 786                             Point tempPoint = A;
 787                             A = B;
 788                             B = tempPoint;
 789
 790                             bool tempBool = noEscapeA;
 791                             noEscapeA = noEscapeB;
 792                             noEscapeB = tempBool;
 793
 794                             Orientation tempOrientation = orientationA;
 795                             orientationA = orientationB;
 796                             orientationB = tempOrientation;
 797
 798                             List<ConnectorSegment> tempListSegm = horizontalEscapeSegmentsA;
 799                             horizontalEscapeSegmentsA = horizontalEscapeSegmentsB;
 800                             horizontalEscapeSegmentsB = tempListSegm;
 801
 802                             tempListSegm = verticalEscapeSegmentsA;
 803                             verticalEscapeSegmentsA = verticalEscapeSegmentsB;
 804                             verticalEscapeSegmentsB = tempListSegm;
 805
 806                             continue;
 807                         }
 808                     }
 809
 810                     Point objectPoint = escapePointsA[escapePointsA.Count - 1];
 811
 812                     intersection = EscapeAlgorithm(coverSet, objectPoint,
 813                         ref escapePointsA, ref horizontalEscapeSegmentsA, ref verticalEscapeSegmentsA, ref horizontalEscapeSegmentsB, ref verticalEscapeSegmentsB, ref orientationA,
 814                         out intersectionSegmentA, out intersectionSegmentB, margin, ref noEscapeA);
 815                     if (intersection != null)
 816                     {
 817                         break;
 818                     }
 819                     else
 820                     {
 821                         List<Point> tempList = escapePointsA;
 822                         escapePointsA = escapePointsB;
 823                         escapePointsB = tempList;
 824
 825                         Point tempPoint = A;
 826                         A = B;
 827                         B = tempPoint;
 828
 829                         bool tempBool = noEscapeA;
 830                         noEscapeA = noEscapeB;
 831                         noEscapeB = tempBool;
 832
 833                         Orientation tempOrientation = orientationA;
 834                         orientationA = orientationB;
 835                         orientationB = tempOrientation;
 836
 837                         List<ConnectorSegment> tempListSegm = horizontalEscapeSegmentsA;
 838                         horizontalEscapeSegmentsA = horizontalEscapeSegmentsB;
 839                         horizontalEscapeSegmentsB = tempListSegm;
 840
 841                         tempListSegm = verticalEscapeSegmentsA;
 842                         verticalEscapeSegmentsA = verticalEscapeSegmentsB;
 843                         verticalEscapeSegmentsB = tempListSegm;
 844                     }
 845
 846                 } while (true);
 847
 848                 if (intersection == null)
 849                 {
 850                     return null;
 851                 }
 852
 853                 List<Point> refinedPath = new List<Point>();
 854
 855                 escapePointsA = FirstRefinementAlgorithm(escapePointsA, intersectionSegmentA);
 856                 escapePointsB = FirstRefinementAlgorithm(escapePointsB, intersectionSegmentB);
 857
 858                 for (int j = escapePointsA.Count - 1; j >= 0; j--)
 859                 {
 860                     refinedPath.Add(escapePointsA[j]);
 861                 }
 862                 refinedPath.Add((Point)intersection);
 863                 for (int j = 0; j < escapePointsB.Count; j++)
 864                 {
 865                     refinedPath.Add(escapePointsB[j]);
 866                 }
 867
 868                 SecondRefinementAlgorithm(coverSet, ref refinedPath, margin);
 869
 870                 if (refinedPath.Count > 1 && refinedPath[refinedPath.Count - 1].IsEqualTo(begin))
 871                 {
 872                     refinedPath.Reverse();
 873                 }
 874
 875                 return refinedPath.ToArray();
 876             }
 877             catch (Exception)
 878             {
 879                 return null;
 880             }
 881         }
 882
 883         static void EraseRedundentWarps(CoverSet coverSet, ref List<Point> refinedPath)
 884         {
 885             bool structureChanged;
 886             do
 887             {
 888                 structureChanged = false;
 889                 List<Point> newPath = new List<Point>();
 890                 int currentSegment = 0;
 891                 while (currentSegment < refinedPath.Count - 1)
 892                 {
 893                     Point a1 = refinedPath[currentSegment];
 894                     Point a2 = refinedPath[currentSegment + 1];
 895
 896                     ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2);
 897
 898                     int intersectingSegment = currentSegment + 2;
 899                     while (intersectingSegment < refinedPath.Count - 1)
 900                     {
 901                         Point b1 = refinedPath[intersectingSegment];
 902                         Point b2 = refinedPath[intersectingSegment + 1];
 903                         ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, b1, b2);
 904
 905                         Nullable<Point> intersection = a.Intersect(b);
 906                         if (intersection != null)
 907                         {
 908                             structureChanged = true;
 909                             newPath.Clear();
 910                             for (int i = 0; i <= currentSegment; i++)
 911                             {
 912                                 newPath.Add(refinedPath[i]);
 913                             }
 914                             newPath.Add((Point)intersection);
 915                             for (int i = intersectingSegment + 1; i < refinedPath.Count; i++)
 916                             {
 917                                 newPath.Add(refinedPath[i]);
 918                             }
 919
 920                             List<Point> temp = refinedPath;
 921                             refinedPath = newPath;
 922                             newPath = temp;
 923                             newPath.Clear();
 924
 925                             intersectingSegment = currentSegment + 2;
 926                         }
 927                         else
 928                         {
 929                             intersectingSegment++;
 930                         }
 931                     }
 932                     currentSegment++;
 933                 }
 934             } while (structureChanged);
 935         }
 936
 937         static void SecondRefinementAlgorithm(CoverSet coverSet, ref List<Point> refinedPath, Size margin)
 938         {
 939             EraseRedundentWarps(coverSet, ref refinedPath);
 940             List<Point> newPath = new List<Point>();
 941             int currentSegment = 0;
 942             while (currentSegment < refinedPath.Count - 1)
 943             {
 944                 Point a1 = refinedPath[currentSegment];
 945                 Point a2 = refinedPath[currentSegment + 1];
 946
 947                 bool intersected = false;
 948                 ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2);
 949                 if (a != null)
 950                 {
 951                     Vector sub = a2 - a1;
 952                     int steps = (int)Math.Max(Math.Abs(sub.X / margin.Width), Math.Abs(sub.Y / margin.Height)); //one of the values will be null
 953                     Point direction = GetDirection(a1, a2);
 954                     // Prevent segments overlapping with shape edges.
 955                     ExtendCoversOutwards(coverSet, a.Orientation, lineMargin);
 956
 957                     for (int i = 1; i <= steps; i++)
 958                     {
 959                         Point k = new Point(a1.X + i * margin.Width * direction.X, a1.Y + i * margin.Height * direction.Y);
 960                         if (k.IsEqualTo(a2))
 961                         {
 962                             break;
 963                         }
 964
 965                         ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, k, (a.Orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal);
 966                         int intersectingSegment = currentSegment + 2;
 967                         while (intersectingSegment < refinedPath.Count - 1 && !intersected)
 968                         {
 969                             Point c1 = refinedPath[intersectingSegment];
 970                             Point c2 = refinedPath[intersectingSegment + 1];
 971                             ConnectorSegment c = new ConnectorSegment(c1, c2);
 972
 973                             Nullable<Point> intersection = b.Intersect(c);
 974                             if (intersection != null && c.IsPointOnSegment((Point)intersection))
 975                             {
 976                                 intersected = true;
 977
 978                                 newPath.Clear();
 979                                 for (int j = 0; j <= currentSegment; j++)
 980                                 {
 981                                     newPath.Add(refinedPath[j]);
 982                                 }
 983                                 newPath.Add(k);
 984                                 newPath.Add((Point)intersection);
 985                                 for (int j = intersectingSegment + 1; j < refinedPath.Count; j++)
 986                                 {
 987                                     newPath.Add(refinedPath[j]);
 988                                 }
 989                                 List<Point> temp = refinedPath;
 990                                 refinedPath = newPath;
 991                                 newPath = temp;
 992                                 newPath.Clear();
 993                                 break;
 994                             }
 995
 996                             intersectingSegment++;
 997                         }
 998
 999                         if (intersected)
1000                         {
1001                             break;
1002                         }
1003                     }
1004                     // Restore shape edges.
1005                     ShrinkCoversInwards(coverSet, a.Orientation, lineMargin);
1006                 }
1007                 if (!intersected)
1008                 {
1009                     currentSegment++;
1010                 }
1011             }
1012         }
1013
1014         static List<ConnectorSegment> GetSegmentsForOrientation(CoverSet coverSet, Orientation orientation)
1015         {
1016             List<ConnectorSegment> connectorSegments = null;
1017             if (orientation == Orientation.Horizontal)
1018             {
1019                 connectorSegments = coverSet.HorizontalCovers;
1020             }
1021             else
1022             {
1023                 connectorSegments = coverSet.VerticalCovers;
1024             }
1025             return connectorSegments;
1026         }
1027
1028         static void ShrinkCoversInwards(CoverSet coverSet, Orientation orientation, double shrunkLength)
1029         {
1030             List<ConnectorSegment> connectorSegments = GetSegmentsForOrientation(coverSet, orientation);
1031             foreach (ConnectorSegment connSeg in connectorSegments)
1032             {
1033                 connSeg.ShrinkSegmentInwards(shrunkLength);
1034             }
1035         }
1036
1037         static void ExtendCoversOutwards(CoverSet coverSet, Orientation orientation, double extendedLength)
1038         {
1039             List<ConnectorSegment> connectorSegments = GetSegmentsForOrientation(coverSet, orientation);
1040             foreach (ConnectorSegment connSeg in connectorSegments)
1041             {
1042                 connSeg.ExtendSegmentOutwards(extendedLength);
1043             }
1044         }
1045
1046
1047         struct DistanceFromPoint
1048         {
1049             public ConnectorSegment ConnectorSegment;
1050             public double Distance;
1051             public Point P;
1052
1053             public DistanceFromPoint(ConnectorSegment segment, Point z, Point p)
1054             {
1055                 this.ConnectorSegment = segment;
1056                 this.P = p;
1057                 this.Distance = DesignerGeometryHelper.DistanceBetweenPoints(z, p);
1058             }
1059         }
1060
1061         // Represents a segment - the main entity in the routing algorithm
1062         sealed class ConnectorSegment
1063         {
1064             Orientation orientation;
1065             Point point1;
1066             Point point2;
1067
1068             public ConnectorSegment(Point point1, Point point2)
1069             {
1070                 if (!point1.X.IsEqualTo(point2.X) && !point1.Y.IsEqualTo(point2.Y))
1071                 {
1072                     throw FxTrace.Exception.AsError(new InvalidOperationException(string.Format(CultureInfo.InvariantCulture,
1073                         SR.CannotConstructConnectionSegment, point1.ToString(), point2.ToString())));
1074                 }
1075
1076                 this.point1 = point1;
1077                 this.point2 = point2;
1078                 this.orientation = (this.point1.X.IsEqualTo(this.point2.X) ? Orientation.Vertical : Orientation.Horizontal);
1079             }
1080
1081             public Point A
1082             {
1083                 get
1084                 {
1085                     return this.point1;
1086                 }
1087             }
1088
1089             public Point B
1090             {
1091                 get
1092                 {
1093                     return this.point2;
1094                 }
1095             }
1096
1097             public Orientation Orientation
1098             {
1099                 get
1100                 {
1101                     return this.orientation;
1102                 }
1103             }
1104
1105             public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Point b)
1106             {
1107                 if (!a.X.IsEqualTo(b.X) && !a.Y.IsEqualTo(b.Y))
1108                 {
1109                     return null;
1110                 }
1111
1112                 return ConstructBoundSegment(coverSet, a, a.X.IsEqualTo(b.X) ? Orientation.Vertical : Orientation.Horizontal);
1113             }
1114
1115             public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Orientation orientation)
1116             {
1117                 return (orientation == Orientation.Horizontal) ? SegmentFromLeftToRightCover(coverSet, a) : SegmentFromBottomToTopCover(coverSet, a);
1118             }
1119
1120             public static ConnectorSegment SegmentFromBottomToTopCover(CoverSet coverSet, Point p)
1121             {
1122                 ConnectorSegment bottomCover = coverSet.GetCover(p, DesignerEdges.Bottom);
1123                 ConnectorSegment topCover = coverSet.GetCover(p, DesignerEdges.Top);
1124
1125                 //construct vertical escape segment
1126                 Point bottom = new Point(p.X, (bottomCover != null) ? bottomCover.A.Y : int.MinValue);
1127                 Point top = new Point(p.X, (topCover != null) ? topCover.A.Y : int.MaxValue);
1128                 ConnectorSegment v = new ConnectorSegment(bottom, top);
1129                 return v;
1130             }
1131
1132             public static ConnectorSegment SegmentFromLeftToRightCover(CoverSet coverSet, Point p)
1133             {
1134                 ConnectorSegment leftCover = coverSet.GetCover(p, DesignerEdges.Left);
1135                 ConnectorSegment rightCover = coverSet.GetCover(p, DesignerEdges.Right);
1136
1137                 //construct horizontal escape segment
1138                 Point left = new Point((leftCover != null) ? leftCover.A.X : int.MinValue, p.Y);
1139                 Point right = new Point((rightCover != null) ? rightCover.A.X : int.MaxValue, p.Y);
1140                 ConnectorSegment h = new ConnectorSegment(left, right);
1141                 return h;
1142             }
1143
1144             public bool Covers(Point p)
1145             {
1146                 return (this.orientation == Orientation.Horizontal) ?
1147                     (p.X.IsNoLessThan(Math.Min(this.point1.X, this.point2.X)) && p.X.IsNoGreaterThan(Math.Max(this.point1.X, this.point2.X))) :
1148                     (p.Y.IsNoLessThan(Math.Min(this.point1.Y, this.point2.Y)) && p.Y.IsNoGreaterThan(Math.Max(this.point1.Y, this.point2.Y)));
1149             }
1150
1151             public override bool Equals(object obj)
1152             {
1153                 ConnectorSegment segment = obj as ConnectorSegment;
1154                 if (segment == null)
1155                 {
1156                     return false;
1157                 }
1158                 return (this.point1.IsEqualTo(segment.A) && this.point2.IsEqualTo(segment.B) && Orientation == segment.Orientation);
1159             }
1160
1161             public bool Overlaps(ConnectorSegment segment)
1162             {
1163                 if (segment == null)
1164                 {
1165                     return false;
1166                 }
1167                 if (this.Orientation == segment.Orientation)
1168                 {
1169                     return this.IsPointOnSegment(segment.point1) || this.IsPointOnSegment(segment.point2) || segment.IsPointOnSegment(this.point1) || segment.IsPointOnSegment(this.point2);
1170                 }
1171                 return false;
1172             }
1173
1174             public Point ExtendPointOutwards(Point p)
1175             {
1176                 if (!p.IsEqualTo(this.point1) && !p.IsEqualTo(this.point2))
1177                 {
1178                     return p;
1179                 }
1180
1181                 double k = ((this.orientation == Orientation.Horizontal) ? p.X : p.Y);
1182                 double k1 = ((this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y);
1183                 double k2 = ((this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y);
1184                 k += k.IsEqualTo(Math.Min(k1, k2)) ? -1.0 : 1.0;
1185                 return new Point((this.orientation == Orientation.Horizontal) ? k : p.X, (this.orientation == Orientation.Horizontal) ? p.Y : k);
1186             }
1187
1188             public void ExtendSegmentOutwards(double extendedLength)
1189             {
1190                 if (this.Orientation == Orientation.Horizontal)
1191                 {
1192                     if (this.point1.X > this.point2.X)
1193                     {
1194                         this.point1 = Point.Add(this.point1, new Vector(extendedLength, 0));
1195                         this.point2 = Point.Add(this.point2, new Vector(-extendedLength, 0));
1196                     }
1197                     else
1198                     {
1199                         this.point1 = Point.Add(this.point1, new Vector(-extendedLength, 0));
1200                         this.point2 = Point.Add(this.point2, new Vector(extendedLength, 0));
1201                     }
1202                 }
1203                 else
1204                 {
1205                     if (this.point1.Y > this.point2.Y)
1206                     {
1207                         this.point1 = Point.Add(this.point1, new Vector(0, extendedLength));
1208                         this.point2 = Point.Add(this.point2, new Vector(0, -extendedLength));
1209                     }
1210                     else
1211                     {
1212                         this.point1 = Point.Add(this.point1, new Vector(0, -extendedLength));
1213                         this.point2 = Point.Add(this.point2, new Vector(0, extendedLength));
1214                     }
1215                 }
1216             }
1217
1218             public void ShrinkSegmentInwards(double shrunkLength)
1219             {
1220                 this.ExtendSegmentOutwards(-shrunkLength);
1221             }
1222
1223             public override int GetHashCode()
1224             {
1225                 return this.point1.GetHashCode() ^ this.point2.GetHashCode() ^ Orientation.GetHashCode();
1226             }
1227
1228             public Nullable<Point> Intersect(ConnectorSegment segment)
1229             {
1230                 if (this.orientation == segment.Orientation)
1231                 {
1232                     return null;
1233                 }
1234
1235                 ConnectorSegment vertical = (this.orientation == Orientation.Vertical) ? this : segment;
1236                 ConnectorSegment horizontal = (this.orientation == Orientation.Vertical) ? segment : this;
1237
1238                 if (vertical.A.X < Math.Min(horizontal.A.X, horizontal.B.X) || vertical.A.X > Math.Max(horizontal.A.X, horizontal.B.X))
1239                 {
1240                     return null;
1241                 }
1242
1243                 if (horizontal.A.Y < Math.Min(vertical.A.Y, vertical.B.Y) || horizontal.A.Y > Math.Max(vertical.A.Y, vertical.B.Y))
1244                 {
1245                     return null;
1246                 }
1247
1248                 return new Point(vertical.A.X, horizontal.A.Y);
1249             }
1250
1251             public bool IsPointOnSegment(Point p)
1252             {
1253                 if ((this.orientation == Orientation.Horizontal && !p.Y.IsEqualTo(this.point1.Y)) || (this.orientation == Orientation.Vertical && !p.X.IsEqualTo(this.point1.X)))
1254                 {
1255                     return false;
1256                 }
1257
1258                 double k = (this.orientation == Orientation.Horizontal) ? p.X : p.Y;
1259                 double k1 = (this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y;
1260                 double k2 = (this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y;
1261                 return k.IsNoLessThan(Math.Min(k1, k2)) && k.IsNoGreaterThan(Math.Max(k1, k2));
1262             }
1263
1264             public ConnectorSegment PerpendicularThroughPoint(Point p)
1265             {
1266                 Orientation newOrientation = (this.orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal;
1267                 Point newPoint = new Point(p.X, p.Y);
1268                 if (newOrientation == Orientation.Horizontal)
1269                 {
1270                     newPoint.X = int.MaxValue;
1271                 }
1272                 else
1273                 {
1274                     newPoint.Y = int.MaxValue;
1275                 }
1276
1277                 return new ConnectorSegment(p, newPoint);
1278             }
1279
1280             // We consider the whole line to which this segment belongs for this test
1281             public bool PointLiesOnThisLine(Point p)
1282             {
1283                 return (this.orientation == Orientation.Horizontal) ? p.Y.IsEqualTo(this.point1.Y) : p.X.IsEqualTo(this.point1.X);
1284             }
1285         }
1286
1287         sealed class CoverSet
1288         {
1289             List<ConnectorSegment> horizontalCovers = new List<ConnectorSegment>();
1290             List<ConnectorSegment> usedEscapeLine = new List<ConnectorSegment>();
1291             List<ConnectorSegment> verticalCovers = new List<ConnectorSegment>();
1292
1293             public List<ConnectorSegment> HorizontalCovers
1294             {
1295                 get { return this.horizontalCovers; }
1296             }
1297
1298             public List<ConnectorSegment> VerticalCovers
1299             {
1300                 get { return this.verticalCovers; }
1301             }
1302
1303             public CoverSet(Rect[] rectanglesToExclude, Point[] linesToExclude)
1304             {
1305                 foreach (Rect rectangle in rectanglesToExclude)
1306                 {
1307                     AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Top), new Point(rectangle.Left, rectangle.Bottom)));
1308                     AddCover(new ConnectorSegment(new Point(rectangle.Right, rectangle.Top), new Point(rectangle.Right, rectangle.Bottom)));
1309                     AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Top), new Point(rectangle.Right, rectangle.Top)));
1310                     AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Bottom), new Point(rectangle.Right, rectangle.Bottom)));
1311                 }
1312
1313                 for (int i = 0; i < linesToExclude.Length / 2; i++)
1314                 {
1315                     AddCover(new ConnectorSegment(linesToExclude[i * 2], linesToExclude[(i * 2) + 1]));
1316                 }
1317             }
1318
1319             public void AddCover(ConnectorSegment cover)
1320             {
1321                 List<ConnectorSegment> covers = (cover.Orientation == Orientation.Vertical) ? this.verticalCovers : this.horizontalCovers;
1322
1323                 for (int i = 0; i < covers.Count; i++)
1324                 {
1325                     ConnectorSegment existingCover = covers[i];
1326                     if (cover.IsPointOnSegment(existingCover.A) && cover.IsPointOnSegment(existingCover.B))
1327                     {
1328                         covers.RemoveAt(i);
1329                         break;
1330                     }
1331                     else if (existingCover.IsPointOnSegment(cover.A) && existingCover.IsPointOnSegment(cover.B))
1332                     {
1333                         return;
1334                     }
1335                 }
1336
1337                 covers.Add(cover);
1338             }
1339
1340
1341             public void AddUsedEscapeLine(ConnectorSegment segment)
1342             {
1343                 this.usedEscapeLine.Add(segment);
1344             }
1345
1346             public void ClearUsedLines()
1347             {
1348                 this.usedEscapeLine.Clear();
1349             }
1350
1351             public bool EscapeLineHasBeenUsed(Point escapePoint)
1352             {
1353                 for (int i = 0; i < this.usedEscapeLine.Count; i++)
1354                 {
1355                     ConnectorSegment usedSegment = this.usedEscapeLine[i];
1356                     if (usedSegment.IsPointOnSegment(escapePoint))
1357                     {
1358                         return true;
1359                     }
1360                 }
1361                 return false;
1362             }
1363
1364             // Gets the cover on the given side (closest cover to the given side) for the point out of all stored segments
1365             public ConnectorSegment GetCover(Point p, DesignerEdges side)
1366             {
1367                 ConnectorSegment cover = null;
1368                 int distance = 0;
1369
1370                 if (side == DesignerEdges.Left || side == DesignerEdges.Right)
1371                 {
1372                     for (int i = 0; i < this.verticalCovers.Count; i++)
1373                     {
1374                         ConnectorSegment segment = this.verticalCovers[i];
1375                         int currentDistance = (int)((side == DesignerEdges.Left) ? p.X - segment.A.X : segment.A.X - p.X);
1376                         if (currentDistance > 0 && segment.Covers(p))
1377                         {
1378                             if (cover == null || distance > currentDistance)
1379                             {
1380                                 cover = segment;
1381                                 distance = currentDistance;
1382                             }
1383                         }
1384                     }
1385                 }
1386                 else
1387                 {
1388                     for (int i = 0; i < this.horizontalCovers.Count; i++)
1389                     {
1390                         ConnectorSegment segment = this.horizontalCovers[i];
1391                         int currentDistance = (int)((side == DesignerEdges.Bottom) ? p.Y - segment.A.Y : segment.A.Y - p.Y);
1392                         if (currentDistance > 0 && segment.Covers(p))
1393                         {
1394                             if (cover == null || distance > currentDistance)
1395                             {
1396                                 cover = segment;
1397                                 distance = currentDistance;
1398                             }
1399                         }
1400                     }
1401                 }
1402
1403                 return cover;
1404             }
1405
1406             public List<ConnectorSegment> GetCovers(Point p, DesignerEdges side)
1407             {
1408                 List<ConnectorSegment> covers = new List<ConnectorSegment>();
1409
1410                 if (side == DesignerEdges.Left || side == DesignerEdges.Right)
1411                 {
1412                     for (int i = 0; i < this.verticalCovers.Count; i++)
1413                     {
1414                         ConnectorSegment segment = this.verticalCovers[i];
1415                         int currentDistance = (int)((side == DesignerEdges.Left) ? p.X - segment.A.X : segment.A.X - p.X);
1416                         if (currentDistance > 0 && segment.Covers(p))
1417                         {
1418                             covers.Add(segment);
1419                         }
1420                     }
1421                 }
1422                 else
1423                 {
1424                     for (int i = 0; i < this.horizontalCovers.Count; i++)
1425                     {
1426                         ConnectorSegment segment = this.horizontalCovers[i];
1427                         int currentDistance = (int)((side == DesignerEdges.Bottom) ? p.Y - segment.A.Y : segment.A.Y - p.Y);
1428                         if (currentDistance > 0 && segment.Covers(p))
1429                         {
1430                             covers.Add(segment);
1431                         }
1432                     }
1433                 }
1434
1435                 return covers;
1436             }
1437
1438             public bool IsEscapePoint(Point origin, Point escape, DesignerEdges side)
1439             {
1440                 ConnectorSegment originalCover = this.GetCover(origin, side);
1441                 int originalDistance;
1442                 if (side == DesignerEdges.Left || side == DesignerEdges.Right)
1443                 {
1444                     originalDistance = (int)(originalCover.A.X - escape.X);
1445                 }
1446                 else
1447                 {
1448                     originalDistance = (int)(originalCover.A.Y - escape.Y);
1449                 }
1450
1451                 if (originalCover.Covers(escape))
1452                 {
1453                     return false;
1454                 }
1455
1456                 List<ConnectorSegment> newCovers = this.GetCovers(escape, side);
1457                 for (int i = 0; i < newCovers.Count; i++)
1458                 {
1459                     ConnectorSegment newCover = newCovers[i];
1460                     if (newCover == originalCover)
1461                     {
1462                         return false;
1463                     }
1464
1465                     int newDistance;
1466                     if (side == DesignerEdges.Left || side == DesignerEdges.Right)
1467                     {
1468                         newDistance = (int)Math.Abs(newCover.A.X - escape.X);
1469                     }
1470                     else
1471                     {
1472                         newDistance = (int)Math.Abs(newCover.A.Y - escape.Y);
1473                     }
1474
1475                     if (Math.Sign(newDistance) == Math.Sign(originalDistance) && Math.Abs(newDistance) < Math.Abs(originalDistance))
1476                     {
1477                         return false;
1478                     }
1479                 }
1480
1481                 return true;
1482             }
1483         }
1484
1485         sealed class DistanceSorter : IComparer<DistanceFromPoint>
1486         {
1487             DistanceSorter()
1488             {
1489             }
1490
1491             public static void Sort(ref List<DistanceFromPoint> distances)
1492             {
1493                 DistanceSorter sorter = new DistanceSorter();
1494                 distances.Sort(sorter);
1495             }
1496
1497             int IComparer<DistanceFromPoint>.Compare(DistanceFromPoint lhs, DistanceFromPoint rhs)
1498             {
1499                 if (lhs.Distance.IsEqualTo(rhs.Distance))
1500                 {
1501                     return 0;
1502                 }
1503                 else if (lhs.Distance > rhs.Distance)
1504                 {
1505                     return 1;
1506                 }
1507                 else
1508                 {
1509                     return -1;
1510                 }
1511             }
1512         }
1513
1514     }
1515 }