大家好，我是前端西瓜哥。
在上篇文章我們討論了使用 臟矩形渲染，通過重渲染局部的圖形來提優(yōu)化 Canvas 的性能，將 GPU 密集轉(zhuǎn)換為 CPU 密集。
CPU 密集在哪？
在需要遍歷 所有的圖形，判斷它們是否和臟矩形發(fā)生相交（碰撞），保存發(fā)生碰抓給你的圖形，將它們在局部進行重繪。
有沒有辦法減少需要遍歷的圖形，不要遍歷全部的圖形，而是少量的圖形呢？有一個辦法是使用 四叉樹。
四叉樹碰撞檢測原理
我們將區(qū)域的分割表述為 “節(jié)點”，因為是四叉樹；
將畫布上的真實圖形就叫做 “圖形”。
四叉樹本質(zhì)使用了 空間分割，給圖形加 索引，將視口界面分割成多個區(qū)域，每個區(qū)域記住自己包含了哪些圖形。
然后移動目標圖形時，判斷它落在哪個區(qū)域，取出所在區(qū)域的圖形，這些圖形集合就是和目標圖形發(fā)生碰撞圖形的超集。
這些區(qū)域外的圖形就被我們排除了。
算法實現(xiàn)的要點：
創(chuàng)建根節(jié)點，根節(jié)點保存區(qū)域的信息 x、y、width 和 height。
添加圖形時，當一個節(jié)點內(nèi)的節(jié)點數(shù)量大于閥值，就將整個區(qū)域均等切割為 4 等份的子節(jié)點，將圖形從當前區(qū)域取出，重新放入到這些子節(jié)點內(nèi)，從而將節(jié)點的歸屬劃分為更小的區(qū)域。
（原來的區(qū)域轉(zhuǎn)換為索引層，真正保存節(jié)點的地方放到了它的子區(qū)域上）
當我們提供一個碰撞矩形，我們從四叉樹頂節(jié)點往下找，看是否有子節(jié)點。如果有，使用矩形碰撞算法找出它所在的子節(jié)點有哪些（可能有多個）。對這些子節(jié)點重復前面的操作，進行遞歸，找到所有的圖形。
這些圖形就是碰撞矩形可能相交的矩形，但相對所有圖形，又不至于太多。
四叉樹碰撞檢測算法
先看看經(jīng)典算法實現(xiàn)。
算法我就不自己實現(xiàn)了，這里展示 quadtree-js 庫的代碼實現(xiàn)。
https://github.com/timohausmann/quadtree-js。
構(gòu)造函數(shù)：
function Quadtree(bounds, max_objects, max_levels, level) {
this.max_objects = max_objects || 10; // 節(jié)點內(nèi)最大對象數(shù)量
this.max_levels = max_levels || 4; // 樹的最大深度
this.level = level || 0;
this.bounds = bounds; // 區(qū)域，結(jié)構(gòu)為 {x, y, width, height}
this.objects = []; // 保存圖形的地方
this.nodes = []; // 4 個子節(jié)點，到達閥值時才創(chuàng)建
}這是一個內(nèi)部私有方法，當節(jié)點內(nèi)圖形過多，超過閥值，就將當前節(jié)點分裂成 4 個子節(jié)點：
// 切割：生成 4 個子節(jié)點
Quadtree.prototype.split = function () {
var nextLevel = this.level + 1,
subWidth = this.bounds.width / 2,
subHeight = this.bounds.height / 2,
x = this.bounds.x,
y = this.bounds.y;
// 右上
this.nodes[0] = new Quadtree(
{
x: x + subWidth,
y: y,
width: subWidth,
height: subHeight,
},
this.max_objects,
this.max_levels,
nextLevel
);
// 左上
this.nodes[1] = new Quadtree(
{
x: x,
y: y,
width: subWidth,
height: subHeight,
},
this.max_objects,
this.max_levels,
nextLevel
);
// 左下
this.nodes[2] = new Quadtree(
{
x: x,
y: y + subHeight,
width: subWidth,
height: subHeight,
},
this.max_objects,
this.max_levels,
nextLevel
);
// 右下
this.nodes[3] = new Quadtree(
{
x: x + subWidth,
y: y + subHeight,
width: subWidth,
height: subHeight,
},
this.max_objects,
this.max_levels,
nextLevel
);
};
計算某個圖形落在當前節(jié)點的哪個子節(jié)點，拿到對應節(jié)點索引值數(shù)組：
// 找到某個 box 落在在哪個區(qū)域
Quadtree.prototype.getIndex = function (pRect) {
var indexes = [],
verticalMidpoint = this.bounds.x + this.bounds.width / 2,
horizontalMidpoint = this.bounds.y + this.bounds.height / 2;
var startIsNorth = pRect.y < horizontalMidpoint,
startIsWest = pRect.x < verticalMidpoint,
endIsEast = pRect.x + pRect.width > verticalMidpoint,
endIsSouth = pRect.y + pRect.height > horizontalMidpoint;
// top-right quad
if (startIsNorth && endIsEast) {
indexes.push(0);
}
// top-left quad
if (startIsWest && startIsNorth) {
indexes.push(1);
}
// bottom-left quad
if (startIsWest && endIsSouth) {
indexes.push(2);
}
// bottom-right quad
if (endIsEast && endIsSouth) {
indexes.push(3);
}
return indexes;
};
插入一個圖形，先看是否存在子節(jié)點，有的話說明當前節(jié)點變成了索引層，通過矩形碰撞算法找到所在的子節(jié)點，對這些子節(jié)點做插入操作：
Quadtree.prototype.insert = function (pRect) {
var i = 0,
indexes;
// 存在子節(jié)點，則插入到子節(jié)點
if (this.nodes.length) {
indexes = this.getIndex(pRect); // 找到索引位置
for (i = 0; i < indexes.length; i++) {
this.nodes[indexes[i]].insert(pRect); // 遞歸 insert
}
return;
}
// 沒有子節(jié)點，不是索引層，圖形放到前節(jié)點下
// （有個小 BUG，就是不在范圍內(nèi)的圖形也加上去了）
this.objects.push(pRect);
// 如果對象太多，構(gòu)建子節(jié)點
if (
this.objects.length > this.max_objects &&
this.level < this.max_levels
) {
if (!this.nodes.length) {
this.split();
}
// 將 objects 取出，放入這些子節(jié)點中
for (i = 0; i < this.objects.length; i++) {
indexes = this.getIndex(this.objects[i]);
for (var k = 0; k < indexes.length; k++) {
this.nodes[indexes[k]].insert(this.objects[i]);
}
}
this.objects = [];
}
};返回目標圖形所在節(jié)點下的所有圖形：
// 傳入一個矩形，取出它所在節(jié)點的所有矩形
// 這個方法能返回
Quadtree.prototype.retrieve = function (pRect) {
// 提取目標矩形所在區(qū)間下的所有矩形
var indexes = this.getIndex(pRect),
returnObjects = this.objects;
// 可能需要遞歸。
//if we have subnodes, retrieve their objects
if (this.nodes.length) {
for (var i = 0; i < indexes.length; i++) {
returnObjects = returnObjects.concat(
this.nodes[indexes[i]].retrieve(pRect)
);
}
}
// 移除重復的節(jié)點
returnObjects = returnObjects.filter(function (item, index) {
return returnObjects.indexOf(item) >= index;
});
return returnObjects;
};
非常簡單，一些可以改善的能力。
- 沒有添加映射功能，最后返回的圖形都是 box 對象信息，我們可以考慮改造為 insert(rect, data)，保存額外的信息，比如實際形狀對象或id。
- 動態(tài)收縮：移除某個圖形后更新樹結(jié)構(gòu)，并在發(fā)現(xiàn)圖形數(shù)量低于閥值時，取出圖形放到父節(jié)點上，銷毀子節(jié)點；
- 修改根節(jié)點范圍 后，需要重置整棵樹，如何高效重置；
- 四叉樹的圖形類型，常見的是矩形，但還可以是點、直線、曲線等，如果需要可以考慮支持。
請根據(jù)實際需要進行擴展。
一些權(quán)衡
處于節(jié)點內(nèi)分割線上的圖形，它是歸屬于多個子節(jié)點的，所以最終會同時放到它的多個子節(jié)點下，會花費內(nèi)存。
極端情況下，一個非常大的圖形，會保存在所有的節(jié)點下。
如果想節(jié)省內(nèi)存，可以直接保存到當前節(jié)點上，不放到子節(jié)點上，可以減少內(nèi)存使用，只是最后返回的被碰撞圖形會多一點。因為圖形可能只壓在了兩個子節(jié)點的交界線上，比如 A、 B ，但目標矩形是在其他的子節(jié)點 C 上，但因為它們來自同一個父節(jié)點，所以拿到了這個不可能在 C 的圖形。
后者會更好一些，但如果一個圖形剛好在畫布中心，那每次取出的碰撞圖形都會有它（這點可以通過松散四叉樹解決）。
松散四叉樹
經(jīng)典四叉樹有個問題，就是如果圖形的物理信息是比較動態(tài)的，當總是在邊界附近時，就會發(fā)生頻繁地將圖形從一個節(jié)點取出并放到另個節(jié)點下。
對此我們可以額外設置一個出口邊界。這個出口邊界要比入口邊界要大，只有當圖形離開這個出口邊界，才會更新提取圖形到新的節(jié)點。
這樣，當圖形劃分到另一個節(jié)點上時，就 需要移動較長的距離才能回到原來節(jié)點下，輕微地移動不會導致劇烈的更新。
通常出口邊界邊長為入口邊界的兩倍最佳，為什么不知道，經(jīng)驗之談。
其他空間分割思想的算法
簡單介紹一些也使用了 空間分割 思想的算法。
- 跳表：一種有序鏈表，通過疊加大量的索引層，可以進行鏈表形式的 “二分查找”，達到高效的
O(logn) 時間復雜度，但也帶來了內(nèi)存的消耗。Redis 中的有序集合（Sorted Set）底層使用了跳表，一個原因是可以高效地獲取區(qū)間內(nèi)的數(shù)據(jù)集； - B+ 樹：一種平衡二叉樹，有點像跳表，但樹的層數(shù)最多為三層，MySQL 的索引實現(xiàn)使用了 B+ 樹，因為層數(shù)較少，可以減少 IO 操作；
- R 樹：R 表示矩形的意思。相比前面兩種單維的范圍查找，R 樹能做高效的高維查找。比如地圖中，我們可以通過 R 樹將 距離 相近的高維圖形合并為一個大節(jié)點，當搜索 “2km 內(nèi)的藥店” 時，如果你落到某個大節(jié)點上，我們只要遍歷一個大節(jié)點下的所有節(jié)點，而不是遍歷整個市，或整個國家。
R 樹的思路是最接近四叉樹的，它其實是另一種 減少圖形遍歷的方案，可以適用于高效剔除視口范圍之外的圖形。
R 樹有個 star 數(shù)很多的庫，叫做 RBush，感興趣可以看看。
https://github.com/mourner/rbush。
