in GraphLayout/MSAGL/GraphmapsWithMesh/MeshCreator.cs [1356:1513]
public static void CreateCompetitionMeshWithLeftPriority(Tiling g, Dictionary<int, Node> idToNode, int maxX, int maxY)
{
//for each node, create four line segments
CreateFourRaysPerVertex(g, maxX, maxY);
Dictionary<LineSegment, int> removeList = new Dictionary<LineSegment, int>();
Dictionary<LineSegment, int> addList = new Dictionary<LineSegment, int>();
for (int iteration = 0; iteration <= Math.Max(maxX, maxY); iteration++)
{
//for each line segment check whether it hits any other segment or point
//if so then create a new junction at that point
for (int nodeIndex1 = 0; nodeIndex1 < g.N; nodeIndex1++)
{
foreach (LineSegment ls1 in g.VList[nodeIndex1].SegmentList.Keys)
{
if (g.VList[nodeIndex1].SegmentList[ls1] == false) continue;
for (int nodeIndex2 = 0; nodeIndex2 < g.N; nodeIndex2++)
{
if (nodeIndex1 == nodeIndex2) continue;
foreach (LineSegment ls2 in g.VList[nodeIndex2].SegmentList.Keys)
{
if (MsaglUtilities.PointIsOnAxisAlignedSegment(ls2, ls1.End))
{
//if they are parallel then create an edge
if (((int)ls1.Start.X == (int)ls1.End.X && (int)ls2.Start.X == (int)ls2.End.X)
|| ((int)ls1.Start.Y == (int)ls1.End.Y && (int)ls2.Start.Y == (int)ls2.End.Y))
{
if ((int)ls1.End.X == (int)ls2.Start.X && (int)ls1.End.Y == (int)ls2.Start.Y) continue;
int a = FindVertexClosestToSegmentEnd(g, ls1);
int b = FindVertexClosestToSegmentEnd(g, ls2);
if (a == b)
{
// degenerate parallel collision
//Point coordinates multiplied by >=3 so that this condition does not arise.
}
if (g.AddEdge(a, b))
{
LineSegment l = new LineSegment(ls1.Start, ls2.Start);
if (!addList.ContainsKey(l)) addList.Add(l, -1);
l = new LineSegment(ls2.Start, ls1.Start);
if (!addList.ContainsKey(l)) addList.Add(l, -1);
if (!removeList.ContainsKey(ls1)) removeList.Add(ls1, nodeIndex1);
if (!removeList.ContainsKey(ls2)) removeList.Add(ls2, nodeIndex2);
}
}
//create a new node at the intersection point
else
{
if (MsaglUtilities.PointIsOnAxisAlignedSegment(ls2, ls1.End) &&
MsaglUtilities.PointIsOnAxisAlignedSegment(ls1, ls2.End) &&
nodeIndex1 > nodeIndex2) continue;
if (g.GetNode((int)ls1.End.X, (int)ls1.End.Y) == -1)
{
//create the edges
int a = FindClosestVertexWhileWalkingToStart(g, ls2, ls1.End);
int b = FindClosestVertexWhileWalkingToEnd(g, ls2, ls1.End);
int c = FindVertexClosestToSegmentEnd(g, ls1);
int d = g.NumOfnodes;
g.VList[d] = new Vertex((int)ls1.End.X, (int)ls1.End.Y) { Id = d };
g.NumOfnodes++;
if (a >= 0) g.AddEdge(a, d);
if (b >= 0) g.AddEdge(b, d);
if (c >= 0) g.AddEdge(c, d);
if (a == b)
System.Diagnostics.Debug.WriteLine("degenerate");
if (a >= 0 && b >= 0) g.RemoveEdge(a, b);
if (!removeList.ContainsKey(ls1) && MsaglUtilities.HittedSegmentComesFromLeft(ls2, ls1))
{
removeList.Add(ls1, nodeIndex1);
if (!addList.ContainsKey(ls1)) addList.Add(ls1, -1);
}
}
else
{
int a = g.GetNode((int)ls1.End.X, (int)ls1.End.Y);
int b = FindVertexClosestToSegmentEnd(g, ls1);
if (b == -1)
System.Diagnostics.Debug.WriteLine("vertex not found error");
g.AddEdge(a, b);
if (!removeList.ContainsKey(ls1) && MsaglUtilities.HittedSegmentComesFromLeft(ls2, ls1))
{
removeList.Add(ls1, nodeIndex1);
if (!addList.ContainsKey(ls1)) addList.Add(ls1, -1);
}
}
}
}
}
}
}
}
foreach (var s in removeList)
{
g.VList[s.Value].SegmentList.Remove(s.Key);
}
removeList.Clear();
foreach (var s in addList)
{
if (s.Value >= 0) g.VList[s.Value].SegmentList.Add(s.Key, true);
else g.VList[g.GetNode((int)s.Key.Start.X, (int)s.Key.Start.Y)].SegmentList.Add(s.Key, false);
}
addList.Clear();
int nodeIndex;
for (nodeIndex = 0; nodeIndex < g.N; nodeIndex++)
{
foreach (LineSegment ls in g.VList[nodeIndex].SegmentList.Keys)
{
if (g.VList[nodeIndex].SegmentList[ls] == false) continue;
var nextWeightedPoint = GrowOneUnit(ls, maxX + 1, maxY + 1);
if (nextWeightedPoint.X >= 0)
{
LineSegment l_new = new LineSegment(ls.Start, nextWeightedPoint);
if (!addList.ContainsKey(l_new)) addList.Add(l_new, nodeIndex);
if (!removeList.ContainsKey(ls)) removeList.Add(ls, nodeIndex);
}
}
}
foreach (var s in removeList)
{
g.VList[s.Value].SegmentList.Remove(s.Key);
}
removeList.Clear();
foreach (var s in addList)
{
if (s.Value >= 0) g.VList[s.Value].SegmentList.Add(s.Key, true);
else g.VList[g.GetNode((int)s.Key.Start.X, (int)s.Key.Start.Y)].SegmentList.Add(s.Key, false);
}
addList.Clear();
}
FixMesh(g);
}