Skip to content

Latest commit

 

History

History
279 lines (256 loc) · 8.72 KB

README.md

File metadata and controls

279 lines (256 loc) · 8.72 KB
Raw

Barnes-Hut tree in Rust

Based on The Barnes-Hut Algorithm by Tom Ventimiglia & Kevin Wayne.
"A quad-tree is similar to a binary tree, except that each node has 4 children"

Made to learn Rust

My friend Tristan Brismontier was building a (more advance) Barnes-Hut in C# using Unity.
It looks like a nice project for learning Rust.
Also, an interesting candidate for building an Anomaly Detection Service

How to use

Add barnes dependency in Cargo.toml:

[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);
}

This code use 8 points:
barnes-hut quadrant

It produce this quadtree:
barnes-hut tree


The display:
```JS Square { x: 0, y: 0, lenght: 80, weight: 8, point: None, region: Some( Region { nw: Square { x: 0, y: 40, lenght: 40, weight: 1, point: Some( Point { x: 13, y: 62, name: "A" } ), region: None }, ne: Square { x: 40, y: 40, lenght: 40, weight: 3, point: None, region: Some( Region { nw: Square { x: 40, y: 60, lenght: 20, weight: 2, point: None, region: Some( Region { nw: Square { x: 40, y: 70, lenght: 10, weight: 0, point: None, region: None }, ne: Square { x: 50, y: 70, lenght: 10, weight: 1, point: Some( Point { x: 54, y: 72, name: "B" } ), region: None }, sw: Square { x: 40, y: 60, lenght: 10, weight: 1, point: Some( Point { x: 45, y: 65, name: "C" } ), region: None }, se: Square { x: 50, y: 60, lenght: 10, weight: 0, point: None, region: None } } ) }, ne: Square { x: 60, y: 60, lenght: 20, weight: 0, point: None, region: None }, sw: Square { x: 40, y: 40, lenght: 20, weight: 0, point: None, region: None }, se: Square { x: 60, y: 40, lenght: 20, weight: 1, point: Some( Point { x: 62, y: 57, name: "D" } ), region: None } } ) }, sw: Square { x: 0, y: 0, lenght: 40, weight: 3, point: None, region: Some( Region { nw: Square { x: 0, y: 20, lenght: 20, weight: 0, point: None, region: None }, ne: Square { x: 20, y: 20, lenght: 20, weight: 1, point: Some( Point { x: 38, y: 38, name: "E" } ), region: None }, sw: Square { x: 0, y: 0, lenght: 20, weight: 1, point: Some( Point { x: 11, y: 5, name: "F" } ), region: None }, se: Square { x: 20, y: 0, lenght: 20, weight: 1, point: Some( Point { x: 32, y: 11, name: "G" } ), region: None } } ) }, se: Square { x: 40, y: 0, lenght: 40, weight: 1, point: Some( Point { x: 52, y: 8, name: "H" } ), region: None } } ) } ```

Performance

in x: number of point to place in the tree
in y: time used in second

perf1

28 second to insert 40.000.000 point in the Barnes-Hut tree.
(on MacBook Pro 8 core)

Contact

Developed by Martin Magakian [email protected]
by Anomaly Detection

License

MIT License (MIT)