「干货」面试官问我如何快速搜索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”代表矩形。由于所有对象都位于此边界矩形内，因此不与边界矩形相交的查询也不能与任何包含的对象相交。在叶级，每个矩形描述一个对象；在更高级别，聚合包括越来越多的对象。这也可以看作是对数据集的越来越粗略的近似。说着有点抽象，还是看一张图：
我来详细解释下这张图：
- 首先我们假设所有数据都是二维空间下的点，我们从图中这个R8区域说起，也就是那个shape of data object。别把那一块不规则图形看成一个数据，我们把它看作是多个数据围成的一个区域。为了实现R树结构，我们用一个最小边界矩形恰好框住这个不规则区域，这样，我们就构造出了一个区域：R8。R8的特点很明显，就是正正好好框住所有在此区域中的数据。其他实线包围住的区域，如R9，R10，R12等都是同样的道理。这样一来，我们一共得到了12个最最基本的最小矩形。这些矩形都将被存储在子结点中。
- 下一步操作就是进行高一层次的处理。我们发现R8，R9，R10三个矩形距离最为靠近，因此就可以用一个更大的矩形R3恰好框住这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对象。
HTMLImageElementHTMLVideoElementHTMLCanvasElementCanvasRenderingContext2D,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万个矩形，速度还是非常快的，也就是1点几毫秒，增加到100万个矩形，canvas 已经有点画不出来了，整个页面已经卡顿了，这边涉及到canvas的性能问题，当图形的数量过多，或者数量过大的时候，fps会大幅度下降的。可以采用批量绘制的方法，还有一种优化手段是分层渲染
我引用一下官方的Rbush的性能图，供大家参考。
总结
最后总结下：rbush 是一种空间索引搜索🔍算法，当你涉及到空间几何搜索的时候，尤其在地图场景下，因为Rbush 实现的原理是比较搜索物体的boundingBox 和已知的boundingBox 求交集， 如果不相交，那么在树的遍历过程中就已经过滤掉了。
链接：https://juejin.cn/post/6989027459601547294
