3 个版本
使用旧的 Rust 2015
| 0.1.2 | 2015 年 6 月 2 日 |
|---|---|
| 0.1.1 | 2015 年 6 月 2 日 |
| 0.1.0 | 2015 年 6 月 2 日 |
#150 在 #multi-threading
22 每月下载次数
80KB
226 行
Rust 中的巴恩斯-胡特树
基于 Tom Ventimiglia & Kevin Wayne 的 巴恩斯-胡特算法。
"四叉树类似于二叉树，但每个节点有 4 个子节点"。
为了学习 Rust 而制作
我的朋友 Tristan Brismontier 正在构建一个（更高级的）使用 Unity 的 C# 版巴恩斯-胡特算法。
这看起来像是一个很好的 Rust 学习项目。
此外，它也是一个构建 异常检测服务 的有趣候选者。
如何使用
在 Cargo.toml 中添加 barnes 依赖项
[dependencies]
barnes = "0.1.0"
extern crate barnes;
use data::{Point, Square, Region};
use tree::Tree;
fn create_points() -> Vec<Point> {
vec![
Point::new(13, 62, "A"),
Point::new(45, 65, "C"),
Point::new(54, 72, "B"),
Point::new(62, 57, "D"),
Point::new(38, 38, "E"),
Point::new(11, 5, "F"),
Point::new(32, 11, "G"),
Point::new(52, 8, "H"),
]
}
fn main() {
let mut square = Square::new(0, 0, 80);
square = Tree.compute_root(square, create_points());
println!("{:?}", square);
}
此代码使用 8 个点
它产生这个四叉树
显示
```JS Square { x: 0, y: 0, length: 80, weight: 8, point: None, region: Some( Region { nw: Square { x: 0, y: 40, length: 40, weight: 1, point: Some( Point { x: 13, y: 62, name: "A" } ), region: None }, ne: Square { x: 40, y: 40, length: 40, weight: 3, point: None, region: Some( Region { nw: Square { x: 40, y: 60, length: 20, weight: 2, point: None, region: Some( Region { nw: Square { x: 40, y: 70, length: 10, weight: 0, point: None, region: None }, ne: Square { x: 50, y: 70, length: 10, weight: 1, point: Some( Point { x: 54, y: 72, name: "B" } ), region: None }, sw: Square { x: 40, y: 60, length: 10, weight: 1, point: Some( Point { x: 45, y: 65, name: "C" } ), region: None }, se: Square { x: 50, y: 60, length: 10, weight: 0, point: None, region: None } } ) }, ne: Square { x: 60, y: 60, length: 20, weight: 0, point: None, region: None }, sw: Square { x: 40, y: 40, length: 20, weight: 0, point: None, region: None }, se: Square { x: 60, y: 40, length: 20, weight: 1, point: Some( Point { x: 62, y: 57, name: "D" } ), region: None } } ) }, sw: Square { x: 0, y: 0, length: 40, weight: 3, point: None, region: Some( Region { nw: Square { x: 0, y: 20, length: 20, weight: 0, point: None, region: None }, ne: Square { x: 20, y: 20, length: 20, weight: 1, point: Some( Point { x: 38, y: 38, name: "E" } ), region: None }, sw: Square { x: 0, y: 0, length: 20, weight: 1, point: Some( Point { x: 11, y: 5, name: "F" } ), region: None }, se: Square { x: 20, y: 0, length: 20, weight: 1, point: Some( Point { x: 32, y: 11, name: "G" } ), region: None } } ) }, se: Square { x: 40, y: 0, length: 40, weight: 1, point: Some( Point { x: 52, y: 8, name: "H" } ), region: None } } ) } ```
性能
x：树中放置的点数
y：所用时间（秒）
在Barnes-Hut树中插入4000万点耗时28秒。
(在MacBook Pro 8核心处理器上)
联系
由Martin Magakian开发 [email protected]
由 Anomaly Detection 提供
许可证
MIT许可证 (MIT)