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

94.68

/operators/src/processing/circle_merging_quadtree/grid.rs

use geoengine_datatypes::primitives::{AxisAlignedRectangle, BoundingBox2D, Coordinate2D};

use super::{
    circle_of_points::CircleOfPoints, circle_radius_model::CircleRadiusModel,
    hash_map::SeparateChainingHashMap,
};

/// A Grid that contains non-overlapping circles.
/// It merges circles automatically upon insert if there are multiples circles in a grid cell.
#[derive(Clone, Debug)]
pub struct Grid<C: CircleRadiusModel> {
    offset: Coordinate2D,
    cell_width: f64,
    number_of_horizontal_cells: usize,
    cells: SeparateChainingHashMap<u16, CircleOfPoints>,
    radius_model: C,
}

impl<C: CircleRadiusModel> Grid<C> {
    pub fn new(bbox: BoundingBox2D, radius_model: C) -> Self {
        // cell width s.th. every circle in the cell overlaps with every other circle in the cell
        let cell_width =
            (2. * radius_model.min_radius() + radius_model.delta()) / std::f64::consts::SQRT_2;

        let map_width = bbox.size_x();
        let map_height = bbox.size_y();

        let mut number_of_horizontal_cells = (map_width / cell_width).ceil() as usize;
        let number_of_vertical_cells = (map_height / cell_width).ceil() as usize;

        if (number_of_horizontal_cells * number_of_vertical_cells) > 256 * 256 {
            // cap the number of cells to fit in a u16
            number_of_horizontal_cells = number_of_horizontal_cells.max(256);

            // since we don't store `number_of_vertical_cells`, we don't need to update it
        }

        let offset_x = (bbox.lower_left().x / cell_width).floor() * cell_width;
        let offset_y = (bbox.lower_left().y / cell_width).floor() * cell_width;

        Self {
            offset: Coordinate2D {
                x: offset_x,
                y: offset_y,
            },
            cell_width,
            number_of_horizontal_cells,
            cells: SeparateChainingHashMap::new(),
            radius_model,
        }
    }

    pub fn insert(&mut self, circle_of_points: CircleOfPoints) {
        let grid_x = ((circle_of_points.circle.x() - self.offset.x) / self.cell_width) as usize;
        let grid_y = ((circle_of_points.circle.y() - self.offset.x) / self.cell_width) as usize;

        // uses XY-order, but could also use Z-order
        let grid_pos = grid_y * self.number_of_horizontal_cells + grid_x;

        match self.cells.entry(grid_pos as u16) {
            super::hash_map::ValueRef::Vacant(entry_pos) => {
                self.cells.insert_unchecked(entry_pos, circle_of_points);
            }
            super::hash_map::ValueRef::Occupied(matched_circle_of_points) => {
                matched_circle_of_points.merge(&circle_of_points, &self.radius_model);
            }
        }
    }

    /// Creates a draining iterator that can be used to remove all circles from the grid.
    pub fn drain(self) -> impl Iterator<Item = CircleOfPoints> {
        self.cells.into_iter()
    }

    pub fn radius_model(&self) -> &C {
        &self.radius_model
    }
}

#[cfg(test)]
mod tests {
    use geoengine_datatypes::primitives::{Circle, TimeInterval};

    use crate::processing::circle_merging_quadtree::circle_radius_model::LogScaledRadius;

    use super::*;

    #[test]
    fn test_grid() {
        let mut grid = Grid::new(
            BoundingBox2D::new((0., 0.).into(), (10., 10.).into()).unwrap(),
            LogScaledRadius::new(2., 1.).unwrap(),
        );

        grid.insert(CircleOfPoints::new_with_one_point(
            Circle::new(1., 1., 1.),
            TimeInterval::default(),
            Default::default(),
        ));
        grid.insert(CircleOfPoints::new_with_one_point(
            Circle::new(2., 1., 1.),
            TimeInterval::default(),
            Default::default(),
        ));
        grid.insert(CircleOfPoints::new_with_one_point(
            Circle::new(6., 6., 1.),
            TimeInterval::default(),
            Default::default(),
        ));

        assert_eq!(
            grid.drain().collect::<Vec<_>>(),
            vec![
                CircleOfPoints::new(
                    Circle::new(1.5, 1., 2.693_147_180_559_945_4),
                    2,
                    TimeInterval::default(),
                    Default::default(),
                )
                .unwrap(),
                CircleOfPoints::new_with_one_point(
                    Circle::new(6., 6., 1.),
                    TimeInterval::default(),
                    Default::default(),
                ),
            ]
        );
    }

    // TODO: test dataset with close-by points and compare with same dataset after raster vector join
}

1	use geoengine_datatypes::primitives::{AxisAlignedRectangle, BoundingBox2D, Coordinate2D};
2
3	use super::{
4	circle_of_points::CircleOfPoints, circle_radius_model::CircleRadiusModel,
5	hash_map::SeparateChainingHashMap,
6	};
7
8	/// A Grid that contains non-overlapping circles.
9	/// It merges circles automatically upon insert if there are multiples circles in a grid cell.
10	#[derive(Clone, Debug)]	×
11	pub struct Grid<C: CircleRadiusModel> {
12	offset: Coordinate2D,
13	cell_width: f64,
14	number_of_horizontal_cells: usize,
15	cells: SeparateChainingHashMap<u16, CircleOfPoints>,
16	radius_model: C,
17	}
18
19	impl<C: CircleRadiusModel> Grid<C> {
20	pub fn new(bbox: BoundingBox2D, radius_model: C) -> Self {	5✔
21	// cell width s.th. every circle in the cell overlaps with every other circle in the cell	5✔
22	let cell_width =	5✔
23	(2. * radius_model.min_radius() + radius_model.delta()) / std::f64::consts::SQRT_2;	5✔
24		5✔
25	let map_width = bbox.size_x();	5✔
26	let map_height = bbox.size_y();	5✔
27		5✔
28	let mut number_of_horizontal_cells = (map_width / cell_width).ceil() as usize;	5✔
29	let number_of_vertical_cells = (map_height / cell_width).ceil() as usize;	5✔
30		5✔
31	if (number_of_horizontal_cells * number_of_vertical_cells) > 256 * 256 {	5✔
32	// cap the number of cells to fit in a u16	×
33	number_of_horizontal_cells = number_of_horizontal_cells.max(256);	×
34		×
35	// since we don't store `number_of_vertical_cells`, we don't need to update it	×
36	}	5✔
37
38	let offset_x = (bbox.lower_left().x / cell_width).floor() * cell_width;	5✔
39	let offset_y = (bbox.lower_left().y / cell_width).floor() * cell_width;	5✔
40		5✔
41	Self {	5✔
42	offset: Coordinate2D {	5✔
43	x: offset_x,	5✔
44	y: offset_y,	5✔
45	},	5✔
46	cell_width,	5✔
47	number_of_horizontal_cells,	5✔
48	cells: SeparateChainingHashMap::new(),	5✔
49	radius_model,	5✔
50	}	5✔
51	}	5✔
52
53	pub fn insert(&mut self, circle_of_points: CircleOfPoints) {	33✔
54	let grid_x = ((circle_of_points.circle.x() - self.offset.x) / self.cell_width) as usize;	33✔
55	let grid_y = ((circle_of_points.circle.y() - self.offset.x) / self.cell_width) as usize;	33✔
56		33✔
57	// uses XY-order, but could also use Z-order	33✔
58	let grid_pos = grid_y * self.number_of_horizontal_cells + grid_x;	33✔
59		33✔
60	match self.cells.entry(grid_pos as u16) {	33✔
61	super::hash_map::ValueRef::Vacant(entry_pos) => {	11✔
62	self.cells.insert_unchecked(entry_pos, circle_of_points);	11✔
63	}	11✔
64	super::hash_map::ValueRef::Occupied(matched_circle_of_points) => {	22✔
65	matched_circle_of_points.merge(&circle_of_points, &self.radius_model);	22✔
66	}	22✔
67	}
68	}	33✔
69
70	/// Creates a draining iterator that can be used to remove all circles from the grid.
71	pub fn drain(self) -> impl Iterator<Item = CircleOfPoints> {	5✔
72	self.cells.into_iter()	5✔
73	}	5✔
74
75	pub fn radius_model(&self) -> &C {	34✔
76	&self.radius_model	34✔
77	}	34✔
78	}
79
80	#[cfg(test)]
81	mod tests {
82	use geoengine_datatypes::primitives::{Circle, TimeInterval};
83
84	use crate::processing::circle_merging_quadtree::circle_radius_model::LogScaledRadius;
85
86	use super::*;
87
88	#[test]	1✔
89	fn test_grid() {	1✔
90	let mut grid = Grid::new(	1✔
91	BoundingBox2D::new((0., 0.).into(), (10., 10.).into()).unwrap(),	1✔
92	LogScaledRadius::new(2., 1.).unwrap(),	1✔
93	);	1✔
94		1✔
95	grid.insert(CircleOfPoints::new_with_one_point(	1✔
96	Circle::new(1., 1., 1.),	1✔
97	TimeInterval::default(),	1✔
98	Default::default(),	1✔
99	));	1✔
100	grid.insert(CircleOfPoints::new_with_one_point(	1✔
101	Circle::new(2., 1., 1.),	1✔
102	TimeInterval::default(),	1✔
103	Default::default(),	1✔
104	));	1✔
105	grid.insert(CircleOfPoints::new_with_one_point(	1✔
106	Circle::new(6., 6., 1.),	1✔
107	TimeInterval::default(),	1✔
108	Default::default(),	1✔
109	));	1✔
110		1✔
111	assert_eq!(	1✔
112	grid.drain().collect::<Vec<_>>(),	1✔
113	vec![	1✔
114	CircleOfPoints::new(	1✔
115	Circle::new(1.5, 1., 2.693_147_180_559_945_4),	1✔
116	2,	1✔
117	TimeInterval::default(),	1✔
118	Default::default(),	1✔
119	)	1✔
120	.unwrap(),	1✔
121	CircleOfPoints::new_with_one_point(	1✔
122	Circle::new(6., 6., 1.),	1✔
123	TimeInterval::default(),	1✔
124	Default::default(),	1✔
125	),	1✔
126	]	1✔
127	);	1✔
128	}	1✔
129
130	// TODO: test dataset with close-by points and compare with same dataset after raster vector join
131	}

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