cell_map/iterators/
slicers.rs

1//! Provides the [`Slicer`] trait and slicers types that determine the order and pattern in which
2//! data is produced by an interator over a [`CellMap`].
3//!
4//! [`CellMap`]: crate::CellMap
5
6// ------------------------------------------------------------------------------------------------
7// IMPORTS
8// ------------------------------------------------------------------------------------------------
9
10use nalgebra::{Point2, Vector2};
11use ndarray::{s, Array2, ArrayView2, ArrayViewMut2};
12use serde::Serialize;
13
14use crate::{
15    cell_map::Bounds, extensions::Point2Ext, map_metadata::CellMapMetadata, CellMap, Error, Layer,
16};
17
18// ------------------------------------------------------------------------------------------------
19// TRAITS
20// ------------------------------------------------------------------------------------------------
21
22/// Trait which allows a [`CellMapIter`] or [`CellMapIterMut`] struct to determine what shape the
23/// data in the iteration should be produced in. For example:
24///
25/// - [`Cells`] produces data in each cell in `(x, y)` order, x increasing most rapidly.
26/// - [`Windows`] produces rectangular views in `(x, y`) order, x increasing most rapidly.
27/// - [`Line`] produces cells along the line connecting two positions in the parent frame.
28///
29/// [`Slicer`]s are designed to be used in iterators, so after a `.slice` or `.slice_mut` the user
30/// shall call [`Slicer::advance()`] on the type.
31///
32/// [`CellMapIter`]: crate::iterators::CellMapIter
33/// [`CellMapIterMut`]: crate::iterators::CellMapIterMut
34pub trait Slicer<'a, L, T>
35where
36    L: Layer,
37{
38    /// The non-mutable output type for the data of this [`Slicer`].
39    type Output;
40
41    /// The mutable output type for the data of this [`Slicer`].
42    type OutputMut;
43
44    /// Perform the slice on the given `data` layer, or `None` if the slicer has reached the end of
45    /// its data.
46    fn slice(&self, data: &'a Array2<T>) -> Option<Self::Output>;
47
48    /// Perform a mutable slice on the given `data` layer, or `None` if the slicer has reached the
49    /// end of its data.
50    fn slice_mut(&self, data: &'a mut Array2<T>) -> Option<Self::OutputMut>;
51
52    /// Advance the [`Slicer`] to the next index.
53    fn advance(&mut self);
54
55    /// Return the current index of the [`Slicer`], or `None` if the slicer has reached the end of
56    /// its data.
57    fn index(&self) -> Option<Point2<usize>>;
58
59    /// Resets the index of this [`Slicer`] so that it can be used on the next layer in the
60    /// iteration. The `layer` input is used for slicers which need to monitor which layer they are
61    /// on.
62    fn reset(&mut self, layer: Option<L>);
63}
64
65/// Rectangular bounds in an XY plane. Lower bound is inclusive, upper exclusive.
66pub(crate) type RectBounds = Vector2<(usize, usize)>;
67
68/// A [`Slicer`] which produces cells in `(x, y)` order inside a layer, with `x` increasing most
69/// rapidly.
70#[derive(Debug, Clone, Copy)]
71pub struct Cells {
72    bounds: RectBounds,
73    index: Point2<usize>,
74}
75
76/// A [`Slicer`] which produces rectangular views into a layer in `(x, y)` order, increasing `x`
77/// most rapidly. A boundary of the `semi_width` of the window around the outside edge of the map
78/// is used to prevent indexing outside the map.
79#[derive(Debug, Clone, Copy)]
80pub struct Windows {
81    bounds: RectBounds,
82    index: Point2<usize>,
83    semi_width: Vector2<usize>,
84}
85
86/// A [`Slicer`] which produces cells along the line connecting two points in the parent frame.
87///
88/// This slicer will uses the algorithm described in
89/// [here](https://theshoemaker.de/2016/02/ray-casting-in-2d-grids/), meaning that all cells the
90/// line intersects will be yielded only once.
91#[derive(Debug, Clone)]
92#[allow(missing_copy_implementations)]
93pub struct Line {
94    bounds: Bounds,
95    map_meta: CellMapMetadata,
96
97    start_parent: Point2<f64>,
98    end_parent: Point2<f64>,
99
100    dir: Vector2<f64>,
101    dir_sign: Vector2<f64>,
102
103    start_map: Point2<f64>,
104    end_map: Point2<f64>,
105    current_map: Option<Point2<f64>>,
106
107    end_index: Point2<usize>,
108
109    #[cfg(feature = "debug_iters")]
110    step_report_file: std::sync::Arc<std::fs::File>,
111}
112
113#[derive(Debug, Clone, Copy, Serialize)]
114struct LineStepData {
115    start_parent: Point2<f64>,
116    end_parent: Point2<f64>,
117
118    dir: Vector2<f64>,
119    dir_sign: Vector2<f64>,
120
121    start_map: Point2<f64>,
122    end_map: Point2<f64>,
123    current_map: Option<Point2<f64>>,
124
125    end_index: Point2<usize>,
126
127    delta: Vector2<f64>,
128}
129
130// ------------------------------------------------------------------------------------------------
131// IMPLS
132// ------------------------------------------------------------------------------------------------
133
134impl Cells {
135    pub(crate) fn from_map<L: Layer, T>(map: &CellMap<L, T>) -> Self {
136        let cells = map.num_cells();
137        Self {
138            bounds: Vector2::new((0, cells.x), (0, cells.y)),
139            index: Point2::new(0, 0),
140        }
141    }
142}
143
144impl<'a, L, T> Slicer<'a, L, T> for Cells
145where
146    L: Layer,
147    T: 'a,
148{
149    type Output = &'a T;
150    type OutputMut = &'a mut T;
151
152    fn slice(&self, data: &'a Array2<T>) -> Option<Self::Output> {
153        data.get(self.index.as_array2_index())
154    }
155
156    fn slice_mut(&self, data: &'a mut Array2<T>) -> Option<Self::OutputMut> {
157        data.get_mut(self.index.as_array2_index())
158    }
159
160    fn advance(&mut self) {
161        self.index.x += 1;
162
163        if !self.index.in_bounds(&self.bounds) {
164            self.index.y += 1;
165            self.index.x = self.bounds.x.0;
166        }
167    }
168
169    fn index(&self) -> Option<Point2<usize>> {
170        if self.index.in_bounds(&self.bounds) {
171            Some(self.index)
172        } else {
173            None
174        }
175    }
176
177    fn reset(&mut self, _layer: Option<L>) {
178        self.index = Point2::new(self.bounds.x.0, self.bounds.y.0);
179    }
180}
181
182impl Windows {
183    pub(crate) fn from_map<L: Layer, T>(
184        map: &CellMap<L, T>,
185        semi_width: Vector2<usize>,
186    ) -> Result<Self, Error> {
187        let cells = map.num_cells();
188
189        if semi_width.x * 2 + 1 > cells.x || semi_width.y * 2 + 1 > cells.y {
190            Err(Error::WindowLargerThanMap(
191                semi_width * 2 + Vector2::new(1, 1),
192                cells,
193            ))
194        } else {
195            let bounds = Vector2::new(
196                (semi_width.x, cells.x - semi_width.x),
197                (semi_width.y, cells.y - semi_width.y),
198            );
199
200            Ok(Self {
201                bounds,
202                index: Point2::new(bounds.x.0, bounds.y.0),
203                semi_width,
204            })
205        }
206    }
207}
208
209impl<'a, L, T> Slicer<'a, L, T> for Windows
210where
211    L: Layer,
212    T: 'a,
213{
214    type Output = ArrayView2<'a, T>;
215    type OutputMut = ArrayViewMut2<'a, T>;
216
217    fn slice(&self, data: &'a Array2<T>) -> Option<Self::Output> {
218        if self.index.in_bounds(&self.bounds) {
219            let x0 = self.index.x - self.semi_width.x;
220            let x1 = self.index.x + self.semi_width.x + 1;
221            let y0 = self.index.y - self.semi_width.y;
222            let y1 = self.index.y + self.semi_width.y + 1;
223            Some(data.slice(s![y0..y1, x0..x1]))
224        } else {
225            None
226        }
227    }
228
229    fn slice_mut(&self, data: &'a mut Array2<T>) -> Option<Self::OutputMut> {
230        if self.index.in_bounds(&self.bounds) {
231            let x0 = self.index.x - self.semi_width.x;
232            let x1 = self.index.x + self.semi_width.x + 1;
233            let y0 = self.index.y - self.semi_width.y;
234            let y1 = self.index.y + self.semi_width.y + 1;
235            Some(data.slice_mut(s![y0..y1, x0..x1]))
236        } else {
237            None
238        }
239    }
240
241    fn advance(&mut self) {
242        self.index.x += 1;
243
244        if !self.index.in_bounds(&self.bounds) {
245            self.index.y += 1;
246            self.index.x = self.bounds.x.0;
247        }
248    }
249
250    fn index(&self) -> Option<Point2<usize>> {
251        if self.index.in_bounds(&self.bounds) {
252            Some(self.index)
253        } else {
254            None
255        }
256    }
257
258    fn reset(&mut self, _layer: Option<L>) {
259        self.index = Point2::new(self.bounds.x.0, self.bounds.y.0);
260    }
261}
262
263impl Line {
264    pub(crate) fn from_map<L: Layer, T>(
265        map_meta: CellMapMetadata,
266        start_parent: Point2<f64>,
267        end_parent: Point2<f64>,
268    ) -> Result<Self, Error> {
269        // Calculate start and end points in map frame, note these aren't cell indices, instead
270        // they are floating point positions within the map frame, which we get by not casting the
271        // output of the `to_parent` transforms to usize.
272        let start_map = map_meta.to_parent.inverse_transform_point(&start_parent);
273        let end_map = map_meta.to_parent.inverse_transform_point(&end_parent);
274
275        // Get map edges in floating point for bounds check
276        let map_x_bounds = (
277            map_meta.cell_bounds.x.0 as f64,
278            map_meta.cell_bounds.x.1 as f64,
279        );
280        let map_y_bounds = (
281            map_meta.cell_bounds.y.0 as f64,
282            map_meta.cell_bounds.y.1 as f64,
283        );
284
285        // Check start and end points are inside the map
286        if start_map.x < map_x_bounds.0
287            || start_map.x > map_x_bounds.1
288            || start_map.y < map_y_bounds.0
289            || start_map.y > map_y_bounds.1
290        {
291            return Err(Error::PositionOutsideMap(
292                "Line::Start".into(),
293                start_parent,
294            ));
295        }
296
297        if end_map.x < map_x_bounds.0
298            || end_map.x > map_x_bounds.1
299            || end_map.y < map_y_bounds.0
300            || end_map.y > map_y_bounds.1
301        {
302            return Err(Error::PositionOutsideMap("Line::End".into(), start_parent));
303        }
304
305        // Calculate direction vector
306        let dir = end_map - start_map;
307
308        // Get the direction sign
309        let dir_sign = dir.map(|v| if v < 0.0 { 0.0 } else { 1.0 });
310
311        // Get the cell index of the end point
312        let end_cell = map_meta
313            .index(end_parent)
314            .ok_or_else(|| Error::PositionOutsideMap("Line::End".into(), end_parent))?;
315
316        Ok(Self {
317            bounds: map_meta.cell_bounds,
318            map_meta,
319            start_parent,
320            end_parent,
321            dir,
322            dir_sign,
323            start_map,
324            end_map,
325            current_map: Some(start_map),
326            end_index: end_cell,
327            #[cfg(feature = "debug_iters")]
328            step_report_file: std::sync::Arc::new(
329                std::fs::OpenOptions::new()
330                    .create(true)
331                    .truncate(true)
332                    .write(true)
333                    .open("line_step_report.json")
334                    .unwrap(),
335            ),
336        })
337    }
338
339    /// Gets the current cell index to yield, or `None` if at the end of the line
340    fn get_current_index(&self) -> Option<Point2<usize>> {
341        // Current will be inside the map, since start and end were confirmed to be inside the map
342        // at construction, so simply cast, then convert from bounds to index
343        let current_map_isize = self.current_map?.map(|e| e as isize);
344        self.map_meta.cell_bounds.get_index(current_map_isize)
345    }
346}
347
348impl<'a, L, T> Slicer<'a, L, T> for Line
349where
350    L: Layer,
351    T: 'a,
352{
353    type Output = &'a T;
354
355    type OutputMut = &'a mut T;
356
357    fn slice(&self, data: &'a Array2<T>) -> Option<Self::Output> {
358        // Get the index
359        let index = self.get_current_index()?;
360
361        data.get(index.as_array2_index())
362    }
363
364    fn slice_mut(&self, data: &'a mut Array2<T>) -> Option<Self::OutputMut> {
365        // Get the index
366        let index = self.get_current_index()?;
367
368        data.get_mut(index.as_array2_index())
369    }
370
371    fn advance(&mut self) {
372        // Get the index of the current position, or just return if we're at the end
373        let curr_index = match self.get_current_index() {
374            Some(i) => i,
375            None => return,
376        };
377
378        // Calculate the param value, i.e. how far along the line we are. This will be used to
379        // check if we are beyond the end of the line
380        let param = (self.current_map.unwrap() - self.start_map).norm()
381            / (self.end_map - self.start_map).norm();
382
383        // Calculate the changes in the line parameter needed to reach the next x and y grid line
384        // respectively. Also add on the cell boundary precision to ensure that we will actually
385        // move over the cell boundary line.
386        let delta_param: Vector2<f64> = ((curr_index.cast() + self.dir_sign)
387            - self.current_map.unwrap())
388        .component_div(&self.dir)
389            + Vector2::from_element(self.map_meta.cell_boundary_precision);
390
391        // Whichever component of delta is smaller is what we need to advance along the line by.
392        let delta = delta_param.x.min(delta_param.y);
393
394        // If any of param + delta is > 1, the next point would be beyond the end of the line, so
395        // we should end here
396        if delta + param > 1.0 {
397            self.current_map = None;
398        }
399        // Otherwise, move current to current + dir*delta
400        else {
401            self.current_map = Some(self.current_map.unwrap() + (self.dir * delta));
402        }
403
404        // Write new step report to file
405        #[cfg(feature = "debug_iters")]
406        {
407            use std::io::Write;
408
409            let rpt = LineStepData {
410                start_parent: self.start_parent,
411                end_parent: self.end_parent,
412                dir: self.dir,
413                dir_sign: self.dir_sign,
414                start_map: self.start_map,
415                end_map: self.end_map,
416                current_map: self.current_map,
417                end_index: self.end_index,
418                delta: delta_param,
419            };
420
421            let val = serde_json::to_string_pretty(&rpt).unwrap();
422
423            writeln!(
424                std::sync::Arc::<std::fs::File>::get_mut(&mut self.step_report_file).unwrap(),
425                "{},",
426                val
427            )
428            .unwrap();
429        }
430    }
431
432    fn index(&self) -> Option<Point2<usize>> {
433        self.get_current_index()
434    }
435
436    fn reset(&mut self, _layer: Option<L>) {
437        self.current_map = Some(self.start_map)
438    }
439}
cell_map/iterators/slicers.rs

cell_map/iterators/
slicers.rs
