前言

        在之前的博文自定义Label标签抽稀(openlayers)中，我们自定义了抽稀标签的方法，但是检测两个标签是否碰撞的算法是简单暴力的遍历检测。如果标签一多，我们的方法效率就肯定会变慢。

        有没有方法可以提过检测的效率呢，有，使用数据结构R树即可解决。之前在博文也提到过，openlayers的ol.layer.Vector类可以传入参数declutter，设置为true即可解决。其实openlayer使用的是RBush，这个库封装了对RTree增删查、碰撞检测等方法。

1、openlayers里rbush使用源码分析

        对ol.layer.Vector类里feature是如何绘制的，可以参考之前的分析openlayer, 由一个图标遮盖线段需求引发的思考，可以查看地图详细的渲染逻辑。这里简单梳理下

        ol.PluggableMap#render()

        ol.renderer.canvas.Map#renderFrame(frameState)

        ol.renderer.canvas.VectorLayer#prepareFrame(frameState, layerState)

        ol.renderer.canvas.VectorLayer#composeFrame(frameState, layerState, context)

        ol.render.canvas.ReplayGroup#replay(replayContext, transform, rotation, skippedFeatureUids)

        ol.render.canvas.Replay#replay(context, transform, viewRotation, skippedFeaturesHash)

        ol.render.canvas.Replay#replay_(context, transform, skippedFeaturesHash, instructions, featureCallback, opt_hitExtent)

        最终在类ol.render.canvas.Replay的replay_方法里，在执行switch case语句时，当指令条件是ol.render.canvas.Instruction.DRAW_IMAGE、或者ol.render.canvas.Instruction.DRAW_CHARS时，会有如下代码，也就是说如果最后是绘制文字(ol.style.Text)或者图片（ol.style.Image）时，如果ol.layer.Vector设置declutter为true时，会进行抽稀操作

        这个方法就是openlayer抽稀的核心逻辑了，只有两句。如下红框所示，判断当前的box是否和已有的空间数据碰撞，如果没有碰撞，说明可以执行绘制，将当前的空间数据范围加入rtree并执行绘制。

         这个declutterTree_是哪里来的？是在ol.renderer.canvas.VectorLayer构造里初始化的，ol.ext.rbush其实就是RBush库

2、我们如何使用RBush库

        node环境下直接npm安装；

        如果要js引用的话，先到github上找到rbush库，clone下来后，进入目录依次执行npm install、npm run build命令进行编译，可以在根目录找到rbush.min.js，引入项目即可。

        上面说了openlayer是如何使用rbush的，我们可以参照着写，针对碰撞检测，只需要先new一个Rbush对象，然后使用collides方法，如果返回false，就将新的空间数据insert即可。其api也不复杂，只是要注意下其空间数据的格式，是一个矩形对象，必须要4个属性minX、minY、maxX、maxY。

        针对之前的标签抽稀方法，碰撞检测可以使用RBush来提高效率，代码修改如下

<code> TextDeclutter.prototype.canShow = function (label) {

let x = label.position[0]

let y = label.position[1]

let item = {

minX: x - label.labelWidth / 2 - this.marginX / 2,

minY: y - label.labelHeight / 2 - this.marginY / 2,

maxX: x + label.labelWidth / 2 + this.marginX / 2,

maxY: y + label.labelHeight / 2 + this.marginY / 2

}

if (this.rtree_.collides(item)) {

return false

}

this.rtree_.insert(item)

return true

}

3、RBush常用的API

3.1 创建实例对象

const tree = new RBush();

        RBush的可选参数定义了树节点中的最大条目数。9（默认使用）是大多数应用程序的合理选择。值越高，插入速度越快，搜索速度越慢，反之亦然。

const tree = new RBush(16);

3.2 添加数据

        插入一条数据:

const item = {

minX: 20,

minY: 40,

maxX: 30,

maxY: 50,

foo: 'bar'

};

tree.insert(item);

3.3 删除数据

        删除之前插入的数据:

tree.remove(item);

        默认情况下，RBush通过引用删除对象。但是，您可以传递一个自定义的equals函数，通过值进行比较以进行删除，这在您只有需要删除的对象的副本时非常有用（例如从服务器加载）：

tree.remove(itemCopy, (a, b) => {

return a.id === b.id;

});

        清除所有的数据:

tree.clear();

3.4 数据格式化

        默认情况下，RBush假定数据点的格式为具有minX、minY、maxX和maxY属性的对象。您可以通过如下方式重写toBBox、compareMinX和compareMinY方法来对此进行自定义：

class MyRBush extends RBush {

toBBox([x, y]) { return {minX: x, minY: y, maxX: x, maxY: y}; }

compareMinX(a, b) { return a.x - b.x; }

compareMinY(a, b) { return a.y - b.y; }

}

const tree = new MyRBush();

tree.insert([20, 50]); // accepts [x, y] points

        如果你正在索引一个静态的点列表（索引后不需要添加/删除点），你应该使用kdbush，它的点索引速度比RBush快5-8倍。

3.5 批量插入数据

        将给定数据批量插入树中:

tree.load([item1, item2, ...]);

        批量插入通常比逐一插入项目快2~3倍。批量加载（批量插入到空树中）后，后续查询性能也提高了约20-30%。

        请注意，当您对现有树进行批量插入时，它会将给定的数据批量加载到单独的树中，并将较小的树插入较大的树中。这意味着批量插入对于集群数据（一次更新中的项目彼此靠近）非常有效，但如果数据分散，则会使查询性能变差。

3.6 搜索查询

const result = tree.search({

minX: 40,

minY: 20,

maxX: 80,

maxY: 70

});

        返回给定边界框相交的数据项（点或矩形）数组。请注意，搜索方法接受{minX，minY，maxX，maxY}格式的边界框，而不管数据格式如何。

const allItems = tree.all();

        返回树中的所有数据。

3.7 碰撞检测

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

        如果有任何项目与给定的边界框相交，则返回true，否则返回false。

3.8 导出和导入

// export data as JSON object

const treeData = tree.toJSON();

// import previously exported data

const tree = rbush(9).fromJSON(treeData);

        导入和导出为JSON允许您在服务器（使用Node.js）和浏览器上组合使用RBush，

例如，首先在服务器上对数据进行索引，然后在客户端上导入生成的树数据进行搜索。

请注意，传递给构造函数的`nodeSize`选项在两个树中必须相同，才能使导出/导入正常工作。