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