Struct DynamicMonoTriangulator 

pub struct DynamicMonoTriangulator<V: IndexType, Vec2: Vector2D, Poly: Polygon<Vec2>> { /* private fields */ }

A variant of the sweep-line algorithm that finds the min-weight triangulation for each monotone sub-polygon using dynamic programming, leading to an overall O(n^2) time complexity.

When using the bound k, the approximation quality decreases the smaller k is, with time O(k^2 n log n). However, for k << n this comes in most cases very quickly close to O(n log n).

For the quality of the approximation it is generally beneficial to rotate the mesh such that the mesh can be decomposed in a large number of y-monotone components.

Trait Implementations

impl<V: Clone + IndexType, Vec2: Clone + Vector2D, Poly: Clone + Polygon<Vec2>> Clone for DynamicMonoTriangulator<V, Vec2, Poly>

fn clone(&self) -> DynamicMonoTriangulator<V, Vec2, Poly>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V: Debug + IndexType, Vec2: Debug + Vector2D, Poly: Debug + Polygon<Vec2>> Debug for DynamicMonoTriangulator<V, Vec2, Poly>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<V: IndexType, Vec2: Vector2D, Poly: Polygon<Vec2>> MonotoneTriangulator for DynamicMonoTriangulator<V, Vec2, Poly>

fn new(v: usize) -> Self

Create a new reflex chain with a single value

fn is_right(&self) -> bool

Whether the chain is oriented to the right

fn left( &mut self, value: usize, _: &mut Triangulation<'_, V>, _: &Vec<IndexedVertex2D<V, Vec2>>, )

Add a new value to the left reflex chain

fn finish( &mut self, indices: &mut Triangulation<'_, V>, vec2s: &Vec<IndexedVertex2D<V, Vec2>>, )

Finish triangulating the reflex chain

type V = V

The index type used in the mesh

type Vec2 = Vec2

The vector type used in the mesh

fn last_opposite(&self) -> usize

Get the last inserted element of the opposite chain TODO: Get rid of this. It’s confusing to use and only use in the split case.

fn sanity_check(&self, _: usize, _: usize, _: &Option<Self>)

Validate the data structure

fn right( &mut self, value: usize, _: &mut Triangulation<'_, V>, _: &Vec<IndexedVertex2D<V, Vec2>>, )

Add a new value to the right chain