geometry_algorithm/
monotone_subdivision.rs

1//! Y-monotone subdivision of a Cartesian polygon.
2//!
3//! Boost.Geometry has no monotone-partition entry. Every triangle is
4//! y-monotone, so the native ear-cut triangulation supplies a valid (though
5//! finer than maximal) monotone subdivision without introducing a second
6//! polygon-cutting kernel.
7
8use alloc::vec::Vec;
9
10use geometry_cs::{CartesianFamily, CoordinateSystem};
11use geometry_model::Polygon as ModelPolygon;
12use geometry_tag::SameAs;
13use geometry_trait::{Point, Polygon};
14
15use crate::triangulate_earcut::triangulate_earcut;
16
17/// Subdivide a Cartesian polygon into y-monotone owned polygons.
18///
19/// The current native contract returns triangular pieces; triangles are valid
20/// y-monotone polygons and preserve the source area exactly up to floating-point
21/// arithmetic.
22#[inline]
23#[must_use]
24pub fn monotone_subdivision<Pg, P>(polygon: &Pg) -> Vec<ModelPolygon<P>>
25where
26    Pg: Polygon<Point = P>,
27    P: Point<Scalar = f64> + Copy,
28    P::Cs: CoordinateSystem,
29    <P::Cs as CoordinateSystem>::Family: SameAs<CartesianFamily>,
30{
31    triangulate_earcut(polygon)
32}
33
34#[cfg(test)]
35mod tests {
36    use geometry_cs::Cartesian;
37    use geometry_model::{Point2D, Polygon, Ring};
38
39    use super::monotone_subdivision;
40
41    #[test]
42    fn reflex_polygon_subdivides_to_triangles() {
43        type P = Point2D<f64, Cartesian>;
44        let polygon: Polygon<P> = Polygon::new(Ring::from_vec(alloc::vec![
45            P::new(0.0, 0.0),
46            P::new(0.0, 2.0),
47            P::new(1.0, 1.0),
48            P::new(2.0, 2.0),
49            P::new(2.0, 0.0),
50            P::new(0.0, 0.0),
51        ]));
52        let pieces = monotone_subdivision(&polygon);
53        assert_eq!(pieces.len(), 3);
54        assert!(pieces.iter().all(|piece| piece.outer.0.len() == 4));
55    }
56}
geometry_algorithm/monotone_subdivision.rs

geometry_algorithm/
monotone_subdivision.rs
