TRIANGULATE
Triangulate a Polygonal Region


TRIANGULATE is a MATLAB program which triangulates a polygonal region.

The polygon is defined by an input file which gives the coordinates of the vertices of the polygon, in counterclockwise order.

No consecutive pair of vertices should be equal; when describing a polygon, sometimes the first and last vertices are equal. For this program, that is not the case. To describe a square, your input file should contain four pairs of coordinates, for instance.

The vertices should be listed in counterclockwise order. If you list them in clockwise order, then the area will probably come out negative. The program will retry the calculation by reversing the order of the vertices.

It is possible to create a "polygon" that has zero area. The program will refuse to process such an object.

The polygon does not need to be convex. However, you should be careful not to specify a polygon which crosses itself, since this means the interior of the polygon is not well defined, and hence a triangulation is not well defined. As a simple example of such a problem, consider the four vertices of a square in counterclockwise order: V1, V2, V3, V4, and list them instead as V1, V3, V2, V4. This shape cannot be triangulated.

The output of the program is a list of the "diagonal lines" defined by pairs of vertices which constitute the triangulation, a list of the nodes that form the triangles of the triangulation, and an image of the triangulated polygon.

The program is based on a C program by Joseph ORourke.

Usage:

triangulate ( 'prefix', 'animate' )
where reads the file and writes the files

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

TRIANGULATE is available in a C version and a MATLAB version.

Related Data and Programs:

CONVEX_HULL, a MATLAB program which demonstrates the computation of the convex hull of a set of 2D points.

HAND_DATA, MATLAB programs which carry out some numerical exercises based on data that came from tracing several points on a person's hand.

MAPLE_AREA, a MATLAB library which takes the list of pixels that form the boundary of the image of a maple leaf within a picture, and uses grid, Monte Carlo, and Quasi Monte Carlo sampling to estimate the area of the leaf.

MAPLE_BOUNDARY, a MATLAB library which reads an image of a maple leaf and extracts the list of pixels that form the boundary.

POLYGON, a dataset directory which contains examples of polygons.

TRIANGLE, a C program which triangulates a set of points.

Reference:

Source Code:

Examples and Tests:

COMB is an example of a "comb" polygon of 10 vertices

HAND outlines a hand using 59 vertices.

I18 is an example of a complicated nonconvex polygon, using 18 vertices.

SNAKE is an example defining a "snake" polygon using 12 vertices.

SQUARE is an example defining a square, using 4 vertices.

TE53 is an example in which the vertices have been (incorrectly) listed in clockwise order. The program detects this problem and reverses the ordering before proceeding. The example uses 26 vertices.

TRIANGLE is an example defining a triangle, using 3 vertices.

You can go up one level to the MATLAB source codes.


Last revised on 03 January 2013.