大家好，我是前端西瓜哥。
今天我们来看看 R 树是什么？以及它为什么能够提高图形的检索速度。
R 树（R-tree）是一种 空间索引技术，能够是从大量的节点中，快速找到特定范围的元素集合，而不用一个不落地遍历所有节点。
思路和其他索引算法（比如 B 树、跳表）有点像，但 R 树针对的是高维数据的查询 。R 树的 “R” 指的是矩形（Rectangle）。
举个具体的例子，假设有一张地图，上面有几百万个节点，要快速找某个位置半径 2 公里的所有餐馆的信息。
低效的做法是遍历这几百万的节点的位置，判断距离是否小于 2 公里。
但如果用上索引技术，比如 R 树，我们就能利用索引去 空间换时间，快速拿到特定范围的节点超集，比如几千个。
接着只需要遍历这几千个节点去判断符合条件的节点就可以了，而不需要完完整整遍历所有的节点。
除此之外还可以：
下面看一下在图形编辑器的一个场景。
我们构建了一棵图形树，图形树的图形有位置、宽高等属性，并渲染在画布上。
需要实现选择功能，绘制一个矩形选区，使和该选区矩形相交的图形高亮。
为实现这个能力，我们计算图形树上的每个图形的包围盒：一个用 minX，minY、maxX、maxY 表达的一个矩形，它刚好包围住图形。
包围盒的作用是简化碰撞算法，一些复杂的图形，比如贝塞尔曲线，如果要严格意义上判断碰撞，是要进行复杂的计算的，在有大量图形的场景下，性能非常糟糕。
所以业内常用矩形包围盒的碰撞来简化，这种算法非常简单高效，可直接用来替代原本复杂精细的碰撞检测，或是在进行复杂碰撞算法前先做一层过滤，避免无谓的复杂运算。
// 矩形是否相交function intersects(a, b) { return b.minX <= a.maxX && b.minY <= a.maxY && b.maxX >= a.minX && b.maxY >= a.minY;}这个包围盒特点，就很适合拿来应用 R 树来提高图形树的 检索效率。
R 树的数据结构是一个平衡树。
和其他索引树类似，R 树的叶子节点是数据节点，保存有图形信息和它的最小包围矩形（MBR）。
最小包围矩形其实就是包围盒。
结构大概类似这样：
{ minX: 20, minY: 40, maxX: 30, maxY: 50, // 保存图形数据，比如图形对象 id，或图形对象本身 data: {}};R 树会将距离相近的数据节点收集起来，并放到同一个父节点下。这个父节点是 索引节点，不会保存图形信息，但会记录子节点的合并的包围盒数据。
父节点如果多了，也会把它们收集起来，放到一个新的父节点下。
这样就形成了一个树的结构。
实际生产环境，推荐使用一个名为 RBush 的高性能 NPM 库。
代码用法示例：
import RBush from "rbush";// 创建一个 R 树实例const tree = new RBush();// 也可以指定一个索引节点最多有几个子节点，默认是 9 个const tree2 = new RBush(16);检索的过程如下：
提供一个选区矩形，从根节点开始，往下递归查找判断选取矩形是否和当前节点矩形相交。
直到可能相交的节点遍历完结束，然后返回 result 数组。
RBush 的搜索写法：
const result = tree.search({ minX: 20, minY: 20, maxX: 80, maxY: 70,});其源码实现：
class RBush { // ... search(bbox) { let node = this.data; const result = []; if (!intersects(bbox, node)) return result; const toBBox = this.toBBox; const nodesToSearch = []; while (node) { for (let i = 0; i < node.children.length; i++) { const child = node.children[i]; const childBBox = node.leaf ? toBBox(child) : child; if (intersects(bbox, childBBox)) { // 1. 遍历到数据节点 if (node.leaf) result.push(child); // 2. 索引节点 // 2.1. 包含关系，索引节点下的所有数据节点都加进 result else if (contains(bbox, childBBox)) this._all(child, result); // 2.2. 相交不包含关系，继续判断相交 else nodesToSearch.push(child); } } node = nodesToSearch.pop(); } return result; } _all(node, result) { const nodesToSearch = []; while (node) { if (node.leaf) result.push(...node.children); else nodesToSearch.push(...node.children); node = nodesToSearch.pop(); } return result; }}在图形编辑器初始化的时候，我们要计算图形树所有图形的包围盒，然后插入到 R 树上。
RBush 插入单个节点的写法：
const item = { minX: 20, minY: 40, maxX: 30, maxY: 50, graphId: '123',};tree.insert(item);支持批量插入节点，RBush 针对批量添加做了优化，效率比单个插入更高。
tree.load([item1, item2, /* ... */]);R 数作为索引数据，是要实时更新。
为此，我们需在每次图形物理属性改变的时候，重新计算包围盒，并更新 R 树。
tree.remove(item);tree.insert(newItem);还有一种同样可以减少遍历节点数量的算法，叫做 四叉树（Quadtree）碰撞检测。
四叉树将视口界面分割成多个区域，每个区域记住自己包含了哪些图形。
然后移动目标图形时，判断它落在哪个区域，取出所在区域的图形，这些图形集合就是和目标图形发生碰撞图形的超集。
当一个区域的图形数量过多时，又会进行分裂，再次分成 4 个区域。
四叉树更适合图形均匀分布的场景，如果不均匀，会产生大量空节点，且查询效率会降低。
R 树除了处理二维，还可以处理更高维度的数据，相比四叉树更适合范围查询。
本文链接：http://www.28at.com/showinfo-26-59641-0.html图形遍历效率低？试试 R 树
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
