图形遍历效率低?试试 R 树

2024年 1月 10日 62.8k 0

大家好,我是前端西瓜哥。

今天我们来看看 R 树是什么?以及它为什么能够提高图形的检索速度。

R 树(R-tree)是一种 空间索引技术,能够是从大量的节点中,快速找到特定范围的元素集合,而不用一个不落地遍历所有节点。

思路和其他索引算法(比如 B 树、跳表)有点像,但 R 树针对的是高维数据的查询 。R 树的 “R” 指的是矩形(Rectangle)。

举个具体的例子,假设有一张地图,上面有几百万个节点,要快速找某个位置半径 2 公里的所有餐馆的信息。

低效的做法是遍历这几百万的节点的位置,判断距离是否小于 2 公里。

但如果用上索引技术,比如 R 树,我们就能利用索引去 空间换时间,快速拿到特定范围的节点超集,比如几千个。

接着只需要遍历这几千个节点去判断符合条件的节点就可以了,而不需要完完整整遍历所有的节点。

除此之外还可以:

  • 快速检索平面中和选区矩形相交的二维图形;
  • 在数据库中快速找出多维度的产品,比如价格、库存、过期时间在特定范围的商品。

R 树的数据结构

下面看一下在图形编辑器的一个场景。

我们构建了一棵图形树,图形树的图形有位置、宽高等属性,并渲染在画布上。

需要实现选择功能,绘制一个矩形选区,使和该选区矩形相交的图形高亮。

为实现这个能力,我们计算图形树上的每个图形的包围盒:一个用 minX,minY、maxX、maxY 表达的一个矩形,它刚好包围住图形。

包围盒的作用是简化碰撞算法,一些复杂的图形,比如贝塞尔曲线,如果要严格意义上判断碰撞,是要进行复杂的计算的,在有大量图形的场景下,性能非常糟糕。

所以业内常用矩形包围盒的碰撞来简化,这种算法非常简单高效,可直接用来替代原本复杂精细的碰撞检测,或是在进行复杂碰撞算法前先做一层过滤,避免无谓的复杂运算。

// 矩形是否相交
function intersects(a, b) {
  return b.minX = 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);

R 树的检索

检索的过程如下:

提供一个选区矩形,从根节点开始,往下递归查找判断选取矩形是否和当前节点矩形相交。

  • 若不相交,其下的节点也不会相交,该节点对应的子树就不需要继续递归了。
  • 若相交且为数据节点(叶子节点),将其放到 result 数组。
  • 若是包含关系,其下的所有数据节点放到 result 数组。
  • 若相交但并不包含,则遍历其下的子节点,重复前面的操作。

直到可能相交的节点遍历完结束,然后返回 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 树的更新

1、初始化

在图形编辑器初始化的时候,我们要计算图形树所有图形的包围盒,然后插入到 R 树上。

RBush 插入单个节点的写法:

const item = {
  minX: 20,
  minY: 40,
  maxX: 30,
  maxY: 50,
  graphId: '123',
};

tree.insert(item);

支持批量插入节点,RBush 针对批量添加做了优化,效率比单个插入更高。

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

2、更新

R 数作为索引数据,是要实时更新。

为此,我们需在每次图形物理属性改变的时候,重新计算包围盒,并更新 R 树。

tree.remove(item);
tree.insert(newItem);

四叉树(Quadtree)

还有一种同样可以减少遍历节点数量的算法,叫做 四叉树(Quadtree)碰撞检测。

四叉树将视口界面分割成多个区域,每个区域记住自己包含了哪些图形。

然后移动目标图形时,判断它落在哪个区域,取出所在区域的图形,这些图形集合就是和目标图形发生碰撞图形的超集。

当一个区域的图形数量过多时,又会进行分裂,再次分成 4 个区域。

四叉树更适合图形均匀分布的场景,如果不均匀,会产生大量空节点,且查询效率会降低。

R 树除了处理二维,还可以处理更高维度的数据,相比四叉树更适合范围查询。

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论