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