3929938005

Build Type

push

github

Committed by GitHub

Commit Message

Merge #713

Run Details

84930 of 96741 relevant lines covered (87.79%)

79640.1 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

89.44

/operators/src/processing/circle_merging_quadtree/quadtree.rs

use std::collections::VecDeque;

use geoengine_datatypes::primitives::{BoundingBox2D, Circle, Coordinate2D, TimeInterval};

use super::{circle_of_points::CircleOfPoints, circle_radius_model::CircleRadiusModel, node::Node};

#[derive(Debug)]
pub struct CircleMergingQuadtree<C: CircleRadiusModel> {
    head: Box<Node>,
    circle_radius_model: C,
    max_items_per_node: usize,
}

pub struct IntoIter {
    stack: Vec<Node>,
}

pub struct Iter<'t> {
    stack: Vec<&'t Node>,
    output: Vec<CircleOfPoints>,
}

pub struct RectangleIter<'a> {
    stack: VecDeque<&'a Node>,
}

impl<C> CircleMergingQuadtree<C>
where
    C: CircleRadiusModel,
{
    pub fn new(bounds: BoundingBox2D, circle_radius_model: C, max_items_per_node: usize) -> Self {
        CircleMergingQuadtree {
            head: Box::new(Node::new(bounds)),
            circle_radius_model,
            max_items_per_node,
        }
    }

    pub fn insert(&mut self, coordinate: &Coordinate2D) {
        let new_circle = CircleOfPoints::new_with_one_point(
            Circle::from_coordinate(coordinate, self.circle_radius_model.min_radius()),
            TimeInterval::default(),
            Default::default(), // TODO: allow inserting attribute data
        );

        self.insert_circle(new_circle);
    }

    /// Use the output of a tree as input to another one.
    ///
    /// This is useful to build a lower resolution tree upon existing circles.
    pub fn insert_tree(&mut self, tree: CircleMergingQuadtree<C>) {
        for circle in tree {
            self.insert_circle(circle);
        }
    }

    pub fn insert_circle(&mut self, new_circle: CircleOfPoints) {
        let mut insert_attempt = self.head.try_insert(
            new_circle,
            self.circle_radius_model.delta(),
            self.max_items_per_node,
        );

        while let Err((circle1, circle2)) = insert_attempt {
            let mut new_circle = circle1;
            new_circle.merge(&circle2, &self.circle_radius_model);
            insert_attempt = self.head.try_insert(
                new_circle,
                self.circle_radius_model.delta(),
                self.max_items_per_node,
            );
        }
    }

    pub fn iter_rectangles(&self) -> RectangleIter {
        let mut stack = VecDeque::new();
        stack.push_back(&*self.head);
        RectangleIter { stack }
    }
}

impl<C> IntoIterator for CircleMergingQuadtree<C>
where
    C: CircleRadiusModel,
{
    type Item = CircleOfPoints;
    type IntoIter = IntoIter;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            stack: vec![*self.head],
        }
    }
}

impl Iterator for IntoIter {
    type Item = CircleOfPoints;

    fn next(&mut self) -> Option<Self::Item> {
        let mut top_node = self.stack.pop();

        while let Some(mut node) = top_node {
            match node.circles.pop() {
                Some(circle) => {
                    self.stack.push(node);
                    return Some(circle);
                }
                None => {
                    if let Some(link) = node.link {
                        self.stack.append(&mut (link as Box<[_]>).into_vec());
                    }
                    top_node = self.stack.pop();
                }
            }
        }

        None
    }
}

impl<'t, C> IntoIterator for &'t CircleMergingQuadtree<C>
where
    C: CircleRadiusModel,
{
    type Item = CircleOfPoints;
    type IntoIter = Iter<'t>;

    fn into_iter(self) -> Self::IntoIter {
        Iter {
            stack: vec![self.head.as_ref()],
            output: Vec::new(),
        }
    }
}

impl<'t> Iterator for Iter<'t> {
    type Item = CircleOfPoints;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(circle) = self.output.pop() {
            return Some(circle);
        }

        let mut top_node = self.stack.pop();

        while let Some(node) = top_node {
            self.output.append(&mut node.circles.clone());

            if let Some(ref quad_reference) = node.link {
                self.stack
                    .extend_from_slice(&quad_reference.iter().collect::<Vec<&Node>>());
            }

            if self.output.is_empty() {
                top_node = self.stack.pop();
            } else {
                return self.output.pop();
            }
        }

        None
    }
}

impl<'a> Iterator for RectangleIter<'a> {
    type Item = &'a BoundingBox2D;

    fn next(&mut self) -> Option<Self::Item> {
        self.stack.pop_front().map(|node| {
            if let Some(ref link) = node.link {
                for child_node in link.iter() {
                    self.stack.push_back(child_node);
                }
            }

            &node.rectangle
        })
    }
}

#[cfg(test)]
mod test {
    use crate::processing::circle_merging_quadtree::circle_radius_model::LogScaledRadius;

    use super::*;
    use std::{cmp::Ordering, num::NonZeroUsize};

    #[test]
    fn insert_single_item() {
        let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();
        let mut tree = CircleMergingQuadtree::new(
            BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),
            circle_radius_model,
            1,
        );

        let p1 = Coordinate2D::new(0.0, 0.0);
        tree.insert(&p1);

        let mut iter = tree.into_iter();
        assert_eq!(
            Some(
                CircleOfPoints::new(
                    Circle::new(0.0, 0.0, 5.0),
                    1,
                    TimeInterval::default(),
                    Default::default()
                )
                .unwrap()
            ),
            iter.next()
        );

        assert_eq!(None, iter.next());
    }

    #[test]
    fn insert_two_items_merge() {
        let points = vec![Coordinate2D::new(50.0, 50.0), Coordinate2D::new(50.0, 50.0)];
        let points_size = NonZeroUsize::new(points.len()).unwrap();

        let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();
        let mut tree = CircleMergingQuadtree::new(
            BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),
            circle_radius_model,
            1,
        );

        for p in &points {
            tree.insert(p);
        }

        let mut iter = tree.into_iter();
        assert_eq!(
            Some(
                CircleOfPoints::new(
                    Circle::new(
                        50.0,
                        50.0,
                        circle_radius_model.calculate_radius(points_size)
                    ),
                    points_size.get(),
                    TimeInterval::default(),
                    Default::default()
                )
                .unwrap()
            ),
            iter.next()
        );

        assert_eq!(None, iter.next());
    }

    #[test]
    fn insert_two_items_merge_with_move() {
        let points = vec![Coordinate2D::new(48.0, 48.0), Coordinate2D::new(50.0, 50.0)];
        let points_size = NonZeroUsize::new(points.len()).unwrap();

        let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();
        let mut tree = CircleMergingQuadtree::new(
            BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),
            circle_radius_model,
            1,
        );

        for p in &points {
            tree.insert(p);
        }

        let mut iter = tree.into_iter();
        assert_eq!(
            Some(
                CircleOfPoints::new(
                    Circle::new(
                        49.0,
                        49.0,
                        circle_radius_model.calculate_radius(points_size)
                    ),
                    points_size.get(),
                    TimeInterval::default(),
                    Default::default()
                )
                .unwrap()
            ),
            iter.next()
        );

        assert_eq!(None, iter.next());
    }

    #[test]
    fn insert_five_items_merge() {
        let points = vec![
            Coordinate2D::new(20.0, 50.0),
            Coordinate2D::new(20.0, 50.0),
            Coordinate2D::new(20.0, 50.0),
            Coordinate2D::new(20.0, 50.0),
            Coordinate2D::new(20.0, 50.0),
        ];
        let points_size = points.len();

        let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();
        let mut tree = CircleMergingQuadtree::new(
            BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),
            circle_radius_model,
            1,
        );

        for p in &points {
            tree.insert(p);
        }

        let mut iter = tree.into_iter();
        assert_eq!(
            Some(
                CircleOfPoints::new(
                    Circle::new(
                        20.0,
                        50.0,
                        circle_radius_model.calculate_radius(NonZeroUsize::new(5).unwrap())
                    ),
                    points_size,
                    TimeInterval::default(),
                    Default::default()
                )
                .unwrap()
            ),
            iter.next()
        );

        assert_eq!(None, iter.next());
    }

    #[test]
    fn insert_two_items_no_merge() {
        let points = vec![Coordinate2D::new(50.0, 50.0), Coordinate2D::new(75.0, 75.0)];

        let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();
        let mut tree = CircleMergingQuadtree::new(
            BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),
            circle_radius_model,
            1,
        );

        for p in &points {
            tree.insert(p);
        }

        let mut results = Vec::with_capacity(2);
        for circle in tree {
            results.push(circle);
        }
        results.sort_by(|a, b| match a.circle.x().partial_cmp(&b.circle.x()) {
            Some(Ordering::Greater | Ordering::Less) => Ordering::Greater,
            _ => a
                .circle
                .y()
                .partial_cmp(&b.circle.y())
                .unwrap_or(Ordering::Equal),
        });

        let mut iter = results.into_iter();
        assert_eq!(
            Some(
                CircleOfPoints::new(
                    Circle::new(50.0, 50.0, 5.0),
                    1,
                    TimeInterval::default(),
                    Default::default()
                )
                .unwrap(),
            ),
            iter.next()
        );
        assert_eq!(
            Some(
                CircleOfPoints::new(
                    Circle::new(75.0, 75.0, 5.0),
                    1,
                    TimeInterval::default(),
                    Default::default()
                )
                .unwrap(),
            ),
            iter.next()
        );

        assert_eq!(None, iter.next());
    }

    #[test]
    fn bounding_rectangle() {
        let bounds =
            BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap();

        let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();
        let tree = CircleMergingQuadtree::new(bounds, circle_radius_model, 1);

        let mut iter = tree.iter_rectangles();
        assert_eq!(Some(&bounds), iter.next());

        assert_eq!(None, iter.next());
    }

    #[test]
    fn bounding_rectangle_after_split() {
        let bounds =
            BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap();

        let points = vec![
            Coordinate2D::new(150.0, 150.0),
            Coordinate2D::new(50.0, 50.0),
        ];

        let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();
        let mut tree = CircleMergingQuadtree::new(bounds, circle_radius_model, 1);

        for point in &points {
            tree.insert(point);
        }

        let bounding_boxes = tree.iter_rectangles().collect::<Vec<_>>();

        assert_eq!(
            bounding_boxes,
            vec![
                &bounds,
                &BoundingBox2D::new_from_center(Coordinate2D::new(50.0, 50.0), 50.0, 50.0).unwrap(),
                &BoundingBox2D::new_from_center(Coordinate2D::new(150.0, 50.0), 50.0, 50.0)
                    .unwrap(),
                &BoundingBox2D::new_from_center(Coordinate2D::new(50.0, 150.0), 50.0, 50.0)
                    .unwrap(),
                &BoundingBox2D::new_from_center(Coordinate2D::new(150.0, 150.0), 50.0, 50.0)
                    .unwrap(),
            ]
        );
    }
}

1	use std::collections::VecDeque;
2
3	use geoengine_datatypes::primitives::{BoundingBox2D, Circle, Coordinate2D, TimeInterval};
4
5	use super::{circle_of_points::CircleOfPoints, circle_radius_model::CircleRadiusModel, node::Node};
6
7	#[derive(Debug)]	×
8	pub struct CircleMergingQuadtree<C: CircleRadiusModel> {
9	head: Box<Node>,
10	circle_radius_model: C,
11	max_items_per_node: usize,
12	}
13
14	pub struct IntoIter {
15	stack: Vec<Node>,
16	}
17
18	pub struct Iter<'t> {
19	stack: Vec<&'t Node>,
20	output: Vec<CircleOfPoints>,
21	}
22
23	pub struct RectangleIter<'a> {
24	stack: VecDeque<&'a Node>,
25	}
26
27	impl<C> CircleMergingQuadtree<C>
28	where
29	C: CircleRadiusModel,
30	{
31	pub fn new(bounds: BoundingBox2D, circle_radius_model: C, max_items_per_node: usize) -> Self {	11✔
32	CircleMergingQuadtree {	11✔
33	head: Box::new(Node::new(bounds)),	11✔
34	circle_radius_model,	11✔
35	max_items_per_node,	11✔
36	}	11✔
37	}	11✔
38
39	pub fn insert(&mut self, coordinate: &Coordinate2D) {	14✔
40	let new_circle = CircleOfPoints::new_with_one_point(	14✔
41	Circle::from_coordinate(coordinate, self.circle_radius_model.min_radius()),	14✔
42	TimeInterval::default(),	14✔
43	Default::default(), // TODO: allow inserting attribute data	14✔
44	);	14✔
45		14✔
46	self.insert_circle(new_circle);	14✔
47	}	14✔
48
49	/// Use the output of a tree as input to another one.
50	///
51	/// This is useful to build a lower resolution tree upon existing circles.
52	pub fn insert_tree(&mut self, tree: CircleMergingQuadtree<C>) {	×
53	for circle in tree {	×
54	self.insert_circle(circle);	×
55	}	×
56	}	×
57
58	pub fn insert_circle(&mut self, new_circle: CircleOfPoints) {	23✔
59	let mut insert_attempt = self.head.try_insert(	23✔
60	new_circle,	23✔
61	self.circle_radius_model.delta(),	23✔
62	self.max_items_per_node,	23✔
63	);	23✔
64
65	while let Err((circle1, circle2)) = insert_attempt {	29✔
66	let mut new_circle = circle1;	6✔
67	new_circle.merge(&circle2, &self.circle_radius_model);	6✔
68	insert_attempt = self.head.try_insert(	6✔
69	new_circle,	6✔
70	self.circle_radius_model.delta(),	6✔
71	self.max_items_per_node,	6✔
72	);	6✔
73	}	6✔
74	}	23✔
75
76	pub fn iter_rectangles(&self) -> RectangleIter {	2✔
77	let mut stack = VecDeque::new();	2✔
78	stack.push_back(&*self.head);	2✔
79	RectangleIter { stack }	2✔
80	}	2✔
81	}
82
83	impl<C> IntoIterator for CircleMergingQuadtree<C>
84	where
85	C: CircleRadiusModel,
86	{
87	type Item = CircleOfPoints;
88	type IntoIter = IntoIter;
89
90	fn into_iter(self) -> Self::IntoIter {	9✔
91	IntoIter {	9✔
92	stack: vec![*self.head],	9✔
93	}	9✔
94	}	9✔
95	}
96
97	impl Iterator for IntoIter {
98	type Item = CircleOfPoints;
99
100	fn next(&mut self) -> Option<Self::Item> {	24✔
101	let mut top_node = self.stack.pop();	24✔
102
103	while let Some(mut node) = top_node {	65✔
104	match node.circles.pop() {	56✔
105	Some(circle) => {	15✔
106	self.stack.push(node);	15✔
107	return Some(circle);	15✔
108	}
109	None => {
110	if let Some(link) = node.link {	41✔
111	self.stack.append(&mut (link as Box<[_]>).into_vec());	8✔
112	}	33✔
113	top_node = self.stack.pop();	41✔
114	}
115	}
116	}
117
118	None	9✔
119	}	24✔
120	}
121
122	impl<'t, C> IntoIterator for &'t CircleMergingQuadtree<C>
123	where
124	C: CircleRadiusModel,
125	{
126	type Item = CircleOfPoints;
127	type IntoIter = Iter<'t>;
128
129	fn into_iter(self) -> Self::IntoIter {	×
130	Iter {	×
131	stack: vec![self.head.as_ref()],	×
132	output: Vec::new(),	×
133	}	×
134	}	×
135	}
136
137	impl<'t> Iterator for Iter<'t> {
138	type Item = CircleOfPoints;
139
140	fn next(&mut self) -> Option<Self::Item> {
141	if let Some(circle) = self.output.pop() {	×
142	return Some(circle);	×
143	}	×
144		×
145	let mut top_node = self.stack.pop();	×
146
147	while let Some(node) = top_node {	×
148	self.output.append(&mut node.circles.clone());	×
149
150	if let Some(ref quad_reference) = node.link {	×
151	self.stack	×
152	.extend_from_slice(&quad_reference.iter().collect::<Vec<&Node>>());	×
153	}	×
154
155	if self.output.is_empty() {	×
156	top_node = self.stack.pop();	×
157	} else {	×
158	return self.output.pop();	×
159	}
160	}
161
162	None	×
163	}	×
164	}
165
166	impl<'a> Iterator for RectangleIter<'a> {
167	type Item = &'a BoundingBox2D;
168
169	fn next(&mut self) -> Option<Self::Item> {	8✔
170	self.stack.pop_front().map(\|node\| {	8✔
171	if let Some(ref link) = node.link {	6✔
172	for child_node in link.iter() {	4✔
173	self.stack.push_back(child_node);	4✔
174	}	4✔
175	}	5✔
176
177	&node.rectangle	6✔
178	})	8✔
179	}	8✔
180	}
181
182	#[cfg(test)]
183	mod test {
184	use crate::processing::circle_merging_quadtree::circle_radius_model::LogScaledRadius;
185
186	use super::*;
187	use std::{cmp::Ordering, num::NonZeroUsize};
188
189	#[test]	1✔
190	fn insert_single_item() {	1✔
191	let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();	1✔
192	let mut tree = CircleMergingQuadtree::new(	1✔
193	BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),	1✔
194	circle_radius_model,	1✔
195	1,	1✔
196	);	1✔
197		1✔
198	let p1 = Coordinate2D::new(0.0, 0.0);	1✔
199	tree.insert(&p1);	1✔
200		1✔
201	let mut iter = tree.into_iter();	1✔
202	assert_eq!(	1✔
203	Some(	1✔
204	CircleOfPoints::new(	1✔
205	Circle::new(0.0, 0.0, 5.0),	1✔
206	1,	1✔
207	TimeInterval::default(),	1✔
208	Default::default()	1✔
209	)	1✔
210	.unwrap()	1✔
211	),	1✔
212	iter.next()	1✔
213	);	1✔
214
215	assert_eq!(None, iter.next());	1✔
216	}	1✔
217
218	#[test]	1✔
219	fn insert_two_items_merge() {	1✔
220	let points = vec![Coordinate2D::new(50.0, 50.0), Coordinate2D::new(50.0, 50.0)];	1✔
221	let points_size = NonZeroUsize::new(points.len()).unwrap();	1✔
222		1✔
223	let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();	1✔
224	let mut tree = CircleMergingQuadtree::new(	1✔
225	BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),	1✔
226	circle_radius_model,	1✔
227	1,	1✔
228	);	1✔
229
230	for p in &points {	3✔
231	tree.insert(p);	2✔
232	}	2✔
233
234	let mut iter = tree.into_iter();	1✔
235	assert_eq!(	1✔
236	Some(	1✔
237	CircleOfPoints::new(	1✔
238	Circle::new(	1✔
239	50.0,	1✔
240	50.0,	1✔
241	circle_radius_model.calculate_radius(points_size)	1✔
242	),	1✔
243	points_size.get(),	1✔
244	TimeInterval::default(),	1✔
245	Default::default()	1✔
246	)	1✔
247	.unwrap()	1✔
248	),	1✔
249	iter.next()	1✔
250	);	1✔
251
252	assert_eq!(None, iter.next());	1✔
253	}	1✔
254
255	#[test]	1✔
256	fn insert_two_items_merge_with_move() {	1✔
257	let points = vec![Coordinate2D::new(48.0, 48.0), Coordinate2D::new(50.0, 50.0)];	1✔
258	let points_size = NonZeroUsize::new(points.len()).unwrap();	1✔
259		1✔
260	let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();	1✔
261	let mut tree = CircleMergingQuadtree::new(	1✔
262	BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),	1✔
263	circle_radius_model,	1✔
264	1,	1✔
265	);	1✔
266
267	for p in &points {	3✔
268	tree.insert(p);	2✔
269	}	2✔
270
271	let mut iter = tree.into_iter();	1✔
272	assert_eq!(	1✔
273	Some(	1✔
274	CircleOfPoints::new(	1✔
275	Circle::new(	1✔
276	49.0,	1✔
277	49.0,	1✔
278	circle_radius_model.calculate_radius(points_size)	1✔
279	),	1✔
280	points_size.get(),	1✔
281	TimeInterval::default(),	1✔
282	Default::default()	1✔
283	)	1✔
284	.unwrap()	1✔
285	),	1✔
286	iter.next()	1✔
287	);	1✔
288
289	assert_eq!(None, iter.next());	1✔
290	}	1✔
291
292	#[test]	1✔
293	fn insert_five_items_merge() {	1✔
294	let points = vec![	1✔
295	Coordinate2D::new(20.0, 50.0),	1✔
296	Coordinate2D::new(20.0, 50.0),	1✔
297	Coordinate2D::new(20.0, 50.0),	1✔
298	Coordinate2D::new(20.0, 50.0),	1✔
299	Coordinate2D::new(20.0, 50.0),	1✔
300	];	1✔
301	let points_size = points.len();	1✔
302		1✔
303	let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();	1✔
304	let mut tree = CircleMergingQuadtree::new(	1✔
305	BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),	1✔
306	circle_radius_model,	1✔
307	1,	1✔
308	);	1✔
309
310	for p in &points {	6✔
311	tree.insert(p);	5✔
312	}	5✔
313
314	let mut iter = tree.into_iter();	1✔
315	assert_eq!(	1✔
316	Some(	1✔
317	CircleOfPoints::new(	1✔
318	Circle::new(	1✔
319	20.0,	1✔
320	50.0,	1✔
321	circle_radius_model.calculate_radius(NonZeroUsize::new(5).unwrap())	1✔
322	),	1✔
323	points_size,	1✔
324	TimeInterval::default(),	1✔
325	Default::default()	1✔
326	)	1✔
327	.unwrap()	1✔
328	),	1✔
329	iter.next()	1✔
330	);	1✔
331
332	assert_eq!(None, iter.next());	1✔
333	}	1✔
334
335	#[test]	1✔
336	fn insert_two_items_no_merge() {	1✔
337	let points = vec![Coordinate2D::new(50.0, 50.0), Coordinate2D::new(75.0, 75.0)];	1✔
338		1✔
339	let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();	1✔
340	let mut tree = CircleMergingQuadtree::new(	1✔
341	BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap(),	1✔
342	circle_radius_model,	1✔
343	1,	1✔
344	);	1✔
345
346	for p in &points {	3✔
347	tree.insert(p);	2✔
348	}	2✔
349
350	let mut results = Vec::with_capacity(2);	1✔
351	for circle in tree {	3✔
352	results.push(circle);	2✔
353	}	2✔
354	results.sort_by(\|a, b\| match a.circle.x().partial_cmp(&b.circle.x()) {	1✔
355	Some(Ordering::Greater \| Ordering::Less) => Ordering::Greater,	1✔
356	_ => a	×
357	.circle	×
358	.y()	×
359	.partial_cmp(&b.circle.y())	×
360	.unwrap_or(Ordering::Equal),	×
361	});	1✔
362		1✔
363	let mut iter = results.into_iter();	1✔
364	assert_eq!(	1✔
365	Some(	1✔
366	CircleOfPoints::new(	1✔
367	Circle::new(50.0, 50.0, 5.0),	1✔
368	1,	1✔
369	TimeInterval::default(),	1✔
370	Default::default()	1✔
371	)	1✔
372	.unwrap(),	1✔
373	),	1✔
374	iter.next()	1✔
375	);	1✔
376	assert_eq!(	1✔
377	Some(	1✔
378	CircleOfPoints::new(	1✔
379	Circle::new(75.0, 75.0, 5.0),	1✔
380	1,	1✔
381	TimeInterval::default(),	1✔
382	Default::default()	1✔
383	)	1✔
384	.unwrap(),	1✔
385	),	1✔
386	iter.next()	1✔
387	);	1✔
388
389	assert_eq!(None, iter.next());	1✔
390	}	1✔
391
392	#[test]	1✔
393	fn bounding_rectangle() {	1✔
394	let bounds =	1✔
395	BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap();	1✔
396		1✔
397	let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();	1✔
398	let tree = CircleMergingQuadtree::new(bounds, circle_radius_model, 1);	1✔
399		1✔
400	let mut iter = tree.iter_rectangles();	1✔
401	assert_eq!(Some(&bounds), iter.next());	1✔
402
403	assert_eq!(None, iter.next());	1✔
404	}	1✔
405
406	#[test]	1✔
407	fn bounding_rectangle_after_split() {	1✔
408	let bounds =	1✔
409	BoundingBox2D::new_from_center(Coordinate2D::new(100.0, 100.0), 100.0, 100.0).unwrap();	1✔
410		1✔
411	let points = vec![	1✔
412	Coordinate2D::new(150.0, 150.0),	1✔
413	Coordinate2D::new(50.0, 50.0),	1✔
414	];	1✔
415		1✔
416	let circle_radius_model = LogScaledRadius::new(5.0, 1.0).unwrap();	1✔
417	let mut tree = CircleMergingQuadtree::new(bounds, circle_radius_model, 1);	1✔
418
419	for point in &points {	3✔
420	tree.insert(point);	2✔
421	}	2✔
422
423	let bounding_boxes = tree.iter_rectangles().collect::<Vec<_>>();	1✔
424		1✔
425	assert_eq!(	1✔
426	bounding_boxes,	1✔
427	vec![	1✔
428	&bounds,	1✔
429	&BoundingBox2D::new_from_center(Coordinate2D::new(50.0, 50.0), 50.0, 50.0).unwrap(),	1✔
430	&BoundingBox2D::new_from_center(Coordinate2D::new(150.0, 50.0), 50.0, 50.0)	1✔
431	.unwrap(),	1✔
432	&BoundingBox2D::new_from_center(Coordinate2D::new(50.0, 150.0), 50.0, 50.0)	1✔
433	.unwrap(),	1✔
434	&BoundingBox2D::new_from_center(Coordinate2D::new(150.0, 150.0), 50.0, 50.0)	1✔
435	.unwrap(),	1✔
436	]	1✔
437	);	1✔
438	}	1✔
439	}

geo-engine / geoengine / 3929938005

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous