Collide Tree
A test for colliding many objects that runs at O(n*lg(n))
and can be used at any number of dimensions
This runs faster than the naive, "compare everything with everything else" system, with over 25 elements.
With 1000 Elements, it runs in a 5th of the time.
- Naive : ~= 210.3ms
- Collide Tree: ~= 38.ms
How to use it.
The CollideTree object is dependant on the following two traits
When you create the CollideTree, you must provide it with a <T:BoundBox>. This will represent the area the tree will put the items into. Items you add will all be of type <L:Located+Debug> and the bounds method must return a T.
to get a list of collisions from a list of 'L', simply add them to the tree, and use the closure to mark what you want to do with the collisions.
let list = create_range_list;
let mut tree = new;
//the vec for building the result
let mut t_col = Vec new;
for a in &list