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