39 releases (7 breaking)

0.8.11 Jul 21, 2020
0.8.5 Mar 31, 2020
0.7.4 Dec 23, 2019
0.5.6 Nov 30, 2019
0.1.1 Nov 5, 2018

#92 in Data structures

Download history 146/week @ 2020-04-08 150/week @ 2020-04-15 18/week @ 2020-04-22 3/week @ 2020-04-29 38/week @ 2020-05-06 1/week @ 2020-05-13 11/week @ 2020-05-20 39/week @ 2020-05-27 131/week @ 2020-06-03 38/week @ 2020-06-17 38/week @ 2020-07-01 39/week @ 2020-07-08 80/week @ 2020-07-15 103/week @ 2020-07-22

144 downloads per month

MIT/Apache

2MB
4.5K 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.

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::*;

fn main() {
    let mut aabbs = [
        bbox(rect(0isize, 10, 0, 10), 0),
        bbox(rect(15, 20, 15, 20), 0),
        bbox(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_intersections_mut(|a, b| {
        *a += 1;
        *b += 1;
    });

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

Dependencies