Canvas图形编辑器-数据结构与History(undo/redo)

2024-04-16 06:28
文章标签 编辑器 数据结构 canvas 图形 history undo redo

本文主要是介绍Canvas图形编辑器-数据结构与History(undo/redo)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Canvas图形编辑器-数据结构与History(undo/redo)

这是作为 社区老给我推Canvas，于是我也学习Canvas做了个简历编辑器 的后续内容，主要是介绍了对数据结构的设计以及History能力的实现。

  • 在线编辑: https://windrunnermax.github.io/CanvasEditor
  • 开源地址: https://github.com/WindrunnerMax/CanvasEditor

关于Canvas简历编辑器项目的相关文章:

  • 社区老给我推Canvas，我也学习Canvas做了个简历编辑器
  • Canvas图形编辑器-数据结构与History(undo/redo)
  • Canvas图形编辑器-我的剪贴板里究竟有什么数据
  • Canvas简历编辑器-图形绘制与状态管理(轻量级DOM)
  • Canvas简历编辑器-Monorepo+Rspack工程实践

描述

对于编辑器而言，History也就是undo和redo是必不可少的能力，实现历史记录的方法通常有两种:

  1. 存储全量快照，也就是说我我们每进行一个操作,都需要将全量的数据通常也就是JSON格式的数据存到一个数组里，如果用户此时触发了redo就将全量的数据取出应用到Editor对象当中。这种实现方式的优点是简单，不需要过多的设计，缺点就是一旦操作的多了就容易炸内存。

  2. 基于Op的实现，Op就是对于一个操作的原子化记录，举个例子如果将图形A向右移动3px，那么这个Op就可以是type: "MOVE", offset: [3, 0]，那么如果想要做回退操作依然很简单，只需要将其反向操作即type: "MOVE", offset: [-3, 0]就可以了，这种方式的优点是粒度更细，存储压力小，缺点是需要复杂的设计以及计算。

既然我们是从零开始设计一个编辑器，那么大概率是不会采用方案1的，我们更希望能够设计原子化的Op来实现History，所以从这个方向开始我们就需要先设计数据结构。

数据结构

我特别推荐大家去看一下 quill-delta 的数据结构设计，这个数据结构的设计非常棒，其可以用来描述一篇富文本，同时也可以用来构建change对富文本做完整的增删改操作，对于数据的compose、invert、diff等操作也一应俱全，而且quill-delta也可以是富文本OT协同算法的实现，这其中的设计还是非常牛逼的。

其实我之前也没有设计过数据结构，更不用谈设计Op去实现历史记录功能了，所以我在设计数据结构的时候是抓耳挠腮、寝食难安，想设计出 quill-delta 这种级别的数据描述几乎是不可能了，所以只能依照我的想法来简单地设计，这其中有很多不完善的地方后边可能还会有所改动。

因为之前也没有接触过Canvas，所以我的主要目标是学习，所以我希望任何的实现都以尽可能简单的方向走。那么在这里我认为任何元素都是矩形，因为绘制矩阵是比较简单的，所以图形元素基类的x, y, width, height属性是确定的，再加上还有层级结构，那么就再加一个z，此外由于需要标识图形，所以还需要给其设置一个id。

class Delta {public readonly id: string;protected x: number;protected y: number;protected z: number;protected width: number;protected height: number;
}

因为我想做一个插件化的实现，也就是说所有的图形都应该继承这个类，那么这个自定义的函数体肯定是需要存储自己的数据，所以在这里加一个attrs属性，又因为想简单实现整个功能，所以这个数据类型就被定义为Record<string, string>。因为是插件化的，每个图形的绘制应该由子类来实现，所以需要定义绘制函数的抽象方法，于是一个数据结构就这么设计好了，关于插件化的设计我们后续可以再继续聊。

abstract class Delta {public readonly id: string;protected x: number;protected y: number;protected z: number;protected width: number;protected height: number;public attrs: DeltaAttributes;public abstract drawing: (ctx: CanvasRenderingContext2D) => void;
}

那么现在已经有了基本的数据结构，我们可以设想一下究竟应该有哪几种操作，经过考虑大概无非是 插入INSERT、删除DELETE、移动MOVE、调整大小RESIZE、修改属性REVISE，这五个Op就可以覆盖我们对于当前编辑器图形的所有操作了，所以我们后续的设计都要围绕着这五个操作来进行。

看起来其实并不难，但实际上想要将其设计好并不容易，因为我们目标是History所以我们不光要顾及正向的操作，还需要设计好invert也就是反向操作，依旧以之前的MOVE操作举例，我们移动一个元素可以使用MOVE(3, 0)，反向操作就可以直接生成也就是MOVE(3, 0).invert = MOVE(-3, 0)，那么RESIZE操作呢，尤其是在多选操作时的RESIZE，我们需要想办法让其能够实现invert操作，一种方法是记录每个点的移动距离，但是这样对于每个Op存储的信息有点过多，我们在构造一个正向的Op时也需要将相关的数据拉到Op中，同样对于REVISE而言我们需要将属性的前值和后值都放在Op中才可以继续执行。

那么如何比较好的解决这个问题呢，很明显如果我们想用轻量的数据来承载内容，那么先前的数据在不一定会使用的情况下我们是没必要存储的，那是不是可以自动提取相关的内容作为invert-op呢，当然是可以的，我们可以在进行invert的时候，将未操作前的Delta一并作为参数传入就好了，我们可以来验证一下，我们的函数签名将会是Op.invert(Delta) = Op'。

// Prev DeltaSet
[{id: "xxx", x: x1, y: y1, width: w1, height: h1}]
// ResizeOp
RESIZE({id: "xxx", x: x2, y: y2})
// Next DeltaSet
[{id: "xxx", x: x1 + x2, y: y1 + y2, width: w1, height: w1}]
// Invert InsertOp
RESIZE({id: "xxx", x: -x2, y: -y2})// Prev DeltaSet
[{id: "xxx", x: x1, y: y1, width: w1, height: h1}]
// ResizeOp
RESIZE({id: "xxx", x: x2, y: y2, width: w2, height: h2})
// Next DeltaSet
[{id: "xxx", x: x2, y: y2, width: w2, height: h2}]
// Invert InsertOp
RESIZE({id: "xxx", x: x1, y: y1, width: w1, height: h1})

看起来是没有问题的，所以我们现在可以设计全量的Op和Invert方法了，在这里因为我最开始是预计要设计组合也就是将几个图形组合在一起操作的能力，所以还预留了一个parentId作为后期开发拓展用，但是暂时是用不上的所以这个字段暂时可以忽略。下面的Invert实际上就是case by case地进行转换，INSERT -> DELETE、DELETE -> INSERT、MOVE -> MOVE、RESIZE -> RESIZE、REVISE -> REVISE。这其中的DeltaSet可以理解为当前的所有Delta数据，类型签名类似于Record<string, Delta>，是扁平的结构，便于数据查找。

export type OpPayload = {[OP_TYPE.INSERT]: { delta: Delta; parentId: string };[OP_TYPE.DELETE]: { id: string; parentId: string };[OP_TYPE.MOVE]: { ids: string[]; x: number; y: number };[OP_TYPE.RESIZE]: { id: string; x: number; y: number; width: number; height: number };[OP_TYPE.REVISE]: { id: string; attrs: DeltaAttributes };
};export class Op<T extends OpType> {public readonly type: T;public readonly payload: OpPayload[T];constructor(type: T, payload: OpPayload[T]) {this.type = type;this.payload = payload;}public invert(prev: DeltaSet) {switch (this.type) {case OP_TYPE.INSERT: {const payload = this.payload as OpPayload[typeof OP_TYPE.INSERT];const { delta, parentId } = payload;return new Op(OP_TYPE.DELETE, { id: delta.id, parentId });}case OP_TYPE.DELETE: {const payload = this.payload as OpPayload[typeof OP_TYPE.DELETE];const { id, parentId } = payload;const delta = prev.get(id);if (!delta) return null;return new Op(OP_TYPE.INSERT, { delta, parentId });}case OP_TYPE.MOVE: {const payload = this.payload as OpPayload[typeof OP_TYPE.MOVE];const { x, y, ids } = payload;return new Op(OP_TYPE.MOVE, { ids, x: -x, y: -y });}case OP_TYPE.RESIZE: {const payload = this.payload as OpPayload[typeof OP_TYPE.RESIZE];const { id } = payload;const delta = prev.get(id);if (!delta) return null;const { x, y, width, height } = delta.getRect();return new Op(OP_TYPE.RESIZE, { id, x, y, width, height });}case OP_TYPE.REVISE: {const payload = this.payload as OpPayload[typeof OP_TYPE.REVISE];const { id, attrs } = payload;const delta = prev.get(id);if (!delta) return null;const prevAttrs: DeltaAttributes = {};for (const key of Object.keys(attrs)) {prevAttrs[key] = delta.getAttr(key);}return new Op(OP_TYPE.REVISE, { id, attrs: prevAttrs });}default:break;}return null;}
}

History

既然我们已经设计好了基于Op的原子化操作以及数据结构，那么紧接着我们就可以开始做History能力了，在这里首先需要注意我们先前对于Invert的思想是让其根据DeltaSet自动先生成InvertOp，在这里我们可以有两种方案来实现。

  1. 第一种方式是在应用Op之前我们先根据当前的DeltaSet自动生成一个InvertOp，然后将这个Op交给History模块存储起来作为Undo的组操作即可。

  2. 第二种方式是我们在应用Op之前首先生成一遍新的Previous DeltaSet，是一个immer的副本，然后将Prev DeltaSet以及Next DeltaSet一并作为OnChangeEvent交给History模块进行后续的操作。

最终我是选择了方案二作为整体实现，倒是没有什么具体依据，只是觉得这个immer的副本可能不仅会在这里使用，作为事件的一部分分发先前的数据值我认为是合理的，所以在应用Op的时候大致实现如下。

public apply(op: OpSetType, applyOptions?: ApplyOptions) {const options = applyOptions || { source: "user", undoable: true };const previous = new DeltaSet(this.editor.deltaSet.getDeltas());switch (op.type) {// 根据不同的`Op`执行不同的操作}this.editor.event.trigger(EDITOR_EVENT.CONTENT_CHANGE, {previous,current: this.editor.deltaSet,changes: op,options,});
}

其实我们也可以看到，整个编辑器内部的通信是依赖于event这个模块的，也就是说这个apply函数不会直接调用History的相关内容，我们的History模块是独立挂载CONTENT_CHANGE事件的。那么紧接着，我们需要设计History模块的数据存储，我们先来明确一下想要实现的内容，现在原子化的Op已经设计好了，所以在设计History模块时就不需要全量保存快照了，但是如果每个操作都需要并入History Stack的话可能并不是很好，通常都是有N个Op的一并Undo/Redo，所以这个模块应该有一个定时器与缓存数组还有最大时间，如果在N毫秒秒内没有新的Op加入的话就将Op并入History Stack，还有就是常规的undo stack以及redo stack，栈存储的内容也不应该很大，所以还需要设置最大存储量。

export class History {private readonly DELAY = 800;private readonly STACK_SIZE = 100;private temp: OpSetType[];private undoStack: OpSetType[][];private redoStack: OpSetType[][];private timer: ReturnType<typeof setTimeout> | null;
}

前边也提到过我们都是通过事件来进行通信的，所以这里需要先挂载事件，并且在这里将Invert的Op构建好，将其置入批量操作的缓存中。

  constructor(private editor: Editor) {this.editor.event.on(EDITOR_EVENT.CONTENT_CHANGE, this.onContentChange, 10);}destroy() {this.editor.event.off(EDITOR_EVENT.CONTENT_CHANGE, this.onContentChange);}private onContentChange = (e: ContentChangeEvent) => {if (!e.options.undoable) return void 0;this.redoStack = [];const { previous, changes } = e;const invert = changes.invert(previous);if (invert) {this.temp.push(invert);if(!this.timer) {this.timer = setTimeout(this.collectImmediately, this.DELAY);}}};

后来我在思考一个问题，如果这N毫秒内用户进行了Undo操作应该怎么办，后来想想实际上很简单，此时只需要清除定时器，将暂存的Op[]立即放置于Redo Stack即可。

  private collectImmediately = () => {if (!this.temp.length) return void 0;this.undoStack.push(this.temp);this.temp = [];this.redoStack = [];this.timer && clearTimeout(this.timer);this.timer = null;if (this.undoStack.length > this.STACK_SIZE) this.undoStack.shift();};

后边就是实际进行redo和undo的操作了，只不过在这里批量操作是使用循环每个Op都需要单独Apply的，这样感觉并不是很好，毕竟需要修改多次，虽然后边的渲染我只会进行一次批量渲染，但是这里事件触发的次数有点多，另外这里有个点还需要注意，我们在History模块里进行的操作，本身不应该再记入History中，所以这里还有一个ApplyOptions的设置需要注意。此外，在undo之后需要将这部分内容再次invert之后入redo stack，反过来也是一样的，此时我们直接取当前编辑器的DeltaSet即可。

  public undo() {this.collectImmediately();if (!this.undoStack.length) return void 0;const ops = this.undoStack.pop();if (!ops) return void 0;this.editor.canvas.mask.clearWithOp();this.redoStack.push(ops.map(op => op.invert(this.editor.deltaSet)).filter(Boolean) as OpSetType[]);this.editor.logger.debug("UNDO", ops);ops.forEach(op => this.editor.state.apply(op, { source: "undo", undoable: false }));}public redo() {if (!this.redoStack.length) return void 0;const ops = this.redoStack.pop();if (!ops) return void 0;this.editor.canvas.mask.clearWithOp();this.undoStack.push(ops.map(op => op.invert(this.editor.deltaSet)).filter(Boolean) as OpSetType[]);this.editor.logger.debug("REDO", ops);ops.forEach(op => this.editor.state.apply(op, { source: "redo", undoable: false }));}

最后

本文我们介绍总结了我们的图形编辑器中数据结构的设计以及History模块的实现，虽然暂时不涉及到Canvas本身，但是这都是作为编辑器本身的基础能力，也是通用的能力可以学习。后边我们可以介绍的能力还有很多，例如复制粘贴模块、画布分层、事件管理、无限画布、按需绘制、性能优化、焦点控制、参考线、富文本、快捷键、层级控制、渲染顺序、事件模拟、PDF排版等等，整体来说还是比较有意思的，欢迎关注我并留意后续的文章。

这篇关于Canvas图形编辑器-数据结构与History(undo/redo)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/908014。

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
DAY16：什么是慢查询，导致的原因，优化方法 | undo log、redo log、binlog的用处 | MySQL有哪些锁

DAY16：什么是慢查询，导致的原因，优化方法 | undo log、redo log、binlog的用处 | MySQL有哪些锁

目录 什么是慢查询，导致的原因，优化方法 undo log、redo log、binlog的用处  MySQL有哪些锁   什么是慢查询，导致的原因，优化方法 数据库查询的执行时间超过指定的超时时间时，就被称为慢查询。 导致的原因： 查询语句比较复杂：查询涉及多个表，包含复杂的连接和子查询，可能导致执行时间较长。查询数据量大：当查询的数据量庞大时，即使查询本身并不复杂，也可能导致
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
第六章习题11.输出以下图形

第六章习题11.输出以下图形

🌏个人博客：尹蓝锐的博客 希望文章能够给到初学的你一些启发～ 如果觉得文章对你有帮助的话，点赞 + 关注+ 收藏支持一下笔者吧～ 1、题目要求： 输出以下图形
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2