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

66.37

/operators/src/processing/circle_merging_quadtree/node.rs

use geo::intersects::Intersects;
use geoengine_datatypes::{operations::Contains, primitives::BoundingBox2D};

use super::circle_of_points::CircleOfPoints;

pub type QuadReference = [Node; 4];

///  * `top_left`
///  * `top_right`
///  * `bottom_left`
///  * `bottom_right`
pub type Link = Option<Box<QuadReference>>;

#[derive(Debug)]
pub struct Node {
    pub rectangle: BoundingBox2D,
    pub circles: Vec<CircleOfPoints>,
    pub link: Link,
}

pub type TryResult = Result<(), (CircleOfPoints, CircleOfPoints)>;
type PartialTryResult = Option<CircleOfPoints>;

impl Node {
    pub fn new(rectangle: BoundingBox2D) -> Self {
        Node {
            rectangle,
            circles: Vec::new(),
            link: None,
        }
    }

    pub fn add(
        &mut self,
        circle: CircleOfPoints,
        epsilon_distance: f64,
        max_items_per_node: usize,
    ) {
        if let Some(ref mut link) = self.link {
            // node is splitted

            for section in link.iter_mut() {
                if section
                    .rectangle
                    .contains(&circle.circle.buffer(epsilon_distance))
                {
                    // should not be reached, but just in case
                    section.add(circle, epsilon_distance, max_items_per_node);
                    return;
                }
            }

            self.circles.push(circle);
        } else {
            // node is unsplitted

            self.circles.push(circle);

            // handle overflow
            if self.circles.len() > max_items_per_node {
                let (top_left_rect, top_right_rect, bottom_left_rect, bottom_right_rect) =
                    self.rectangle.split_into_quarters();

                let mut link = Box::new([
                    Node::new(top_left_rect),
                    Node::new(top_right_rect),
                    Node::new(bottom_left_rect),
                    Node::new(bottom_right_rect),
                ]);

                'circle: for circle in std::mem::take(&mut self.circles) {
                    for section in link.iter_mut() {
                        if section
                            .rectangle
                            .contains(&circle.circle.buffer(epsilon_distance))
                        {
                            section.add(circle, epsilon_distance, max_items_per_node);
                            continue 'circle;
                        }
                    }

                    self.circles.push(circle);
                }

                self.link = Some(link);
            }
        }
    }

    pub fn try_insert(
        &mut self,
        mut new_circle: CircleOfPoints,
        epsilon_distance: f64,
        max_items_per_node: usize,
    ) -> TryResult {
        // overlap with a contained circle
        if let Some(circle) = self.remove_intersecting_circle(&new_circle, epsilon_distance) {
            return Err((new_circle, circle));
        }

        // try to insert in children
        if let Some(ref mut quad) = self.link {
            let result =
                Node::try_insert_children(quad, new_circle, epsilon_distance, max_items_per_node);

            match result {
                Ok(try_result) => {
                    return try_result;
                }
                Err(returned_new_circle) => {
                    new_circle = returned_new_circle;

                    // try to find overlap in intersecting child nodes
                    for section in quad.iter_mut() {
                        if section
                            .rectangle
                            .intersects(&new_circle.circle.buffer(epsilon_distance))
                        {
                            if let Some(circle) = section.try_partial(&new_circle, epsilon_distance)
                            {
                                return Err((new_circle, circle));
                            }
                        }
                    }
                }
            }
        }

        self.add(new_circle, epsilon_distance, max_items_per_node);
        Ok(())
    }

    #[inline]
    fn try_insert_children(
        quad: &mut QuadReference,
        new_circle: CircleOfPoints,
        epsilon_distance: f64,
        max_items_per_node: usize,
    ) -> Result<TryResult, CircleOfPoints> {
        for section in quad.iter_mut() {
            if section
                .rectangle
                .contains(&new_circle.circle.buffer(epsilon_distance))
            {
                return Ok(section.try_insert(new_circle, epsilon_distance, max_items_per_node));
            }
        }
        Err(new_circle)
    }

    fn try_partial(
        &mut self,
        new_circle: &CircleOfPoints,
        epsilon_distance: f64,
    ) -> PartialTryResult {
        if let Some(circle) = self.remove_intersecting_circle(new_circle, epsilon_distance) {
            return Some(circle);
        }

        if let Some(quad) = self.link.as_mut() {
            for section in quad.iter_mut() {
                if section
                    .rectangle
                    .intersects(&new_circle.circle.buffer(epsilon_distance))
                {
                    if let Some(circle) = section.try_partial(new_circle, epsilon_distance) {
                        return Some(circle);
                    }
                }
            }
        }

        None
    }

    fn remove_intersecting_circle(
        &mut self,
        test_circle: &CircleOfPoints,
        epsilon_distance: f64,
    ) -> Option<CircleOfPoints> {
        let mut remove_index = None;
        for (i, circle) in self.circles.iter().enumerate() {
            if circle
                .circle
                .intersects_with_epsilon(&test_circle.circle, epsilon_distance)
            {
                remove_index = Some(i);
                break;
            }
        }

        remove_index.map(|i| self.circles.remove(i))
    }
}

impl PartialEq for Node {
    fn eq(&self, other: &Self) -> bool {
        self.rectangle == other.rectangle
    }
}

1	use geo::intersects::Intersects;
2	use geoengine_datatypes::{operations::Contains, primitives::BoundingBox2D};
3
4	use super::circle_of_points::CircleOfPoints;
5
6	pub type QuadReference = [Node; 4];
7
8	/// * `top_left`
9	/// * `top_right`
10	/// * `bottom_left`
11	/// * `bottom_right`
12	pub type Link = Option<Box<QuadReference>>;
13
14	#[derive(Debug)]	×
15	pub struct Node {
16	pub rectangle: BoundingBox2D,
17	pub circles: Vec<CircleOfPoints>,
18	pub link: Link,
19	}
20
21	pub type TryResult = Result<(), (CircleOfPoints, CircleOfPoints)>;
22	type PartialTryResult = Option<CircleOfPoints>;
23
24	impl Node {
25	pub fn new(rectangle: BoundingBox2D) -> Self {	47✔
26	Node {	47✔
27	rectangle,	47✔
28	circles: Vec::new(),	47✔
29	link: None,	47✔
30	}	47✔
31	}	47✔
32
33	pub fn add(
34	&mut self,
35	circle: CircleOfPoints,
36	epsilon_distance: f64,
37	max_items_per_node: usize,
38	) {
39	if let Some(ref mut link) = self.link {	36✔
40	// node is splitted
41
42	for section in link.iter_mut() {	×
43	if section	×
44	.rectangle	×
45	.contains(&circle.circle.buffer(epsilon_distance))	×
46	{
47	// should not be reached, but just in case
48	section.add(circle, epsilon_distance, max_items_per_node);	×
49	return;	×
50	}	×
51	}
52
53	self.circles.push(circle);	×
54	} else {
55	// node is unsplitted
56
57	self.circles.push(circle);	36✔
58		36✔
59	// handle overflow	36✔
60	if self.circles.len() > max_items_per_node {	36✔
61	let (top_left_rect, top_right_rect, bottom_left_rect, bottom_right_rect) =	9✔
62	self.rectangle.split_into_quarters();	9✔
63		9✔
64	let mut link = Box::new([	9✔
65	Node::new(top_left_rect),	9✔
66	Node::new(top_right_rect),	9✔
67	Node::new(bottom_left_rect),	9✔
68	Node::new(bottom_right_rect),	9✔
69	]);	9✔
70
71	'circle: for circle in std::mem::take(&mut self.circles) {	18✔
72	for section in link.iter_mut() {	50✔
73	if section	50✔
74	.rectangle	50✔
75	.contains(&circle.circle.buffer(epsilon_distance))	50✔
76	{
77	section.add(circle, epsilon_distance, max_items_per_node);	13✔
78	continue 'circle;	13✔
79	}	37✔
80	}
81
82	self.circles.push(circle);	5✔
83	}
84
85	self.link = Some(link);	9✔
86	}	27✔
87	}
88	}	36✔
89
90	pub fn try_insert(
91	&mut self,
92	mut new_circle: CircleOfPoints,
93	epsilon_distance: f64,
94	max_items_per_node: usize,
95	) -> TryResult {
96	// overlap with a contained circle
97	if let Some(circle) = self.remove_intersecting_circle(&new_circle, epsilon_distance) {	30✔
98	return Err((new_circle, circle));	6✔
99	}	24✔
100
101	// try to insert in children
102	if let Some(ref mut quad) = self.link {	24✔
103	let result =	1✔
104	Node::try_insert_children(quad, new_circle, epsilon_distance, max_items_per_node);	1✔
105		1✔
106	match result {	1✔
107	Ok(try_result) => {	1✔
108	return try_result;	1✔
109	}
110	Err(returned_new_circle) => {	×
111	new_circle = returned_new_circle;	×
112
113	// try to find overlap in intersecting child nodes
114	for section in quad.iter_mut() {	×
115	if section	×
116	.rectangle	×
117	.intersects(&new_circle.circle.buffer(epsilon_distance))	×
118	{
119	if let Some(circle) = section.try_partial(&new_circle, epsilon_distance)	×
120	{
121	return Err((new_circle, circle));	×
122	}	×
123	}	×
124	}
125	}
126	}
127	}	23✔
128
129	self.add(new_circle, epsilon_distance, max_items_per_node);	23✔
130	Ok(())	23✔
131	}	30✔
132
133	#[inline]
134	fn try_insert_children(	1✔
135	quad: &mut QuadReference,	1✔
136	new_circle: CircleOfPoints,	1✔
137	epsilon_distance: f64,	1✔
138	max_items_per_node: usize,	1✔
139	) -> Result<TryResult, CircleOfPoints> {	1✔
140	for section in quad.iter_mut() {	2✔
141	if section	2✔
142	.rectangle	2✔
143	.contains(&new_circle.circle.buffer(epsilon_distance))	2✔
144	{
145	return Ok(section.try_insert(new_circle, epsilon_distance, max_items_per_node));	1✔
146	}	1✔
147	}
148	Err(new_circle)	×
149	}	1✔
150
151	fn try_partial(
152	&mut self,
153	new_circle: &CircleOfPoints,
154	epsilon_distance: f64,
155	) -> PartialTryResult {
156	if let Some(circle) = self.remove_intersecting_circle(new_circle, epsilon_distance) {	×
157	return Some(circle);	×
158	}	×
159
160	if let Some(quad) = self.link.as_mut() {	×
161	for section in quad.iter_mut() {	×
162	if section	×
163	.rectangle	×
164	.intersects(&new_circle.circle.buffer(epsilon_distance))	×
165	{
166	if let Some(circle) = section.try_partial(new_circle, epsilon_distance) {	×
167	return Some(circle);	×
168	}	×
169	}	×
170	}
171	}	×
172
173	None	×
174	}	×
175
176	fn remove_intersecting_circle(	30✔
177	&mut self,	30✔
178	test_circle: &CircleOfPoints,	30✔
179	epsilon_distance: f64,	30✔
180	) -> Option<CircleOfPoints> {	30✔
181	let mut remove_index = None;	30✔
182	for (i, circle) in self.circles.iter().enumerate() {	30✔
183	if circle	14✔
184	.circle	14✔
185	.intersects_with_epsilon(&test_circle.circle, epsilon_distance)	14✔
186	{
187	remove_index = Some(i);	6✔
188	break;	6✔
189	}	8✔
190	}
191
192	remove_index.map(\|i\| self.circles.remove(i))	30✔
193	}	30✔
194	}
195
196	impl PartialEq for Node {
197	fn eq(&self, other: &Self) -> bool {	×
198	self.rectangle == other.rectangle	×
199	}	×
200	}

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