1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
//! //! //! //! ~~~~text //! 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 //! //! This crate hopes to provide an efficient 2D space partitioning data structure and useful query algorithms to perform on it. //! It is a hybrid between a [KD Tree](https://en.wikipedia.org/wiki/K-d_tree) and [Sweep and Prune](https://en.wikipedia.org/wiki/Sweep_and_prune). //! //! ## Data Structure //! //! Using this crate, the user can create three flavors of the same fundamental data structure. They each //! have different characteristics that may make you want to use them over the others. You can make a dinotree //! composed of the following: //! //! //! + `(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 //! //! TODO talk about Rect<N> properties. //! //! 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. //! //! //! ## 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. //! #![no_std] #[macro_use] extern crate alloc; extern crate is_sorted; extern crate pdqselect; ///Prelude to include by using: pub use dinotree::prelude::* pub mod prelude{ pub use crate::*; pub use crate::elem::*; pub use crate::bbox::*; pub use crate::query::*; pub use crate::par; pub use crate::tree::node::*; } mod inner_prelude { pub use axgeom::*; pub use core::iter::*; pub use core::marker::PhantomData; pub use alloc::vec::Vec; pub(crate) use super::*; pub(crate) use compt::Visitor; pub(crate) use crate::tree; pub(crate) use crate::tree::analyze_inner::*; pub(crate) use crate::tree::*; pub(crate) use crate::elem::*; pub(crate) use crate::bbox::*; pub(crate) use crate::par; } pub mod query; use axgeom::*; ///Contains code to check the data structure is valid. #[cfg(feature = "analyze")] mod assert_invariants; ///Contains generic code used in all dinotree versions pub use self::tree::*; mod tree; ///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. pub mod par; ///A collection of 1d functions that operate on lists of 2d objects. mod oned; ///Provies a slice that produces BBox's where users can only interact ///with through the HasInner trait so as to protect the invariants of the tree. pub mod elem; ///A collection of different bounding box containers. pub mod bbox; ///Generic slice utillity functions. pub mod util; ///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. pub trait NumTrait: Ord + Copy + Send + Sync {} impl<T> NumTrait for T where T: Ord + Copy + Send + Sync {} ///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. pub unsafe trait HasAabb{ type Num: NumTrait; fn get(&self) -> &Rect<Self::Num>; } ///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. pub trait HasInner:HasAabb{ type Inner; #[inline(always)] fn inner_mut(&mut self)->&mut Self::Inner{ self.get_inner_mut().1 } #[inline(always)] fn inner(&self)->&Self::Inner{ self.get_inner().1 } fn get_inner(&self)->(&Rect<Self::Num>,&Self::Inner); fn get_inner_mut(&mut self)->(&Rect<Self::Num>,&mut Self::Inner); }