1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

//! Implements a few plane-sweep / line-crossings flavored algorithms.
//!
//! 1. [Line Crossings](#line-crossings)
//! 1. [Monotone Decomposition](#monotone-decomposition)
//!
//! # Line Crossings
//!
//! This is an implementation of the [Bentley-Ottman] algorithm to
//! efficiently compute all intersections of a collection of line
//! segments and points. The simplest usage is using the
//! [`Intersections`] iterator which yields all intersections and
//! overlaps. This is essentially a drop-in replacement to using
//! [`line_intersection`] over all pairs, but is typically more
//! efficient.
//!
//! For a more advanced usage such as polygon clipping, use
//! [`CrossingsIter`] which iterates over all intersection points,
//! while also providing information about all segments that start or
//! end at the last yielded point.
//!
//! ## Usage
//!
//! Construct a [`Intersections`] from an iterator of any type
//! implementing the [`Crossable`] trait. The geo-type [`Line`]
//! implements this trait. See the trait documentation for more
//! information on usage with custom types.
//!
//! ```rust
//! use geo::Line;
//! use geo_crossings::Intersections;
//! use std::iter::FromIterator;
//! let input = vec![
//!     Line::from([(1., 0.), (0., 1.)]),
//!     Line::from([(0., 0.5), (1., 0.5)]),
//!     Line::from([(0., 0.), (1., 1.)]),
//! ];
//! let iter = Intersections::<_>::from_iter(input);
//! // All pairs intersect
//! assert_eq!(iter.count(), 3);
//! ```
//!
//! # Monotone Decomposition
//!
//! Partitions a polygon into monotone pieces.  See [`monotone_chains`].
//!
//! [Bentley-Ottman]: //en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
//! [`Line`]: geo::Line
//! [`Point`]: geo::Point
//! [`Coordinate`]: geo::Coordinate
//! [`line_intersection`]: geo::algorithm::line_intersection::line_intersection
mod events;
pub use events::SweepPoint;

mod line_or_point;
mod segments;

pub mod crossings;
pub use crossings::{Crossable, Crossing, CrossingsIter, Intersections};

pub mod monotone;
pub use monotone::{Sweep, monotone_chains};