「乾貨」面試官問我如何快速搜索10萬個矩形?——我說RBush

前言

親愛的coder們,我又來了,一個喜歡圖形的程式設計師👩‍💻,前幾篇文章一直都在教大家怎麼畫地圖、畫折線圖、畫煙花🎆,難道圖形就是這樣嘛,當然不是,一個很簡單的問題, 如果我在canvas中畫了10萬個點,滑鼠在畫布上移動,靠近哪一個點,哪一個點高亮。有同學就說遇事不決 用for循環遍歷哇,我也知道可以用循環解決哇,循環解決幾百個點可以,如果是幾萬甚至幾百萬個點你還循環,你想讓用戶等死?這時就引入今天的主角他來了就是Rbush

rbush

我們先看下定義,這個rbush到底能幫我們解決了什麼問題?

RBush是一個high-performanceJavaScript庫,用於點和矩形的二維空間索引。它基於優化的R-tree數據結構,支援大容量插入。空間索引是一種用於點和矩形的特殊數據結構,允許您非常高效地執行「此邊界框中的所有項目」之類的查詢(例如,比在所有項目上循環快數百倍)。它最常用於地圖和數據可視化。

看定義他是基於優化的R-tree數據結構,那麼R-tree又是什麼呢?

R-trees是用於空間訪問方法的樹數據結構,即用於索引多維資訊,例如地理坐標矩形多邊形。R-tree 在現實世界中的一個常見用途可能是存儲空間對象,例如餐廳位置或構成典型地圖的多邊形:街道、建築物、湖泊輪廓、海岸線等,然後快速找到查詢的答案例如「查找我當前位置 2 公里範圍內的所有博物館」、「檢索我所在位置 2 公里範圍內的所有路段」(以在導航系統中顯示它們)或「查找最近的加油站」(儘管不將道路進入帳戶)。

R-tree的關鍵思想是將附近的對象分組,並在樹的下一個更高級別中用它們的最小邊界矩形表示它們;R-tree 中的「R」代表矩形。由於所有對象都位於此邊界矩形內,因此不與邊界矩形相交的查詢也不能與任何包含的對象相交。在葉級,每個矩形描述一個對象;在更高級別,聚合包括越來越多的對象。這也可以看作是對數據集的越來越粗略的近似。說著有點抽象,還是看一張圖:

R-tree

我來詳細解釋下這張圖:

  1. 首先我們假設所有數據都是二維空間下的點,我們從圖中這個R8區域說起,也就是那個shape of data object。別把那一塊不規則圖形看成一個數據,我們把它看作是多個數據圍成的一個區域。為了實現R樹結構,我們用一個最小邊界矩形恰好框住這個不規則區域,這樣,我們就構造出了一個區域:R8。R8的特點很明顯,就是正正好好框住所有在此區域中的數據。其他實線包圍住的區域,如R9,R10,R12等都是同樣的道理。這樣一來,我們一共得到了12個最最基本的最小矩形。這些矩形都將被存儲在子結點中。
  2. 下一步操作就是進行高一層次的處理。我們發現R8,R9,R10三個矩形距離最為靠近,因此就可以用一個更大的矩形R3恰好框住這3個矩形。
  3. 同樣道理,R15,R16被R6恰好框住,R11,R12被R4恰好框住,等等。所有最基本的最小邊界矩形被框入更大的矩形中之後,再次迭代,用更大的框去框住這些矩形。

演算法

插入

為了插入一個對象,樹從根節點遞歸遍歷。在每一步,檢查當前目錄節點中的所有矩形,並使用啟發式方法選擇候選者,例如選擇需要最少放大的矩形。搜索然後下降到這個頁面,直到到達葉節點。如果葉節點已滿,則必須在插入之前對其進行拆分。同樣,由於窮舉搜索成本太高,因此採用啟發式方法將節點一分為二。將新創建的節點添加到上一層,這一層可以再次溢出,並且這些溢出可以向上傳播到根節點;當這個節點也溢出時,會創建一個新的根節點並且樹的高度增加。

搜索

範圍搜索中,輸入是一個搜索矩形(查詢框)。搜索從樹的根節點開始。每個內部節點包含一組矩形和指向相應子節點的指針,每個葉節點包含空間對象的矩形(指向某個空間對象的指針可以在那裡)。對於節點中的每個矩形,必須確定它是否與搜索矩形重疊。如果是,則還必須搜索相應的子節點。以遞歸方式進行搜索,直到遍歷所有重疊節點。當到達葉節點時,將針對搜索矩形測試包含的邊界框(矩形),如果它們位於搜索矩形內,則將它們的對象(如果有)放入結果集中。

讀著就複雜,但是社區里肯定有大佬替我們封裝好了,就不用自己再去手寫了,寫了寫估計不一定對哈哈哈。

RBUSH 用法

用法

// as a ES module
import RBush from 'rbush';

// as a CommonJS module
const RBush = require('rbush');

創建一個樹🌲

const tree = new RBush(16);

後面的16 是一個可選項,RBush 的一個可選參數定義了樹節點中的最大條目數。 9(默認使用)是大多數應用程式的合理選擇。 更高的值意味著更快的插入和更慢的搜索,反之亦然

插入數據📚

const item = {
    minX: 20,
    minY: 40,
    maxX: 30,
    maxY: 50,
    foo: 'bar'
};
tree.insert(item);

刪除數據📚

tree.remove(item);

默認情況下,RBush按引用移除對象。但是,您可以傳遞一個自定義的equals函數,以便按刪除值進行比較,當您只有需要刪除的對象的副本時(例如,從伺服器載入),這很有用:

tree.remove(itemCopy, (a, b) => {
    return a.id === b.id;
});

刪除所有數據

tree.clear();

搜索🔍

const result = tree.search({
    minX: 40,
    minY: 20,
    maxX: 80,
    maxY: 70
});

api 介紹完畢下面👇開始進入實戰環節一個簡單的小案例——canvas中畫布搜索🔍的。

用圖片填充畫布

填充畫布的的過程中,這裡和大家介紹一個canvas點的api ——createPattern

**CanvasRenderingContext2D**.createPattern() 是 Canvas 2D API 使用指定的影像 (CanvasImageSource)創建模式的方法。 它通過repetition參數在指定的方向上重複元影像。此方法返回一個CanvasPattern對象。

第一個參數是填充畫布的數據源可以是下面這:

第二個參數指定如何重複影像。允許的值有:

  • "repeat" (both directions),
  • "repeat-x" (horizontal only),
  • "repeat-y" (vertical only),
  • "no-repeat" (neither).

如果為空字元串 ('') 或 null (但不是 undefined),repetition將被當作”repeat”。

程式碼如下:

   class search {
      constructor() {
        this.canvas = document.getElementById('map')
        this.ctx = this.canvas.getContext('2d')
        this.tree = new RBush()
        this.fillCanvas()
      }

      fillCanvas() {
        const img = new Image()
        img.src =
          '//ztifly.oss-cn-hangzhou.aliyuncs.com/%E6%B2%B9%E7%94%BB.jpeg'
        img.onload = () => {
          const pattern = this.ctx.createPattern(img, '')
          this.ctx.fillStyle = pattern
          this.ctx.fillRect(0, 0, 960, 600)
        }
      }
    }

這邊有個小提醒的就是圖片載入成功的回調裡面去給畫布創建模式,然後就是this 指向問題, 最後就是填充畫布。

如圖:

image-20210722220842530

數據的生成

數據生成主要在畫布的寬度 和長度的範圍內隨機生成10萬個矩形。插入到rbush數據的格式就是有minX、maxX、minY、maxY。這個實現的思路也是非常的簡單哇, minX用畫布的長度Math.random minY 就是畫布的高度Math.random. 然後最大再此基礎上隨機*20 就OK了,一個矩形就形成了。這個實現的原理就是左上和右下兩個點可以形成一個矩形。程式碼如下:

randomRect() {
  const rect = {}
  rect.minX = parseInt(Math.random() * 960)
  rect.maxX = rect.minX + parseInt(Math.random() * 20)
  rect.minY = parseInt(Math.random() * 600)
  rect.maxY = rect.minY + parseInt(Math.random() * 20)
  rect.name = 'rect' + this.id
  this.id += 1
  return rect
}

然後循環加入10萬條數據:

loadItems(n = 100000) {
  let items = []
  for (let i = 0; i < n; i++) {
    items.push(this.randomRect())
  }
  this.tree.load(items)
}

畫布填充

這裡我創建一個和當前畫布一抹一樣的canvas,但是裡面畫了n個矩形,將這個畫布 當做圖片填充到原先的畫布中。

memCanva() {
  this.memCanv = document.createElement('canvas')
  this.memCanv.height = 600
  this.memCanv.width = 960
  this.memCtx = this.memCanv.getContext('2d')
  this.memCtx.strokeStyle = 'rgba(255,255,255,0.7)'
}

loadItems(n = 10000) {
  let items = []
  for (let i = 0; i < n; i++) {
    const item = this.randomRect()
    items.push(item)
    this.memCtx.rect(
      item.minX,
      item.minY,
      item.maxX - item.minX,
      item.maxY - item.minY
    )
  }
  this.memCtx.stroke()
  this.tree.load(items)
}

然後在載入數據的時候,在當前畫布畫了10000個矩形。這時候新建的畫布有東西了,然後我們用一個drawImage api ,

這個api做了這樣的一個事,就是將畫布用特定資源填充,然後你可以改變位置,後面有參數可以修改,這裡我就不多介紹了, 傳送門

this.ctx.drawImage(this.memCanv, 0, 0)

我們看下效果:

畫布填充效果

添加交互

添加交互, 就是對畫布添加mouseMove 事件, 然後呢我們以滑鼠的位置,形成一個搜索的數據,然後我在統計花費的時間,然後你就會發現,這個Rbush 是真的快。程式碼如下:

 this.canvas.addEventListener('mousemove', this.handler.bind(this))
 // mouseMove 事件
 handler(e) {
    this.clearRect()
    const x = e.offsetX
    const y = e.offsetY
    this.bbox.minX = x - 20
    this.bbox.maxX = x + 20
    this.bbox.minY = y - 20
    this.bbox.maxY = y + 20
    const start = performance.now()
    const res = this.tree.search(this.bbox)
    this.ctx.fillStyle = this.pattern
    this.ctx.strokeStyle = 'rgba(255,255,255,0.7)'
    res.forEach((item) => {
      this.drawRect(item)
    })
    this.ctx.fill()
    this.res.innerHTML =
      'Search Time (ms): ' + (performance.now() - start).toFixed(3)
  }

這裡給大家講解一下,現在我們畫布是黑白的, 然後以滑鼠搜索到數據後,然後我們畫出對應的矩形,這時候呢,可以將矩形的填充模式改成 pattern 模式,這樣便於我們看的更加明顯。fillStyle可以填充3種類型:

ctx.fillStyle = color;
ctx.fillStyle = gradient;
ctx.fillStyle = pattern;

分別代表的是:

填充的模式

OK講解完畢, 直接gif 看在1萬個矩形的搜索中Rbush的表現怎麼樣。

rbush 演示

這是1萬個矩形我換成10萬個矩形我們在看看效果:

10萬個點

我們發現增加到10萬個矩形,速度還是非常快的,增加到100萬個矩形,canvas 已經有點畫不出來了,整個頁面已經卡頓了,這邊涉及到canvas的性能問題,當圖形的數量過多,或者數量過大的時候,fps會大幅度下降的。

總結

最後總結下:rbush 是一種空間索引搜索🔍演算法,當你涉及到空間幾何搜索的時候,尤其在地圖場景下,因為Rbush 實現的原理是比較搜索物體的boundingBox 和已知的boundingBox 求交集, 如果不相交,那麼在樹的遍歷過程中就已經過濾掉了。最後文章寫作不易,如果有錯誤的話歡迎指正。如果看了對你有幫助的話,希望你能為我點個關注 和👍, 這是對我最大的支援!

學習交流

搜索公眾號【前端圖形】,後台回復”加群”二字, 就可以加入可視化學習交流群哦! 一起學習吧!

參考文獻

深入理解空間演算法

R樹詳細解釋

維基百科-R樹的介紹

Alex2wong