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

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

我来详细解释下这张图：

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