Collide Tree

一个针对多个物体碰撞的测试，运行速度为 O(n*lg(n))，且可在任意维度下使用

这比简单的“逐个比较所有物体”的系统运行得更快，超过25个元素。

对于1000个元素，它运行的时间仅为五分之一。

• 简单方法：约210.3毫秒
• Collide Tree：约38毫秒

如何使用它。

CollideTree对象依赖于以下两个特质

pub trait BoundBox: Sized + Clone {
    ///Split the box in half somehow, normally this should vary in direction
    fn split(&self) -> (Self, Self);
    ///Test if one box collides with another.
    fn hits(&self, b: &Self) -> bool;
}

pub trait Located {
    type Box: BoundBox;
    fn bounds(&self) -> Self::Box;
}

当你创建CollideTree时，你必须提供它一个 <T:BoundBox>。这将代表树将项目放入的区域。你添加的项目都将为类型 <L:Located+Debug>，且边界方法必须返回一个T。

要从一组'L'中获取碰撞列表，只需将它们添加到树中，并使用闭包来标记你对碰撞想要做什么。

    let list = create_range_list(1000);
    let mut tree = CollideTree::new(Bounds::new(0., 0., 1000., 1000.));

    //the vec for building the result 
    let mut t_col = Vec::new();


    for a in &list {
        //in the closure add the collision ids to the result. or do something else with them
        tree.add_item(a.clone(), &mut |a, b| t_col.push((a.id, b.id)));
    }