圖形編輯器開(kāi)發(fā)：基于相交策略選中圖形
大家好，我是前端西瓜哥。
我開(kāi)發(fā)的圖形編輯器，原本選中圖形是基于選區(qū)是否完全包含對(duì)應(yīng)圖形來(lái)判斷其是否被選中，使用的是矩形包含判斷。
編輯器 github 地址：
https://github.com/F-star/suika
線上體驗(yàn)：
https://blog.fstars.wang/app/suika/
但用著用著，我發(fā)現(xiàn)包含可能并不是一個(gè)好策略。
我想要選中一個(gè)大矩形，就比較費(fèi)勁，要畫(huà)一個(gè)比它還大的選區(qū)，可能還會(huì)把其他的矩形不小心放進(jìn)去（那你別用選區(qū)，直接點(diǎn)選?。?/p>
不管怎樣，我選擇同時(shí)提供 “包含（contain）” 和 "相交（intersect）" 兩種模式，默認(rèn)使用相交策略。
包含選擇
包含策略很簡(jiǎn)單，遍歷圖形，對(duì)比 selection 選區(qū)矩形和圖形的包圍盒，判斷是否為前者包含后者的關(guān)系。
如果是，就放到選中圖形集合中。
相比相交的實(shí)現(xiàn)，算法不復(fù)雜。
// 矩形 1 是否包含矩形 2
function isRectContain(rect1: IRect, rect2: IRect) {
return (
rect1.x <= rect2.x &&
rect1.y <= rect2.y &&
rect1.x + rect1.width >= rect2.x + rect2.width &&
rect1.y + rect1.height >= rect2.y + rect2.height
);
}
// 使用
for (const el of elements) {
// getBBox 拿到的是 AABB 包圍盒
if(isRectContain(selection, el.getBBox())) {
selectSet.add(el);
}
}相交選擇
相交（也叫碰撞）的實(shí)現(xiàn)類似。
// 兩矩形是否相交
function isRectIntersect(rect1: IRect, rect2: IRect) {
return (
rect1.x <= rect2.x + rect2.width &&
rect1.x + rect1.width >= rect2.x &&
rect1.y <= rect2.y + rect2.height &&
rect1.y + rect1.height >= rect2.y
);
}
// 使用
for (const el of elements) {
// getBBox 拿到的是 AABB 包圍盒
if(isRectIntersect(selection, el.getBBox())) {
selectSet.add(el);
}
}效果：
看起來(lái)不錯(cuò)，但它這個(gè)相交檢測(cè)，很 “粗糙”。
因?yàn)樯厦鎸?shí)現(xiàn)，只做了大的 AABB 包圍盒的相交檢測(cè)，沒(méi)有做小的 OBB 包圍盒的相交檢測(cè)。
對(duì)于發(fā)生旋轉(zhuǎn)的圖形，selection 如果和包裹圖形的空白區(qū)域相交了，圖形也被選中。
這種事情，不要啊。
OBB 相交檢測(cè)
我們來(lái)實(shí)現(xiàn)更精準(zhǔn)的 OBB 的相交檢測(cè)。
為此西瓜哥我調(diào)研（其實(shí)是瞎想）了幾個(gè)方案，并研究了算法實(shí)現(xiàn)。
方案 1：線段相交判斷
直接一點(diǎn)，判斷 selection 的邊和圖形的邊是否有相交的。
核心算法實(shí)現(xiàn)為：
type Point = [number, number];
function crossProduct(p1: Point, p2: Point, p3: Point): number {
const x1 = p2[0] - p1[0];
const y1 = p2[1] - p1[1];
const x2 = p3[0] - p1[0];
const y2 = p3[1] - p1[1];
return x1 * y2 - x2 * y1;
}
function isSegmentIntersect(
seg1: [Point, Point],
seg2: [Point, Point],
): boolean {
const [a, b] = seg1;
const [c, d] = seg2;
const d1 = crossProduct(a, b, c);
const d2 = crossProduct(a, b, d);
const d3 = crossProduct(c, d, a);
const d4 = crossProduct(c, d, b);
// 突然發(fā)現(xiàn)這里可以做一個(gè)短路計(jì)算優(yōu)化
return d1 * d2 < 0 && d3 * d4 < 0;
}光是比較 1 對(duì)線段，就要進(jìn)行如此多的計(jì)算。而我們要對(duì)比 4 * 4，共 16 組（當(dāng)然這是最壞情況）。
感覺(jué) 8 太行，最后沒(méi)選擇該方案。
（理論上應(yīng)該做性能測(cè)試對(duì)比各種實(shí)現(xiàn)的，還要考慮用戶使用選區(qū)的場(chǎng)景，是否會(huì)經(jīng)常出現(xiàn)特定算法的最壞時(shí)間復(fù)雜度的情形，有空再做吧）
方案2：分離軸定理算法
這個(gè)算法挺有意思。
分離軸（Separating Axis Theorem，簡(jiǎn)稱SAT），它的思想是：
如果能找到一條直線將兩個(gè)圖形分開(kāi)，那說(shuō)明這兩個(gè)圖形不相交。
如圖：
具體做法是做投影。（通過(guò)降維，將大問(wèn)題拆分成小問(wèn)題）
我們會(huì)對(duì)兩個(gè)凸多邊形做投影，投影到的線稱為 “分離軸”。
分離軸基本選擇的是兩個(gè)圖形的每條邊對(duì)應(yīng)的法向量。當(dāng)發(fā)現(xiàn)投影產(chǎn)生的兩條線段沒(méi)有相交，那找到了那條那條分割兩圖形的直線，證明兩個(gè)凸多邊形不相交。
否則繼續(xù)，如果都沒(méi)找到，說(shuō)明相交。
下圖是以一個(gè)圖形的藍(lán)邊的法向量作為分離軸，進(jìn)行投影的示意圖。
求投影會(huì)用到向量點(diǎn)乘的運(yùn)算。
因?yàn)椴皇潜疚闹攸c(diǎn)，具體實(shí)現(xiàn)細(xì)節(jié)就不講解了，可以考慮以后專門(mén)寫(xiě)一篇文章。
矩形碰撞，特殊的分離軸定理碰撞
不知道你發(fā)現(xiàn)沒(méi)有，從分離軸線的角度去看，兩個(gè)沒(méi)有旋轉(zhuǎn)矩形的相交判斷，其實(shí)是一個(gè)特例。
我們?cè)谂袛噙x區(qū)矩形和圖形的 AABB 包圍盒是否相交時(shí)，其實(shí)就已經(jīng)完成了 基于選區(qū)矩形對(duì)應(yīng)的所有分離軸 的投影上是否相交的比較。
接下來(lái)我們只要再對(duì)圖形的邊對(duì)應(yīng)的分離軸線投影，去對(duì)比就好了。
怎么做呢？
我們 “旋轉(zhuǎn)回來(lái)”，將圖形掰正，選區(qū)矩形產(chǎn)生了旋轉(zhuǎn)角度，計(jì)算選區(qū)矩形的 AABB 包圍盒，再進(jìn)行矩形對(duì)比就好了。
這樣，圖形的分離軸的投影也對(duì)比完了，所有的分離軸都對(duì)比了，就能判斷出選區(qū)和圖形的 OBB 包圍盒是否碰撞了。
甚至都不用向量點(diǎn)乘。
OBB 相交判斷代碼實(shí)現(xiàn)
下面給出代碼實(shí)現(xiàn)。
// 使用相交策略，遍歷圖形是否和選區(qū)矩形相交。
for (const el of elements) {
let isSelected = false; // 是否被選中到
// 首先做 AABB 碰撞檢測(cè)
// 絕大多數(shù)場(chǎng)景下，只有少數(shù)圖形和選區(qū)有相交
if (!isRectIntersect(selection, el.getBBox())) {
// 其實(shí)這里用 break; 在意圖上更明顯
isSelected = false;
} else {
// 如果旋轉(zhuǎn)角度為 90 的倍數(shù)，
// 則 OBB 等價(jià)于 AABB，前面已經(jīng)判斷了，沒(méi)必要繼續(xù)算了
if (el.rotation % HALF_PI == 0) {
isSelected = true;
} else {
// OBB 碰撞檢測(cè)
// 使用分離軸定理的特殊寫(xiě)法
const { x: cx, y: cy } = el.getCenter();
const r = -el.rotation;
const s1 = transformRotate(selection.x, selection.y, r, cx, cy);
// 下面一大段代碼都是求選區(qū)旋轉(zhuǎn)后的 AABB
const s2 = transformRotate(
selection.x + selection.width,
selection.y + selection.height,
r,
cx,
cy,
);
const s3 = transformRotate(
selection.x + selection.width,
selection.y,
r,
cx,
cy,
);
const s4 = transformRotate(
selection.x,
selection.y + selection.height,
r,
cx,
cy,
);
const rotatedSelectionX = Math.min(s1.x, s2.x, s3.x, s4.x);
const rotatedSelectionY = Math.min(s1.y, s2.y, s3.y, s4.y);
const rotatedSelectionWidth =
Math.max(s1.x, s2.x, s3.x, s4.x) - rotatedSelectionX;
const rotatedSelectionHeight =
Math.max(s1.y, s2.y, s3.y, s4.y) - rotatedSelectionY;
// 這個(gè)就是選區(qū)矩形旋轉(zhuǎn)后的 AABB 包圍盒
const rotatedSelection = {
x: rotatedSelectionX,
y: rotatedSelectionY,
width: rotatedSelectionWidth,
height: rotatedSelectionHeight,
};
// 對(duì)比它們（注意圖形不要再用 AABB 了）
isSelected = isRectIntersect(rotatedSelection, {
x: el.x,
y: el.y,
width: el.width,
height: el.height,
});
}
}
// 更新選中圖形集合
if (isSelected) {
selectSet.add(el);
}
}看看效果，很完美。
結(jié)尾
矩形相交是分離軸定理相交算法的特殊情況。
