#tree #dinotree #kdtree #space-partitioning

dinotree

An aabb space partitioning 2d tree data structure

19 releases (4 breaking)

✓ Uses Rust 2018 edition

new 0.5.1 Sep 18, 2019
0.5.0 Sep 16, 2019
0.4.4 Sep 10, 2019
0.3.0 Jan 26, 2019
0.1.0 Oct 29, 2018

#171 in Data structures

Download history 12/week @ 2019-06-05 48/week @ 2019-06-12 37/week @ 2019-06-19 72/week @ 2019-06-26 83/week @ 2019-07-03 48/week @ 2019-07-10 12/week @ 2019-07-17 21/week @ 2019-07-31 36/week @ 2019-08-07 1/week @ 2019-08-14 48/week @ 2019-08-21 58/week @ 2019-08-28 88/week @ 2019-09-04 48/week @ 2019-09-11

184 downloads per month
Used in 1 crate

MIT/Apache

63KB
1K SLoC

Provides the dinotree data structure and ways to traverse it. All divide and conquer style query algorithms that you can do on this tree would be done using the Vistr nd VistrMut visitors. No actual query algorithms are provided in this crate. Only the data structure and a way to construct it are provided in this crate.


lib.rs:

2d Tree Divider Representation:


   o   ┆┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┃         ┆         o
 ┈┈┈┈┈┈┆     o      o     ┃     o   ┆   o                 o
 ───────o─────────────────┃         o┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈
               ┆       o  o   o     ┆
       o       ┆    o     ┃┈┈┈┈┈o┈┈┈┆       o
               ┆   o      ┃         o             o
               ┆┈┈┈┈┈┈┈┈┈┈┃         ┆                   o
     o         o    o     ┃───────o────────────────────────
               ┆          ┃                ┆   o
 ┈┈┈┈┈┈┈┈┈┈┈┈┈┈┆      o   o   o            ┆┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈
    o          ┆          ┃┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┈┆         o
         o     ┆   o      ┃        o       ┆   o
               ┆          ┃                ┆

Axis alternates every level.
Divider placement is placed at the median at each level.
Objects that intersect a divider belong to that node.
Every divider keeps track of how thick a line would have to be
to 'cover' all the bots it owns.
All the objects in a node are sorted along that node's axis.


Overview

Provides the dinotree data structure and ways to traverse it. No actual query algorithms are provided in this crate. Only the data structure and a way to construct and traverse it are provided in this crate.

Data Structure

Using this crate, the user can create three flavors of the same fundamental data structure are provided. They each have different characteristics that may make you want to use them over the others. You can make a dinotree composed of either:

  • (Rect<N>,&mut T) is the most well rounded and most performant in most cases. The aabb's themselves don't have a level of indirection. Broad-phase algorithms need to look at these very often. It's only when these algorithms detect a intersection do they need to look further, which doesnt happen as often. so a level of indirection here is not so bad. The fact that T is a pointer, also means that more aabb's will be in cache at once, further speeding up algorithms that need to look at the aabb's very often.

  • (Rect<N>,T) performs slightly better during the querying phase, But suffers during the construction phase. There is also no easy way to return the elements back to their original positions on destructing of the tree (something you don't need to worry about with pointers). One benefit of using this tree, is that it owns the elements completely, so there are no lifetime references to worry about. The performance of this type of tree is also heavily influenced by the size of T.

  • &mut (Rect<N>,T) has comparable tree construction times to (Rect<N>,&mut T) given that we are just sorting and swapping pointers, but there is no cache-coherence during the query phase, so this can cause real slow down to query algorithms if there are many overlapping elements.

DinoTreeOwned

A verion of the tree where the tree owns the elements in side of it. The user is encouraged to use the lifetimed version, though, as that does not use unsafe{}. But this might mean that the user has to re-construct the tree more often than it needs to be. It is composed internally of the equivalent to (Rect<N>,&mut T), the most well-rounded data layout as described above.

NotSorted

For comparison, a normal kd-tree is provided by NotSorted. In this tree, the elements are not sorted along an axis at each level. Construction of NotSorted is faster than DinoTree since it does not have to sort bots that belong to each node along an axis. But most query algorithms can usually take advantage of this extra property.

User Protection

A lot is done to forbid the user from violating the invariants of the tree once constructed while still allowing them to mutate elements of the tree. The user can mutably traverse down the tree with a VistrMut and ElemSliceMut, but the elements that are returned have already been destructured in such a way that the user only has read-only access to the Rect<N>, even if they do have write access to the inner T.

Usage Guidlines

If you insert aabb's with zero width or zero height, it is unspecified behavior (but still safe). It is expected that all elements in the tree take up some area. This is not inteded to be used as a "point" tree. Using this tree for a point tree would be inefficient since the data layout assumes there is a aabb, which is composed of 4 numbers when a point would be just 2.

That said, an aabb is composed of half-open ranges [start,end). So one could simulate a "point", by putting in a very small epsilon value to ensure that end>start.

Dependencies

~1.5MB
~30K SLoC