rust_3d/
aa_bb_tree_2d.rs

1/*
2Copyright 2018 Martin Buck
3
4Permission is hereby granted, free of charge, to any person obtaining a copy
5of this software and associated documentation files (the "Software"),
6to deal in the Software without restriction, including without limitation the
7rights to use, copy, modify, merge, publish, distribute, sublicense,
8and/or sell copies of the Software, and to permit persons to whom the Software
9is furnished to do so, subject to the following conditions:
10
11The above copyright notice and this permission notice shall
12be included all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
18DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
20OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21*/
22
23//! AABBTree2D, an axis aligned bounding box tree in 2D for fast collision detection
24
25use crate::*;
26
27use std::marker::PhantomData;
28
29//------------------------------------------------------------------------------
30
31#[derive(Clone)]
32/// AABBTree2D, an axis aligned bounding box tree in 2D for fast collision detection
33pub enum AABBTree2D<HB>
34where
35    HB: HasBoundingBox2D + Clone,
36{
37    Empty,
38    Leaf(AABBTree2DLeaf<HB>),
39    Branch(AABBTree2DBranch<HB>),
40}
41
42//------------------------------------------------------------------------------
43
44// currently often calculates the bounding box, try cache it
45impl<HB> AABBTree2D<HB>
46where
47    HB: HasBoundingBox2D + Clone,
48{
49    pub fn new(data: Vec<HB>, maxdepth: usize, allowed_bucket_size: usize) -> Self {
50        Self::new_rec(data, maxdepth, allowed_bucket_size, 0)
51    }
52
53    pub fn any<'a>(&'a self, f: &dyn Fn(&HB) -> bool) -> bool {
54        match self {
55            Self::Empty => false,
56            Self::Leaf(leaf) => leaf.any(f),
57            Self::Branch(branch) => branch.any(f),
58        }
59    }
60
61    pub fn for_each_collision_candidate<'a>(&'a self, bb: &BoundingBox2D, f: &mut dyn FnMut(&HB)) {
62        match self {
63            Self::Empty => (),
64            Self::Leaf(leaf) => leaf.for_each_collision_candidate(bb, f),
65            Self::Branch(branch) => branch.for_each_collision_candidate(bb, f),
66        }
67    }
68
69    pub fn bb_colliding<'a>(&'a self, bb: &BoundingBox2D, result: &mut Vec<&'a HB>) {
70        match self {
71            Self::Empty => (),
72            Self::Leaf(leaf) => leaf.bb_colliding(bb, result),
73            Self::Branch(branch) => branch.bb_colliding(bb, result),
74        }
75    }
76
77    pub fn bb_crossing_x_value<'a>(&'a self, x: f64, result: &mut Vec<&'a HB>) {
78        match self {
79            Self::Empty => (),
80            Self::Leaf(leaf) => leaf.bb_crossing_x_value(x, result),
81            Self::Branch(branch) => branch.bb_crossing_x_value(x, result),
82        }
83    }
84
85    pub fn bb_crossing_y_value<'a>(&'a self, y: f64, result: &mut Vec<&'a HB>) {
86        match self {
87            Self::Empty => (),
88            Self::Leaf(leaf) => leaf.bb_crossing_y_value(y, result),
89            Self::Branch(branch) => branch.bb_crossing_y_value(y, result),
90        }
91    }
92
93    fn new_rec(data: Vec<HB>, maxdepth: usize, allowed_bucket_size: usize, depth: usize) -> Self {
94        match data.len() {
95            0 => AABBTree2D::Empty,
96            1 => {
97                let bb = Self::bb_of(&data).unwrap(); //unwrap fine, since data non empty and with valid bbs (see new)
98                AABBTree2D::Leaf(AABBTree2DLeaf::new(data, bb))
99            }
100            _ => {
101                if depth >= maxdepth || data.len() <= allowed_bucket_size {
102                    let bb = Self::bb_of(&data).unwrap(); //unwrap fine, since data non empty and with valid bbs (see new)
103                    AABBTree2D::Leaf(AABBTree2DLeaf::new(data, bb))
104                } else {
105                    let compx = depth % 2 != 0;
106                    let bb = Self::bb_of(&data).unwrap(); //unwrap fine due to early return in new and data not empty
107                    let center = bb.center_bb();
108
109                    let dleft = data
110                        .iter()
111                        .cloned()
112                        .filter(|x| Self::is_left_of(compx, &x.bounding_box(), &center))
113                        .collect::<Vec<_>>();
114                    let dright = data
115                        .iter()
116                        .cloned()
117                        .filter(|x| Self::is_right_of(compx, &x.bounding_box(), &center))
118                        .collect::<Vec<_>>();
119
120                    if (dleft.len() == dright.len()) && dleft.len() == data.len() {
121                        AABBTree2D::Leaf(AABBTree2DLeaf::new(data, bb))
122                    } else {
123                        let left = Box::new(Self::new_rec(
124                            dleft,
125                            maxdepth,
126                            allowed_bucket_size,
127                            depth + 1,
128                        ));
129                        let right = Box::new(Self::new_rec(
130                            dright,
131                            maxdepth,
132                            allowed_bucket_size,
133                            depth + 1,
134                        ));
135
136                        AABBTree2D::Branch(AABBTree2DBranch::new(left, right, bb))
137                    }
138                }
139            }
140        }
141    }
142
143    fn is_left_of(compx: bool, bb: &BoundingBox2D, center: &Point2D) -> bool {
144        if compx {
145            bb.min_p().x() < center.x()
146        } else {
147            bb.min_p().y() < center.y()
148        }
149    }
150
151    fn is_right_of(compx: bool, bb: &BoundingBox2D, center: &Point2D) -> bool {
152        if compx {
153            bb.max_p().x() >= center.x()
154        } else {
155            bb.max_p().y() >= center.y()
156        }
157    }
158
159    fn bb_of(data: &Vec<HB>) -> Result<BoundingBox2D> {
160        if data.len() == 0 {
161            return Err(ErrorKind::TooFewPoints);
162        }
163        let mut result = data[0].bounding_box();
164        for x in data.iter() {
165            result.consume(x.bounding_box());
166        }
167
168        Ok(result)
169    }
170}
171
172//------------------------------------------------------------------------------
173
174#[derive(Clone)]
175/// Leaf of the AABBTree2D
176pub struct AABBTree2DLeaf<HB>
177where
178    HB: HasBoundingBox2D,
179{
180    data: Vec<HB>,
181    bb: BoundingBox2D,
182    _marker: PhantomData<HB>,
183}
184
185impl<HB> AABBTree2DLeaf<HB>
186where
187    HB: HasBoundingBox2D + Clone,
188{
189    pub fn new(data: Vec<HB>, bb: BoundingBox2D) -> Self {
190        AABBTree2DLeaf {
191            data,
192            bb,
193            _marker: PhantomData,
194        }
195    }
196
197    pub fn any<'a>(&'a self, f: &dyn Fn(&HB) -> bool) -> bool {
198        for x in self.data.iter() {
199            if f(x) {
200                //unwrap fine due to early return in new
201                return true;
202            }
203        }
204        false
205    }
206
207    pub fn for_each_collision_candidate<'a>(&'a self, bb: &BoundingBox2D, f: &mut dyn FnMut(&HB)) {
208        if !self.bb.collides_with(bb) {
209            return;
210        }
211        for x in self.data.iter() {
212            if x.bounding_box().collides_with(bb) {
213                f(x)
214            }
215        }
216    }
217
218    pub fn bb_colliding<'a>(&'a self, bb: &BoundingBox2D, result: &mut Vec<&'a HB>) {
219        if self.bb.collides_with(bb) {
220            for x in self.data.iter() {
221                if x.bounding_box().collides_with(bb) {
222                    result.push(x)
223                }
224            }
225        }
226    }
227
228    pub fn bb_crossing_x_value<'a>(&'a self, x: f64, result: &mut Vec<&'a HB>) {
229        if self.bb.crossing_x_value(x) {
230            for d in self.data.iter() {
231                if d.bounding_box().crossing_x_value(x) {
232                    result.push(d)
233                }
234            }
235        }
236    }
237
238    pub fn bb_crossing_y_value<'a>(&'a self, y: f64, result: &mut Vec<&'a HB>) {
239        if self.bb.crossing_y_value(y) {
240            for d in self.data.iter() {
241                if d.bounding_box().crossing_y_value(y) {
242                    result.push(d)
243                }
244            }
245        }
246    }
247}
248
249//------------------------------------------------------------------------------
250
251#[derive(Clone)]
252/// Branch of the AABBTree2D
253pub struct AABBTree2DBranch<HB>
254where
255    HB: HasBoundingBox2D + Clone,
256{
257    left: Box<AABBTree2D<HB>>,
258    right: Box<AABBTree2D<HB>>,
259    bb: BoundingBox2D,
260    _marker: PhantomData<HB>,
261}
262
263impl<HB> AABBTree2DBranch<HB>
264where
265    HB: HasBoundingBox2D + Clone,
266{
267    pub fn new(left: Box<AABBTree2D<HB>>, right: Box<AABBTree2D<HB>>, bb: BoundingBox2D) -> Self {
268        AABBTree2DBranch {
269            left,
270            right,
271            bb,
272            _marker: PhantomData,
273        }
274    }
275
276    pub fn any<'a>(&'a self, f: &dyn Fn(&HB) -> bool) -> bool {
277        self.left.any(f) || self.right.any(f)
278    }
279
280    pub fn for_each_collision_candidate<'a>(&'a self, bb: &BoundingBox2D, f: &mut dyn FnMut(&HB)) {
281        if !self.bb.collides_with(bb) {
282            return;
283        }
284
285        self.left.for_each_collision_candidate(bb, f);
286        self.right.for_each_collision_candidate(bb, f);
287    }
288
289    pub fn bb_colliding<'a>(&'a self, bb: &BoundingBox2D, result: &mut Vec<&'a HB>) {
290        if self.bb.collides_with(bb) {
291            self.left.bb_colliding(bb, result);
292            self.right.bb_colliding(bb, result);
293        }
294    }
295
296    pub fn bb_crossing_x_value<'a>(&'a self, x: f64, result: &mut Vec<&'a HB>) {
297        if self.bb.crossing_x_value(x) {
298            self.left.bb_crossing_x_value(x, result);
299            self.right.bb_crossing_x_value(x, result);
300        }
301    }
302
303    pub fn bb_crossing_y_value<'a>(&'a self, y: f64, result: &mut Vec<&'a HB>) {
304        if self.bb.crossing_y_value(y) {
305            self.left.bb_crossing_y_value(y, result);
306            self.right.bb_crossing_y_value(y, result);
307        }
308    }
309}
rust_3d/aa_bb_tree_2d.rs

rust_3d/
aa_bb_tree_2d.rs
