RBush

RBush 是一个高性能的 Dart 库，用于点和矩形的 2D 空间索引。
它基于一个优化的R树数据结构，支持批量插入。

空间索引 是一个用于点和矩形的特殊数据结构
它允许你非常高效地执行“在此边界框内的所有项”之类的查询
(例如，比遍历所有项快数百倍)。
它最常用于地图和数据可视化。

用法

// Create a tree with up to 16 elements in a leaf.
final tree = RBush(16);

// Bulk load elements (empty in this case, so here it's a no-op).
tree.load(<RBushElement>[]);

// Insert a single element.
tree.insert(RBushElement(
  minX: 10, minY: 10,
  maxX: 20, maxY: 30,
  data: 'sample data'
));

// Find the element we've inserted.
final List<RBushElement> found = tree.search(
    RBushBox(minX: 5, minY: 5, maxX: 25, maxY: 25));

// Remove all elements from the tree.
tree.clear();

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

要存储不同类型的项，请从 RBushBase<T> 继承（或实例化）。
例如

class MyItem {
  final String id;
  final LatLng location;
  
  const MyItem(this.id, this.location);
}

final tree = RBushBase<MyItem>(
  maxEntries: 4,
  toBBox: (item) => RBushBox(
    minX: item.location.longitude,
    maxX: item.location.longitude,
    minY: item.location.latitude,
    maxY: item.location.latitude,
  ),
  getMinX: (item) => item.location.longitude,
  getMinY: (item) => item.location.latitude,
);

K 近邻

RBushBase 类还包含一个用于最近邻搜索的 knn() 方法。
这在使用 r-tree 存储点要素时特别有用，
就像上面的示例一样。

请注意，对于较大的地理区域，距离会不正确，因为
该类使用勾股定理距离 (dx² + dy²)，而不是 Haversine 或大圆距离。

Tiny Queue 和 Quick Select

该包还包括了一个优先级队列和
一个选择算法的移植的快速版本。这些是 r-tree 内部使用的，但可能
对您也有用。

上游

该库是 Vladimir Agafonkin 编写的几个 JavaScript 库的直接移植
Vladimir Agafonkin

所有这些都已根据 MIT 或 ISC 许可证发布。

GitHub

查看 Github