为什么径向树布局绘图算法会产生交叉边缘? [英] Why Radial tree layout drawing algorithm is making crossed edges?

问题描述

根据 Mr.Andy Pavlo

我的算法实现

 public void RadialPositions(Tree rootedTree, Node vertex, double alfa, double beta,列表<RadialPoint<string>>输出图){//检查顶点是否是rootedTree的根如果(顶点.IsRoot){顶点.点.X = 0;顶点.点.Y = 0;outputGraph.Add(new RadialPoint){节点 = 顶点，点 = 新点{X = 0,Y = 0},ParentPoint = 空});}//从0开始的顶点深度int depthOfVertex = vertex.Depth;双θ=阿尔法；双半径 = Constants.CircleRadius + (Constants.Delta * depthOfVertex);//在以v为根的子树中留下numberint leaveNumber = BFS.BreatFirstSearch(vertex);foreach (var child in vertex.Children){//在以child为根的子树中留下numberint lambda = BFS.BreatFirstSearch(child);double mi = theta + ((double)lambda/leaveNumber * (beta - alfa));double x = radius * Math.Cos((theta + mi)/2.0);double y = radius * Math.Sin((theta + mi)/2.0);//设置x和ychild.Point.X = x;child.Point.Y = y;outputGraph.Add(new RadialPoint){节点 = 孩子，点 = 新点{X = X，Y = y,半径 = 半径},ParentPoint = vertex.Point});如果(child.Children.Count > 0){child.Point.Y = y;child.Point.X = x;RadialPositions(rootedTree, child, theta, mi, outputGraph);}θ = 米；}}

获取叶子的BFS算法

 public static int BreatFirstSearch(Node root){访问变量 = 新列表<节点>();var queue = new Queue>();int 叶 = 0;访问.添加(根)；queue.Enqueue(root);而(队列.计数！= 0){var current = queue.Dequeue();if (current.Children.Count == 0)叶子++;foreach(current.Children 中的 var 节点){if (!visited.Contains(node)){访问.添加(节点)；queue.Enqueue(节点)；}}}回叶；}

初始调用

 var outputPoints = new List>();alg.RadialPositions(tree, tree.Root,0, 360, outputPoints);

mr.Pavlo 结果

我对简单样本的结果

解决方案

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

I am implementing radial layout drawing algorithm, according to the publication of mr.Andy Pavlo link [page 18]

The problem is, that my result contains crossed edges. Which is something that is unacceptable. I found some solution, similiar problem link but I was not able to implement them into this algorithm (I would have to change the whole approach to the solution). In addition, the algorithm by Mr. Andy Pavlo should be able to solve this problem. When we look at the result of its algorithm, there are no crossed edges here. What am I doing wrong? Am I missing something? Thank you in advance.

Mr.Pavlo pseudo code of algorithm

My implementation of algorithm

        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 algorithm for getting leaves

    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;
    }

Initial call

        var outputPoints = new List<RadialPoint<string>>();
        alg.RadialPositions(tree, tree.Root,0, 360, outputPoints);

mr.Pavlo result

My result on simple sample

解决方案

Math.Cos and Sin expect the input angle to be in radians, not degrees. In your initial method call, your upper angle limit (beta) should be 2 * Math.PI, not 360. This will ensure that all the angles you calculate will be in radians and not degrees.

这篇关于为什么径向树布局绘图算法会产生交叉边缘?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！