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

Question

根据 Andy Pavlo 先生的出版物，我正在实现径向布局绘制算法 link [第 18 页]

问题是，我的结果包含交叉边。这是 Not Acceptable 。我找到了一些解决方案，类似的问题 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。这将确保您计算的所有角度都以弧度而不是度数为单位。