圖形編輯器開(kāi)發(fā)：參考線吸附效功能，讓圖形自動(dòng)對(duì)齊
最近我給圖形編輯器增加了參照線吸附功能，講講我的實(shí)現(xiàn)思路。
我正在開(kāi)發(fā)的圖形設(shè)計(jì)工具：
https://github.com/F-star/suika
線上體驗(yàn)：
https://blog.fstars.wang/app/suika/
效果是被移動(dòng)的圖形會(huì)參考周圍圖形，自動(dòng)與它們進(jìn)行吸附對(duì)齊。
不得不說(shuō)，很酷炫。
感覺(jué)這個(gè)圖形編輯器突然變得靈動(dòng)起來(lái)，有了靈魂一般。
為什么需要參照線吸附功能？
這里的參照線，指的是在移動(dòng)目標(biāo)圖形時(shí)，當(dāng)靠近其他圖形的包圍盒的延長(zhǎng)線（看不見(jiàn)）時(shí)，會(huì)（1）繪制出最近的延長(zhǎng)線和延長(zhǎng)線上的點(diǎn)，（2）并將目標(biāo)圖形吸附上去，輕松實(shí)現(xiàn)（3）對(duì)齊的效果。
可以看到，通過(guò)參照線，我們很容易就能實(shí)現(xiàn)各種對(duì)齊，比如兩圖形的底邊和定邊對(duì)齊、右下角和左上角對(duì)齊。
這在 以對(duì)齊為基本要素 的視覺(jué)設(shè)計(jì)中，是非常好用的功能。
整體思路
整體思路為：
- 記錄參照線。
- 找出目標(biāo)圖形最靠近的水平參照線和垂直參照線。
- 計(jì)算出偏移值 offsetX、offsetY。
- 標(biāo)記要繪制的所有參照線段（不是兩端無(wú)限延長(zhǎng)的）。
- 修正圖形的 x、y。
- 繪制參照線和點(diǎn)。
記錄參照線
首先是確定能夠作為 “參照” 的參照?qǐng)D形。
通常來(lái)說(shuō)，參照?qǐng)D形為視口內(nèi)的圖形，并排除掉被移動(dòng)的目標(biāo)圖形。視口外的圖形通常都不在設(shè)計(jì)師的關(guān)注區(qū)域內(nèi)。
確認(rèn)好參照?qǐng)D形后，計(jì)算出它們的包圍盒（bbox）。
這次的包圍盒有點(diǎn)特殊，要多給一個(gè)中點(diǎn)坐標(biāo)，因?yàn)橹芯€也要作為參照線。
接口簽名為：
export interface IBoxWithMid {
minX: number;
minY: number;
midX: number;
midY: number;
maxX: number;
maxY: number;
}它們組成了參照?qǐng)D形的 8 個(gè)點(diǎn)，沿著這些點(diǎn)繪制豎線和橫線，就是被移動(dòng)的目標(biāo)圖形對(duì)應(yīng)要吸附的參照線。
被移動(dòng)的圖形也要計(jì)算包圍盒，并得到 5 個(gè)點(diǎn)。
基于這些點(diǎn)的產(chǎn)生的水平線和垂直線，在靠近參照線時(shí)會(huì)吸附到最近的參照線上，分為水平移動(dòng)和垂直移動(dòng)兩個(gè)維度。
編輯器上的效果：
我們首先要把所有的參照線記錄下來(lái)，在圖形準(zhǔn)備移動(dòng)（mousedown）的時(shí)候。大致有以下這幾個(gè)操作：
- 遍歷參照?qǐng)D形（在視口內(nèi)，且不為被移動(dòng)目標(biāo)圖形）；
- 計(jì)算出它們的包圍盒，得到 8 個(gè)點(diǎn)，3 條垂直線和 3 條水平線。在一條垂直線上的多個(gè)點(diǎn)，其 x 值是相同的，y 不同，我們 x 作為 key，y 的數(shù)組為 value，保存到 hLineMap 映射對(duì)象中。每一項(xiàng)代表一條垂直線；
- 水平線同理，保存在 vLineMap 中。
- 然后對(duì)這兩個(gè) map 的 key 保存到 sortedXs 或 sortedYs 數(shù)組中，并排序，方便之后二分查找提高查找效率。
抽象一個(gè) RefLine（參照線）類。
interface IVerticalLine { // 有多個(gè)端點(diǎn)的垂直線
x: number;
ys: number[];
}
interface IHorizontalLine { // 有多個(gè)端點(diǎn)的水平線
y: number;
xs: number[];
}
class RefLine {
// 參照?qǐng)D形產(chǎn)生的垂直參照線，y 相同（作為 key），x 值不同（作為 value）
private hLineMap = new Map<number, number[]>();
// 參照?qǐng)D形產(chǎn)生的水平照線，x 相同（作為 key），y 值不同（作為 value）
private vLineMap = new Map<number, number[]>();
// 對(duì) hLineMap 的 key 排序，方便高效二分查找，找到最近的線
private sortedXs: number[] = [];
// 對(duì) vLineMap 的 key 排序
private sortedYs: number[] = [];
private toDrawVLines: IVerticalLine[] = []; // 等待繪制的垂直參照線
private toDrawHLines: IHorizontalLine[] = []; // 等待繪制的水平參照線
constructor(private editor: Editor) {}
cacheXYToBbox() {
this.clear();
const hLineMap = this.hLineMap;
const vLineMap = this.vLineMap;
const selectIdSet = this.editor.selectedElements.getIdSet();
const viewportBbox = this.editor.viewportManager.getBbox2();
for (const graph of this.editor.sceneGraph.children) {
// 排除掉被移動(dòng)的圖形
if (selectIdSet.has(graph.id)) {
continue;
}
const bbox = bboxToBboxWithMid(graph.getBBox2());
// 排除在視口外的圖形
if (!isRectIntersect2(viewportBbox, bbox)) {
continue;
}
// 將參照?qǐng)D形記錄下來(lái)
// 這里是水平線，特點(diǎn)是 x 相同。
this.addBboxToMap(hLineMap, bbox.minX, [bbox.minY, bbox.maxY]);
this.addBboxToMap(hLineMap, bbox.midX, [bbox.minY, bbox.maxY]);
this.addBboxToMap(hLineMap, bbox.maxX, [bbox.minY, bbox.maxY]);
this.addBboxToMap(vLineMap, bbox.minY, [bbox.minX, bbox.maxX]);
this.addBboxToMap(vLineMap, bbox.midY, [bbox.minX, bbox.maxX]);
this.addBboxToMap(vLineMap, bbox.maxY, [bbox.minX, bbox.maxX]);
}
this.sortedXs = Array.from(hLineMap.keys()).sort((a, b) => a - b);
this.sortedYs = Array.from(vLineMap.keys()).sort((a, b) => a - b);
}
private addBboxToMap(
m: Map<number, number[]>,
xOrY: number,
xsOrYs: number[],
) {
const line = m.get(xOrY);
if (line) {
line.push(...xsOrYs);
} else {
m.set(xOrY, [...xsOrYs]);
}
}
// ...
}找出最近參照線
然后是找出目標(biāo)圖形最靠近的水平參照線和垂直參照線。
這一步是在圖形移動(dòng)（mousemove）時(shí)做的，是動(dòng)態(tài)變化的。
首先我們分別找到目標(biāo)圖形的 minX、midX、maxX 的最近垂直參照線，然后計(jì)算出它們各自的絕對(duì)距離，最后找出這里面最小的一個(gè)。
class RefLinet {
updateRefLine(_targetBbox: IBox2): {
offsetX: number;
offsetY: number;
} {
// 重置
this.toDrawVLines = [];
this.toDrawHLines = [];
// 目標(biāo)對(duì)象的包圍盒，這里補(bǔ)上 midX，midY
const targetBbox = bboxToBboxWithMid(_targetBbox);
const hLineMap = this.hLineMap;
const vLineMap = this.vLineMap;
const sortedXs = this.sortedXs;
const sortedYs = this.sortedYs;
// 一個(gè)參照?qǐng)D形都沒(méi)有，結(jié)束
if (sortedXs.length === 0 && sortedYs.length === 0) {
return { offsetX: 0, offsetY: 0 };
}
// 如果 offsetX 到最后還是 undefined，說(shuō)明沒(méi)有找到最靠近的垂直參照線
let offsetX: number | undefined = undefined;
let offsetY: number | undefined = undefined;
// 分別找到目標(biāo)圖形的 minX、midX、maxX 的最近垂直參照線
const closestMinX = getClosestValInSortedArr(sortedXs, targetBbox.minX);
const closestMidX = getClosestValInSortedArr(sortedXs, targetBbox.midX);
const closestMaxX = getClosestValInSortedArr(sortedXs, targetBbox.maxX);
// 分別計(jì)算出距離
const distMinX = Math.abs(closestMinX - targetBbox.minX);
const distMidX = Math.abs(closestMidX - targetBbox.midX);
const distMaxX = Math.abs(closestMaxX - targetBbox.maxX);
// 找到最近距離
const closestXDist = Math.min(distMinX, distMidX, distMaxX);
// y 同理
}
}這里有一個(gè)比較重要的算法，就是找出排序數(shù)組中，離目標(biāo)值最近的數(shù)組元素。
該算法為二分查找的變體，雖然原理不復(fù)雜，但一次能寫對(duì)卻不容易。這里我是找 gpt 幫我寫的，非常完美。
實(shí)現(xiàn)如下：
const getClosestValInSortedArr = (
sortedArr: number[],
target: number,
) => {
if (sortedArr.length === 0) {
throw new Error('sortedArr can not be empty');
}
if (sortedArr.length === 1) {
return sortedArr[0];
}
let left = 0;
let right = sortedArr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (sortedArr[mid] === target) {
return sortedArr[mid];
} else if (sortedArr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// check if left or right is out of bound
if (left >= sortedArr.length) {
return sortedArr[right];
}
if (right < 0) {
return sortedArr[left];
}
// check which one is closer
return Math.abs(sortedArr[right] - target) <=
Math.abs(sortedArr[left] - target)
? sortedArr[right]
: sortedArr[left];
};計(jì)算偏移值
前面我們得到了最小距離 closestXDist。
接著我們要判斷其是否小于一個(gè)特定的臨界值 tol。不可能你離著十米開(kāi)外，移動(dòng)一下就千里迢迢吸附過(guò)來(lái)了吧。
如果滿足，在臨界值內(nèi)，我們就繼續(xù)。
offsetX 還差一步就能算出來(lái)了：確定正負(fù)，因?yàn)?closestXDist 是一個(gè)絕對(duì)值，不能直接用。
那我們就拿這個(gè)最小距離和之前計(jì)算出的三個(gè)距離 distMinX、distMidX、distMaxX對(duì)比，找到相等的，就能計(jì)算出 offsetX 了。
const isEqualNum = (a: number, b: number) => Math.abs(a - b) < 0.00001;
const tol = 5 / zoom; // 最小距離不能超過(guò)這個(gè)
// 確認(rèn)偏移值 offsetX
if (closestXDist <= tol) {
// 這里考慮了一下浮點(diǎn)數(shù)誤差
if (isEqualNum(closestXDist, distMinX)) {
offsetX = closestMinX - targetBbox.minX;
} else if (isEqualNum(closestXDist, distMidX)) {
offsetX = closestMidX - targetBbox.midX;
} else if (isEqualNum(closestXDist, distMaxX)) {
offsetX = closestMaxX - targetBbox.maxX;
} else {
throw new Error('it should not reach here, please put a issue to us');
}
}offsetY 同理，不贅述。
標(biāo)記需繪制參照線段
計(jì)算出了 offsetX 和 offsetY。
接下來(lái)要修正一下我們的 targetBbox。
const correctedTargetBbox = { ...targetBbox };
if (offsetX !== undefined) {
correctedTargetBbox.minX += offsetX;
correctedTargetBbox.midX += offsetX;
correctedTargetBbox.maxX += offsetX;
}
if (offsetY !== undefined) {
correctedTargetBbox.minY += offsetY;
correctedTargetBbox.midY += offsetY;
correctedTargetBbox.maxY += offsetY;
}修正后的目標(biāo)圖形的包圍盒，它的邊就和一些參照線發(fā)生了對(duì)齊。
對(duì)齊的參照線，可能一條沒(méi)有，可能只有一條，也可能有最多的 6 條。
基于新的目標(biāo)圖形，我們來(lái)找它落在的參照線有哪些。
// offsetX 不為 undefined，說(shuō)明落在了臨界值內(nèi)
if (offsetX !== undefined) {
/*************** 左垂直的參考線 ************/
// 對(duì)比 “offset” 和 “離 minX 最近的垂直線到 minX 的距離（不是絕對(duì)值）”
if (isEqualNum(offsetX, closestMinX - targetBbox.minX)) {
// 創(chuàng)建一個(gè)垂直線對(duì)象（特點(diǎn)是這些點(diǎn)的 x 相同）
const vLine: IVerticalLine = {
x: closestMinX,
ys: [],
};
// 修正后的目標(biāo)圖形的對(duì)應(yīng)點(diǎn)。
vLine.ys.push(correctedTargetBbox.minY);
vLine.ys.push(correctedTargetBbox.maxY);
// 參照?qǐng)D形上的點(diǎn)
vLine.ys.push(...hLineMap.get(closestMinX)!);
// 添加到 “待繪制垂線集合”
this.toDrawVLines.push(vLine);
}
/*************** 中間垂直的參考線 ************/
if (isEqualNum(offsetX, closestMidX - targetBbox.midX)
) {
const vLine: IVerticalLine = {
x: closestMidX,
ys: [],
};
vLine.ys.push(correctedTargetBbox.midY);
vLine.ys.push(...hLineMap.get(closestMidX)!);
this.toDrawVLines.push(vLine);
}
/*************** 右垂直的參考線 ************/
// ...
}
// 水平線同理
if (offsetY !== undefined) {
/*************** 上水平的參考線 ************/
/*************** 中間水平的參考線 ************/
/*************** 下水平的參考線 ************/
}修正圖形的 x、y
計(jì)算出的 offsetX 和 offsetY，記得拿去修正被移動(dòng)目標(biāo)圖形的 x 和 y。
const onMousemove = (e) => {
// ...
const { offsetX, offsetY } = this.editor.refLine.updateRefLine(
bboxToBbox2(this.editor.selectedElements.getBBox()!),
);
// 修正
for (let i = 0, len = selectedElements.length; i < len; i++) {
selectedElements[i].x = startPoints[i].x + dx + offsetX;
selectedElements[i].y = startPoints[i].y + dy + offsetY;
}
}繪制參照線和點(diǎn)
最后是繪制參照線，以繪制垂直線為例。
for (const vLine of this.toDrawVLines) {
let minY = Infinity;
let maxY = -Infinity;
// 這個(gè)是世界坐標(biāo)系轉(zhuǎn)視口坐標(biāo)系
const { x } = this.editor.sceneCoordsToViewport(vLine.x, 0);
// 遍歷繪制點(diǎn)
for (const y_ of vLine.ys) {
// TODO: optimize
const { y } = this.editor.sceneCoordsToViewport(0, y_);
minY = Math.min(minY, y);
maxY = Math.max(maxY, y);
// 可能有重復(fù)的點(diǎn)，用備忘錄排除掉
const key = `${x},${y}`;
if (pointsSet.has(key)) {
continue;
}
pointsSet.add(key);
// 繪制點(diǎn)
drawXShape(ctx, x, y, pointSize);
}
// 所有點(diǎn)中的 minY 和 maxY，繪制線段
drawLine(ctx, x, minY, x, maxY);
}
水平線同理。
優(yōu)化點(diǎn)
- 這里的實(shí)現(xiàn)，在圖形有旋轉(zhuǎn)角度的時(shí)候，參照線會(huì)過(guò)多顯得冗余，可以精簡(jiǎn)一些，減少要對(duì)比的參照線。
- 對(duì)齊到像素網(wǎng)格的時(shí)候，包圍盒的值要取整。
- 考慮和按住 Shift 固定 x 或 y 平移的情況，此時(shí)有一個(gè) offset 不能去進(jìn)行校正。
最后
總結(jié)一下，參考線吸附的實(shí)現(xiàn)，就是找出最近的垂直線和水平線，計(jì)算出 offsetX 和 offsetY，修正被移動(dòng)圖形的 x 和 y，并記錄并繪制出最終重合的參考線。
另外很感謝 Github Copilot，幫我寫了很多模板代碼。如果讓我自己復(fù)制然后改改的話，很容易寫錯(cuò)。
