爲什麼徑向樹佈局繪圖算法是交叉邊緣？

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。這將確保您計算的所有角度都是弧度而不是度數。