﻿ ConnectorRouter.cs
 File: System.Activities.Presentation\System\Activities\Presentation\FreeFormEditing\ConnectorRouter.cs Project: ndp\cdf\src\NetFx40\Tools\System.Activities.Presentation.csproj (System.Activities.Presentation)
 ```//------------------------------------------------------------ // Copyright (c) Microsoft Corporation. All rights reserved. //------------------------------------------------------------ namespace System.Activities.Presentation.FreeFormEditing { using System; using System.Collections.Generic; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Globalization; using System.Windows; using System.Windows.Controls; using System.Runtime; using System.Activities.Presentation.View; using System.Activities.Presentation.Internal.PropertyEditing; using System.Windows.Input; // // ConnectorRouter class implements the cannonical Hightower's algorithm. // See reference paper: Hightower, "A solution to line-routing problem on the continuous plane", DAC-69. // // Algorithm advantages: // 1. Very fast. // 2. Low memory requirement. // 2. Very flexible. // // Algorithm disadvantages: // 1. Do not guarantee to generate the shortest path. // 2. May fail to find a route even if it does exist. // internal static class ConnectorRouter { const int connectorMargin = 30; // Used for second refinement algorithm: prevent segment overlapping with the shape edge. const int lineMargin = 10; // Used for inner blockage of the source/destination shape. const double delta = 1; // The tolerance between the end point of the routed line and the source/destination ConnectionPoint. internal const double EndPointTolerance = 1; [Flags] enum DesignerEdges { None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8, All = 15 } //This is used for dragging source point of a connector.(In this case we know only the destination connection point). internal static Point[] Route(FreeFormPanel panel, Point srPoint, ConnectionPoint destConnPoint) { Fx.Assert(panel.IsOutmostPanel(), "panel should be the outmost FreeFormPanel"); UIElement destElement = destConnPoint.ParentDesigner; return Route(panel, srPoint, FreeFormPanel.GetLocationRelativeToOutmostPanel(destConnPoint), null, FreeFormPanel.GetEdgeRelativeToOutmostPanel(destConnPoint), null, destElement); } //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 destPoint) { Fx.Assert(panel.IsOutmostPanel(), "panel should be the outmost FreeFormPanel"); UIElement srcElement = srcConnPoint.ParentDesigner; return Route(panel, FreeFormPanel.GetLocationRelativeToOutmostPanel(srcConnPoint), destPoint, FreeFormPanel.GetEdgeRelativeToOutmostPanel(srcConnPoint), null, srcElement, null); } //This is used for link creation gesture to show the adorner. internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnectionPoint, MouseEventArgs e) { Fx.Assert(panel.IsOutmostPanel(), "panel should be the outmost FreeFormPanel"); Point[] points = null; // Used to keep consistency between preview and actual result. // Check if we are hiting a connection point if (typeof(ConnectionPointsAdorner).IsAssignableFrom(Mouse.DirectlyOver.GetType())) { ConnectionPointsAdorner destConnPtsAdorner = Mouse.DirectlyOver as ConnectionPointsAdorner; ConnectionPoint destConnPoint = FreeFormPanel.ConnectionPointHitTest(e.GetPosition(panel), destConnPtsAdorner); if (destConnPoint != null && !destConnPoint.Equals(srcConnectionPoint)) { return Route(panel, FreeFormPanel.GetLocationRelativeToOutmostPanel(srcConnectionPoint), FreeFormPanel.GetLocationRelativeToOutmostPanel(destConnPoint), FreeFormPanel.GetEdgeRelativeToOutmostPanel(srcConnectionPoint), FreeFormPanel.GetEdgeRelativeToOutmostPanel(destConnPoint), srcConnectionPoint.ParentDesigner, destConnPtsAdorner.AdornedElement); } else { return null; } } else { points = ConnectorRouter.Route(panel, srcConnectionPoint, e.GetPosition(panel)); } return points; } //This is used when we know both the source and destination connection points. internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint, ConnectionPoint destConnPoint) { Fx.Assert(panel.IsOutmostPanel(), "panel should be the outmost FreeFormPanel"); UIElement srcElement = srcConnPoint.ParentDesigner; UIElement destElement = destConnPoint.ParentDesigner; return Route(panel, FreeFormPanel.GetLocationRelativeToOutmostPanel(srcConnPoint), FreeFormPanel.GetLocationRelativeToOutmostPanel(destConnPoint), FreeFormPanel.GetEdgeRelativeToOutmostPanel(srcConnPoint), FreeFormPanel.GetEdgeRelativeToOutmostPanel(destConnPoint), srcElement, destElement); } internal static Point GetDirection(Point from, Point to) { Vector vec = to - from; return new Point( vec.X.IsEqualTo(0) ? 0 : Math.Sign(vec.X), vec.Y.IsEqualTo(0) ? 0 : Math.Sign(vec.Y) ); } static ConnectorSegment SrcEdge; static ConnectorSegment DestEdge; static void AddExcludedAndSrcDestRects(FreeFormPanel outmostPanel, FreeFormPanel panel, Point srcPoint, Point destPoint, UIElement srcElement, UIElement destElement, List excludedRects, List srcDestRects) { foreach (UIElement child in panel.Children) { if (!(child is Connector)) { Thickness margin = new Thickness(0); 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); Rect rect = new Rect(Point.Add(panel.TranslatePoint(FreeFormPanel.GetLocation(child), outmostPanel), new Vector(margin.Left, margin.Top)), childSize); // We don't want to add containing rectangles to the exclusion list, otherwise the algorithm will fail to find a path Rect shrunk = new Rect(rect.X + delta, rect.Y + delta, rect.Width - delta * 2, rect.Height - delta * 2); if (!shrunk.Contains(srcPoint) && !shrunk.Contains(destPoint)) { excludedRects.Add(rect); } if (srcElement == child) { srcDestRects.Add(rect); } else if (destElement == child) { srcDestRects.Add(rect); } UIElement element = VirtualizedContainerService.TryGetVirtualizedElement(child); if (element != null && typeof(INestedFreeFormPanelContainer).IsAssignableFrom(element.GetType())) { FreeFormPanel childPanel = ((INestedFreeFormPanelContainer)element).GetChildFreeFormPanel(); if (childPanel != null) { AddExcludedAndSrcDestRects(outmostPanel, childPanel, srcPoint, destPoint, srcElement, destElement, excludedRects, srcDestRects); } } } } } internal static Point[] Route(FreeFormPanel panel, Point srcPoint, Point destPoint, List srcEdge, List destEdge, UIElement srcElement, UIElement destElement) { if (panel == null) { throw FxTrace.Exception.AsError(new ArgumentNullException("panel")); } List excludedRects = new List(); List srcDestRects = new List(); List excludedLines = new List(); foreach (UIElement child in panel.Children) { if (child.GetType() == typeof(Connector)) { Connector connector = (Connector)child; for (int i = 0; i < connector.Points.Count - 1; i++) { excludedLines.Add(new Point(connector.Points[i].X, connector.Points[i].Y)); excludedLines.Add(new Point(connector.Points[i + 1].X, connector.Points[i + 1].Y)); } } } AddExcludedAndSrcDestRects(panel, panel, srcPoint, destPoint, srcElement, destElement, excludedRects, srcDestRects); return Route(srcPoint, destPoint, srcEdge, destEdge, excludedRects, excludedLines, srcDestRects); } internal static Point[] Route(Point srcPoint, Point destPoint, List srcEdge, List destEdge, List excludedRects, List excludedLines, List srcDestRects) { 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]); } Rect[] srcDestRectsCopy = srcDestRects.ToArray(); foreach (Rect rect in srcDestRectsCopy) { // Add shrunk rectangle to avoid connector passing through the inner area of the src/dest rectangle Rect shrunk = new Rect(rect.X + delta, rect.Y + delta, rect.Width - delta * 2, rect.Height - delta * 2); srcDestRects.Add(shrunk); excludedRects.Add(shrunk); } return TryRoute(srcPoint, destPoint, excludedRects, excludedLines, srcDestRects); } static Point[] TryRoute(Point srcPoint, Point destPoint, List excludedRects, List excludedLines, List srcDestRects) { Point[] segments = GetRoutedLineSegments(srcPoint, destPoint, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), excludedLines.ToArray()); // If we failed to find a routed path, ignore all the lines and try again. if (!AreSegmentsValid(segments)) { segments = GetRoutedLineSegments(srcPoint, destPoint, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), new Point[] { }); } // If we failed to find a routed path, ignore all other shapes except the source and destination shape. if (!AreSegmentsValid(segments)) { segments = GetRoutedLineSegments(srcPoint, destPoint, new Size(connectorMargin, connectorMargin), srcDestRects.ToArray(), new Point[] { }); } // If we still don't find a routed path, return the direct path. if (!AreSegmentsValid(segments)) { double slope = DesignerGeometryHelper.SlopeOfLineSegment(srcPoint, destPoint); Point intermediatePoint = (slope < 1) ? new Point(destPoint.X, srcPoint.Y) : new Point(srcPoint.X, destPoint.Y); segments = new Point[] { srcPoint, intermediatePoint, destPoint }; } segments = RemoveRedundantPoints(new List(segments)); return segments; } //In a list of points specifying a connector, remove consecutive equivalent points. internal static Point[] RemoveRedundantPoints(List points) { for (int i = points.Count - 1; i > 0; i--) { if (points[i].IsEqualTo(points[i - 1])) { points.RemoveAt(i); } } List toRemove = new List(); int index1 = 0; int index2 = 1; int index3 = 2; while (index3 < points.Count) { if (points[index1].X.IsEqualTo(points[index3].X) || points[index1].Y.IsEqualTo(points[index3].Y)) { toRemove.Add(index2); } else { index1 = index2; } ++index2; ++index3; } for (int i = points.Count - 1; i > 0; i--) { if (toRemove.Contains(i)) { points.RemoveAt(i); } } return points.ToArray(); } static void AddBoundPoint(ref List 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)); } } internal static bool AreSegmentsValid(Point[] segments) { if (segments == null || segments.Length < 2) { return false; } for (int i = 1; i < segments.Length; i++) { if (!segments[i - 1].X.IsEqualTo(segments[i].X) && !segments[i - 1].Y.IsEqualTo(segments[i].Y)) { return false; } } return true; } [SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity", Justification = "This is a legacy algorithm.")] static Nullable EscapeAlgorithm(CoverSet coverSet, Point Z, ref List escapePointsA, ref List horizontalSegmentsA, ref List verticalSegmentsA, ref List horizontalSegmentsB, ref List verticalSegmentsB, ref Orientation orientationA, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB, Size margin, ref bool noEscapeA) { Nullable 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); 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.Overlaps(ConnectorRouter.SrcEdge) || h.Overlaps(ConnectorRouter.DestEdge)) { h = null; } else { horizontalSegmentsA.Add(h); } ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, Z); if (v.Overlaps(ConnectorRouter.SrcEdge) || v.Overlaps(ConnectorRouter.DestEdge)) { v = null; } else { verticalSegmentsA.Add(v); } // Check if the new escape line(s) intersect with the existing ones if (h != null) { for (int i = 0; i < verticalSegmentsB.Count; i++) { ConnectorSegment segment = verticalSegmentsB[i]; intersection = h.Intersect(segment); if (intersection != null) { intersectionSegmentA = h; intersectionSegmentB = segment; return intersection; } } } if (v != null) { for (int i = 0; i < horizontalSegmentsB.Count; i++) { ConnectorSegment segment = horizontalSegmentsB[i]; intersection = v.Intersect(segment); if (intersection != null) { intersectionSegmentA = v; intersectionSegmentB = segment; return intersection; } } } Nullable escapePoint = null; if (v != null) { escapePoint = EscapeProcessI(coverSet, Z, v, Orientation.Horizontal, margin); if (escapePoint != null) { orientationA = Orientation.Vertical; escapePointsA.Add((Point)escapePoint); return null; } } if (h != null) { escapePoint = EscapeProcessI(coverSet, Z, h, Orientation.Vertical, margin); if (escapePoint != null) { orientationA = Orientation.Horizontal; escapePointsA.Add((Point)escapePoint); return null; } } bool intersectionFlag = false; // Flags indicating if we can still continue in the given directions bool continue1, continue2, continue3, continue4; 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 escape = EscapeProcessII(coverSet, Orientation.Vertical, ref escapePointsA, ref horizontalSegmentsA, ref verticalSegmentsA, ref horizontalSegmentsB, ref verticalSegmentsB, r1, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB); if (escape != null) { verticalSegmentsA.Add(v); if (intersectionFlag) { return escape; } orientationA = Orientation.Horizontal; coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r1)); coverSet.AddUsedEscapeLine(new ConnectorSegment(r1, (Point)escape)); escapePointsA.Add((Point)escape); return null; } } } if (rightCover != null && h != null) { r2.X -= margin.Width; if (r2.X > Z.X) { continue2 = true; Nullable escape = EscapeProcessII(coverSet, Orientation.Horizontal, ref escapePointsA, ref horizontalSegmentsA, ref verticalSegmentsA, ref horizontalSegmentsB, ref verticalSegmentsB, r2, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB); if (escape != null) { horizontalSegmentsA.Add(h); if (intersectionFlag) { return escape; } orientationA = Orientation.Vertical; coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r2)); coverSet.AddUsedEscapeLine(new ConnectorSegment(r2, (Point)escape)); escapePointsA.Add((Point)escape); return null; } } } if (bottomCover != null && v != null) { r3.Y += margin.Height; if (r3.Y < Z.Y) { continue3 = true; Nullable escape = EscapeProcessII(coverSet, Orientation.Vertical, ref escapePointsA, ref horizontalSegmentsA, ref verticalSegmentsA, ref horizontalSegmentsB, ref verticalSegmentsB, r3, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB); if (escape != null) { verticalSegmentsA.Add(v); if (intersectionFlag) { return escape; } orientationA = Orientation.Horizontal; coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r3)); coverSet.AddUsedEscapeLine(new ConnectorSegment(r3, (Point)escape)); escapePointsA.Add((Point)escape); return null; } } } if (leftCover != null && h != null) { r4.X += margin.Width; if (r4.X < Z.X) { continue4 = true; Nullable escape = EscapeProcessII(coverSet, Orientation.Horizontal, ref escapePointsA, ref horizontalSegmentsA, ref verticalSegmentsA, ref horizontalSegmentsB, ref verticalSegmentsB, r4, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB); if (escape != null) { horizontalSegmentsA.Add(h); if (intersectionFlag) { return escape; } orientationA = Orientation.Vertical; coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r4)); coverSet.AddUsedEscapeLine(new ConnectorSegment(r4, (Point)escape)); escapePointsA.Add((Point)escape); return null; } } } } while (continue1 || continue2 || continue3 || continue4); noEscapeA = true; return null; } static Nullable EscapeProcessI(CoverSet coverSet, Point Z, ConnectorSegment escapeLine, Orientation orientation, Size margin) { List extremitiesList = new List(4); 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 = GetDirection(Z, p); if (((orientation == Orientation.Vertical) ? direction.X : direction.Y).IsEqualTo(0)) { ConnectorSegment segment = extremitiesList[i].ConnectorSegment; p = segment.ExtendPointOutwards(p); direction = GetDirection(Z, p); p = extremitiesList[i].P; } DesignerEdges side; if (orientation == Orientation.Vertical) { side = (direction.Y < 0) ? DesignerEdges.Bottom : DesignerEdges.Top; } else { 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); } ConnectorSegment newEscapeLine = new ConnectorSegment(Z, escapePoint); if (!coverSet.EscapeLineHasBeenUsed(escapePoint) && escapeLine.IsPointOnSegment(escapePoint) && !escapeLine.A.IsEqualTo(escapePoint) && !escapeLine.B.IsEqualTo(escapePoint) && coverSet.IsEscapePoint(Z, escapePoint, side)) { coverSet.AddUsedEscapeLine(newEscapeLine); return escapePoint; } } return null; } static Nullable EscapeProcessII(CoverSet coverSet, Orientation orientation, ref List escapePointsA, ref List horizontalSegmentsA, ref List verticalSegmentsA, ref List horizontalSegmentsB, ref List verticalSegmentsB, Point R, Size margin, out bool intersectionFlag, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB) { intersectionFlag = false; intersectionSegmentA = null; intersectionSegmentB = null; ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, R); ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, R); for (int i = 0; i < verticalSegmentsB.Count; i++) { ConnectorSegment segment = verticalSegmentsB[i]; Nullable intersection = h.Intersect(segment); if (intersection != null) { intersectionFlag = true; intersectionSegmentA = h; intersectionSegmentB = segment; escapePointsA.Add(R); return intersection; } } for (int i = 0; i < horizontalSegmentsB.Count; i++) { ConnectorSegment segment = horizontalSegmentsB[i]; Nullable intersection = v.Intersect(segment); if (intersection != null) { intersectionFlag = true; intersectionSegmentA = v; intersectionSegmentB = segment; escapePointsA.Add(R); return intersection; } } Nullable escapePointI = null; if (orientation == Orientation.Horizontal) { escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin); if (escapePointI != null) { verticalSegmentsA.Add(v); escapePointsA.Add(R); return escapePointI; } escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin); if (escapePointI != null) { horizontalSegmentsA.Add(h); escapePointsA.Add(R); return escapePointI; } } else { escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin); if (escapePointI != null) { horizontalSegmentsA.Add(h); escapePointsA.Add(R); return escapePointI; } escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin); if (escapePointI != null) { verticalSegmentsA.Add(v); escapePointsA.Add(R); return escapePointI; } } return null; } static List FirstRefinementAlgorithm(List points, ConnectorSegment intersectionSegment) { List refinedSet = new List(); ConnectorSegment k = intersectionSegment; while (points.Count > 0) { Point point; int i = points.Count - 1; while (!k.PointLiesOnThisLine(points[i]) && i > 0) { i--; } while (i > 0 && k.PointLiesOnThisLine(points[i - 1])) { i--; } point = points[i]; refinedSet.Add(point); while (points.Count > i) { points.RemoveAt(i); } k = k.PerpendicularThroughPoint(point); } 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 escapePointsA = new List(); //escape points from begin to end List escapePointsB = new List(); //escape points from end to begin //horizontal/vertical escape segments from A List horizontalEscapeSegmentsA = new List(); List verticalEscapeSegmentsA = new List(); //horizontal/vertical escape segments from B List horizontalEscapeSegmentsB = new List(); List verticalEscapeSegmentsB = new List(); Orientation orientationA = Orientation.Horizontal; Orientation orientationB = Orientation.Horizontal; escapePointsA.Add(begin); escapePointsB.Add(end); bool noEscapeA = false; bool noEscapeB = false; Nullable intersection = null; ConnectorSegment intersectionSegmentA = null; ConnectorSegment intersectionSegmentB = null; try { do { if (noEscapeA) { if (noEscapeB) { break; } else { List tempList = escapePointsA; escapePointsA = escapePointsB; escapePointsB = tempList; Point tempPoint = A; A = B; B = tempPoint; bool tempBool = noEscapeA; noEscapeA = noEscapeB; noEscapeB = tempBool; Orientation tempOrientation = orientationA; orientationA = orientationB; orientationB = tempOrientation; List tempListSegm = horizontalEscapeSegmentsA; horizontalEscapeSegmentsA = horizontalEscapeSegmentsB; horizontalEscapeSegmentsB = tempListSegm; tempListSegm = verticalEscapeSegmentsA; verticalEscapeSegmentsA = verticalEscapeSegmentsB; verticalEscapeSegmentsB = tempListSegm; continue; } } Point objectPoint = escapePointsA[escapePointsA.Count - 1]; intersection = EscapeAlgorithm(coverSet, objectPoint, ref escapePointsA, ref horizontalEscapeSegmentsA, ref verticalEscapeSegmentsA, ref horizontalEscapeSegmentsB, ref verticalEscapeSegmentsB, ref orientationA, out intersectionSegmentA, out intersectionSegmentB, margin, ref noEscapeA); if (intersection != null) { break; } else { List tempList = escapePointsA; escapePointsA = escapePointsB; escapePointsB = tempList; Point tempPoint = A; A = B; B = tempPoint; bool tempBool = noEscapeA; noEscapeA = noEscapeB; noEscapeB = tempBool; Orientation tempOrientation = orientationA; orientationA = orientationB; orientationB = tempOrientation; List tempListSegm = horizontalEscapeSegmentsA; horizontalEscapeSegmentsA = horizontalEscapeSegmentsB; horizontalEscapeSegmentsB = tempListSegm; tempListSegm = verticalEscapeSegmentsA; verticalEscapeSegmentsA = verticalEscapeSegmentsB; verticalEscapeSegmentsB = tempListSegm; } } while (true); if (intersection == null) { return null; } List refinedPath = new List(); escapePointsA = FirstRefinementAlgorithm(escapePointsA, intersectionSegmentA); escapePointsB = FirstRefinementAlgorithm(escapePointsB, intersectionSegmentB); for (int j = escapePointsA.Count - 1; j >= 0; j--) { refinedPath.Add(escapePointsA[j]); } refinedPath.Add((Point)intersection); for (int j = 0; j < escapePointsB.Count; j++) { refinedPath.Add(escapePointsB[j]); } SecondRefinementAlgorithm(coverSet, ref refinedPath, margin); if (refinedPath.Count > 1 && refinedPath[refinedPath.Count - 1].IsEqualTo(begin)) { refinedPath.Reverse(); } return refinedPath.ToArray(); } catch (Exception) { return null; } } static void EraseRedundentWarps(CoverSet coverSet, ref List refinedPath) { bool structureChanged; do { structureChanged = false; List newPath = new List(); int currentSegment = 0; while (currentSegment < refinedPath.Count - 1) { Point a1 = refinedPath[currentSegment]; Point a2 = refinedPath[currentSegment + 1]; ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2); 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 intersection = a.Intersect(b); if (intersection != null) { structureChanged = true; newPath.Clear(); 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 temp = refinedPath; refinedPath = newPath; newPath = temp; newPath.Clear(); intersectingSegment = currentSegment + 2; } else { intersectingSegment++; } } currentSegment++; } } while (structureChanged); } static void SecondRefinementAlgorithm(CoverSet coverSet, ref List refinedPath, Size margin) { EraseRedundentWarps(coverSet, ref refinedPath); List newPath = new List(); int currentSegment = 0; while (currentSegment < refinedPath.Count - 1) { Point a1 = refinedPath[currentSegment]; Point a2 = refinedPath[currentSegment + 1]; bool intersected = false; ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2); if (a != null) { Vector sub = a2 - a1; int steps = (int)Math.Max(Math.Abs(sub.X / margin.Width), Math.Abs(sub.Y / margin.Height)); //one of the values will be null Point direction = GetDirection(a1, a2); // Prevent segments overlapping with shape edges. ExtendCoversOutwards(coverSet, a.Orientation, lineMargin); 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.IsEqualTo(a2)) { break; } ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, k, (a.Orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal); 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 intersection = b.Intersect(c); if (intersection != null && c.IsPointOnSegment((Point)intersection)) { intersected = true; newPath.Clear(); 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 temp = refinedPath; refinedPath = newPath; newPath = temp; newPath.Clear(); break; } intersectingSegment++; } if (intersected) { break; } } // Restore shape edges. ShrinkCoversInwards(coverSet, a.Orientation, lineMargin); } if (!intersected) { currentSegment++; } } } static List GetSegmentsForOrientation(CoverSet coverSet, Orientation orientation) { List connectorSegments = null; if (orientation == Orientation.Horizontal) { connectorSegments = coverSet.HorizontalCovers; } else { connectorSegments = coverSet.VerticalCovers; } return connectorSegments; } static void ShrinkCoversInwards(CoverSet coverSet, Orientation orientation, double shrunkLength) { List connectorSegments = GetSegmentsForOrientation(coverSet, orientation); foreach (ConnectorSegment connSeg in connectorSegments) { connSeg.ShrinkSegmentInwards(shrunkLength); } } static void ExtendCoversOutwards(CoverSet coverSet, Orientation orientation, double extendedLength) { List connectorSegments = GetSegmentsForOrientation(coverSet, orientation); foreach (ConnectorSegment connSeg in connectorSegments) { connSeg.ExtendSegmentOutwards(extendedLength); } } 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 = DesignerGeometryHelper.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.IsEqualTo(point2.X) && !point1.Y.IsEqualTo(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.IsEqualTo(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; } } public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Point b) { if (!a.X.IsEqualTo(b.X) && !a.Y.IsEqualTo(b.Y)) { return null; } return ConstructBoundSegment(coverSet, a, a.X.IsEqualTo(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 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; } public bool Covers(Point p) { return (this.orientation == Orientation.Horizontal) ? (p.X.IsNoLessThan(Math.Min(this.point1.X, this.point2.X)) && p.X.IsNoGreaterThan(Math.Max(this.point1.X, this.point2.X))) : (p.Y.IsNoLessThan(Math.Min(this.point1.Y, this.point2.Y)) && p.Y.IsNoGreaterThan(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.IsEqualTo(segment.A) && this.point2.IsEqualTo(segment.B) && Orientation == segment.Orientation); } public bool Overlaps(ConnectorSegment segment) { if (segment == null) { return false; } if (this.Orientation == segment.Orientation) { return this.IsPointOnSegment(segment.point1) || this.IsPointOnSegment(segment.point2) || segment.IsPointOnSegment(this.point1) || segment.IsPointOnSegment(this.point2); } return false; } public Point ExtendPointOutwards(Point p) { if (!p.IsEqualTo(this.point1) && !p.IsEqualTo(this.point2)) { return p; } double k = ((this.orientation == Orientation.Horizontal) ? p.X : p.Y); double k1 = ((this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y); double k2 = ((this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y); k += k.IsEqualTo(Math.Min(k1, k2)) ? -1.0 : 1.0; return new Point((this.orientation == Orientation.Horizontal) ? k : p.X, (this.orientation == Orientation.Horizontal) ? p.Y : k); } public void ExtendSegmentOutwards(double extendedLength) { if (this.Orientation == Orientation.Horizontal) { if (this.point1.X > this.point2.X) { this.point1 = Point.Add(this.point1, new Vector(extendedLength, 0)); this.point2 = Point.Add(this.point2, new Vector(-extendedLength, 0)); } else { this.point1 = Point.Add(this.point1, new Vector(-extendedLength, 0)); this.point2 = Point.Add(this.point2, new Vector(extendedLength, 0)); } } else { if (this.point1.Y > this.point2.Y) { this.point1 = Point.Add(this.point1, new Vector(0, extendedLength)); this.point2 = Point.Add(this.point2, new Vector(0, -extendedLength)); } else { this.point1 = Point.Add(this.point1, new Vector(0, -extendedLength)); this.point2 = Point.Add(this.point2, new Vector(0, extendedLength)); } } } public void ShrinkSegmentInwards(double shrunkLength) { this.ExtendSegmentOutwards(-shrunkLength); } public override int GetHashCode() { return this.point1.GetHashCode() ^ this.point2.GetHashCode() ^ Orientation.GetHashCode(); } public Nullable 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); } public bool IsPointOnSegment(Point p) { if ((this.orientation == Orientation.Horizontal && !p.Y.IsEqualTo(this.point1.Y)) || (this.orientation == Orientation.Vertical && !p.X.IsEqualTo(this.point1.X))) { return false; } double k = (this.orientation == Orientation.Horizontal) ? p.X : p.Y; double k1 = (this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y; double k2 = (this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y; return k.IsNoLessThan(Math.Min(k1, k2)) && k.IsNoGreaterThan(Math.Max(k1, k2)); } public ConnectorSegment PerpendicularThroughPoint(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.IsEqualTo(this.point1.Y) : p.X.IsEqualTo(this.point1.X); } } sealed class CoverSet { List horizontalCovers = new List(); List usedEscapeLine = new List(); List verticalCovers = new List(); public List HorizontalCovers { get { return this.horizontalCovers; } } public List VerticalCovers { get { return this.verticalCovers; } } 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))); } 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 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)) { covers.RemoveAt(i); break; } else if (existingCover.IsPointOnSegment(cover.A) && existingCover.IsPointOnSegment(cover.B)) { return; } } covers.Add(cover); } public void AddUsedEscapeLine(ConnectorSegment segment) { this.usedEscapeLine.Add(segment); } public void ClearUsedLines() { this.usedEscapeLine.Clear(); } 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; } // Gets 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; } public List GetCovers(Point p, DesignerEdges side) { List covers = new List(); 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) { 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); } if (originalCover.Covers(escape)) { return false; } List newCovers = this.GetCovers(escape, side); for (int i = 0; i < newCovers.Count; i++) { ConnectorSegment newCover = newCovers[i]; 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 { DistanceSorter() { } public static void Sort(ref List distances) { DistanceSorter sorter = new DistanceSorter(); distances.Sort(sorter); } int IComparer.Compare(DistanceFromPoint lhs, DistanceFromPoint rhs) { if (lhs.Distance.IsEqualTo(rhs.Distance)) { return 0; } else if (lhs.Distance > rhs.Distance) { return 1; } else { return -1; } } } } } ```