27 releases (6 breaking)

✓ Uses Rust 2018 edition

new 0.7.5 Jan 13, 2020
0.7.4 Dec 23, 2019
0.6.2 Dec 1, 2019
0.5.6 Nov 30, 2019
0.1.1 Nov 5, 2018

#84 in Data structures

Download history 17/week @ 2019-10-03 21/week @ 2019-10-17 19/week @ 2019-10-24 34/week @ 2019-10-31 20/week @ 2019-11-07 23/week @ 2019-11-14 23/week @ 2019-11-21 219/week @ 2019-11-28 51/week @ 2019-12-05 695/week @ 2019-12-12 23/week @ 2019-12-19 30/week @ 2019-12-26 30/week @ 2020-01-02 211/week @ 2020-01-09

462 downloads per month

MIT/Apache

2MB
4K SLoC

Overview

This crate hopes to provide an efficient 2D space partitioning data structure and useful query algorithms to perform on it in a hopefully simple cohesive api. It is a hybrid between a KD Tree and Sweep and Prune. Uses no_std, but uses the alloc crate. Please see the dinotree-book which is a work in-progress high level explanation and analysis of this crate.

Inner projects

The dinotree_alg_demo inner project is meant to show case the use of these algorithms. It depends on the piston 2d engine to draw to the screen.

Analysis

Please see the book for a work in progress writeup of the design and analysis of the algorithms in this project.

Screenshot

Screen capture from the inner dinotree_alg_demo project.

screenshot

Example

use axgeom::rect;
use dinotree_alg::prelude::*;

fn main(){
	let mut aabbs=[
		BBox::new(rect(0isize,10,0,10),0),    
		BBox::new(rect(15,20,15,20),0), 
		BBox::new(rect(5,15,5,15),0)
	];
	
	//Create a layer of direction.
	let mut ref_aabbs  = aabbs.iter_mut().collect::<Vec<_>>();

	//This will change the order of the elements in bboxes,
	//but this is okay since we populated it with mutable references.	
	let mut tree=DinoTree::new(&mut ref_aabbs);

	//Find all colliding aabbs.
	tree.find_collisions_mut(|mut a,mut b|{
		*a.inner_mut()+=1;
		*b.inner_mut()+=1;
	});

	assert_eq!(aabbs[0].inner, 1);
	assert_eq!(aabbs[1].inner, 0);
	assert_eq!(aabbs[2].inner, 1);
}

Dependencies