大家好，我是前端西瓜哥。

在上篇文章我們討論了使用 臟矩形渲染，通過重渲染局部的圖形來提優(yōu)化 Canvas 的性能，將 GPU 密集轉(zhuǎn)換為 CPU  密集。

CPU 密集在哪？

在需要遍歷 所有的圖形，判斷它們是否和臟矩形發(fā)生相交（碰撞），保存發(fā)生碰抓給你的圖形，將它們在局部進(jìn)行重繪。

有沒有辦法減少需要遍歷的圖形，不要遍歷全部的圖形，而是少量的圖形呢？有一個(gè)辦法是使用 四叉樹。

四叉樹碰撞檢測原理

我們將區(qū)域的分割表述為 “節(jié)點(diǎn)”，因?yàn)槭撬牟鏄洌?/p>

將畫布上的真實(shí)圖形就叫做 “圖形”。

四叉樹本質(zhì)使用了 空間分割，給圖形加 索引，將視口界面分割成多個(gè)區(qū)域，每個(gè)區(qū)域記住自己包含了哪些圖形。

然后移動目標(biāo)圖形時(shí)，判斷它落在哪個(gè)區(qū)域，取出所在區(qū)域的圖形，這些圖形集合就是和目標(biāo)圖形發(fā)生碰撞圖形的超集。

這些區(qū)域外的圖形就被我們排除了。

算法實(shí)現(xiàn)的要點(diǎn)：

創(chuàng)建根節(jié)點(diǎn)，根節(jié)點(diǎn)保存區(qū)域的信息 x、y、width 和 height。

添加圖形時(shí)，當(dāng)一個(gè)節(jié)點(diǎn)內(nèi)的節(jié)點(diǎn)數(shù)量大于閥值，就將整個(gè)區(qū)域均等切割為 4 等份的子節(jié)點(diǎn)，將圖形從當(dāng)前區(qū)域取出，重新放入到這些子節(jié)點(diǎn)內(nèi)，從而將節(jié)點(diǎn)的歸屬劃分為更小的區(qū)域。

（原來的區(qū)域轉(zhuǎn)換為索引層，真正保存節(jié)點(diǎn)的地方放到了它的子區(qū)域上）

當(dāng)我們提供一個(gè)碰撞矩形，我們從四叉樹頂節(jié)點(diǎn)往下找，看是否有子節(jié)點(diǎn)。如果有，使用矩形碰撞算法找出它所在的子節(jié)點(diǎn)有哪些（可能有多個(gè)）。對這些子節(jié)點(diǎn)重復(fù)前面的操作，進(jìn)行遞歸，找到所有的圖形。

這些圖形就是碰撞矩形可能相交的矩形，但相對所有圖形，又不至于太多。

四叉樹碰撞檢測算法

先看看經(jīng)典算法實(shí)現(xiàn)。

算法我就不自己實(shí)現(xiàn)了，這里展示 quadtree-js 庫的代碼實(shí)現(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é)點(diǎn)內(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 個(gè)子節(jié)點(diǎn)，到達(dá)閥值時(shí)才創(chuàng)建
}

這是一個(gè)內(nèi)部私有方法，當(dāng)節(jié)點(diǎn)內(nèi)圖形過多，超過閥值，就將當(dāng)前節(jié)點(diǎn)分裂成 4 個(gè)子節(jié)點(diǎn)：

// 切割：生成 4 個(gè)子節(jié)點(diǎn)
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
  );
};

計(jì)算某個(gè)圖形落在當(dāng)前節(jié)點(diǎn)的哪個(gè)子節(jié)點(diǎn)，拿到對應(yīng)節(jié)點(diǎn)索引值數(shù)組：

// 找到某個(gè) box 落在在哪個(gè)區(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;
};

插入一個(gè)圖形，先看是否存在子節(jié)點(diǎn)，有的話說明當(dāng)前節(jié)點(diǎn)變成了索引層，通過矩形碰撞算法找到所在的子節(jié)點(diǎn)，對這些子節(jié)點(diǎn)做插入操作：

Quadtree.prototype.insert = function (pRect) {
  var i = 0,
    indexes;
  // 存在子節(jié)點(diǎn)，則插入到子節(jié)點(diǎn)
  if (this.nodes.length) { 
    indexes = this.getIndex(pRect); // 找到索引位置

    for (i = 0; i < indexes.length; i++) {
      this.nodes[indexes[i]].insert(pRect); // 遞歸 insert
    }
    return;
  }
  // 沒有子節(jié)點(diǎn)，不是索引層，圖形放到前節(jié)點(diǎn)下
  // （有個(gè)小 BUG，就是不在范圍內(nèi)的圖形也加上去了）
  this.objects.push(pRect);

  // 如果對象太多，構(gòu)建子節(jié)點(diǎn)
  if (
    this.objects.length > this.max_objects &&
    this.level < this.max_levels
  ) {
    if (!this.nodes.length) {
      this.split();
    }
    // 將 objects 取出，放入這些子節(jié)點(diǎn)中
    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 = [];
  }
};

返回目標(biāo)圖形所在節(jié)點(diǎn)下的所有圖形：

// 傳入一個(gè)矩形，取出它所在節(jié)點(diǎn)的所有矩形
// 這個(gè)方法能返回
Quadtree.prototype.retrieve = function (pRect) {
  // 提取目標(biāo)矩形所在區(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)
      );
    }
  }
  // 移除重復(fù)的節(jié)點(diǎn)
  returnObjects = returnObjects.filter(function (item, index) {
    return returnObjects.indexOf(item) >= index;
  });
  return returnObjects;
};

非常簡單，一些可以改善的能力。

1. 沒有添加映射功能，最后返回的圖形都是 box 對象信息，我們可以考慮改造為 insert(rect, data)，保存額外的信息，比如實(shí)際形狀對象或id。
2. 動態(tài)收縮：移除某個(gè)圖形后更新樹結(jié)構(gòu)，并在發(fā)現(xiàn)圖形數(shù)量低于閥值時(shí)，取出圖形放到父節(jié)點(diǎn)上，銷毀子節(jié)點(diǎn)；
3. 修改根節(jié)點(diǎn)范圍 后，需要重置整棵樹，如何高效重置；
4. 四叉樹的圖形類型，常見的是矩形，但還可以是點(diǎn)、直線、曲線等，如果需要可以考慮支持。

請根據(jù)實(shí)際需要進(jìn)行擴(kuò)展。

一些權(quán)衡

處于節(jié)點(diǎn)內(nèi)分割線上的圖形，它是歸屬于多個(gè)子節(jié)點(diǎn)的，所以最終會同時(shí)放到它的多個(gè)子節(jié)點(diǎn)下，會花費(fèi)內(nèi)存。

極端情況下，一個(gè)非常大的圖形，會保存在所有的節(jié)點(diǎn)下。

如果想節(jié)省內(nèi)存，可以直接保存到當(dāng)前節(jié)點(diǎn)上，不放到子節(jié)點(diǎn)上，可以減少內(nèi)存使用，只是最后返回的被碰撞圖形會多一點(diǎn)。因?yàn)閳D形可能只壓在了兩個(gè)子節(jié)點(diǎn)的交界線上，比如 A、 B ，但目標(biāo)矩形是在其他的子節(jié)點(diǎn) C 上，但因?yàn)樗鼈儊碜酝粋€(gè)父節(jié)點(diǎn)，所以拿到了這個(gè)不可能在 C 的圖形。

后者會更好一些，但如果一個(gè)圖形剛好在畫布中心，那每次取出的碰撞圖形都會有它（這點(diǎn)可以通過松散四叉樹解決）。

松散四叉樹

經(jīng)典四叉樹有個(gè)問題，就是如果圖形的物理信息是比較動態(tài)的，當(dāng)總是在邊界附近時(shí)，就會發(fā)生頻繁地將圖形從一個(gè)節(jié)點(diǎn)取出并放到另個(gè)節(jié)點(diǎn)下。

對此我們可以額外設(shè)置一個(gè)出口邊界。這個(gè)出口邊界要比入口邊界要大，只有當(dāng)圖形離開這個(gè)出口邊界，才會更新提取圖形到新的節(jié)點(diǎn)。

這樣，當(dāng)圖形劃分到另一個(gè)節(jié)點(diǎn)上時(shí)，就 需要移動較長的距離才能回到原來節(jié)點(diǎn)下，輕微地移動不會導(dǎo)致劇烈的更新。

通常出口邊界邊長為入口邊界的兩倍最佳，為什么不知道，經(jīng)驗(yàn)之談。

其他空間分割思想的算法

簡單介紹一些也使用了 空間分割 思想的算法。

1. 跳表：一種有序鏈表，通過疊加大量的索引層，可以進(jìn)行鏈表形式的 “二分查找”，達(dá)到高效的 O(logn) 時(shí)間復(fù)雜度，但也帶來了內(nèi)存的消耗。Redis 中的有序集合（Sorted Set）底層使用了跳表，一個(gè)原因是可以高效地獲取區(qū)間內(nèi)的數(shù)據(jù)集；
2. B+ 樹：一種平衡二叉樹，有點(diǎn)像跳表，但樹的層數(shù)最多為三層，MySQL 的索引實(shí)現(xiàn)使用了 B+ 樹，因?yàn)閷訑?shù)較少，可以減少 IO 操作；
3. R 樹：R 表示矩形的意思。相比前面兩種單維的范圍查找，R 樹能做高效的高維查找。比如地圖中，我們可以通過 R 樹將 距離 相近的高維圖形合并為一個(gè)大節(jié)點(diǎn)，當(dāng)搜索 “2km 內(nèi)的藥店” 時(shí)，如果你落到某個(gè)大節(jié)點(diǎn)上，我們只要遍歷一個(gè)大節(jié)點(diǎn)下的所有節(jié)點(diǎn)，而不是遍歷整個(gè)市，或整個(gè)國家。

R 樹的思路是最接近四叉樹的，它其實(shí)是另一種 減少圖形遍歷的方案，可以適用于高效剔除視口范圍之外的圖形。

R 樹有個(gè) star 數(shù)很多的庫，叫做 RBush，感興趣可以看看。

https://github.com/mourner/rbush。