## barnes

A multithreaded Barnes Hut Algorithm implementation

### 3 releases

Uses old Rust 2015

 0.1.2 Jun 2, 2015 Jun 2, 2015 Jun 2, 2015

#610 in Algorithms

80KB
226 lines

# 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"

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

``````[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:

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

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

# Contact

Developed by Martin Magakian dev.martin.magakian@gmail.com
by Anomaly Detection