Struct MonotonicPolygons

pub struct MonotonicPolygons<T: GeoNum>(/* private fields */);

A multi-polygon represented as a collection of (disjoint) monotone polygons.

This structure is optimized for point-in-polygon queries, and is typically much faster than the equivalent method on Polygon. This is because a single monotone polygon can be tested for intersection with a point in O(log n) time, where n is the number of vertices in the polygon. In contrast, the equivalent method on Polygon is O(n). Typically, a polygon can be sub-divided into a small number of monotone polygons, thus providing a significant speed-up.

Example

Construct a MonotonicPolygons from a Polygon, or a MultiPolygon using MontonicPolygons::from, and query point intersection via the Intersects<Coord> trait.

use geo::prelude::*;
use geo::{polygon, coord};

let polygon = polygon![
    (x: -2., y: 1.),
    (x: 1., y: 3.),
    (x: 4., y: 1.),
    (x: 1., y: -1.),
    (x: -2., y: 1.),
];
let mp = MonotonicPolygons::from(polygon);
assert!(mp.intersects(&coord!(x: -2., y: 1.)));

Implementations

impl<T: GeoNum> MonotonicPolygons<T>

pub fn subdivisions(&self) -> &Vec<MonoPoly<T>>

Get a reference to the monotone polygons.

pub fn into_subdivisions(self) -> Vec<MonoPoly<T>>

Reduce to inner Vec of monotone polygons.

Trait Implementations

impl<T: Clone + GeoNum> Clone for MonotonicPolygons<T>

fn clone(&self) -> MonotonicPolygons<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + GeoNum> Debug for MonotonicPolygons<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: GeoNum> From<MultiPolygon<T>> for MonotonicPolygons<T>

fn from(mp: MultiPolygon<T>) -> Self

Converts to this type from the input type.

impl<T: GeoNum> From<Polygon<T>> for MonotonicPolygons<T>

fn from(poly: Polygon<T>) -> Self

Converts to this type from the input type.

impl<T: GeoNum> Intersects<Coord<T>> for MonotonicPolygons<T>

fn intersects(&self, other: &Coord<T>) -> bool