Crate triangulate

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.

 
// 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. The expected runtime for each polygon or hole with n vertices is O(n log* n), a near-linear runtime.

Modules

• formats
  Predefined implementations of FanFormat, FanBuilder, ListFormat, and ListBuilder

Structs

• IndexWith
  Wrapper to change the PolygonList::Index type
• IndexWithIter
  Iterator for the IndexWith wrapper
• Trapezoidation
  The trapezoidation of a PolygonList generated as the first step of triangulation.

Enums

• PolygonElement
  Used to destinguish multiple polygons while iterating with PolygonList::iter_indices.
• TrapezoidationError
  Describes an error which occurred during trapezoidation
• TriangleWinding
  The order the vertices in a polygon are listed in
• TriangulationError
  Describes an error which occurred during triangulation

Traits

• Fan
  A triangle fan with vertices of type V
• FanBuilder
  Performs the construction of triangle fans
• FanFormat
  Describes the construction and layout of a triangle fans
• Fans
  A collection of multiple Fans.
• List
  A list of triangles represented as triplets of vertices of type V
• ListBuilder
  Performs the construction of a triangle list
• ListFormat
  Describes the construction and layout of a triangle list
• Mappable
  A type which can map its members of type T to other types (e.g. [usize; 2] is Mappable over usize to produce [u16; 2], [u32; 2], etc.)
• Polygon
  An indexable polygon’s vertices
• PolygonList
  An indexable list of polygons and their vertices
• Real
  A trait for real number types that do not necessarily have floating-point-specific characteristics such as NaN and infinity.
• Vertex
  A two-dimensional point.
• VertexIndex
  A type which can be used to index a specific Vertex. Automatically implemented for all Eq + Clone types