「干货」面试官问我如何快速搜索10万个矩形？——我说RBush

[wzf1997]

前言

亲爱的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”代表矩形。由于所有对象都位于此边界矩形内，因此不与边界矩形相交的查询也不能与任何包含的对象相交。在叶级，每个矩形描述一个对象；在更高级别，聚合包括越来越多的对象。这也可以看作是对数据集的越来越粗略的近似。说着有点抽象，还是看一张图：

我来详细解释下这张图：

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对象。

第一个参数是填充画布的数据源可以是下面这：

• HTMLImageElement
• HTMLVideoElement
• HTMLCanvasElement
• CanvasRenderingContext2D,
• ImageBitmap,
• ImageData,
• Blob.

第二个参数指定如何重复图像。允许的值有：

• "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 =
          'https://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 指向问题， 最后就是填充画布。

如图：

数据的生成

数据生成主要在画布的宽度 和长度的范围内随机生成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的表现怎么样。

这是1万个矩形我换成10万个矩形我们在看看效果：

我们发现增加到10万个矩形，速度还是非常快的，增加到100万个矩形，canvas 已经有点画不出来了，整个页面已经卡顿了，这边涉及到canvas的性能问题，当图形的数量过多，或者数量过大的时候，fps会大幅度下降的。

总结

最后总结下：rbush 是一种空间索引搜索🔍算法，当你涉及到空间几何搜索的时候，尤其在地图场景下，因为Rbush 实现的原理是比较搜索物体的boundingBox 和已知的boundingBox 求交集， 如果不相交，那么在树的遍历过程中就已经过滤掉了。最后文章写作不易，如果有错误的话欢迎指正。如果看了对你有帮助的话，希望你能为我点个关注 和👍， 这是对我最大的支持！

学习交流

搜索公众号【前端图形】，后台回复"加群"二字， 就可以加入可视化学习交流群哦！ 一起学习吧！

参考文献

深入理解空间算法

R树详细解释

维基百科-R树的介绍

Alex2wong

[fantasticit]

👍🏻