Code:
/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / cdf / src / NetFx40 / Tools / System.Activities.Core.Presentation / System / Activities / Core / Presentation / ConnectorRouter.cs / 1305376 / ConnectorRouter.cs
//------------------------------------------------------------
// Copyright (c) Microsoft Corporation. All rights reserved.
//-----------------------------------------------------------
namespace System.Activities.Core.Presentation
{
using System.Collections.Generic;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Shapes;
using System.Globalization;
using System.Diagnostics.CodeAnalysis;
internal static class ConnectorRouter
{
const int connectorMargin = 30;
[Flags]
enum DesignerEdges
{
None = 0,
Left = 1,
Top = 2,
Right = 4,
Bottom = 8,
All = 15
}
//This is used for link creation gesture to show the adorner.(In this case we know only the source connection point).
internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint, Point end)
{
return Route(panel, srcConnPoint.Location, end, srcConnPoint.Edge, null);
}
//This is used when we know both the source and destination connection points.
internal static Point[] Route(FreeFormPanel panel, ConnectionPoint srcConnPoint , ConnectionPoint destConnPoint)
{
return Route(panel, srcConnPoint.Location, destConnPoint.Location, srcConnPoint.Edge, destConnPoint.Edge);
}
//This is used when we move the end connection point.
internal static Point[] Route(FreeFormPanel panel, Point begin, Point end)
{
return Route(panel, begin, end, null, null);
}
internal static bool AreAllSegmentsVerticalOrHorizontal(Point[] segments)
{
if (segments == null || segments.Length == 0)
{
return false;
}
for (int i = 1; i < segments.Length; i++)
{
if (segments[i - 1].X != segments[i].X && segments[i - 1].Y != segments[i].Y)
{
return false;
}
}
return true;
}
static ConnectorSegment SrcEdge;
static ConnectorSegment DestEdge;
//This method is the wrapper over the routing logic taken from Workflow V1.
static Point[] Route(FreeFormPanel panel, Point begin, Point end, List srcEdge, List destEdge)
{
Point[] segments;
if (panel == null)
{
throw FxTrace.Exception.AsError(new ArgumentNullException("panel"));
}
List < Rect > excludedRects = new List < Rect >();
List < Point > excludedLines = new List < Point >();
foreach (UIElement child in panel.Children)
{
if (child.GetType() == typeof(Connector))
{
for (int i = 0; i < (((Connector)child).Points.Count) - 1; i++)
{
excludedLines.Add(new Point(((Connector)child).Points[i].X, ((Connector)child).Points[i].Y));
excludedLines.Add(new Point(((Connector)child).Points[i + 1].X, ((Connector)child).Points[i + 1].Y));
}
}
else
{
//Since the connectors will touch the UIElement, they will pass through the margin around the UIElement.
//Hence excluding the margin in excludedRects.
Thickness margin = new Thickness(0);
Point origin = FreeFormPanel.GetLocation(child);
FrameworkElement frameworkChild = child as FrameworkElement;
if (frameworkChild != null)
{
margin = frameworkChild.Margin;
}
Size childSize = new Size(frameworkChild.DesiredSize.Width - margin.Left - margin.Right, frameworkChild.DesiredSize.Height - margin.Top - margin.Bottom);
excludedRects.Add(new Rect(Point.Add(FreeFormPanel.GetLocation(child), new Vector(margin.Left, margin.Top)), childSize));
}
}
ConnectorRouter.SrcEdge = null;
ConnectorRouter.DestEdge = null;
if (srcEdge != null)
{
//ConnectorSegment should only be a segment from left to right or top to bottom.
int smallerIndex = (srcEdge[0].X < srcEdge[1].X || srcEdge[0].Y < srcEdge[1].Y) ? 0 : 1;
ConnectorRouter.SrcEdge = new ConnectorSegment(srcEdge[smallerIndex], srcEdge[1 - smallerIndex]);
}
if (destEdge != null)
{
int smallerIndex = (destEdge[0].X < destEdge[1].X || destEdge[0].Y < destEdge[1].Y) ? 0 : 1;
ConnectorRouter.DestEdge = new ConnectorSegment(destEdge[smallerIndex], destEdge[1 - smallerIndex]);
}
segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), excludedLines.ToArray());
//WE NEED TO INCLUDE THESE FALLBACKS DUE TO A
if (!AreAllSegmentsVerticalOrHorizontal(segments))
{
segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), excludedRects.ToArray(), new Point[] { });
//segments = GetRoutedLineSegments(begin, end, new Size(connectorMargin, connectorMargin), new Rect[] { }, excludedLines.ToArray());
}
//DIRECT PATH
if (!AreAllSegmentsVerticalOrHorizontal(segments))
{
double slope = DesignerGeometryHelper.SlopeOfLineSegment(begin, end);
Point intermediatePoint = (slope < 1) ? new Point(end.X, begin.Y) : new Point(begin.X, end.Y);
segments = new Point[] { begin, intermediatePoint, end };
}
segments = RemoveRedundantPoints(new List(segments));
return segments;
}
//In a list of points specifying a connector, remove consecutive equal points.
static Point[] RemoveRedundantPoints(List points)
{
for (int i = points.Count - 1; i > 0; i--)
{
if (points[i].Equals(points[i - 1]))
{
points.RemoveAt(i);
}
}
return points.ToArray();
}
static void AddBoundPoint(ref List < DistanceFromPoint > extremitiesList, Point p, ConnectorSegment segment, Point Z)
{
if (p.X != int.MinValue && p.X != int.MaxValue && p.Y != int.MinValue && p.Y != int.MaxValue)
{
extremitiesList.Add(new DistanceFromPoint(segment, Z, p));
}
}
//Escape Algorithm
static Nullable < Point > EscapeAlgorithm(CoverSet coverSet, Point Z,
ref List < Point > LeA, ref List < ConnectorSegment > LhA, ref List < ConnectorSegment > LvA, ref List < ConnectorSegment > LhB, ref List < ConnectorSegment > LvB,
ref Orientation orientationA, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB, Size margin, ref bool noEscapeA)
{
Nullable < Point > intersection = null;
intersectionSegmentA = null;
intersectionSegmentB = null;
ConnectorSegment leftCover = coverSet.GetCover(Z, DesignerEdges.Left);
ConnectorSegment rightCover = coverSet.GetCover(Z, DesignerEdges.Right);
ConnectorSegment bottomCover = coverSet.GetCover(Z, DesignerEdges.Bottom);
ConnectorSegment topCover = coverSet.GetCover(Z, DesignerEdges.Top);
//P1: construct escape line(s) - on the beginning of the algorithm it will create two lines
ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, Z);
//We do not want the routed line to coincide with the source or dest edge.
//Hence the edge should never be an escape line.
if (h.Equals(ConnectorRouter.SrcEdge) || h.Equals(ConnectorRouter.DestEdge))
{
h = null;
}
else
{
LhA.Add(h);
}
ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, Z);
if (v.Equals(ConnectorRouter.SrcEdge) || v.Equals(ConnectorRouter.DestEdge))
{
v = null;
}
else
{
LvA.Add(v);
}
//P2 check if the new escape line(s) intersect with the existing ones
if (h != null)
{
for (int i = 0; i < LvB.Count; i++)
{
ConnectorSegment segment = LvB[i];
intersection = h.Intersect(segment);
if (intersection != null)
{
intersectionSegmentA = h;
intersectionSegmentB = segment;
return intersection;
}
}
}
if (v != null)
{
for (int i = 0; i < LhB.Count; i++)
{
ConnectorSegment segment = LhB[i];
intersection = v.Intersect(segment);
if (intersection != null)
{
intersectionSegmentA = v;
intersectionSegmentB = segment;
return intersection;
}
}
}
//there was no intersection found above, continue on
//P3 find an escape point
//Call Escape Process I
//Escape process I P1
Nullable escapePoint = null;
if (v != null)
{
escapePoint = EscapeProcessI(coverSet, Z, v, Orientation.Horizontal, margin);
if (escapePoint != null)
{
orientationA = Orientation.Vertical;
LeA.Add((Point)escapePoint);
return null;
}
}
//Escape process I P2
if (h != null)
{
escapePoint = EscapeProcessI(coverSet, Z, h, Orientation.Vertical, margin);
if (escapePoint != null)
{
orientationA = Orientation.Horizontal;
LeA.Add((Point)escapePoint);
return null;
}
}
//Call Escape process II
bool intersectionFlag = false;
//flags indicating if we can still continue in the given directions
bool continue1, continue2, continue3, continue4;
//CHANGE THIS.
Point r1 = new Point(), r2 = new Point(), r3 = new Point(), r4 = new Point();
if (topCover != null)
{
r1 = new Point(Z.X, topCover.A.Y);
}
if (rightCover != null)
{
r2 = new Point(rightCover.A.X, Z.Y);
}
if (bottomCover != null)
{
r3 = new Point(Z.X, bottomCover.A.Y);
}
if (leftCover != null)
{
r4 = new Point(leftCover.A.X, Z.Y);
}
do
{
continue1 = continue2 = continue3 = continue4 = false;
if (topCover != null && v != null)
{
r1.Y -= margin.Height;
if (r1.Y > Z.Y)
{
continue1 = true;
Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Vertical,
ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r1, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
if (escape != null)
{
LvA.Add(v);
if (intersectionFlag)
{
return escape;
}
orientationA = Orientation.Horizontal;
coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r1));
coverSet.AddUsedEscapeLine(new ConnectorSegment(r1, (Point)escape));
LeA.Add((Point)escape);
return null;
}
}
}
if (rightCover != null && h != null)
{
r2.X -= margin.Width;
if (r2.X > Z.X)
{
continue2 = true;
Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Horizontal,
ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r2, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
if (escape != null)
{
LhA.Add(h);
if (intersectionFlag)
{
return escape;
}
orientationA = Orientation.Vertical;
coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r2));
coverSet.AddUsedEscapeLine(new ConnectorSegment(r2, (Point)escape));
LeA.Add((Point)escape);
return null;
}
}
}
if (bottomCover != null && v != null)
{
r3.Y += margin.Height;
if (r3.Y < Z.Y)
{
continue3 = true;
Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Vertical,
ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r3, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
if (escape != null)
{
LvA.Add(v);
if (intersectionFlag)
{
return escape;
}
orientationA = Orientation.Horizontal;
coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r3));
coverSet.AddUsedEscapeLine(new ConnectorSegment(r3, (Point)escape));
LeA.Add((Point)escape);
return null;
}
}
}
if (leftCover != null && h!= null)
{
r4.X += margin.Width;
if (r4.X < Z.X)
{
continue4 = true;
Nullable < Point > escape = EscapeProcessII(coverSet, Orientation.Horizontal,
ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, r4, margin, out intersectionFlag, out intersectionSegmentA, out intersectionSegmentB);
if (escape != null)
{
LhA.Add(h);
if (intersectionFlag)
{
return escape;
}
orientationA = Orientation.Vertical;
coverSet.AddUsedEscapeLine(new ConnectorSegment(Z, r4));
coverSet.AddUsedEscapeLine(new ConnectorSegment(r4, (Point)escape));
LeA.Add((Point)escape);
return null;
}
}
}
//continue the loop until there is a place to go in either of the directions
} while (continue1 || continue2 || continue3 || continue4);
noEscapeA = true;
return null;
}
//Escape Process I
static Nullable < Point > EscapeProcessI(CoverSet coverSet, Point Z,
ConnectorSegment escapeLine, Orientation orientation, Size margin)
{
//perform extremity point permutation by the distance from the object point
//when sorting points store to which segments they belong (this is needed further when
//deciding to side of the point to move if the extremity coincide with the object point
//on abscissa or ordinata axis)
List < DistanceFromPoint > extremitiesList = new List < DistanceFromPoint >(4); //at most four points
ConnectorSegment lesserCover = coverSet.GetCover(Z, (orientation == Orientation.Horizontal) ? DesignerEdges.Left : DesignerEdges.Bottom);
if (lesserCover != null)
{
AddBoundPoint(ref extremitiesList, lesserCover.A, lesserCover, Z);
AddBoundPoint(ref extremitiesList, lesserCover.B, lesserCover, Z);
}
ConnectorSegment higherCover = coverSet.GetCover(Z, (orientation == Orientation.Horizontal) ? DesignerEdges.Right : DesignerEdges.Top);
if (higherCover != null)
{
AddBoundPoint(ref extremitiesList, higherCover.A, higherCover, Z);
AddBoundPoint(ref extremitiesList, higherCover.B, higherCover, Z);
}
if (extremitiesList.Count == 0)
{
return null;
}
DistanceSorter.Sort(ref extremitiesList);
for (int i = 0; i < extremitiesList.Count; i++)
{
Point p = extremitiesList[i].P;
Point direction = new Point(Math.Sign(p.X - Z.X), Math.Sign(p.Y - Z.Y));
if (((orientation == Orientation.Vertical) ? direction.X : direction.Y) == 0)
{
//if extremity is on the same abscissa(ordinata) line with the object point, need to be more careful
ConnectorSegment segment = extremitiesList[i].ConnectorSegment;
p = segment.ExtendPointOutwards(p);
direction = new Point(Math.Sign(p.X - Z.X), Math.Sign(p.Y - Z.Y));
p = extremitiesList[i].P;
}
DesignerEdges side; //which side is the cover we are trying to escape
if (orientation == Orientation.Vertical)
{
//we are escaping either top or bottom
side = (direction.Y < 0) ? DesignerEdges.Bottom : DesignerEdges.Top;
}
else
{
//we are escaping either left or right
side = (direction.X < 0) ? DesignerEdges.Left : DesignerEdges.Right;
}
Point escapePoint;
if ((orientation == Orientation.Vertical))
{
escapePoint = new Point(p.X + direction.X * margin.Width, Z.Y);
}
else
{
escapePoint = new Point(Z.X, p.Y + direction.Y * margin.Height);
}
//the new escape point should
//1) lay on the given escape line (except the bounding points since they belong to covers)
//2) not lay on any of the already tested escape segments - all points belonging to them are already worthless
ConnectorSegment newEscapeLine = new ConnectorSegment(Z, escapePoint);
if (!coverSet.EscapeLineHasBeenUsed(escapePoint) &&
escapeLine.IsPointOnSegment(escapePoint) && escapeLine.A != escapePoint && escapeLine.B != escapePoint &&
coverSet.IsEscapePoint(Z, escapePoint, side))
{
coverSet.AddUsedEscapeLine(newEscapeLine);
return escapePoint;
}
}
return null;
}
//Escape Process II
static Nullable < Point > EscapeProcessII(CoverSet coverSet, Orientation orientation, ref List < Point > LeA,
ref List < ConnectorSegment > LhA, ref List < ConnectorSegment > LvA, ref List < ConnectorSegment > LhB, ref List < ConnectorSegment > LvB,
Point R, Size margin, out bool intersectionFlag, out ConnectorSegment intersectionSegmentA, out ConnectorSegment intersectionSegmentB)
{
intersectionFlag = false;
intersectionSegmentA = null;
intersectionSegmentB = null;
//rebuild invalidated covers
ConnectorSegment h = ConnectorSegment.SegmentFromLeftToRightCover(coverSet, R);
ConnectorSegment v = ConnectorSegment.SegmentFromBottomToTopCover(coverSet, R);
//check intersections
for (int i = 0; i < LvB.Count; i++)
{
ConnectorSegment segment = LvB[i];
Nullable < Point > itersection = h.Intersect(segment);
if (itersection != null)
{
intersectionFlag = true;
intersectionSegmentA = h;
intersectionSegmentB = segment;
LeA.Add(R);
return itersection;
}
}
for (int i = 0; i < LhB.Count; i++)
{
ConnectorSegment segment = LhB[i];
Nullable < Point > itersection = v.Intersect(segment);
if (itersection != null)
{
intersectionFlag = true;
intersectionSegmentA = v;
intersectionSegmentB = segment;
LeA.Add(R);
return itersection;
}
}
Nullable < Point > escapePointI = null;
//now do both horizontal and vertical escape processes I from that point...
//the order is important based on 'orientation' argument
if (orientation == Orientation.Horizontal)
{
escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin);
if (escapePointI != null)
{
LvA.Add(v);
LeA.Add(R);
return escapePointI;
}
escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin);
if (escapePointI != null)
{
LhA.Add(h);
LeA.Add(R);
return escapePointI;
}
}
else
{
escapePointI = EscapeProcessI(coverSet, R, h, Orientation.Vertical, margin);
if (escapePointI != null)
{
LhA.Add(h);
LeA.Add(R);
return escapePointI;
}
escapePointI = EscapeProcessI(coverSet, R, v, Orientation.Horizontal, margin);
if (escapePointI != null)
{
LvA.Add(v);
LeA.Add(R);
return escapePointI;
}
}
return null;
}
//remove all non-corner points
static List < Point > FirstRefinementAlgorithm(List < Point > Le, ConnectorSegment intersectionSegment)
{
List < Point > refinedSet = new List < Point >();
ConnectorSegment k = intersectionSegment;
while (Le.Count > 0)
{
Point pi;
int i = Le.Count - 1;
//find the first point that lies on k
while (!k.PointLiesOnThisLine(Le[i]) && i > 0)
{
i--;
}
//find the least point that lies on k
while (i > 0 && k.PointLiesOnThisLine(Le[i - 1]))
{
i--;
}
//save the point
pi = Le[i];
refinedSet.Add(pi);
//remove all the points up to the found one from the original list
while (Le.Count > i)
{
Le.RemoveAt(i);
}
//continue with the points lying on the line perpendecular to the previous one and passing through the
//found point
k = k.PeprendecularThroughPoint(pi);
}
return refinedSet;
}
[SuppressMessage("Microsoft.Design", "CA1031:DoNotCatchGeneralExceptionTypes",
Justification = "Catch all exceptions to prevent crash.")]
[SuppressMessage("Reliability", "Reliability108:IsFatalRule",
Justification = "Catch all exceptions to prevent crash.")]
static Point[] GetRoutedLineSegments(Point begin, Point end, Size margin, Rect[] rectanglesToExclude, Point[] linesToExclude)
{
if (rectanglesToExclude == null)
{
throw FxTrace.Exception.AsError(new ArgumentNullException("rectanglesToExclude"));
}
if (linesToExclude == null)
{
throw FxTrace.Exception.AsError(new ArgumentNullException("linesToExclude"));
}
if ((linesToExclude.Length % 2) > 0)
{
throw FxTrace.Exception.AsError(new ArgumentException("Error"));
}
CoverSet coverSet = new CoverSet(rectanglesToExclude, linesToExclude);
coverSet.ClearUsedLines();
Point A = begin;
Point B = end;
//escape points
List < Point > LeA = new List < Point >(); //escape points from begin to end
List < Point > LeB = new List < Point >(); //escape points from end to begin
//horizontal/vertical escape segments from A
List < ConnectorSegment > LhA = new List < ConnectorSegment >();
List < ConnectorSegment > LvA = new List < ConnectorSegment >();
//horizontal/vertical escape segments from B
List < ConnectorSegment > LhB = new List < ConnectorSegment >();
List < ConnectorSegment > LvB = new List < ConnectorSegment >();
Orientation orientationA = Orientation.Horizontal;
Orientation orientationB = Orientation.Horizontal;
//P0
LeA.Add(begin);
LeB.Add(end);
bool noEscapeA = false;
bool noEscapeB = false;
Nullable < Point > intersection = null;
ConnectorSegment intersectionSegmentA = null;
ConnectorSegment intersectionSegmentB = null;
try
{
do
{
//P1
if (noEscapeA)
{
if (noEscapeB)
{
//we failed to find the point
break;
}
else
{
//P2
//swap A and B (with all appropriate lists and flags...)
List < Point > tempList = LeA;
LeA = LeB;
LeB = tempList;
Point tempPoint = A;
A = B;
B = tempPoint;
bool tempBool = noEscapeA;
noEscapeA = noEscapeB;
noEscapeB = tempBool;
Orientation tempOrientation = orientationA;
orientationA = orientationB;
orientationB = tempOrientation;
List < ConnectorSegment > tempListSegm = LhA;
LhA = LhB;
LhB = tempListSegm;
tempListSegm = LvA;
LvA = LvB;
LvB = tempListSegm;
continue;
}
}
Point objectPoint = LeA[LeA.Count - 1];
Point targetPoint = B;
intersection = EscapeAlgorithm(coverSet, objectPoint,
ref LeA, ref LhA, ref LvA, ref LhB, ref LvB, ref orientationA,
out intersectionSegmentA, out intersectionSegmentB, margin, ref noEscapeA);
if (intersection != null)
{
break;
}
else
{
//swap A and B (with all appropriate lists and flags...)
List < Point > tempList = LeA;
LeA = LeB;
LeB = tempList;
Point tempPoint = A;
A = B;
B = tempPoint;
bool tempBool = noEscapeA;
noEscapeA = noEscapeB;
noEscapeB = tempBool;
Orientation tempOrientation = orientationA;
orientationA = orientationB;
orientationB = tempOrientation;
List < ConnectorSegment > tempListSegm = LhA;
LhA = LhB;
LhB = tempListSegm;
tempListSegm = LvA;
LvA = LvB;
LvB = tempListSegm;
}
} while (true);
//we failed
if (intersection == null)
{
return null;
}
List < Point > refinedPath = new List < Point >();
//P3 apply refinement algorithms
//first refinement algorithm
LeA = FirstRefinementAlgorithm(LeA, intersectionSegmentA);
LeB = FirstRefinementAlgorithm(LeB, intersectionSegmentB);
//before going into the second refinement, construct the full path
for (int j = LeA.Count - 1; j >= 0; j--)
{
refinedPath.Add(LeA[j]);
}
refinedPath.Add((Point)intersection);
for (int j = 0; j < LeB.Count; j++)
{
refinedPath.Add(LeB[j]);
}
//perform second refinement algorithm on the full path
SecondRefinementAlgorithm(coverSet, ref refinedPath, margin);
if (refinedPath.Count > 1 && refinedPath[refinedPath.Count - 1] == begin)
{
refinedPath.Reverse();
}
return refinedPath.ToArray();
}
catch (Exception)
{
//Debug.Assert(false, "Investigate if we ever get here. got an exception:\n" + ex.Message);
return null;
}
}
//remove superflous parts from the path
static void SecondRefinementAlgorithm(CoverSet coverSet, ref List < Point > refinedPath, Size margin)
{
List < Point > newPath = new List < Point >();
//Part I: extend every segment in the path to see if it intersects any other segment
int currentSegment = 0;
while (currentSegment < refinedPath.Count - 1)
{
Point a1 = refinedPath[currentSegment];
Point a2 = refinedPath[currentSegment + 1];
//need to construct a segment through the points that is limited by the covers
ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2);
//try to intersect it with every segment after the current one
//and the next one (which we know does intersect with the current one)
int intersectingSegment = currentSegment + 2;
while (intersectingSegment < refinedPath.Count - 1)
{
Point b1 = refinedPath[intersectingSegment];
Point b2 = refinedPath[intersectingSegment + 1];
ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, b1, b2);
Nullable < Point > intersection = a.Intersect(b);
if (intersection != null)
{
newPath.Clear();
//need to remove all points between a1 and b2 and insert the point of intersectin there
for (int i = 0; i <= currentSegment; i++)
{
newPath.Add(refinedPath[i]);
}
newPath.Add((Point)intersection);
for (int i = intersectingSegment + 1; i < refinedPath.Count; i++)
{
newPath.Add(refinedPath[i]);
}
List < Point > temp = refinedPath;
refinedPath = newPath;
newPath = temp;
newPath.Clear();
//reset the second segment number and go through all segments once more
//until there are no intersections left
intersectingSegment = currentSegment + 2;
}
else
{
intersectingSegment++;
}
}
//we need to keep looking for intersections until we reach the very last one
currentSegment++;
}
//Part II: construct segments perpendecular to every segment and see if they intersect any other segment
currentSegment = 0;
while (currentSegment < refinedPath.Count - 1)
{
Point a1 = refinedPath[currentSegment];
Point a2 = refinedPath[currentSegment + 1];
//need to construct a segment through the points that is limited by the covers
bool intersected = false;
ConnectorSegment a = ConnectorSegment.ConstructBoundSegment(coverSet, a1, a2);
if (a != null)
{
Point direction = new Point(a2.X - a1.X, a2.Y - a1.Y);
//see how many intemediate points we can construct
int steps = (int)Math.Max(Math.Abs(direction.X / margin.Width), Math.Abs(direction.Y / margin.Height)); //one of the values will be null
direction.X = (int)Math.Sign(direction.X);
direction.Y = (int)Math.Sign(direction.Y);
for (int i = 1; i <= steps; i++)
{
Point k = new Point(a1.X + i * margin.Width * direction.X, a1.Y + i * margin.Height * direction.Y);
if (k == a2)
{
break;
}
ConnectorSegment b = ConnectorSegment.ConstructBoundSegment(coverSet, k, (a.Orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal);
//now try to intersect that segment with every segment after the current one and the one after it
int intersectingSegment = currentSegment + 2;
while (intersectingSegment < refinedPath.Count - 1 && !intersected)
{
Point c1 = refinedPath[intersectingSegment];
Point c2 = refinedPath[intersectingSegment + 1];
ConnectorSegment c = new ConnectorSegment(c1, c2);
Nullable < Point > intersection = b.Intersect(c);
if (intersection != null && c.IsPointOnSegment((Point)intersection))
{
intersected = true;
newPath.Clear();
//need to remove all points between a1 and b2 and insert k and the point of intersection there
for (int j = 0; j <= currentSegment; j++)
{
newPath.Add(refinedPath[j]);
}
newPath.Add(k);
newPath.Add((Point)intersection);
for (int j = intersectingSegment + 1; j < refinedPath.Count; j++)
{
newPath.Add(refinedPath[j]);
}
List < Point > temp = refinedPath;
refinedPath = newPath;
newPath = temp;
newPath.Clear();
break;
}
intersectingSegment++;
}
//if there was an intersection, exit the for loop
if (intersected)
{
break;
}
}
}
//if there was an intersection, run the same segment again to see if there are other intersecting segments
if (!intersected)
{
currentSegment++;
}
}
}
//Struct DistanceFromPoint
//sorting of extremities by closedness to point Z
struct DistanceFromPoint
{
public ConnectorSegment ConnectorSegment;
public double Distance;
public Point P;
public DistanceFromPoint(ConnectorSegment segment, Point z, Point p)
{
this.ConnectorSegment = segment;
this.P = p;
this.Distance = ConnectorSegment.DistanceBetweenPoints(z, p);
}
}
// represents a segment - the main entity in the routing algorithm
sealed class ConnectorSegment
{
Orientation orientation;
Point point1;
Point point2;
public ConnectorSegment(Point point1, Point point2)
{
if (point1.X != point2.X && point1.Y != point2.Y)
{
throw FxTrace.Exception.AsError(new InvalidOperationException(string.Format(CultureInfo.InvariantCulture,
SR.CannotConstructConnectionSegment, point1.ToString(), point2.ToString())));
}
this.point1 = point1;
this.point2 = point2;
this.orientation = ((this.point1.X == this.point2.X) ? Orientation.Vertical : Orientation.Horizontal);
}
public Point A
{
get
{
return this.point1;
}
}
public Point B
{
get
{
return this.point2;
}
}
public Orientation Orientation
{
get
{
return this.orientation;
}
}
//given two points construct a segment through them from lesser cover to higher
public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Point b)
{
//Debug.Assert(!(a.X != b.X && a.Y != b.Y), "arbitrary segment, only horizontal or vertical ones are allowed!");
if (a.X != b.X && a.Y != b.Y)
{
return null;
}
return ConstructBoundSegment(coverSet, a, (a.X == b.X) ? Orientation.Vertical : Orientation.Horizontal);
}
public static ConnectorSegment ConstructBoundSegment(CoverSet coverSet, Point a, Orientation orientation)
{
return (orientation == Orientation.Horizontal) ? SegmentFromLeftToRightCover(coverSet, a) : SegmentFromBottomToTopCover(coverSet, a);
}
public static double DistanceBetweenPoints(Point p, Point q)
{
return Math.Sqrt((double)(p.X - q.X) * (p.X - q.X) + (double)(p.Y - q.Y) * (p.Y - q.Y));
}
public static ConnectorSegment SegmentFromBottomToTopCover(CoverSet coverSet, Point p)
{
ConnectorSegment bottomCover = coverSet.GetCover(p, DesignerEdges.Bottom);
ConnectorSegment topCover = coverSet.GetCover(p, DesignerEdges.Top);
//construct vertical escape segment
Point bottom = new Point(p.X, (bottomCover != null) ? bottomCover.A.Y : int.MinValue);
Point top = new Point(p.X, (topCover != null) ? topCover.A.Y : int.MaxValue);
ConnectorSegment v = new ConnectorSegment(bottom, top);
return v;
}
public static ConnectorSegment SegmentFromLeftToRightCover(CoverSet coverSet, Point p)
{
ConnectorSegment leftCover = coverSet.GetCover(p, DesignerEdges.Left);
ConnectorSegment rightCover = coverSet.GetCover(p, DesignerEdges.Right);
//construct horizontal escape segment
Point left = new Point((leftCover != null) ? leftCover.A.X : int.MinValue, p.Y);
Point right = new Point((rightCover != null) ? rightCover.A.X : int.MaxValue, p.Y);
ConnectorSegment h = new ConnectorSegment(left, right);
return h;
}
//"segment l covers a point p, if the perpendicular from p to the line of which l is a segment intersects l"
//since a) we only have horizotal or vertical segments and b) some segments will be unbound, we have to store and use orientation
//flag to do analyzis
public bool Covers(Point p)
{
return (this.orientation == Orientation.Horizontal) ? (p.X >= Math.Min(this.point1.X, this.point2.X) && p.X <= Math.Max(this.point1.X, this.point2.X)) : (p.Y >= Math.Min(this.point1.Y, this.point2.Y) && p.Y <= Math.Max(this.point1.Y, this.point2.Y));
}
public override bool Equals(object obj)
{
ConnectorSegment segment = obj as ConnectorSegment;
if (segment == null)
{
return false;
}
return (this.point1 == segment.A && this.point2 == segment.B && Orientation == segment.Orientation);
}
public Point ExtendPointOutwards(Point p)
{
if (p != this.point1 && p != this.point2)
{
return p;
}
int k = (int)((this.orientation == Orientation.Horizontal) ? p.X : p.Y);
int k1 = (int)((this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y);
int k2 = (int)((this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y);
if (k == Math.Min(k1, k2))
{
k--;
}
else
{
k++;
}
return new Point((this.orientation == Orientation.Horizontal) ? k : p.X, (this.orientation == Orientation.Horizontal) ? p.Y : k);
}
public override int GetHashCode()
{
return this.point1.GetHashCode() ^ this.point2.GetHashCode() ^ Orientation.GetHashCode();
}
//see if the two segments intersect
//greatly simplified by the fact that we only have vertical or horizontal segments
//should work fine with {Max, Min}Value values
public Nullable < Point > Intersect(ConnectorSegment segment)
{
if (this.orientation == segment.Orientation)
{
return null;
}
ConnectorSegment vertical = (this.orientation == Orientation.Vertical) ? this : segment;
ConnectorSegment horizontal = (this.orientation == Orientation.Vertical) ? segment : this;
if (vertical.A.X < Math.Min(horizontal.A.X, horizontal.B.X) || vertical.A.X > Math.Max(horizontal.A.X, horizontal.B.X))
{
return null;
}
if (horizontal.A.Y < Math.Min(vertical.A.Y, vertical.B.Y) || horizontal.A.Y > Math.Max(vertical.A.Y, vertical.B.Y))
{
return null;
}
return new Point(vertical.A.X, horizontal.A.Y);
}
//we consider just the segment for this test
public bool IsPointOnSegment(Point p)
{
if ((this.orientation == Orientation.Horizontal && p.Y != this.point1.Y) || (this.orientation == Orientation.Vertical && p.X != this.point1.X))
{
return false;
}
int k = (int)((this.orientation == Orientation.Horizontal) ? p.X : p.Y);
int k1 = (int)((this.orientation == Orientation.Horizontal) ? this.point1.X : this.point1.Y);
int k2 = (int)((this.orientation == Orientation.Horizontal) ? this.point2.X : this.point2.Y);
return k >= Math.Min(k1, k2) && k <= Math.Max(k1, k2);
}
public ConnectorSegment PeprendecularThroughPoint(Point p)
{
Orientation newOrientation = (this.orientation == Orientation.Horizontal) ? Orientation.Vertical : Orientation.Horizontal;
Point newPoint = new Point(p.X, p.Y);
if (newOrientation == Orientation.Horizontal)
{
newPoint.X = int.MaxValue;
}
else
{
newPoint.Y = int.MaxValue;
}
return new ConnectorSegment(p, newPoint);
}
//we consider the whole line to which this segment belongs for this test
public bool PointLiesOnThisLine(Point p)
{
return (this.orientation == Orientation.Horizontal) ? p.Y == this.point1.Y : p.X == this.point1.X;
}
}
//Class CoverSet (Set of vertical and horizontal covers)
sealed class CoverSet
{
List < ConnectorSegment > horizontalCovers = new List < ConnectorSegment >();
List < ConnectorSegment > usedEscapeLine = new List < ConnectorSegment >();
List < ConnectorSegment > verticalCovers = new List < ConnectorSegment >();
public CoverSet(Rect[] rectanglesToExclude, Point[] linesToExclude)
{
foreach (Rect rectangle in rectanglesToExclude)
{
AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Top), new Point(rectangle.Left, rectangle.Bottom)));
AddCover(new ConnectorSegment(new Point(rectangle.Right, rectangle.Top), new Point(rectangle.Right, rectangle.Bottom)));
AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Top), new Point(rectangle.Right, rectangle.Top)));
AddCover(new ConnectorSegment(new Point(rectangle.Left, rectangle.Bottom), new Point(rectangle.Right, rectangle.Bottom)));
}
//Add the linesegments to cover
for (int i = 0; i < linesToExclude.Length / 2; i++)
{
AddCover(new ConnectorSegment(linesToExclude[i * 2], linesToExclude[(i * 2) + 1]));
}
}
public void AddCover(ConnectorSegment cover)
{
List < ConnectorSegment > covers = (cover.Orientation == Orientation.Vertical) ? this.verticalCovers : this.horizontalCovers;
for (int i = 0; i < covers.Count; i++)
{
ConnectorSegment existingCover = covers[i];
if (cover.IsPointOnSegment(existingCover.A) && cover.IsPointOnSegment(existingCover.B))
{
//both points of vertical are on the new segment, delete the vertical and add the new one instead
covers.RemoveAt(i);
break;
}
else if (existingCover.IsPointOnSegment(cover.A) && existingCover.IsPointOnSegment(cover.B))
{
//both points of the new segment are on an existing segment already - skip this one
return;
}
}
covers.Add(cover);
}
public void AddUsedEscapeLine(ConnectorSegment segment)
{
this.usedEscapeLine.Add(segment);
}
public void ClearUsedLines()
{
this.usedEscapeLine.Clear();
}
//the new escape point should not lay on any of the already used escape segments
public bool EscapeLineHasBeenUsed(Point escapePoint)
{
for (int i = 0; i < this.usedEscapeLine.Count; i++)
{
ConnectorSegment usedSegment = this.usedEscapeLine[i];
if (usedSegment.IsPointOnSegment(escapePoint))
{
return true;
}
}
return false;
}
//get the cover on the given side (closest cover to the given side) for the point out of all stored segments
public ConnectorSegment GetCover(Point p, DesignerEdges side)
{
ConnectorSegment cover = null;
int distance = 0;
if (side == DesignerEdges.Left || side == DesignerEdges.Right)
{
for (int i = 0; i < this.verticalCovers.Count; i++)
{
ConnectorSegment segment = this.verticalCovers[i];
int currentDistance = (int)((side == DesignerEdges.Left) ? p.X - segment.A.X : segment.A.X - p.X);
if (currentDistance > 0 && segment.Covers(p))
{
if (cover == null || distance > currentDistance)
{
cover = segment;
distance = currentDistance;
}
}
}
}
else
{
for (int i = 0; i < this.horizontalCovers.Count; i++)
{
ConnectorSegment segment = this.horizontalCovers[i];
int currentDistance = (int)((side == DesignerEdges.Bottom) ? p.Y - segment.A.Y : segment.A.Y - p.Y);
if (currentDistance > 0 && segment.Covers(p))
{
if (cover == null || distance > currentDistance)
{
cover = segment;
distance = currentDistance;
}
}
}
}
return cover;
}
//get the cover on the given side (closest cover to the given side) for the point out of all stored segments
public List < ConnectorSegment > GetCovers(Point p, DesignerEdges side)
{
List < ConnectorSegment > covers = new List < ConnectorSegment >();
if (side == DesignerEdges.Left || side == DesignerEdges.Right)
{
for (int i = 0; i < this.verticalCovers.Count; i++)
{
ConnectorSegment segment = this.verticalCovers[i];
int currentDistance = (int)((side == DesignerEdges.Left) ? p.X - segment.A.X : segment.A.X - p.X);
if (currentDistance > 0 && segment.Covers(p))
{
covers.Add(segment);
}
}
}
else
{
for (int i = 0; i < this.horizontalCovers.Count; i++)
{
ConnectorSegment segment = this.horizontalCovers[i];
int currentDistance = (int)((side == DesignerEdges.Bottom) ? p.Y - segment.A.Y : segment.A.Y - p.Y);
if (currentDistance > 0 && segment.Covers(p))
{
covers.Add(segment);
}
}
}
return covers;
}
public bool IsEscapePoint(Point origin, Point escape, DesignerEdges side)
{
//get the original cover
ConnectorSegment originalCover = this.GetCover(origin, side);
int originalDistance;
if (side == DesignerEdges.Left || side == DesignerEdges.Right)
{
originalDistance = (int)(originalCover.A.X - escape.X);
}
else
{
originalDistance = (int)(originalCover.A.Y - escape.Y);
}
// the escape point should not be covered by the the original cover
if (originalCover.Covers(escape))
{
return false;
}
//it should not also be covered by any member of other segments between the original cover and the original point
List < ConnectorSegment > newCovers = this.GetCovers(escape, side);
for (int i = 0; i < newCovers.Count; i++)
{
ConnectorSegment newCover = newCovers[i];
//should never happen, just in case...
if (newCover == originalCover)
{
return false;
}
int newDistance;
if (side == DesignerEdges.Left || side == DesignerEdges.Right)
{
newDistance = (int)Math.Abs(newCover.A.X - escape.X);
}
else
{
newDistance = (int)Math.Abs(newCover.A.Y - escape.Y);
}
if (Math.Sign(newDistance) == Math.Sign(originalDistance) && Math.Abs(newDistance) < Math.Abs(originalDistance))
{
return false;
}
}
return true;
}
}
sealed class DistanceSorter : IComparer < DistanceFromPoint >
{
DistanceSorter()
{
}
public static void Sort(ref List < DistanceFromPoint > distances)
{
DistanceSorter sorter = new DistanceSorter();
distances.Sort(sorter);
}
int IComparer < DistanceFromPoint >.Compare(DistanceFromPoint lhs, DistanceFromPoint rhs)
{
if (lhs.Distance == rhs.Distance)
{
return 0;
}
else if (lhs.Distance > rhs.Distance)
{
return 1;
}
else
{
return -1;
}
}
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- DataServiceQueryException.cs
- VectorValueSerializer.cs
- SqlRemoveConstantOrderBy.cs
- RadioButton.cs
- Paragraph.cs
- TreeViewCancelEvent.cs
- NodeFunctions.cs
- AppModelKnownContentFactory.cs
- BindingListCollectionView.cs
- TrackingCondition.cs
- Module.cs
- MenuBase.cs
- AstNode.cs
- SmtpNegotiateAuthenticationModule.cs
- ImmutableCollection.cs
- SEHException.cs
- CorrelationService.cs
- UiaCoreProviderApi.cs
- RequestCache.cs
- HttpCachePolicy.cs
- MainMenu.cs
- QilParameter.cs
- ToolboxComponentsCreatingEventArgs.cs
- TaskFormBase.cs
- GZipStream.cs
- CompilerTypeWithParams.cs
- Message.cs
- DataConnectionHelper.cs
- BindingWorker.cs
- StylusPointCollection.cs
- ApplicationManager.cs
- VariableQuery.cs
- TreeNodeStyleCollection.cs
- XmlDictionaryString.cs
- EvidenceTypeDescriptor.cs
- Timer.cs
- MsmqAppDomainProtocolHandler.cs
- EntityDataSourceChangingEventArgs.cs
- PersonalizationProvider.cs
- EncoderFallback.cs
- Int32CAMarshaler.cs
- GradientStop.cs
- KerberosSecurityTokenParameters.cs
- TextSpan.cs
- XPathAncestorQuery.cs
- IndicFontClient.cs
- MachineKeySection.cs
- ValueUtilsSmi.cs
- ClientBuildManagerTypeDescriptionProviderBridge.cs
- NamespaceCollection.cs
- VisualTarget.cs
- Visual3D.cs
- CategoryEditor.cs
- Matrix.cs
- CqlWriter.cs
- MetadataArtifactLoaderCompositeResource.cs
- Helpers.cs
- XmlNodeReader.cs
- Transactions.cs
- RewritingProcessor.cs
- Bookmark.cs
- CodeMemberEvent.cs
- RayMeshGeometry3DHitTestResult.cs
- NetTcpSecurityElement.cs
- KeySpline.cs
- AuthStoreRoleProvider.cs
- Listener.cs
- BaseParser.cs
- CompositeActivityCodeGenerator.cs
- SynchronizationContext.cs
- Int32AnimationBase.cs
- DependencyObjectPropertyDescriptor.cs
- PackageRelationshipCollection.cs
- ResourceAttributes.cs
- CodeSnippetExpression.cs
- RemotingException.cs
- EmptyImpersonationContext.cs
- OracleCommandBuilder.cs
- HttpProfileBase.cs
- PointF.cs
- SqlDataSource.cs
- TemplateInstanceAttribute.cs
- SafeNativeMethodsMilCoreApi.cs
- DependencyPropertyConverter.cs
- AttributeUsageAttribute.cs
- WebPartZoneBaseDesigner.cs
- ImportCatalogPart.cs
- SafeProcessHandle.cs
- util.cs
- BindingCompleteEventArgs.cs
- PropertyTabAttribute.cs
- DataGridViewRowPostPaintEventArgs.cs
- ScrollBarRenderer.cs
- Html32TextWriter.cs
- BindingBase.cs
- DifferencingCollection.cs
- SendKeys.cs
- XmlObjectSerializer.cs
- StorageComplexPropertyMapping.cs
- ControlBindingsCollection.cs