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.

Usage

// A hollow square shape // ________ // | ____ | // | | | | // | |____| | // |________| let polygons: Vec<Vec<MyVert>> = vec![ vec![(0., 0.).into(), (0., 1.).into(), (1., 1.).into(), (1., 0.).into()], vec![(0.05, 0.05).into(), (0.05, 0.95).into(), (0.95, 0.95).into(), (0.95, 0.05).into()] ]; // `output` is an arbitrary triangulation of polygons in a format determined by the type parameter (in this case, a `Vec` of triangle fans represented by a `Vec` of the `MyVert` vertices). let output: Vec<Vec<MyVert>> = polygons.triangulate_default::<builders::VecVecFanBuilder<_>>().unwrap();

Input traits

Output traits

Preconditions

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.