hprtree

关于

这是一个 Rust 的 Hilbert-Packed-R-Tree 实现（也许可以参考 维基百科）。

处理坐标与 Hilbert 索引之间映射的 (C++) 代码不是我写的，可以在 GitHub 上找到，以及 (!only http) http://threadlocalmutex.com 上的有趣文章链接。

示例用法

use hprtree::{Point, BBox, HPRTreeBuilder};

let mut index = HPRTreeBuilder::new(10);
index.insert("Bob".to_string(), Point{ x: 0f32, y: 0f32 });
for _ in 0..2 {
    index.insert("Alice".to_string(), Point{ x: 1f32, y: 1f32 });
}
index.insert("James".to_string(), Point{ x: 2.5f32, y: -2.5f32 });
index.insert("Annie".to_string(), Point{ x: 20f32, y: 1f32 });
for _ in 0..5 {
    index.insert("Thomas".to_string(), Point{ x: 1f32, y: -50f32 });
}

let index = index.build();

let mut result = Vec::with_capacity(4);
index.query_with_list(&BBox
           {
               minx: -5f32,
               miny: -5f32,
               maxx: 5f32,
               maxy: 5f32
           }, &mut result);

assert!(result.len() == 4); // this Vec now contains the Strings "Bob", "Alice"(x2) and "James"

for i in result {
    assert!(i == "Bob".to_string() || i == "Alice".to_string() || i == "James".to_string());
    // there are absolutely no guarantees regarding ordering though
}

也许还可以看看 lib.rs 中的测试