注册

「干货」面试官问我如何快速搜索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对象。



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



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



如果为空字符串 ('') 或 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 指向问题, 最后就是填充画布。


如图:


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万个矩形,速度还是非常快的,也就是1点几毫秒,增加到100万个矩形,canvas 已经有点画不出来了,整个页面已经卡顿了,这边涉及到canvas的性能问题,当图形的数量过多,或者数量过大的时候,fps会大幅度下降的。可以采用批量绘制的方法,还有一种优化手段是分层渲染


我引用一下官方的Rbush的性能图,供大家参考。


image.png


总结


最后总结下:rbush 是一种空间索引搜索🔍算法,当你涉及到空间几何搜索的时候,尤其在地图场景下,因为Rbush 实现的原理是比较搜索物体的boundingBox 和已知的boundingBox 求交集, 如果不相交,那么在树的遍历过程中就已经过滤掉了。


链接:https://juejin.cn/post/6989027459601547294

0 个评论

要回复文章请先登录注册