根据mr.Andy Pavlo链接 [第18页]的发布，我正在实施径向布局绘图算法
问题是，我的结果包含交叉边缘。这是不可接受的。我找到了一些解决方案，类似的问题链接，但我无法将它们实现到这个算法中（我必须改变整个解决方案的方法）。另外，Andy Pavlo 先生的算法应该可以解决这个问题。当我们查看其算法的结果时，这里没有交叉边。我究竟做错了什么？我错过了什么吗？先感谢您。
Mr.Pavlo 算法伪代码
我的算法实现
public void RadialPositions(Tree<string> rootedTree, Node<string> vertex, double alfa, double beta,
List<RadialPoint<string>> outputGraph)
{
//check if vertex is root of rootedTree
if (vertex.IsRoot)
{
vertex.Point.X = 0;
vertex.Point.Y = 0;
outputGraph.Add(new RadialPoint<string>
{
Node = vertex,
Point = new Point
{
X = 0,
Y = 0
},
ParentPoint = null
});
}
//Depth of vertex starting from 0
int depthOfVertex = vertex.Depth;
double theta = alfa;
double radius = Constants.CircleRadius + (Constants.Delta * depthOfVertex);
//Leaves number in the subtree rooted at v
int leavesNumber = BFS.BreatFirstSearch(vertex);
foreach (var child in vertex.Children)
{
//Leaves number in the subtree rooted at child
int lambda = BFS.BreatFirstSearch(child);
double mi = theta + ((double)lambda / leavesNumber * (beta - alfa));
double x = radius * Math.Cos((theta + mi) / 2.0);
double y = radius * Math.Sin((theta + mi) / 2.0);
//setting x and y
child.Point.X = x;
child.Point.Y = y;
outputGraph.Add(new RadialPoint<string>
{
Node = child,
Point = new Point
{
X = x,
Y = y,
Radius = radius
},
ParentPoint = vertex.Point
});
if (child.Children.Count > 0)
{
child.Point.Y = y;
child.Point.X = x;
RadialPositions(rootedTree, child, theta, mi, outputGraph);
}
theta = mi;
}
}
获取叶子的 BFS 算法
public static int BreatFirstSearch<T>(Node<T> root)
{
var visited = new List<Node<T>>();
var queue = new Queue<Node<T>>();
int leaves = 0;
visited.Add(root);
queue.Enqueue(root);
while (queue.Count != 0)
{
var current = queue.Dequeue();
if (current.Children.Count == 0)
leaves++;
foreach (var node in current.Children)
{
if (!visited.Contains(node))
{
visited.Add(node);
queue.Enqueue(node);
}
}
}
return leaves;
}
初次通话
var outputPoints = new List<RadialPoint<string>>();
alg.RadialPositions(tree, tree.Root,0, 360, outputPoints);
帕夫洛先生结果
我在简单样本上的结果
