mapping_algorithms/polygons/
mod.rs

1// SPDX-License-Identifier: MIT
2/*
3 * Copyright (c) [2023 - Present] Emily Matheys <emilymatt96@gmail.com>
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a copy
6 * of this software and associated documentation files (the "Software"), to deal
7 * in the Software without restriction, including without limitation the rights
8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 * copies of the Software, and to permit persons to whom the Software is
10 * furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be included in all
13 * copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 * SOFTWARE.
22 */
23
24pub use graham_scan::graham_scan;
25pub use jarvis_march::jarvis_march;
26pub use point_in_polygon::{are_multiple_points_in_polygon, is_single_point_in_polygon};
27
28use nalgebra::{ComplexField, Point, Point2, RealField, Scalar};
29use num_traits::{AsPrimitive, Bounded, NumOps};
30
31use crate::{array, ops::RangeInclusive, types::PolygonExtents};
32
33mod graham_scan;
34mod jarvis_march;
35mod point_in_polygon;
36
37#[cfg(feature = "pregenerated")]
38#[doc = "This module contains polygon mapping-algorithms that are pregenerated for single precision floating points."]
39pub mod single_precision {
40    pub use super::graham_scan::single_precision::*;
41    pub use super::jarvis_march::single_precision::*;
42    pub use super::point_in_polygon::single_precision::*;
43}
44
45#[cfg(feature = "pregenerated")]
46#[doc = "This module contains polygon mapping-algorithms that are pregenerated for double precision floating points."]
47pub mod double_precision {
48    pub use super::graham_scan::double_precision::*;
49    pub use super::jarvis_march::double_precision::*;
50    pub use super::point_in_polygon::double_precision::*;
51}
52
53/// This function calculates the extents of the polygon, i.e., the minimum and maximum values for each coordinate dimension.
54///
55/// # Generics
56/// * `T`: one of [`f32`] or [`f64`].
57/// * `N`: a constant generic of type [`usize`].
58///
59/// # Arguments
60/// * `polygon`: a slice of [`Point`].
61///
62/// # Returns
63/// See [`PolygonExtents`]
64#[cfg_attr(
65    feature = "tracing",
66    tracing::instrument("Calculate Polygon Extents", skip_all, level = "info")
67)]
68pub fn calculate_polygon_extents<T, const N: usize>(
69    polygon: &[Point<T, N>],
70) -> Option<PolygonExtents<T, N>>
71where
72    T: Bounded + Copy + RealField,
73{
74    let mut extents_accumulator: [RangeInclusive<T>; N] =
75        array::from_fn(|_| <T as Bounded>::max_value()..=<T as Bounded>::min_value());
76
77    if polygon.len() < 3 {
78        return None;
79    }
80
81    for vertex in polygon {
82        for (extent_for_dimension, vertex_coord) in
83            extents_accumulator.iter_mut().zip(vertex.coords.iter())
84        {
85            *extent_for_dimension = extent_for_dimension.start().min(*vertex_coord)
86                ..=extent_for_dimension.end().max(*vertex_coord);
87        }
88    }
89
90    Some(extents_accumulator)
91}
92
93fn calculate_determinant<O: ComplexField + Copy, T: Scalar + NumOps + AsPrimitive<O>>(
94    point_a: &Point2<T>,
95    point_b: &Point2<T>,
96    point_c: &Point2<T>,
97) -> O {
98    T::as_(
99        ((point_b.y - point_a.y) * (point_c.x - point_b.x))
100            - ((point_b.x - point_a.x) * (point_c.y - point_b.y)),
101    )
102}
103
104#[cfg(test)]
105mod tests {
106    use nalgebra::{Point, Point2};
107
108    use crate::Vec;
109
110    use super::*;
111
112    #[test]
113    fn test_calculate_polygon_extents() {
114        // Given:
115        // A set of polygon vertices
116        let polygon = Vec::from([
117            Point2::new(1.0, 1.0),
118            Point2::new(1.0, 4.0),
119            Point2::new(5.0, 4.0),
120            Point2::new(5.0, 1.0),
121        ]);
122
123        // When:
124        // Calculating the extents
125        let extents = calculate_polygon_extents(&polygon);
126        assert_eq!(
127            extents,
128            Some([RangeInclusive::new(1.0, 5.0), RangeInclusive::new(1.0, 4.0)])
129        );
130    }
131
132    #[test]
133    fn test_calculate_polygon_extents_empty_polygon() {
134        // An empty polygon
135        let polygon: Vec<Point<f64, 2>> = Vec::new();
136
137        // Calculating the extents
138        let extents = calculate_polygon_extents(&polygon);
139
140        // Expect the extents to be [max_value..=min_value] for x and y respectively
141        assert_eq!(extents, None);
142    }
143}
mapping_algorithms/polygons/mod.rs

mapping_algorithms/polygons/
mod.rs
