geo/algorithm/monotone/
mod.rs

1mod mono_poly;
2use crate::{Coord, GeoNum, Intersects, MultiPolygon, Polygon};
3pub use mono_poly::MonoPoly;
4
5mod segment;
6use segment::RcSegment;
7pub(crate) use segment::Segment;
8
9mod sweep;
10pub(crate) use sweep::SimpleSweep;
11
12mod builder;
13pub use builder::monotone_subdivision;
14
15/// A multi-polygon represented as a collection of (disjoint) monotone polygons.
16///
17/// This structure is optimized for point-in-polygon queries, and is typically
18/// much faster than the equivalent method on `Polygon`.  This is because a
19/// single monotone polygon can be tested for intersection with a point in
20/// `O(log n)` time, where `n` is the number of vertices in the polygon.  In
21/// contrast, the equivalent method on `Polygon` is `O(n)`.  Typically, a
22/// polygon can be sub-divided into a small number of monotone polygons, thus
23/// providing a significant speed-up.
24///
25/// # Example
26///
27/// Construct a `MonotonicPolygons` from a `Polygon`, or a `MultiPolygon` using
28/// `MontonicPolygons::from`, and query point intersection via the
29/// `Intersects<Coord>` trait.
30///
31/// ```rust
32/// use geo::prelude::*;
33/// use geo::{polygon, coord};
34///
35/// let polygon = polygon![
36///     (x: -2., y: 1.),
37///     (x: 1., y: 3.),
38///     (x: 4., y: 1.),
39///     (x: 1., y: -1.),
40///     (x: -2., y: 1.),
41/// ];
42/// let mp = MonotonicPolygons::from(polygon);
43/// assert!(mp.intersects(&coord!(x: -2., y: 1.)));
44/// ```
45#[derive(Clone, Debug)]
46pub struct MonotonicPolygons<T: GeoNum>(Vec<MonoPoly<T>>);
47
48impl<T: GeoNum> MonotonicPolygons<T> {
49    /// Get a reference to the monotone polygons.
50    pub fn subdivisions(&self) -> &Vec<MonoPoly<T>> {
51        &self.0
52    }
53
54    /// Reduce to inner `Vec` of monotone polygons.
55    pub fn into_subdivisions(self) -> Vec<MonoPoly<T>> {
56        self.0
57    }
58}
59impl<T: GeoNum> From<Polygon<T>> for MonotonicPolygons<T> {
60    fn from(poly: Polygon<T>) -> Self {
61        Self(monotone_subdivision([poly]))
62    }
63}
64
65impl<T: GeoNum> From<MultiPolygon<T>> for MonotonicPolygons<T> {
66    fn from(mp: MultiPolygon<T>) -> Self {
67        Self(monotone_subdivision(mp.0))
68    }
69}
70
71impl<T: GeoNum> Intersects<Coord<T>> for MonotonicPolygons<T> {
72    fn intersects(&self, other: &Coord<T>) -> bool {
73        self.0.iter().any(|mp| mp.intersects(other))
74    }
75}
76
77#[cfg(test)]
78mod tests;
geo/algorithm/monotone/mod.rs

geo/algorithm/monotone/
mod.rs
