rtree.rs

为Rust提供了一个快速的R-tree。从为Tile38设计的实现移植而来。

功能

• 优化 以快速插入和更新。适用于静态和动态数据。
• 标准的 insert、remove 和 search 操作
• 包含用于执行最近邻（kNN）迭代的 nearby 函数
• 支持整数或浮点数坐标。例如 f32、f64、u64 等。
• 使用 const generics 支持多维度。

示例

添加点

use rtree_rs::{RTree, Rect};

let mut tr = RTree::new();

// Insert some points
tr.insert(Rect::new_point([-112.0078, 33.4373]), "PHX");
tr.insert(Rect::new_point([-118.4071, 33.9425]), "LAX");
tr.insert(Rect::new_point([-73.7822, 40.6441]),  "JFK");

// Search a rectangle
for item in tr.search(Rect::new([-112.1, 33.4], [-112.0, 33.5])) {
    println!("{}", item.data);
}

// OUTPUT:
// PHX

添加矩形

tr.insert(Rect::new([10, 10], [20, 20]), "R1");
tr.insert(Rect::new([15, 12], [18, 24]), "R2");

多维度

tr.insert(Rect::new([10, 10, 10], [20, 20, 20]), "R1");
tr.insert(Rect::new_point([15, 12, 24]), "P1");

算法

此实现是原始论文的变体
R-TREES. 空间搜索的动态索引结构

插入

从根节点到叶节点，选择将产生最小膨胀的矩形。如果有平局，则选择面积最小的矩形。

当一个矩形不产生任何膨胀时，它将被立即选择，而无需检查同一节点中的其他矩形。

分割

此实现尝试最小化诸如对子节点进行预排序和比较重叠区域与面积大小之类的密集操作。目标是每个子节点仅进行一次简单的单轴距离计算，目标是在内存中移动子节点的概率为50/50。

当一个矩形达到其最大条目数时，计算其最大轴，并将矩形分割成两个较小的矩形，分别命名为 left 和 right。然后对每个子矩形进行评估，以确定它应该放置在哪个较小的矩形中。为每个子矩形计算两个值，min-dist 和 max-dist。

• min-dist 表示从父节点的最大轴的最小值到子节点的父节点最大轴的最小值的距离。
• max-dist 表示从父节点的最大轴的最大值到子节点的父节点最大轴的最大值的距离。

当 min-dist 小于 max-dist 时，子节点将被放置到 left 矩形内，否则子节点将被放置到 right 矩形内。

如果左侧或右侧的条目数量少于最小允许数量，则将从另一个矩形中取足够的条目以确保达到最小值。选择的是基于最远边缘到另一个矩形轴的距离。

最后，子矩形按照其父节点的最小 x 值进行排序。

删除

与原始算法类似。直接删除目标矩形。当一个矩形的子节点数量低于最小允许数量时，该子节点将从树中删除，并且所有其叶子项目将重新插入到树中，从根节点开始。

搜索

与原始算法相同。

性能

在我的2021款Macbook M1 Max上。

cd bench
cargo run --release

insert:        1,000,000 ops in 347ms, 2,880,185/sec, 347 ns/op
search-item:   1,000,000 ops in 370ms, 2,700,423/sec, 370 ns/op
search-1%:     10,000 ops in 31ms, 321,916/sec, 3106 ns/op
search-5%:     10,000 ops in 233ms, 42,739/sec, 23397 ns/op
search-10%:    10,000 ops in 704ms, 14,195/sec, 70442 ns/op
remove-half:   500,000 ops in 170ms, 2,937,350/sec, 340 ns/op
reinsert-half: 500,000 ops in 169ms, 2,945,730/sec, 339 ns/op
search-item:   1,000,000 ops in 434ms, 2,304,059/sec, 434 ns/op
search-1%:     10,000 ops in 34ms, 287,740/sec, 3475 ns/op
remove-all:    1,000,000 ops in 363ms, 2,751,735/sec, 363 ns/op