Code:
/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / cdf / src / NetFx40 / Tools / System.Activities.Core.Presentation / System / Activities / Core / Presentation / ConnectorRouter.cs / 1305376 / ConnectorRouter.cs
//------------------------------------------------------------ // Copyright (c) Microsoft Corporation. All rights reserved. //----------------------------------------------------------- namespace System.Activities.Core.Presentation { using System.Collections.Generic; using System.Windows; using System.Windows.Controls; using System.Windows.Shapes; using System.Globalization; using System.Diagnostics.CodeAnalysis; internal static class ConnectorRouter { const int connectorMargin = 30; [Flags] enum DesignerEdges { None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8, All = 15 } //This is used for link creation gesture to show the adorner.(In this case we know only the source connection point). internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint, Point end) { return Route(panel, srcConnPoint.Location, end, srcConnPoint.Edge, null); } //This is used when we know both the source and destination connection points. internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint , ConnectionPoint destConnPoint) { return Route(panel, srcConnPoint.Location, destConnPoint.Location, srcConnPoint.Edge, destConnPoint.Edge); } //This is used when we move the end connection point. internal static Point[] Route(FreeFormPanel panel, Point begin, Point end) { return Route(panel, begin, end, null, null); } internal static bool AreAllSegmentsVerticalOrHorizontal(Point[] segments) { if (segments == null || segments.Length == 0) { return false; } for (int i = 1; i < segments.Length; i++) { if (segments[i - 1].X != segments[i].X && segments[i - 1].Y != segments[i].Y) { return false; } } return true; } static ConnectorSegment SrcEdge; static ConnectorSegment DestEdge; //This method is the wrapper over the routing logic taken from Workflow V1. static Point[] Route(FreeFormPanel panel, Point begin, Point end, ListsrcEdge, List destEdge) { Point[] segments; if (panel == null) { throw FxTrace.Exception.AsError(new ArgumentNullException("panel")); } List < Rect > excludedRects = new List < Rect >(); List < Point > excludedLines = new List < Point >(); foreach (UIElement child in panel.Children) { if (child.GetType() == typeof(Connector)) { for (int i = 0; i < (((Connector)child).Points.Count) - 1; i++) { excludedLines.Add(new Point(((Connector)child).Points[i].X, ((Connector)child).Points[i].Y)); excludedLines.Add(new Point(((Connector)child).Points[i + 1].X, ((Connector)child).Points[i + 1].Y)); } } else { //Since the connectors will touch the UIElement, they will pass through the margin around the UIElement. //Hence excluding the margin in excludedRects. Thickness margin = new Thickness(0); Point origin = FreeFormPanel.GetLocation(child); FrameworkElement frameworkChild = child as FrameworkElement; if (frameworkChild != null) { margin = frameworkChild.Margin; } Size childSize = new Size(frameworkChild.DesiredSize.Width - margin.Left - margin.Right, frameworkChild.DesiredSize.Height - margin.Top - margin.Bottom); excludedRects.Add(new Rect(Point.Add(FreeFormPanel.GetLocation(child), new Vector(margin.Left, margin.Top)), childSize)); } } ConnectorRouter.SrcEdge = null; ConnectorRouter.DestEdge = null; if (srcEdge != null) { //ConnectorSegment should only be a segment from left to right or top to bottom. int smallerIndex = (srcEdge[0].X < srcEdge[1].X || srcEdge[0].Y < srcEdge[1].Y) ? 0 : 1; ConnectorRouter.SrcEdge = new ConnectorSegment(srcEdge[smallerIndex], srcEdge[1 - smallerIndex]); } if (destEdge != null) { int smallerIndex = (destEdge[0].X < destEdge[1].X || destEdge[0].Y < destEdge[1].Y) ? 0 : 1; ConnectorRouter.DestEdge = new ConnectorSegment(destEdge[smallerIndex], destEdge[1 - smallerIndex]); } segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), excludedLines.ToArray()); //WE NEED TO INCLUDE THESE FALLBACKS DUE TO A if (!AreAllSegmentsVerticalOrHorizontal(segments)) { segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), new Point[] { }); //segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), new Rect[] { }, excludedLines.ToArray()); } //DIRECT PATH if (!AreAllSegmentsVerticalOrHorizontal(segments)) { double slope = DesignerGeometryHelper.SlopeOfLineSegment(begin, end); Point intermediatePoint = (slope < 1) ? new Point(end.X, begin.Y) : new Point(begin.X, end.Y); segments = new Point[] { begin, intermediatePoint, end }; } segments = RemoveRedundantPoints(new List (segments)); return segments; } //In a list of points specifying a connector, remove consecutive equal points. static Point[] RemoveRedundantPoints(List points) { for (int i = points.Count - 1; i > 0; i--) { if (points[i].Equals(points[i - 1])) { points.RemoveAt(i); } } return points.ToArray(); } static void AddBoundPoint(ref List < DistanceFromPoint > extremitiesList, Point p, ConnectorSegment segment, Point Z) { if (p.X != int.MinValue && p.X != int.MaxValue && p.Y != int.MinValue && p.Y != int.MaxValue) { extremitiesList.Add(new DistanceFromPoint(segment, Z, p)); } } //Escape Algorithm static Nullable < Point > EscapeAlgorithm(CoverSet coverSet, Point Z, ref List < Point > LeA, ref List < ConnectorSegment > LhA, ref List < ConnectorSegment > LvA, ref List < ConnectorSegment > LhB, ref List < ConnectorSegment > LvB, ref Orientation orientationA, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB, Size margin, ref bool noEscapeA) { Nullable < Point > intersection = null; intersectionSegmentA = null; intersectionSegmentB = null; ConnectorSegment leftCover = coverSet.GetCover(Z, DesignerEdges.Left); ConnectorSegment rightCover = coverSet.GetCover(Z, DesignerEdges.Right); ConnectorSegment bottomCover = coverSet.GetCover(Z, DesignerEdges.Bottom); ConnectorSegment topCover = coverSet.GetCover(Z, DesignerEdges.Top); //P1: construct escape line(s) - on the beginning of the algorithm it will create two lines ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, Z); //We do not want the routed line to coincide with the source or dest edge. //Hence the edge should never be an escape line. if (h.Equals(ConnectorRouter.SrcEdge) || h.Equals(ConnectorRouter.DestEdge)) { h = null; } else { LhA.Add(h); } ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, Z); if (v.Equals(ConnectorRouter.SrcEdge) || v.Equals(ConnectorRouter.DestEdge)) { v = null; } else { LvA.Add(v); } //P2 check if the new escape line(s) intersect with the existing ones if (h != null) { for (int i = 0; i < LvB.Count; i++) { ConnectorSegment segment = LvB[i]; intersection = h.Intersect(segment); if (intersection != null) { intersectionSegmentA = h; intersectionSegmentB = segment; return intersection; } } } if (v != null) { for (int i = 0; i < LhB.Count; i++) { ConnectorSegment segment = LhB[i]; intersection = v.Intersect(segment); if (intersection != null) { intersectionSegmentA = v; intersectionSegmentB = segment; return intersection; } } } //there was no intersection found above, continue on //P3 find an escape point //Call Escape Process I //Escape process I P1 Nullable escapePoint = null; if (v != null) { escapePoint = EscapeProcessI(coverSet, Z, v, Orientation.Horizontal, margin); if (escapePoint != null) { orientationA = Orientation.Vertical; LeA.Add((Point)escapePoint); return null; } } //Escape process I P2 if (h != null) { escapePoint = EscapeProcessI(coverSet, Z, h, Orientation.Vertical, margin); if (escapePoint != null) { orientationA = Orientation.Horizontal; LeA.Add((Point)escapePoint); return null; } } //Call Escape process II bool intersectionFlag = false; //flags indicating if we can still continue in the given directions bool continue1, continue2, continue3, continue4; //CHANGE THIS. Point r1 = new Point(), r2 = new Point(), r3 = new Point(), r4 = new Point(); if (topCover != null) { r1 = new Point(Z.X, topCover.A.Y); } if (rightCover != null) { r2 = new Point(rightCover.A.X, Z.Y); } if (bottomCover != null) { r3 = new Point(Z.X, bottomCover.A.Y); } if (leftCover != null) { r4 = new Point(leftCover.A.X, Z.Y); } do { continue1 = continue2 = continue3 = continue4 = false; if (topCover != null && v != null) { r1.Y -= margin.Height; if (r1.Y > Z.Y) { continue1 = true; Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Vertical, ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r1, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB); if (escape != null) { LvA.Add(v); if (intersectionFlag) { return escape; } orientationA = Orientation.Horizontal; coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r1)); coverSet.AddUsedEscapeLine(new ConnectorSegment(r1, (Point)escape)); LeA.Add((Point)escape); return null; } } } if (rightCover != null && h != null) { r2.X -= margin.Width; if (r2.X > Z.X) { continue2 = true; Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Horizontal, ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r2, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB); if (escape != null) { LhA.Add(h); if (intersectionFlag) { return escape; } orientationA = Orientation.Vertical; coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r2)); coverSet.AddUsedEscapeLine(new ConnectorSegment(r2, (Point)escape)); LeA.Add((Point)escape); return null; } } } if (bottomCover != null && v != null) { r3.Y += margin.Height; if (r3.Y < Z.Y) { continue3 = true; Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Vertical, ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r3, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB); if (escape != null) { LvA.Add(v); if (intersectionFlag) { return escape; } orientationA = Orientation.Horizontal; coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r3)); coverSet.AddUsedEscapeLine(new ConnectorSegment(r3, (Point)escape)); LeA.Add((Point)escape); return null; } } } if (leftCover != null && h!= null) { r4.X += margin.Width; if (r4.X < Z.X) { continue4 = true; Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Horizontal, ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r4, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB); if (escape != null) { LhA.Add(h); if (intersectionFlag) { return escape; } orientationA = Orientation.Vertical; coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r4)); coverSet.AddUsedEscapeLine(new ConnectorSegment(r4, (Point)escape)); LeA.Add((Point)escape); return null; } } } //continue the loop until there is a place to go in either of the directions } while (continue1 || continue2 || continue3 || continue4); noEscapeA = true; return null; } //Escape Process I static Nullable < Point > EscapeProcessI(CoverSet coverSet, Point Z, ConnectorSegment escapeLine, Orientation orientation, Size margin) { //perform extremity point permutation by the distance from the object point //when sorting points store to which segments they belong (this is needed further when //deciding to side of the point to move if the extremity coincide with the object point //on abscissa or ordinata axis) List < DistanceFromPoint > extremitiesList = new List < DistanceFromPoint >(4); //at most four points ConnectorSegment lesserCover = coverSet.GetCover(Z, (orientation == Orientation.Horizontal) ? DesignerEdges.Left : DesignerEdges.Bottom); if (lesserCover != null) { AddBoundPoint(ref extremitiesList, lesserCover.A, lesserCover, Z); AddBoundPoint(ref extremitiesList, lesserCover.B, lesserCover, Z); } ConnectorSegment higherCover = coverSet.GetCover(Z, (orientation == Orientation.Horizontal) ? DesignerEdges.Right : DesignerEdges.Top); if (higherCover != null) { AddBoundPoint(ref extremitiesList, higherCover.A, higherCover, Z); AddBoundPoint(ref extremitiesList, higherCover.B, higherCover, Z); } if (extremitiesList.Count == 0) { return null; } DistanceSorter.Sort(ref extremitiesList); for (int i = 0; i < extremitiesList.Count; i++) { Point p = extremitiesList[i].P; Point direction = new Point(Math.Sign(p.X - Z.X), Math.Sign(p.Y - Z.Y)); if (((orientation == Orientation.Vertical) ? direction.X : direction.Y) == 0) { //if extremity is on the same abscissa(ordinata) line with the object point, need to be more careful ConnectorSegment segment = extremitiesList[i].ConnectorSegment; p = segment.ExtendPointOutwards(p); direction = new Point(Math.Sign(p.X - Z.X), Math.Sign(p.Y - Z.Y)); p = extremitiesList[i].P; } DesignerEdges side; //which side is the cover we are trying to escape if (orientation == Orientation.Vertical) { //we are escaping either top or bottom side = (direction.Y < 0) ? DesignerEdges.Bottom : DesignerEdges.Top; } else { //we are escaping either left or right side = (direction.X < 0) ? DesignerEdges.Left : DesignerEdges.Right; } Point escapePoint; if ((orientation == Orientation.Vertical)) { escapePoint = new Point(p.X + direction.X * margin.Width, Z.Y); } else { escapePoint = new Point(Z.X, p.Y + direction.Y * margin.Height); } //the new escape point should //1) lay on the given escape line (except the bounding points since they belong to covers) //2) not lay on any of the already tested escape segments - all points belonging to them are already worthless ConnectorSegment newEscapeLine = new ConnectorSegment(Z, escapePoint); if (!coverSet.EscapeLineHasBeenUsed(escapePoint) && escapeLine.IsPointOnSegment(escapePoint) && escapeLine.A != escapePoint && escapeLine.B != escapePoint && coverSet.IsEscapePoint(Z, escapePoint, side)) { coverSet.AddUsedEscapeLine(newEscapeLine); return escapePoint; } } return null; } //Escape Process II static Nullable < Point > EscapeProcessII(CoverSet coverSet, Orientation orientation, ref List < Point > LeA, ref List < ConnectorSegment > LhA, ref List < ConnectorSegment > LvA, ref List < ConnectorSegment > LhB, ref List < ConnectorSegment > LvB, Point R, Size margin, out bool intersectionFlag, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB) { intersectionFlag = false; intersectionSegmentA = null; intersectionSegmentB = null; //rebuild invalidated covers ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, R); ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, R); //check intersections for (int i = 0; i < LvB.Count; i++) { ConnectorSegment segment = LvB[i]; Nullable < Point > itersection = h.Intersect(segment); if (itersection != null) { intersectionFlag = true; intersectionSegmentA = h; intersectionSegmentB = segment; LeA.Add(R); return itersection; } } for (int i = 0; i < LhB.Count; i++) { ConnectorSegment segment = LhB[i]; Nullable < Point > itersection = v.Intersect(segment); if (itersection != null) { intersectionFlag = true; intersectionSegmentA = v; intersectionSegmentB = segment; LeA.Add(R); return itersection; } } Nullable < Point > escapePointI = null; //now do both horizontal and vertical escape processes I from that point... //the order is important based on 'orientation' argument if (orientation == Orientation.Horizontal) { escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin); if (escapePointI != null) { LvA.Add(v); LeA.Add(R); return escapePointI; } escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin); if (escapePointI != null) { LhA.Add(h); LeA.Add(R); return escapePointI; } } else { escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin); if (escapePointI != null) { LhA.Add(h); LeA.Add(R); return escapePointI; } escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin); if (escapePointI != null) { LvA.Add(v); LeA.Add(R); return escapePointI; } } return null; } //remove all non-corner points static List < Point > FirstRefinementAlgorithm(List < Point > Le, ConnectorSegment intersectionSegment) { List < Point > refinedSet = new List < Point >(); ConnectorSegment k = intersectionSegment; while (Le.Count > 0) { Point pi; int i = Le.Count - 1; //find the first point that lies on k while (!k.PointLiesOnThisLine(Le[i]) && i > 0) { i--; } //find the least point that lies on k while (i > 0 && k.PointLiesOnThisLine(Le[i - 1])) { i--; } //save the point pi = Le[i]; refinedSet.Add(pi); //remove all the points up to the found one from the original list while (Le.Count > i) { Le.RemoveAt(i); } //continue with the points lying on the line perpendecular to the previous one and passing through the //found point k = k.PeprendecularThroughPoint(pi); } return refinedSet; } [SuppressMessage("Microsoft.Design", "CA1031:DoNotCatchGeneralExceptionTypes", Justification = "Catch all exceptions to prevent crash.")] [SuppressMessage("Reliability", "Reliability108:IsFatalRule", Justification = "Catch all exceptions to prevent crash.")] static Point[] GetRoutedLineSegments(Point begin, Point end, Size margin, Rect[] rectanglesToExclude, Point[] linesToExclude) { if (rectanglesToExclude == null) { throw FxTrace.Exception.AsError(new ArgumentNullException("rectanglesToExclude")); } if (linesToExclude == null) { throw FxTrace.Exception.AsError(new ArgumentNullException("linesToExclude")); } if ((linesToExclude.Length % 2) > 0) { throw FxTrace.Exception.AsError(new ArgumentException("Error")); } CoverSet coverSet = new CoverSet(rectanglesToExclude, linesToExclude); coverSet.ClearUsedLines(); Point A = begin; Point B = end; //escape points List < Point > LeA = new List < Point >(); //escape points from begin to end List < Point > LeB = new List < Point >(); //escape points from end to begin //horizontal/vertical escape segments from A List < ConnectorSegment > LhA = new List < ConnectorSegment >(); List < ConnectorSegment > LvA = new List < ConnectorSegment >(); //horizontal/vertical escape segments from B List < ConnectorSegment > LhB = new List < ConnectorSegment >(); List < ConnectorSegment > LvB = new List < ConnectorSegment >(); Orientation orientationA = Orientation.Horizontal; Orientation orientationB = Orientation.Horizontal; //P0 LeA.Add(begin); LeB.Add(end); bool noEscapeA = false; bool noEscapeB = false; Nullable < Point > intersection = null; ConnectorSegment intersectionSegmentA = null; ConnectorSegment intersectionSegmentB = null; try { do { //P1 if (noEscapeA) { if (noEscapeB) { //we failed to find the point break; } else { //P2 //swap A and B (with all appropriate lists and flags...) List < Point > tempList = LeA; LeA = LeB; LeB = tempList; Point tempPoint = A; A = B; B = tempPoint; bool tempBool = noEscapeA; noEscapeA = noEscapeB; noEscapeB = tempBool; Orientation tempOrientation = orientationA; orientationA = orientationB; orientationB = tempOrientation; List < ConnectorSegment > tempListSegm = LhA; LhA = LhB; LhB = tempListSegm; tempListSegm = LvA; LvA = LvB; LvB = tempListSegm; continue; } } Point objectPoint = LeA[LeA.Count - 1]; Point targetPoint = B; intersection = EscapeAlgorithm(coverSet, objectPoint, ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, ref orientationA, out intersectionSegmentA, out intersectionSegmentB, margin, ref noEscapeA); if (intersection != null) { break; } else { //swap A and B (with all appropriate lists and flags...) List < Point > tempList = LeA; LeA = LeB; LeB = tempList; Point tempPoint = A; A = B; B = tempPoint; bool tempBool = noEscapeA; noEscapeA = noEscapeB; noEscapeB = tempBool; Orientation tempOrientation = orientationA; orientationA = orientationB; orientationB = tempOrientation; List < ConnectorSegment > tempListSegm = LhA; LhA = LhB; LhB = tempListSegm; tempListSegm = LvA; LvA = LvB; LvB = tempListSegm; } } while (true); //we failed if (intersection == null) { return null; } List < Point > refinedPath = new List < Point >(); //P3 apply refinement algorithms //first refinement algorithm LeA = FirstRefinementAlgorithm(LeA, intersectionSegmentA); LeB = FirstRefinementAlgorithm(LeB, intersectionSegmentB); //before going into the second refinement, construct the full path for (int j = LeA.Count - 1; j >= 0; j--) { refinedPath.Add(LeA[j]); } refinedPath.Add((Point)intersection); for (int j = 0; j < LeB.Count; j++) { refinedPath.Add(LeB[j]); } //perform second refinement algorithm on the full path SecondRefinementAlgorithm(coverSet, ref refinedPath, margin); if (refinedPath.Count > 1 && refinedPath[refinedPath.Count - 1] == begin) { refinedPath.Reverse(); } return refinedPath.ToArray(); } catch (Exception) { //Debug.Assert(false, "Investigate if we ever get here. got an exception:\n" + ex.Message); return null; } } //remove superflous parts from the path static void SecondRefinementAlgorithm(CoverSet coverSet, ref List < Point > refinedPath, Size margin) { List < Point > newPath = new List < Point >(); //Part I: extend every segment in the path to see if it intersects any other segment int currentSegment = 0; while (currentSegment < refinedPath.Count - 1) { Point a1 = refinedPath[currentSegment]; Point a2 = refinedPath[currentSegment + 1]; //need to construct a segment through the points that is limited by the covers ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2); //try to intersect it with every segment after the current one //and the next one (which we know does intersect with the current one) int intersectingSegment = currentSegment + 2; while (intersectingSegment < refinedPath.Count - 1) { Point b1 = refinedPath[intersectingSegment]; Point b2 = refinedPath[intersectingSegment + 1]; ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, b1, b2); Nullable < Point > intersection = a.Intersect(b); if (intersection != null) { newPath.Clear(); //need to remove all points between a1 and b2 and insert the point of intersectin there for (int i = 0; i <= currentSegment; i++) { newPath.Add(refinedPath[i]); } newPath.Add((Point)intersection); for (int i = intersectingSegment + 1; i < refinedPath.Count; i++) { newPath.Add(refinedPath[i]); } List < Point > temp = refinedPath; refinedPath = newPath; newPath = temp; newPath.Clear(); //reset the second segment number and go through all segments once more //until there are no intersections left intersectingSegment = currentSegment + 2; } else { intersectingSegment++; } } //we need to keep looking for intersections until we reach the very last one currentSegment++; } //Part II: construct segments perpendecular to every segment and see if they intersect any other segment currentSegment = 0; while (currentSegment < refinedPath.Count - 1) { Point a1 = refinedPath[currentSegment]; Point a2 = refinedPath[currentSegment + 1]; //need to construct a segment through the points that is limited by the covers bool intersected = false; ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2); if (a != null) { Point direction = new Point(a2.X - a1.X, a2.Y - a1.Y); //see how many intemediate points we can construct int steps = (int)Math.Max(Math.Abs(direction.X / margin.Width), Math.Abs(direction.Y / margin.Height)); //one of the values will be null direction.X = (int)Math.Sign(direction.X); direction.Y = (int)Math.Sign(direction.Y); for (int i = 1; i <= steps; i++) { Point k = new Point(a1.X + i * margin.Width * direction.X, a1.Y + i * margin.Height * direction.Y); if (k == a2) { break; } ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, k, (a.Orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal); //now try to intersect that segment with every segment after the current one and the one after it int intersectingSegment = currentSegment + 2; while (intersectingSegment < refinedPath.Count - 1 && !intersected) { Point c1 = refinedPath[intersectingSegment]; Point c2 = refinedPath[intersectingSegment + 1]; ConnectorSegment c = new ConnectorSegment(c1, c2); Nullable < Point > intersection = b.Intersect(c); if (intersection != null && c.IsPointOnSegment((Point)intersection)) { intersected = true; newPath.Clear(); //need to remove all points between a1 and b2 and insert k and the point of intersection there for (int j = 0; j <= currentSegment; j++) { newPath.Add(refinedPath[j]); } newPath.Add(k); newPath.Add((Point)intersection); for (int j = intersectingSegment + 1; j < refinedPath.Count; j++) { newPath.Add(refinedPath[j]); } List < Point > temp = refinedPath; refinedPath = newPath; newPath = temp; newPath.Clear(); break; } intersectingSegment++; } //if there was an intersection, exit the for loop if (intersected) { break; } } } //if there was an intersection, run the same segment again to see if there are other intersecting segments if (!intersected) { currentSegment++; } } } //Struct DistanceFromPoint //sorting of extremities by closedness to point Z struct DistanceFromPoint { public ConnectorSegment ConnectorSegment; public double Distance; public Point P; public DistanceFromPoint(ConnectorSegment segment, Point z, Point p) { this.ConnectorSegment = segment; this.P = p; this.Distance = ConnectorSegment.DistanceBetweenPoints(z, p); } } // represents a segment - the main entity in the routing algorithm sealed class ConnectorSegment { Orientation orientation; Point point1; Point point2; public ConnectorSegment(Point point1, Point point2) { if (point1.X != point2.X && point1.Y != point2.Y) { throw FxTrace.Exception.AsError(new InvalidOperationException(string.Format(CultureInfo.InvariantCulture, SR.CannotConstructConnectionSegment, point1.ToString(), point2.ToString()))); } this.point1 = point1; this.point2 = point2; this.orientation = ((this.point1.X == this.point2.X) ? Orientation.Vertical : Orientation.Horizontal); } public Point A { get { return this.point1; } } public Point B { get { return this.point2; } } public Orientation Orientation { get { return this.orientation; } } //given two points construct a segment through them from lesser cover to higher public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Point b) { //Debug.Assert(!(a.X != b.X && a.Y != b.Y), "arbitrary segment, only horizontal or vertical ones are allowed!"); if (a.X != b.X && a.Y != b.Y) { return null; } return ConstructBoundSegment(coverSet, a, (a.X == b.X) ? Orientation.Vertical : Orientation.Horizontal); } public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Orientation orientation) { return (orientation == Orientation.Horizontal) ? SegmentFromLeftToRightCover(coverSet, a) : SegmentFromBottomToTopCover(coverSet, a); } public static double DistanceBetweenPoints(Point p, Point q) { return Math.Sqrt((double)(p.X - q.X) * (p.X - q.X) + (double)(p.Y - q.Y) * (p.Y - q.Y)); } public static ConnectorSegment SegmentFromBottomToTopCover(CoverSet coverSet, Point p) { ConnectorSegment bottomCover = coverSet.GetCover(p, DesignerEdges.Bottom); ConnectorSegment topCover = coverSet.GetCover(p, DesignerEdges.Top); //construct vertical escape segment Point bottom = new Point(p.X, (bottomCover != null) ? bottomCover.A.Y : int.MinValue); Point top = new Point(p.X, (topCover != null) ? topCover.A.Y : int.MaxValue); ConnectorSegment v = new ConnectorSegment(bottom, top); return v; } public static ConnectorSegment SegmentFromLeftToRightCover(CoverSet coverSet, Point p) { ConnectorSegment leftCover = coverSet.GetCover(p, DesignerEdges.Left); ConnectorSegment rightCover = coverSet.GetCover(p, DesignerEdges.Right); //construct horizontal escape segment Point left = new Point((leftCover != null) ? leftCover.A.X : int.MinValue, p.Y); Point right = new Point((rightCover != null) ? rightCover.A.X : int.MaxValue, p.Y); ConnectorSegment h = new ConnectorSegment(left, right); return h; } //"segment l covers a point p, if the perpendicular from p to the line of which l is a segment intersects l" //since a) we only have horizotal or vertical segments and b) some segments will be unbound, we have to store and use orientation //flag to do analyzis public bool Covers(Point p) { return (this.orientation == Orientation.Horizontal) ? (p.X >= Math.Min(this.point1.X, this.point2.X) && p.X <= Math.Max(this.point1.X, this.point2.X)) : (p.Y >= Math.Min(this.point1.Y, this.point2.Y) && p.Y <= Math.Max(this.point1.Y, this.point2.Y)); } public override bool Equals(object obj) { ConnectorSegment segment = obj as ConnectorSegment; if (segment == null) { return false; } return (this.point1 == segment.A && this.point2 == segment.B && Orientation == segment.Orientation); } public Point ExtendPointOutwards(Point p) { if (p != this.point1 && p != this.point2) { return p; } int k = (int)((this.orientation == Orientation.Horizontal) ? p.X : p.Y); int k1 = (int)((this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y); int k2 = (int)((this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y); if (k == Math.Min(k1, k2)) { k--; } else { k++; } return new Point((this.orientation == Orientation.Horizontal) ? k : p.X, (this.orientation == Orientation.Horizontal) ? p.Y : k); } public override int GetHashCode() { return this.point1.GetHashCode() ^ this.point2.GetHashCode() ^ Orientation.GetHashCode(); } //see if the two segments intersect //greatly simplified by the fact that we only have vertical or horizontal segments //should work fine with {Max, Min}Value values public Nullable < Point > Intersect(ConnectorSegment segment) { if (this.orientation == segment.Orientation) { return null; } ConnectorSegment vertical = (this.orientation == Orientation.Vertical) ? this : segment; ConnectorSegment horizontal = (this.orientation == Orientation.Vertical) ? segment : this; if (vertical.A.X < Math.Min(horizontal.A.X, horizontal.B.X) || vertical.A.X > Math.Max(horizontal.A.X, horizontal.B.X)) { return null; } if (horizontal.A.Y < Math.Min(vertical.A.Y, vertical.B.Y) || horizontal.A.Y > Math.Max(vertical.A.Y, vertical.B.Y)) { return null; } return new Point(vertical.A.X, horizontal.A.Y); } //we consider just the segment for this test public bool IsPointOnSegment(Point p) { if ((this.orientation == Orientation.Horizontal && p.Y != this.point1.Y) || (this.orientation == Orientation.Vertical && p.X != this.point1.X)) { return false; } int k = (int)((this.orientation == Orientation.Horizontal) ? p.X : p.Y); int k1 = (int)((this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y); int k2 = (int)((this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y); return k >= Math.Min(k1, k2) && k <= Math.Max(k1, k2); } public ConnectorSegment PeprendecularThroughPoint(Point p) { Orientation newOrientation = (this.orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal; Point newPoint = new Point(p.X, p.Y); if (newOrientation == Orientation.Horizontal) { newPoint.X = int.MaxValue; } else { newPoint.Y = int.MaxValue; } return new ConnectorSegment(p, newPoint); } //we consider the whole line to which this segment belongs for this test public bool PointLiesOnThisLine(Point p) { return (this.orientation == Orientation.Horizontal) ? p.Y == this.point1.Y : p.X == this.point1.X; } } //Class CoverSet (Set of vertical and horizontal covers) sealed class CoverSet { List < ConnectorSegment > horizontalCovers = new List < ConnectorSegment >(); List < ConnectorSegment > usedEscapeLine = new List < ConnectorSegment >(); List < ConnectorSegment > verticalCovers = new List < ConnectorSegment >(); public CoverSet(Rect[] rectanglesToExclude, Point[] linesToExclude) { foreach (Rect rectangle in rectanglesToExclude) { AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Top), new Point(rectangle.Left, rectangle.Bottom))); AddCover(new ConnectorSegment(new Point(rectangle.Right, rectangle.Top), new Point(rectangle.Right, rectangle.Bottom))); AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Top), new Point(rectangle.Right, rectangle.Top))); AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Bottom), new Point(rectangle.Right, rectangle.Bottom))); } //Add the linesegments to cover for (int i = 0; i < linesToExclude.Length / 2; i++) { AddCover(new ConnectorSegment(linesToExclude[i * 2], linesToExclude[(i * 2) + 1])); } } public void AddCover(ConnectorSegment cover) { List < ConnectorSegment > covers = (cover.Orientation == Orientation.Vertical) ? this.verticalCovers : this.horizontalCovers; for (int i = 0; i < covers.Count; i++) { ConnectorSegment existingCover = covers[i]; if (cover.IsPointOnSegment(existingCover.A) && cover.IsPointOnSegment(existingCover.B)) { //both points of vertical are on the new segment, delete the vertical and add the new one instead covers.RemoveAt(i); break; } else if (existingCover.IsPointOnSegment(cover.A) && existingCover.IsPointOnSegment(cover.B)) { //both points of the new segment are on an existing segment already - skip this one return; } } covers.Add(cover); } public void AddUsedEscapeLine(ConnectorSegment segment) { this.usedEscapeLine.Add(segment); } public void ClearUsedLines() { this.usedEscapeLine.Clear(); } //the new escape point should not lay on any of the already used escape segments public bool EscapeLineHasBeenUsed(Point escapePoint) { for (int i = 0; i < this.usedEscapeLine.Count; i++) { ConnectorSegment usedSegment = this.usedEscapeLine[i]; if (usedSegment.IsPointOnSegment(escapePoint)) { return true; } } return false; } //get the cover on the given side (closest cover to the given side) for the point out of all stored segments public ConnectorSegment GetCover(Point p, DesignerEdges side) { ConnectorSegment cover = null; int distance = 0; if (side == DesignerEdges.Left || side == DesignerEdges.Right) { for (int i = 0; i < this.verticalCovers.Count; i++) { ConnectorSegment segment = this.verticalCovers[i]; int currentDistance = (int)((side == DesignerEdges.Left) ? p.X - segment.A.X : segment.A.X - p.X); if (currentDistance > 0 && segment.Covers(p)) { if (cover == null || distance > currentDistance) { cover = segment; distance = currentDistance; } } } } else { for (int i = 0; i < this.horizontalCovers.Count; i++) { ConnectorSegment segment = this.horizontalCovers[i]; int currentDistance = (int)((side == DesignerEdges.Bottom) ? p.Y - segment.A.Y : segment.A.Y - p.Y); if (currentDistance > 0 && segment.Covers(p)) { if (cover == null || distance > currentDistance) { cover = segment; distance = currentDistance; } } } } return cover; } //get the cover on the given side (closest cover to the given side) for the point out of all stored segments public List < ConnectorSegment > GetCovers(Point p, DesignerEdges side) { List < ConnectorSegment > covers = new List < ConnectorSegment >(); if (side == DesignerEdges.Left || side == DesignerEdges.Right) { for (int i = 0; i < this.verticalCovers.Count; i++) { ConnectorSegment segment = this.verticalCovers[i]; int currentDistance = (int)((side == DesignerEdges.Left) ? p.X - segment.A.X : segment.A.X - p.X); if (currentDistance > 0 && segment.Covers(p)) { covers.Add(segment); } } } else { for (int i = 0; i < this.horizontalCovers.Count; i++) { ConnectorSegment segment = this.horizontalCovers[i]; int currentDistance = (int)((side == DesignerEdges.Bottom) ? p.Y - segment.A.Y : segment.A.Y - p.Y); if (currentDistance > 0 && segment.Covers(p)) { covers.Add(segment); } } } return covers; } public bool IsEscapePoint(Point origin, Point escape, DesignerEdges side) { //get the original cover ConnectorSegment originalCover = this.GetCover(origin, side); int originalDistance; if (side == DesignerEdges.Left || side == DesignerEdges.Right) { originalDistance = (int)(originalCover.A.X - escape.X); } else { originalDistance = (int)(originalCover.A.Y - escape.Y); } // the escape point should not be covered by the the original cover if (originalCover.Covers(escape)) { return false; } //it should not also be covered by any member of other segments between the original cover and the original point List < ConnectorSegment > newCovers = this.GetCovers(escape, side); for (int i = 0; i < newCovers.Count; i++) { ConnectorSegment newCover = newCovers[i]; //should never happen, just in case... if (newCover == originalCover) { return false; } int newDistance; if (side == DesignerEdges.Left || side == DesignerEdges.Right) { newDistance = (int)Math.Abs(newCover.A.X - escape.X); } else { newDistance = (int)Math.Abs(newCover.A.Y - escape.Y); } if (Math.Sign(newDistance) == Math.Sign(originalDistance) && Math.Abs(newDistance) < Math.Abs(originalDistance)) { return false; } } return true; } } sealed class DistanceSorter : IComparer < DistanceFromPoint > { DistanceSorter() { } public static void Sort(ref List < DistanceFromPoint > distances) { DistanceSorter sorter = new DistanceSorter(); distances.Sort(sorter); } int IComparer < DistanceFromPoint >.Compare(DistanceFromPoint lhs, DistanceFromPoint rhs) { if (lhs.Distance == rhs.Distance) { return 0; } else if (lhs.Distance > rhs.Distance) { return 1; } else { return -1; } } } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- RuntimeResourceSet.cs
- ProxyGenerator.cs
- SignatureDescription.cs
- SynchronizedInputProviderWrapper.cs
- MbpInfo.cs
- PrintPreviewGraphics.cs
- OleCmdHelper.cs
- CorrelationActionMessageFilter.cs
- XmlEventCache.cs
- VScrollProperties.cs
- StringSorter.cs
- tibetanshape.cs
- ColumnCollection.cs
- Soap12ServerProtocol.cs
- AccessViolationException.cs
- TableItemStyle.cs
- MetadataExchangeBindings.cs
- ModelFunction.cs
- MetadataLocation.cs
- TreeBuilder.cs
- ClientSideQueueItem.cs
- SubpageParagraph.cs
- ByeMessageCD1.cs
- SpeechSynthesizer.cs
- CmsUtils.cs
- SecurityHeaderLayout.cs
- MasterPageParser.cs
- DataTableCollection.cs
- GenerateScriptTypeAttribute.cs
- ProtocolsConfigurationEntry.cs
- PkcsMisc.cs
- DataStreams.cs
- ZipIORawDataFileBlock.cs
- TimeSpan.cs
- StoreItemCollection.cs
- WarningException.cs
- ClientBuildManager.cs
- StylusPointPropertyInfo.cs
- Storyboard.cs
- ErrorTolerantObjectWriter.cs
- HttpValueCollection.cs
- HtmlControlDesigner.cs
- TemplateAction.cs
- StringUtil.cs
- Int64AnimationUsingKeyFrames.cs
- CFStream.cs
- DeviceContexts.cs
- PostBackOptions.cs
- SimpleHandlerBuildProvider.cs
- messageonlyhwndwrapper.cs
- TimeoutException.cs
- _WebProxyDataBuilder.cs
- TableLayout.cs
- DotNetATv1WindowsLogEntryDeserializer.cs
- XmlMembersMapping.cs
- X509PeerCertificateElement.cs
- COM2Properties.cs
- TypedReference.cs
- XmlSchemaElement.cs
- RawStylusActions.cs
- Keywords.cs
- DbProviderFactory.cs
- BuildProviderCollection.cs
- ListControlBuilder.cs
- DetailsViewDesigner.cs
- SqlUnionizer.cs
- HtmlUtf8RawTextWriter.cs
- HybridDictionary.cs
- CopyAttributesAction.cs
- EnumerableRowCollectionExtensions.cs
- HttpTransportBindingElement.cs
- IApplicationTrustManager.cs
- SizeValueSerializer.cs
- RelatedImageListAttribute.cs
- StackOverflowException.cs
- TypeUtil.cs
- AppDomainManager.cs
- SiteMapDataSource.cs
- ObjectViewFactory.cs
- ShimAsPublicXamlType.cs
- HandlerBase.cs
- SecUtil.cs
- StrokeSerializer.cs
- EditorPartCollection.cs
- TraceContext.cs
- MSG.cs
- XmlBindingWorker.cs
- SettingsProperty.cs
- DoWhile.cs
- PrintDialogException.cs
- ApplicationCommands.cs
- LabelInfo.cs
- URLAttribute.cs
- AQNBuilder.cs
- DataStreams.cs
- IdentifierElement.cs
- OracleCommandBuilder.cs
- HostSecurityManager.cs
- ExtractedStateEntry.cs
- AbstractDataSvcMapFileLoader.cs