为什么径向树布局绘图算法会产生交叉边？

Question

根据 mr.Andy Pavlo link [第 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);

mr.Pavlo 结果

我的简单样本结果

Answer 1

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

为什么径向树布局绘图算法会产生交叉边？

Why Radial tree layout drawing algorithm is making crossed edges?

c#

algorithm

tree

graph-visualization

radial