站长资源网页制作
如何使用canvas绘制可移动网格的示例代码
本文主要介绍了如何使用canvas绘制可移动网格的示例代码,分享给大家,具体如下:
效果
说明
这个是真实项目中遇到的需求,我把它抽离出来,屏蔽了那些业务相关的东西,仅从代码角度来考虑这个问题。首先网格大小可配置,每个顶点是可以移动的。看到这个问题,不知道各位是怎么去思考的。就先来说说我自己的思路。
分析
首先需要有一个起点,这样就能确定网格所在的位置,其次就是网格中的每个正方形(我们就按正方形来思考,这样简单一点)的边长是多少,另外每个顶点移动的时候,边也需要跟着移动。
所以其实要存储的就只有两类对象,一类就是线,另外就是顶点。
如何存储顶点和线呢?这里用了一个库fabric.js
,就比较容易的创建顶点和边的对象,并且它也提供了移动边的方法,但是问题也同时出现了:按照上面的显示,一个点最多关联4条边,最少也关联了2条边,如何表示这种顶点和边的关联关系呢?
先想到就是使用数组来存储顶点和线,然后再根据线中包含的顶点坐标来判断这个线是否和某个顶点相连,如果是的话,则将将其加入到顶点的关联属性中。后面当移动顶点的时候,根据顶点拿到其关联的线,去动态改变线的坐标,这样就能实现上面的那种效果了。
实现
下面根据以上分析,我们来实现代码。首先需要存储的对象有顶点、边。然后根据起点坐标以及每个小矩形的边长,很容易就可以计算出所有的顶点坐标。
function Grid({node, unit, row, col, matrix = []}) { // 存储顶点 this.vertexes = []; // 存储边 this.lines = []; // 根据起点坐标以及单位边长计算 for (let i = 0; i <= row; i++) { for (let j = 0; j <= col; j++) { const newVertex = makeRect(node.x + i * unit, node.y + j * unit); this.vertexes.push(newVertex); } } // 添加顶点对象的事件监听器 this.addListener(); }
那么边怎么计算呢,构造边的话,只需要两个顶点就可以连成边,因此我们可以选择遍历顶点来构造边,但是这样的话会造成重复的边,而我们只需要一条边就可以了,不然移动的话,你会发现移动完,下面还会显示一条重叠的边。当然其实最重要的原因就是效率问题,如果不去重的话,会导致计算的时间复杂度过高。
现在有两种方法来解决,一种就是给顶点做标记,当前做线的两端的顶点已经标记过了,那么就跳过当前轮的遍历。另外一种方法,就是可以根据网格这种特定的形状来获取边,如下图,按照两种不同的颜色来计算水平的边和垂直的边。
这样的话,水平方向,就每行两两构成边,垂直方向,就按照一定的间隔连接两个顶点构成边。这里因为后面需要传给算法的格式是二维数组,因此就使用了这个方法。
// ...省略了 // 构造矩阵 this.matrix = []; let index = -1; for (let i = 0; i < this.vertexes.length; i++) { if (i % (col + 1) === 0) { index++; this.matrix[index] = []; } this.matrix[index].push(this.vertexes[i]); } // 根据矩阵添加边 let idx = 0; for (let i = 0; i < this.matrix.length; i++) { for (let j = 0; j < this.matrix[i].length; j++) { // 交叉渲染边,这样能够在可视区内优先展示 this.matrix[i][j+1] && this.makeLine(this.matrix[i][j], this.matrix[i][j+1]); this.vertexes[idx + col + 1] && this.makeLine(this.vertexes[idx], this.vertexes[idx + col + 1]); idx++; } }
后面就是找每个顶点关联了几条边
for (let i = 0; i < this.vertexes.length; i++) { const vertex = this.vertexes[i]; // 根据顶点的坐标是否是边的两端的开始或结束坐标来判断顶点是否与这条边关联 const associateLines = this.lines.filter(item => { return (item.x1 === vertex.left && item.y1 === vertex.top) || (item.x2 === vertext.left && item.y2 === vertex.top); }); vertex.lines = associateLines; }
眼精的同学肯定一眼就看出来啦,这个时间复杂度太高了。所以虽然网格画出来了,但是当顶点数量过多的时候,计算时间太长,导致浏览器卡住了了差不多2s往上,当水平方向有50个顶点,垂直方向有50个顶点,就能明显看到浏览器的卡顿,此时如果有输入框之类的交互UI,是无法做任何操作的,这肯定也是不行滴。
改进
那么有什么方法能够高效的找到顶点和边之间的关联呢?这里就不卖关子了,当然可能还有其他更好的方法,但是笔者知识所限,只能到这啦。
解决办法就是图这种结构,因为图的边可以使用邻接表或者是邻接矩阵来存储,这样如果我存储了一个顶点,那么与这个顶点关联的边其实就确定了,也就是说,我们在添加顶点的时候,就顺便
解决了这种顶点的关联问题,不再需要再次遍历所有的边来找关联了。(这里就不详细介绍图这种数据结构了,有兴趣的同学可以自己查找资料,实际这里运用图的地方也就是这个边和顶点的关联关系,其他什么图的遍历都没有用到)
我们来改进一下我们的代码。
function Grid({node, unit, row, col, matrix = []}) { this.vertexes = []; this.lines = []; this.edges = new Map(); this.addEdges = addEdges; this.addVertexes = addVertexes; }
这里添加了一个新的属性edges
,来存储顶点和边的映射关系。其他的步骤和先前都是一样的,只是更换了添加顶点和边的方法,什么意思呢,看代码其实明白了:
function Grid({node, unit, row, col, matrix = []}) { // ...省略 // 根据矩阵添加边 let idx = 0; for (let i = 0; i < this.matrix.length; i++) { for (let j = 0; j < this.matrix[i].length; j++) { // 交叉渲染边,这样能够在可视区内优先展示 this.matrix[i][j+1] && this.addEdges(this.matrix[i][j], this.matrix[i][j+1]); this.vertexes[idx + col + 1] && this.addEdges(this.vertexes[idx], this.vertexes[idx + col + 1]); idx++; } } // 将边关联到顶点 this.edges.forEach((value, key) => { key.lines = value; }); }
这里我们就将复杂度为O(mn)
的计算降低为了O(n)
,这里m
为lines
的长度,n
为vertexes
的长度。然后再来看下此时计算100*100的顶点数,计算时间只有200ms
,已经能够满足我的需求了。那么图是如何实现这种关联的呢,其实就是每次添加边的时候,将边的两个顶点同时添加进关联关系中,也就是Map
的结构中。
function addEdges(v, w) { const line = makeLine({point1: v, point2: w}); // 顶点v关联了边line this.edges.get(v).push(line); // 顶点w也同时关联了边line this.edges.get(w).push(line); this.lines.push(line); } function addVertexes(v) { this.vertexes.push(v); // 给每个顶点设置一个Map结构 this.edges.set(v, []); }
这样计算完所有的顶点之后,实际顶点关联的边也都确定了,最后只需要遍历一下这些edges
就可以了。
完成了这些之后,开开心心的调用fabric
的api,将这些对象添加进canvas
中就可以了。
// fabric的API,添加fabric对象到画布中 canvas.add(...this.vertexes); canvas.add(...this.lines);
好了,大功告成,可以交差了。运行页面,打开一看,好家伙,计算速度是快了很多,但是渲染的速度惨不忍睹,30*30的顶点数量,页面还是有卡顿的情况,这是怎么回事呢?
仔细想想,添加这么多的对象到画布中,计算量确实是非常大的,但是这里我们也无法改变这种渲染消耗。于是想到了一个折中的方法,就是利用时间切片,简单来说,就是利用requestAnimationFrame
这个API,将渲染任务分割为一个一个的片段,在浏览器空闲时去渲染,这样就不会去阻塞其他浏览器的任务。这里就涉及了一些浏览器渲染的相关知识。
function renderIdleCallback(canvas) { // 任务切片 const points = this.points.slice(); const lines = this.lines.slice(); const task = () => { // 清理canvas的时候,中断后面的渲染 if (this.interrupt) return; if (!points.length && !lines.length) return; let slicePoint = [], sliceLine = []; for (let i = 0; i < 10; i++) { if (points.length) { const top = points.shift(); slicePoint.push(top); } if (lines.length) { const top = lines.shift(); sliceLine.push(top); } } canvas.add(...slicePoint); canvas.add(...sliceLine); window.requestAnimationFrame(task); } task(); }
上面的代码加入了一个标识符来中断渲染,因为存在这样一种情况,本次网格还没有渲染完,就被清理掉又重新渲染,那么就需要停止上次的渲染,重新开始新的渲染了。
总结
好了,到这里也就结束了。由于笔者知识浅薄,只能做到这种满足需求的优化了,更极致的优化就要看各位大佬指点。同时此次尝试也是笔者第一次将所学的数据结构、优化手段结合到项目中,成就感还是非常多的,也是感受到数据结构算法对于程序员的重要性,如果想要突破自己的技术瓶颈,那么这也是绕不开的一个点。