为什么径向树布局绘图算法是交叉边缘？

Question

我实现径向布局绘图算法，根据mr.Andy的帕夫洛link[第18页]

的问题是出版，我的结果包含交叉边缘。这是不可接受的。我发现了一些解决方案，类似的问题link但我无法将它们实现到这个算法中（我将不得不改变整个解决方案）。另外，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); 

mr.Pavlo结果

我上简单的样品结果

Answer 1

Math.Cos和Sin期望输入角是在弧度，不是度数。在您的初始方法调用中，您的上限角度（beta）应该是2 * Math.PI，而不是360。这将确保您计算的所有角度都是弧度而不是度数。