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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#![warn(missing_docs)]

//! # triangulate
//! Subdivides a set of non-self-intersecting polygons into a set of non-overlapping triangles. 
//! Inputs and outputs can be customized to use your required formats to avoid unnecessary conversions.
//! 
//! ```
//! # use triangulate::formats;
//! # use triangulate::{PolygonList, ListFormat};
//! 
//! // A hollow square shape
//! //  ________
//! // |  ____  |
//! // | |    | |
//! // | |____| |
//! // |________|
//! let polygons = vec![
//!     vec![[0f32, 0f32], [0., 1.], [1., 1.], [1., 0.]], 
//!     vec![[0.05, 0.05], [0.05, 0.95], [0.95, 0.95], [0.95, 0.05]]
//! ];
//! let mut triangulated_indices = Vec::<[usize; 2]>::new();
//! polygons.triangulate(formats::IndexedListFormat::new(&mut triangulated_indices).into_fan_builder()).expect("Triangulation failed");
//! println!("First triangle: {:?}, {:?}, {:?}", 
//!     polygons.get_vertex(triangulated_indices[0]), 
//!     polygons.get_vertex(triangulated_indices[1]), 
//!     polygons.get_vertex(triangulated_indices[2]));
//! ```
//! 
//! Any type that implements [Polygon] or [PolygonList] can be triangulated. Most commonly that would be [Vec<_>] or [Vec<Vec<_>>] (where `_`: [Vertex], such as `[f32; 2]`), 
//! but you can implement the trait on your own types.
//! 
//! The output format is also customizable. [PolygonList::triangulate] takes a [FanFormat], which determines the resulting output. 
//! Most commonly, you would want [formats::IndexedListFormat], which stores three indices for every generated triangle in a [List] (like [Vec]).
//! However, this is a [ListFormat] (it takes individual triangles instead of triangle fans), so it must be converted to a [FanFormat] by calling [ListFormat::into_fan_format] (see the example above).
//! Another useful format is [formats::DeindexedListFormat], which deindexes each triangle point to create a [List] of the actual vertices.
//! 
//! ## Input traits
//! * [Vertex]
//! * [VertexIndex]
//! * [Polygon]
//! * [PolygonList]
//! ## Output traits
//! * [Fan]
//! * [Fans]
//! * [List]
//! * [FanFormat]
//! * [FanBuilder]
//! * [ListFormat]
//! * [ListBuilder]
//! 
//! ## Preconditions  
//! * No edge can cross any other edge, whether it is on the same polygon or not.
//! * Each vertex must be part of exactly two edges. Polygons cannot 'share' vertices with each other.
//! * Each vertex must be distinct - no vertex can have x and y coordinates that both compare equal to another vertex's.
//! 
//! These preconditions are not explicitly checked, but an invalid polygon set will likely yield `TriangulationError::InternalError`.
//! 
//! ## Results
//! Because the algorithm involves random ordering, the exact triangulation is not guaranteed to be same between invocations.
//! 
//! ## Algorithm
//! This library is based on [Raimund Seidel's randomized algorithm for triangulating polygons](https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/A%20Simple%20and%20fast.pdf). 
//! The expected runtime for each polygon or hole with *n* vertices is O(*n* [log\*](https://en.wikipedia.org/wiki/Iterated_logarithm) *n*), a near-linear runtime.

mod idx;
mod segment;
mod trapezoid;
mod querynode;
mod trapezoidation;
mod nexus;
mod monotone;
mod mappable;
mod math;
mod fan_builder_state;
mod inputs;
mod outputs;
#[macro_use]
mod errors;

#[cfg(feature = "_debugging")]
pub mod debug;

#[cfg(any(test, feature = "_benchmarking"))]
#[doc(hidden)]
pub mod tests;

pub use trapezoidation::Trapezoidation;
pub use errors::{TrapezoidationError, TriangulationError};

pub(crate) use fan_builder_state::FanBuilderState;

pub use inputs::*;
pub use outputs::*;

pub use mappable::Mappable;

pub use num_traits::real::Real;