美文网首页
树状图布局算法

树状图布局算法

作者: 客昂康 | 来源:发表于2021-02-22 12:01 被阅读0次

    TreeLayout.js:

    var TreeLayout = {
        //递归求左边界
        f1:function(obj, array, depth){
            if((typeof obj.child === "object") && (obj.child.length > 0)){
                var x = obj.child[0].x;
                if(typeof array[depth+1] === "undefined"){
                    array[depth+1] = x;
                }else{
                    if(x < array[depth+1]){
                        array[depth+1] = x;
                    }
                }
                for(var i=0; i<obj.child.length; i++){
                    this.f1(obj.child[i], array, depth+1);
                }
            }
        },
        
        //递归求右边界
        f2:function(obj, array, depth){
            if((typeof obj.child === "object") && (obj.child.length > 0)){
                var x = obj.child[obj.child.length-1].x;
                if(typeof array[depth+1] === "undefined"){
                    array[depth+1] = x;
                }else{
                    if(x > array[depth+1]){
                        array[depth+1] = x;
                    }
                }
                for(var i=0; i<obj.child.length; i++){
                    this.f2(obj.child[i], array, depth+1);
                }
            }
        },
        
        //求左边界,返回新的数组。
        f3:function(obj){
            var left = [];
            left[0] = obj.x;
            this.f1(obj, left, 0);
            return left;
        },
        
        //求右边界,在旧数组上修改。
        f4:function(obj, right){
            right[0] = obj.x;
            this.f2(obj, right, 0);
        },
        
        //通过左右边界计算偏移量
        f5:function(right, left){
            var number = left.length < right.length ? left.length : right.length;
            var depth  = left.length > right.length ? left.length : right.length;
            var offset = right[0] - left[0];
            for(var i=1; i<number; i++){
                if(right[i]-left[i] > offset){
                    offset = right[i] - left[i];
                }
            }
            return offset + 1 + (depth-1)*0.2;
        },
        
        //平移所有节点
        f6:function(obj, offset){
            obj.x += offset;
            if((typeof obj.child === "object") && (obj.child.length > 0)){
                for(var i=0; i<obj.child.length; i++){
                    this.f6(obj.child[i], offset);
                }
            }
        },
        
        //计算所有节点横向虚拟位置,稍后根据画布尺寸以及横竖要求计算所有节点真实位置。
        f7:function(obj){
            if((typeof obj.child === "object") && (obj.child.length > 0)){
                var right = [];                                                 //右边界
                for(var i=0; i<obj.child.length; i++){                          //
                    this.f7(obj.child[i]);                                      //
                    if(i>0){                                                    //
                        this.f4(obj.child[i-1], right);                         //把前面所有子树当做整体,更新这个整体的右边界。
                        var left = this.f3(obj.child[i]);                       //取这个子树的左边界
                        var offset = this.f5(right, left);                      //左右边界比较,求这个子树的偏移量
                        this.f6(obj.child[i], offset);                          //整体移动这个子树
                    }
                }
                obj.x = (obj.child[0].x + obj.child[obj.child.length-1].x) / 2; //父节点在第一个子节点和最后一个子节点的中间。
            }else{
                obj.x = 0;
            }
        },
        
        //计算总深度和总宽度
        f8:function(obj){
            var right = [];
            this.f4(obj, right);
            var maxW = right[0];
            for(var i=1; i<right.length; i++){
                if(maxW < right[i]){
                    maxW = right[i];
                }
            }
            return [maxW, right.length-1];
        },
        
        //根据画布位置和尺寸以及横竖布局来确定所有节点的最终位置
        f9:function(obj, depth, offsetX, offsetY, ratioW, ratioH, horizontal){
            if(horizontal){
                obj.y = Math.round(depth * ratioH + offsetY);
                obj.x = Math.round(obj.x * ratioW + offsetX);
            }else{
                obj.y = Math.round(obj.x * ratioH + offsetY);
                obj.x = Math.round(depth * ratioW + offsetX);
            }
            if((typeof obj.child === "object") && (obj.child.length > 0)){
                for(var i=0; i<obj.child.length; i++){
                    this.f9(obj.child[i], depth+1, offsetX, offsetY, ratioW, ratioH, horizontal);
                }
            }
        },
        
        //横向布局
        horizontal:function(obj, x, y, w, h){
            this.f7(obj);
            var size = this.f8(obj);
            this.f9(obj, 0, x, y, w/size[0], h/size[1], true);
        },
        
        //竖向布局
        vertical:function(obj, x, y, w, h){
            this.f7(obj);
            var size = this.f8(obj);
            this.f9(obj, 0, x, y, w/size[1], h/size[0], false);
        }
    };
    

    用法举例:
    测试数据TreeData.js:

    var treeData = {
        name:"",
        child:[
            {
                name:"",
                child:[
                    {
                        name:"",
                        child:[
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:""
                                    }
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""},
                                            {name:""}
                                        ]
                                    }
                                ]
                            }
                        ]
                    },
                    {
                        name:"",
                        child:[
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    }
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:""
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    },
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""},
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                ]
                            }
                        ]
                    }
                ]
            },
            {
                name:"",
                child:[
                    {name:""},
                    {
                        name:"",
                        child:[
                            {name:""},
                            {name:""},
                            {name:""},
                            {
                                name:"",
                                child:[
                                    {name:""},
                                    {name:""},
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    }
                                ]
                            }
                        ]
                    },
                    {
                        name:""
                    },
                    {
                        name:"",
                        child:[
                            {name:""},
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    }
                                ]
                            }
                        ]
                    },
                    {
                        name:""
                    },
                    {
                        name:""
                    },
                    {
                        name:"",
                        child:[
                            {name:""},
                            {name:""},
                            {name:""},
                            {name:""}
                        ]
                    },
                    {
                        name:""
                    }
                ]
            },
            {
                name:"",
                child:[
                    {
                        name:"",
                        child:[
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""},
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:""
                                    },
                                    {
                                        name:""
                                    },
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                ]
                            }
                        ]
                    },
                    {
                        name:"",
                        child:[
                            {
                                name:"",
                                child:[
                                    {
                                        name:""
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:""
                                    },
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    }
                                ]
                            },
                            {
                                name:""
                            }
                        ]
                    },
                    {
                        name:"",
                        child:[
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    }
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:""
                                    }
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:""
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:""
                                    }
                                ]
                            }
                        ]
                    },
                    {
                        name:"",
                        child:[
                            {
                                name:""
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""},
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""}
                                        ]
                                    }
                                ]
                            },
                            {
                                name:"",
                                child:[
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    },
                                    {
                                        name:""
                                    },
                                    {
                                        name:"",
                                        child:[
                                            {name:""},
                                            {name:""}
                                        ]
                                    }
                                ]
                            }
                        ]
                    }
                ]
            }
        ]
    };
    

    测试程序test.html:

    <!DOCTYPE html>
    <html>
        <head>
            <meta charset="utf-8">
            <title>树状图布局算法测试</title>
            <script src="TreeLayout.js"></script>
            <script src="TreeData.js"></script>
            <style>
                body {
                    margin:0;
                    padding:0;
                    font:14px YaHei,'Microsoft YaHei',Arial,Helvetica,sans-serif;
                }
                
                #svgbox {
                    margin:0;
                    padding:0;
                    border:1px solid #f80;
                }
            </style>
        </head>
        
        <body>
            <svg id="svgbox" width="1600" height="500"></svg>
        </body>
        <script>
            var svgbox = document.getElementById("svgbox");
            
            function drawNode(x, y){
                var node = document.createElementNS("http://www.w3.org/2000/svg", "circle");
                node.setAttribute("cx", x);
                node.setAttribute("cy", y);
                node.setAttribute("r", "7");
                node.setAttribute("stroke", "#444");
                node.setAttribute("stroke-width", "1.5");
                node.setAttribute("fill", "#fff");
                svgbox.appendChild(node);
            }
            
            function drawLine(x1, y1, x2, y2){
                var line = document.createElementNS("http://www.w3.org/2000/svg", "line");
                line.setAttribute("x1", x1);
                line.setAttribute("y1", y1);
                line.setAttribute("x2", x2);
                line.setAttribute("y2", y2);
                line.setAttribute("stroke", "#444");
                line.setAttribute("stroke-width", "1.5");
                svgbox.appendChild(line);
            }
            
            function drawTree(obj){
                if(obj.child){
                    for(var i=0; i<obj.child.length; i++){
                        drawLine(obj.x, obj.y, obj.child[i].x, obj.child[i].y);
                        drawTree(obj.child[i]);
                    }
                }
                drawNode(obj.x, obj.y);
            }
            
            TreeLayout.horizontal(treeData, 50, 50, 1500, 400);
            //TreeLayout.vertical(treeData, 50, 50, 400, 1500);
            drawTree(treeData);
        </script>
    </html>
    

    测试效果:


    横向布局效果

    相关文章

      网友评论

          本文标题:树状图布局算法

          本文链接:https://www.haomeiwen.com/subject/ekbhfltx.html