Triangulation

Triangulation enables you to triangulate simple polygons.

Using Triangulation

To create an Triangulation object, provide its constructor with a [2 x n] matrix, where each column represents a vertex:

The property indicesTriangles yields a [3 x m] matrix. Each column holds the indices for a triangle. The property tree gives you insights into Seidel's algorithm which is further discussed in the section below.

Limitations

As mentioned before Triangulation only supports simple polygons, which are non-intersecting and free of holes.

However, simple polygons may include convex and concave parts.

At least three distinct vertices must be provided in clockwise order. Furthermore, Triangulation is only available for two dimensional data.

OPtional Parameters

Next to the vertices, you may enter a vector containing indices. This enables you to select among the vertices you provided as displayed in the following example:

Algorithm overview

Triangulation is based on Seidel's algorithm, where the polygon is partitioned into trapezoids first. This is accomplished with the aid of a binary tree. Based on the trapezoids diagonals, dividing the polygon into monotone polygons, can be determined. Monotone polygons have one edge, the so-called base, that extends from the lowest to the highest vertex. The remaining vertices are distributed between them.

Triangles are then obtained by clipping ears from the monotone polygons. An ear consists of a tip which is a convex vertex of the monotone polygon and its left and right neighbor. This procedure is repeated until no monotone polygons are left.

More Information

For more detailed information check out:

• APIDoc for Triangulation
• Seidel's algorithm
• FillPolygon