树状图布局算法

2021-02-22  本文已影响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>

测试效果:


横向布局效果
上一篇下一篇

猜你喜欢

热点阅读