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