[−][src]Crate dinotree_alg
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.
Data Structure
Using this crate, the user can create three flavors of the same fundamental data structure. The different characteristics are exlored more in depth in the book mentioned in the overview section.
(Rect<N>,&mut T)*recommended(Rect<N>,T)&mut (Rect<N>,T)
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.
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
The AABB struct that the user must use is from the axgeom crate.
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 anyway 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.
Unsafety
MultiRectMut uses unsafety to allow the user to have mutable references to elements
that belong to rectangle regions that don't intersect at the same time. This is why
the Aabb trait is unsafe.
Modules
| analyze | Contains code to manipulate the dinotree data structure and some of its query algorithms to help analyze and measure their performance. |
| bbox | A collection of different bounding box containers. |
| bbox_helper | Helper module for creating Vecs of different types of BBoxes. |
| dinotree_owned | A version of dinotree that is not lifetimed and uses unsafe{} to own the elements
that are in its tree (as a self-referential struct). Composed of |
| node | Contains node-level building block structs and visitors used for a DinoTree. |
| par | Contains code to write generic code that can be run in parallel, or sequentially. The api is exposed in case users find it useful when writing parallel query code to operate on the tree. |
| pmut | Provides a mutable pointer type that is more restrictive that &mut T, in order to protect tree invariants. PMut is short for protected mutable reference. |
| prelude | Prelude to include by using: pub use dinotree::prelude::* |
| query | Module contains query related structs. |
| util | Generic slice utillity functions. |
Structs
| DinoTree | The data structure this crate revoles around. |
Traits
| Aabb | Trait to signify that this object has an axis aligned bounding box. get() must return a aabb with the same value in it while the element is in the dinotree. This is hard for the user not to do, this the user does not have &mut self, and the aabb is implied to belong to self. But it is still possible through the use of static objects or RefCell/ Mutex, etc. Using this type of methods the user could make different calls to get() return different aabbs. This is unsafe since we allow query algorithms to assume the following: If two object's aabb's don't intersect, then they can be mutated at the same time. |
| HasInner | Trait exposes an api where you can return a read-only reference to the axis-aligned bounding box and at the same time return a mutable reference to a seperate inner section. |
| Num | The underlying number type used for the dinotree. It is auto implemented by all types that satisfy the type constraints. Notice that no arithmatic is possible. The tree is constructed using only comparisons and copying. |
Functions
| default_axis | Constructor of the default axis type. Needed since you cannot construct from type alias's. |
Type Definitions
| DefaultA | The type of the axis of the first node in the dinotree. If it is the y axis, then the first divider will be a horizontal line, since it is partioning space based off of objects y value. |