in GraphLayout/MSAGL/GraphmapsWithMesh/MeshCreator.cs [490:635]
public static void ProcessLeftRays(Tiling g, Dictionary<int, int> Neighbors4, Dictionary<int, int> Neighbors5, int maxX, int maxY, Dictionary<Point, int> locationtoNode)
{
int a;
//LineSegment l;
for (int i = 0; i < g.N; i++)
{
Vertex CurrentVertex = g.VList[i];
if (CurrentVertex.leftRay == null)
{
Vertex Neighbor = null;
Vertex Neighbor4 = null, Neighbor5 = null;
//find the closest neighbor in C4
double distance4 = double.MaxValue;
if (Neighbors4.ContainsKey(g.VList[i].Id))
{
Neighbor4 = g.VList[Neighbors4[g.VList[i].Id]];
distance4 = Math.Abs(Neighbor4.XLoc - CurrentVertex.XLoc) + Math.Abs(Neighbor4.YLoc - CurrentVertex.YLoc);
}
//find the closest neighbor in C5
double distance5 = double.MaxValue;
if (Neighbors5.ContainsKey(g.VList[i].Id))
{
Neighbor5 = g.VList[Neighbors5[g.VList[i].Id]];
distance5 = Math.Abs(Neighbor5.XLoc - CurrentVertex.XLoc) + Math.Abs(Neighbor5.YLoc - CurrentVertex.YLoc);
}
//if (distance4 == double.MaxValue && distance5 == double.MaxValue)
{
//hit the boundary because if there were a vertex on the way - then we did not reach this case
//a = g.InsertVertex(0, CurrentVertex.YLoc);
//g.addEdge(CurrentVertex.Id, a);
//there is no one that can stop the ray
//l = new LineSegment(CurrentVertex.XLoc, CurrentVertex.YLoc, 0, CurrentVertex.YLoc);
//CurrentVertex.leftRay = new Ray(l) { dead = true };
}
//else
{ //there is a ray that can stop the left ray
if (distance4 == double.MaxValue && distance5 == double.MaxValue)
Neighbor = g.VList[g.N + 1];
else if (distance4 < distance5) Neighbor = Neighbor4;
else Neighbor = Neighbor5;
//check if the neighbor is on the same y line of current vertex
if (CurrentVertex.YLoc == Neighbor.YLoc)
{
//find the rightmost point of the neighbor
Vertex rightNeighbor;
do
{
rightNeighbor = Neighbor ;
for (int j = 0; j < g.DegList[Neighbor.Id]; j++)
{
Vertex Candidate = g.VList[g.EList[Neighbor.Id, j].NodeId];
if (Candidate.YLoc > Neighbor.YLoc)
{
Neighbor = Candidate;
break;
}
}
} while (rightNeighbor.Id != Neighbor.Id);
if (rightNeighbor.XLoc >= CurrentVertex.XLoc) continue;
//dont need to find left neighbor since this is the first time ray is growing
g.AddEdge(CurrentVertex.Id, rightNeighbor.Id);
if (!VHEdges.ContainsKey(CurrentVertex.YLoc))
VHEdges[CurrentVertex.YLoc] = new List<OrthogonalEdge>();
VHEdges[CurrentVertex.YLoc].Add(new OrthogonalEdge(CurrentVertex, rightNeighbor));
}
else
{
//check if the left ray already hits a vertical Edge r
OrthogonalEdge r = null;
Vertex ClosestVertex = Neighbor;
if (HVEdges.ContainsKey(Neighbor.XLoc))
{
foreach (var vEdge in HVEdges[Neighbor.XLoc])
{
if (vEdge.a.YLoc <= CurrentVertex.YLoc && vEdge.b.YLoc >= CurrentVertex.YLoc)
{
r = vEdge;
break;
}
//find the vertex on the line that is the closest one
if (Neighbor.YLoc > CurrentVertex.YLoc &&
Neighbor.YLoc >= vEdge.a.YLoc && vEdge.a.YLoc >= CurrentVertex.YLoc &&
Neighbor.YLoc >= vEdge.b.YLoc && vEdge.b.YLoc >= CurrentVertex.YLoc)
{
if (Math.Abs(vEdge.a.YLoc - CurrentVertex.YLoc) <
Math.Abs(ClosestVertex.YLoc - CurrentVertex.YLoc)) ClosestVertex = vEdge.a;
if (Math.Abs(vEdge.b.YLoc - CurrentVertex.YLoc) <
Math.Abs(ClosestVertex.YLoc - CurrentVertex.YLoc)) ClosestVertex = vEdge.b;
}
else if (Neighbor.YLoc < CurrentVertex.YLoc &&
Neighbor.YLoc <= vEdge.a.YLoc && vEdge.a.YLoc <= CurrentVertex.YLoc &&
Neighbor.YLoc <= vEdge.b.YLoc && vEdge.b.YLoc <= CurrentVertex.YLoc)
{
if (Math.Abs(vEdge.a.YLoc - CurrentVertex.YLoc) <
Math.Abs(ClosestVertex.YLoc - CurrentVertex.YLoc)) ClosestVertex = vEdge.a;
if (Math.Abs(vEdge.b.YLoc - CurrentVertex.YLoc) <
Math.Abs(ClosestVertex.YLoc - CurrentVertex.YLoc)) ClosestVertex = vEdge.b;
}
}
}
if (r != null)
{
a = g.InsertVertexWithDuplicateCheck(Neighbor.XLoc, CurrentVertex.YLoc, locationtoNode);
g.RemoveEdge(r.a.Id, r.b.Id);
g.AddEdge(r.a.Id, a);
g.AddEdge(r.b.Id, a);
g.AddEdge(CurrentVertex.Id, a);
if (!HVEdges.ContainsKey(Neighbor.XLoc))
HVEdges[Neighbor.XLoc] = new List<OrthogonalEdge>();
if (!VHEdges.ContainsKey(CurrentVertex.YLoc))
VHEdges[CurrentVertex.YLoc] = new List<OrthogonalEdge>();
HVEdges[Neighbor.XLoc].Remove(r);
HVEdges[Neighbor.XLoc].Add(new OrthogonalEdge(r.a, g.VList[a]));
HVEdges[Neighbor.XLoc].Add(new OrthogonalEdge(r.b, g.VList[a]));
VHEdges[CurrentVertex.YLoc].Add(new OrthogonalEdge(CurrentVertex, g.VList[a]));
}
else
{
a = g.InsertVertexWithDuplicateCheck(ClosestVertex.XLoc, CurrentVertex.YLoc, locationtoNode);
g.AddEdge(CurrentVertex.Id, a);
g.AddEdge(ClosestVertex.Id, a);
if (!HVEdges.ContainsKey(Neighbor.XLoc))
HVEdges[Neighbor.XLoc] = new List<OrthogonalEdge>();
if (!VHEdges.ContainsKey(CurrentVertex.YLoc))
VHEdges[CurrentVertex.YLoc] = new List<OrthogonalEdge>();
VHEdges[CurrentVertex.YLoc].Add(new OrthogonalEdge(CurrentVertex, g.VList[a]));
HVEdges[ClosestVertex.XLoc].Add(new OrthogonalEdge(ClosestVertex, g.VList[a]));
}
}
}
}
}
}