• 所有问题

    • 「学习记录」前端可视化之：一种紧凑树形布局算法的实现（简易版）

    如题所述

    举报该问题
    其他回答
    第1个回答  2024-09-04
    前提

    前段时间做了个与流程图相关的需求，这需求中涉及到了一个自动调整布局的功能

    这让我这个算法小白着实是想破的头脑

    但是总算让我找到了一种布局算法，可用于调整流程图等可视化节点图的布局，让页面空间利用率更高

    这就是今天要说的紧凑树形布局算法

    目标

    熟悉该算法的简易实现

    文章参考以及示例代码

    这里要感谢两位大佬的代码，让我受益匪浅

    后面的内容都是参考大佬们的代码后的一种简易实现

    如果想更深入了解可以去大佬们的githubclone下来慢慢研究

    一种紧凑树形布局算法的实现

    基于vue和jsplumb的工作流编辑器开发(二)

    我的演示代码

    前端可视化之：一种紧凑树形布局算法的实现（简易版）

    预期效果

    下面是我们想要做到的预期效果，由于本文只研究节点布局，不涉及连线，所以在此忽略了连线的步骤。

    我们想要做到的效果如下，相邻节点之间有着最小间距，不会重叠。

    所有分支节点都基于父节点居中。

    这样的布局首先就是美观，而且空间利用率高。

    模拟tree数据

    首先我们来mock一下我们需要的tree数据

    通常后端给到我们的是一个一维对象数组

    这里只有一些简单的name，id，parent，children，

    父子节点关系参考上面的图片

    exportconsttreeInitData=[{name:'node-10',id:10,parent:'',children:[1]},{name:'node-1',id:1,parent:10,children:[2,3,4]},{name:'node-2',id:2,parent:1,children:[5,6,8]},{name:'node-3',id:3,parent:1,children:[7,9]},{name:'node-4',id:4,parent:1,children:[]},{name:'node-5',id:5,parent:2,children:[]},{name:'node-6',id:6,parent:2,children:[]},{name:'node-7',id:7,parent:3,children:[]},{name:'node-8',id:8,parent:2,children:[]},{name:'node-9',id:9,parent:3,children:[]}];

    初始化一些页面常量

    接下来，我们创建一个html文件，引入我们的vue包，利用vue的模板渲染进行布局，当然你用react也是一样的，任何渲染器都可以，这里只讨论算法实现

    先展示一些样式信息

    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>一种紧凑树形布局算法的实现(简易版)</title><style>html,body{margin:0;padding:0;border:0;}#treeBox{width:100vw;height:100vh;position:relative;background-color:#eeeeee;}.treeNode{position:absolute;background-color:#ffffff;text-align:center;line-height:40px;}</style></head></html>

    接着是模板语法部分

    <body><divid="app"><divid="treeBox"><divclass="treeNode"v-for="nodeinlayoutTree":key="node.id":style="getStyle(node)">{{node.id}}</div></div></div></body>

    接着是vue的状态部分data，函数部分

    <scriptsrc="https://ability-1251624226.file.myqcloud.com/base/vue.min.js"></script><scripttype="module">import{treeInitData}from"./treeInitData2.js"constNODE_SIZE=40constY_INTERVAL=100constX_INTERVAL=150constBOX_WIDTH=document.getElementById('treeBox').offsetWidthconstMID_WIDTH=BOX_WIDTH/2newVue({data(){return{treeInitData,treeData:null,layoutTree:[],hashTree:[],rootNode:null}},mounted(){},methods:{getStyle(node){return{left:node.left+'px',top:node.top+'px',width:NODE_SIZE+'px',height:NODE_SIZE+'px'}},},}).$mount('#app')</script>

    这里重点讲一下几个常量的意思：

    NODE_SIZE:节点宽高

    Y_INTERVAL:纵向间距

    X_INTERVAL:横向最小间距

    BOX_WIDTH:容器盒子宽度

    MID_WIDTH:容器盒子宽度的一半（中线）

    这几个常量在实际开发中可以根据不同分辨率来调整

    构造布局树，根节点，hashTree

    我们在上面的data中看到layoutTree，hashTree，rootNode三个响应式数据

    layoutTree是我们用来在模板语法中布局用的一维数组，存在left和top两个字段

    hashTree是一个二维数组，记录了每一层的节点

    rootNode是根节点，是我们进行树的遍历的入口

    接下来我们就来构建这三个东西：

    <scripttype="module">import{treeInitData}from"./treeInitData2.js"constNODE_SIZE=40constY_INTERVAL=100constX_INTERVAL=150constBOX_WIDTH=document.getElementById('treeBox').offsetWidthconstMID_WIDTH=BOX_WIDTH/2newVue({data(){return{treeInitData,treeData:null,layoutTree:[],hashTree:[],rootNode:null}},mounted(){const{layoutTree,rootNode,hashTree}=this.Array2Tree(this.treeInitData)this.layoutTree=layoutTreethis.rootNode=rootNodethis.hashTree=hashTree},methods:{getStyle(node){return{left:node.left+'px',top:node.top+'px',width:NODE_SIZE+'px',height:NODE_SIZE+'px'}},Array2Tree(arr){//创建布局树letlayoutTree=arr.map(item=>{return{...item,left:0,top:0}})//创建树结构并找到根节点lettreeMap={}layoutTree.forEach(element=>{treeMap[element.id]=element});layoutTree.forEach(item=>{if(item.children){item.children=item.children.map(id=>treeMap[id])}})letrootNode=layoutTree.find(item=>!item.parent)//创建哈希树，获取层级关系lethashTree=[]//hashTree[zindex]=[hashTree]constgetHashTree=(root,hashTree,zindex)=>{if(!root){return}if(hashTree[zindex]){hashTree[zindex].push(root)}else{hashTree[zindex]=[root]}root.children.forEach(node=>{getHashTree(node,hashTree,zindex+1)})}getHashTree(rootNode,hashTree,0)console.log(layoutTree,rootNode,hashTree)return{layoutTree,rootNode,hashTree}}},}).$mount('#app')</script>

    在上面的代码中，我们用数组方法map去构造layoutTree，给它加上了left:0,top:0。我们给节点初始坐标为（0，0），

    接着，我们找到rootNode，并进一步改造layoutTree，通过foreach把children改造成对象数组，

    接着，我们利用递归调用getHashTree，创建一个hashTree，这里递归的用法比较简单，不做解析。

    有了这三个数据，我们可以开始布局

    开始布局

    布局整体上分为三个步骤：

    Y轴纵向布局

    X轴横向布局

    X轴子节点调整

    我们算法的核心是最后一个，X轴子节点调整。

    Y轴纵向布局

    这个布局比较简单，由于我们以及拥有了表示层级关系的hashTree，

    很轻松的就可以完成Y轴方向上的设置

    //布局YLayout_Y(){for(leti=0;i<this.hashTree.length;i++){for(letj=0;j<this.hashTree[i].length;j++){this.hashTree[i][j].top=Y_INTERVAL*i+NODE_SIZE*i}}},

    接着我们在钩子中调用：

    mounted(){const{layoutTree,rootNode,hashTree}=this.Array2Tree(this.treeInitData)this.layoutTree=layoutTreethis.rootNode=rootNodethis.hashTree=hashTree//纵向布局this.Layout_Y()},

    我们来看看效果

    可以看到Y轴方向上的设置已经完成，后续布局也不需要再进行变化

    X轴横向布局

    这一步我们要做到的效果是根据设定的X最小横向距离去进行布局，

    这就有些难度了，可能不同人会有不一样的写法，这里我选用的是递归的方式，进行树的深度优先遍历

    先贴代码

    Layout_X(){this.layout_X_deep(this.rootNode,MID_WIDTH)},layout_X_deep(node,leftVal){if(!node)return;//距离中线居中显示node.left=leftVal-NODE_SIZE/2//子节点宽度letlineWidth=(node.children.length-1)*X_INTERVAL+node.children.length*NODE_SIZEletbaseLeft=leftVal-lineWidth/2//遍历子节点for(leti=0;i<node.children.length;i++){this.layout_X_deep(node.children[i],baseLeft+NODE_SIZE/2+i*(NODE_SIZE+X_INTERVAL))}},

    同样的我们在钩子函数里调用一下

    mounted(){const{layoutTree,rootNode,hashTree}=this.Array2Tree(this.treeInitData)this.layoutTree=layoutTreethis.rootNode=rootNodethis.hashTree=hashTree//纵向布局this.Layout_Y()//初始化横向布局this.Layout_X()},

    我们来解读一些关键代码：

    红框1代码：调用递归函数，传入根节点，与容器中线，注意后面传入的参数也是该节点中线坐标。

    红框2代码：设置节点横坐标，由于考虑节点宽高，需要中线坐标减去减去节点坐标的一半

    红框3代码：求得所有子节点的宽度，需要考虑节点本身的宽度，即：节点数量x节点宽度+（节点数量-1）x最小节点纵向间距，最后用传入的leftval减去这个值的一半，就是子节点的起始坐标

    红框4代码：遍历子节点，传入子节点的中线坐标

    最后的效果如下：

    我们可以看到，在节点2与节点3的子节点中，有重叠的部分，接下来算法的核心就是处理这样的情况。

    X轴子节点调整

    这一块是整个布局算法的核心，我们会再次用带hashTree这个数据结构，再次献上上面的图片

    我们先甩一个调整步骤，接下来再用代码去实现

    步骤1：倒序遍历hashTree，从最后一层开始，两两节点对比left值，存在重叠或者小于最小间距的情况，找到其共同祖先节点下的同层子节点（比如上面的节点2，与节点3）

    步骤2：根据重叠节点的差值与最小横向间距，算出整个节点3以及子树需要向右偏移多少才能消除节点重叠的情况，即偏移量leftOffset，然后整体把子树3向右偏移leftOffset。

    步骤3：由于已经进行了子树偏移，需要重新居中一下整个布局，这时候我们找到刚刚节点3的父节点1，根据子节点的数量区分单分支与多分支的情况，算出需要偏移的量，再次对节点1所有的子树进行移动

    步骤4：由于已经进行了子树偏移，我们需要又返回最后一层重新进行遍历比较，直到布局完毕

    所以整个布局流程主要分为以上3步

    代码如下：

    遍历hashTree的代码

    在这里主要是对hashTree进行遍历，然后进行同层俩俩节点判断，在这里leftoffset的计算公示为（最小横向间距+节点宽度-后前俩节点left值的差），然后进行子树移动，再进行居中调整，最后把i设置为最后一层重新遍历。

    节点与子树偏移的代码

    这里运用了递归

    居中调整的代码

    这里主要是针对单子节点与多子节点的情况算出leftoffset，再整体移动子树

    这里关注一下红框内的计算代码

    (nextFlowItemLatest.left-nextFlowItemFirst.left)/2算出子节点整体长度

    (nextFlowItemFirst.left+(nextFlowItemLatest.left-nextFlowItemFirst.left)/2)算出当前子节点的中线

    flowItem.left-(nextFlowItemFirst.left+(nextFlowItemLatest.left-nextFlowItemFirst.left)/2)?与父节点的中线相减就是需要移动的位移

    总结下来就是：找到重叠，移动子树，居中调整，再次遍历hashtree

    运用场景

    该布局的可运用于含树型结构的可视化展示中

    比如一些自动排列功能

    可以很有效的提高空间利用率

    希望大家如果遇到了类似的需求情况

    也可以用上这个算法

    原文：https://juejin.cn/post/7101485031981318174

    logo设计

    创造品牌价值

    ¥500元起

    APP开发

    量身定制，源码交付

    ¥2000元起

    商标注册

    一个好品牌从商标开始

    ¥1480元起

    公司注册

    注册公司全程代办

    ¥0元起

    查

    看

    更

    多

      官方电话官方服务
        官方网站八戒财税知识产权八戒服务商企业需求数字市场
    相似回答
    大家正在搜