TRIANGULATE
Triangulate a Polygonal Region

TRIANGULATE is a MATLAB program which triangulates a polygonal region. The region need not be convex.

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

Note that no two successive vertices can be equal, nor can the first and last vertices be equal.

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' )

• 'prefix' is the filename prefix,
• 'animate' (optional argument) is 'y' if you want to see the process animated;

• 'prefix'_nodes.txt, containing the vertex coordinates,

• 'prefix'_diagonals.txt listing N-3 pairs of vertices that form the internal diagonals of the triangulation.
• 'prefix'_elements.txt listing N-2 triples of vertices that form the triangles of the triangulation.

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.

POLYGON, a dataset directory which contains examples of polygons.

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

Reference:

• Joseph ORourke,
  Computational Geometry in C,
  Second Edition,
  Cambridge, 1998,
  ISBN: 0521649765,
  LC: QA448.D38.

Source Code:

• triangulate.m the source code.

Examples and Tests:

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

• comb_nodes.txt, the input file of vertex coordinates.
• comb.png, a PNG image of the polygon.
• comb_triangulated.png, a PNG image of the triangulated polygon.
• comb_output.txt, the output file.
• comb_diagonals.txt, the output file of internal diagonal edges.
• comb_elements.txt, the output file of triangles that make up the polygon.

HAND outlines a hand using 59 vertices.

• hand_nodes.txt, the input file of vertex coordinates.
• hand.png, a PNG image of the polygon.
• hand_triangulated.png, a PNG image of the triangulated polygon.
• hand_output.txt, the output file.
• hand_diagonals.txt, the output file of internal diagonal edges.
• hand_elements.txt, the output file of triangles that make up the polygon.

I18 is an example of a complicated nonconvex polygon.

• i18_nodes.txt, the input file of vertex coordinates.
• i18.png, a PNG image of the polygon.
• i18_triangulated.png, a PNG image of the triangulated polygon.
• i18_output.txt, the output file.
• i18_diagonals.txt, the output file of diagonal edges.
• i18_elements.txt, the output file of triangles that make up the polygon.

SNAKE is an example defining a "snake" polygon.

• snake_nodes.txt, the input file of vertex coordinates.
• snake.png, a PNG image of the polygon.
• snake_triangulated.png, a PNG image of the triangulated polygon.
• snake_output.txt, the output file.
• snake_diagonals.txt, the output file of diagonal edges.
• snake_elements.txt, the output file of triangles that make up the polygon.

SQUARE is an example defining a square.

• square_nodes.txt, the input file of vertex coordinates.
• square.png, a PNG image of the polygon.
• square_triangulated.png, a PNG image of the triangulated polygon.
• square_output.txt, the output file.
• square_diagonals.txt, the output file of diagonal edges.
• square_elements.txt, the output file of triangles that make up the polygon.

TRIANGLE is an example defining a triangle.

• triangle_nodes.txt, the input file of vertex coordinates.
• triangle.png, a PNG image of the polygon.
• triangle_triangulated.png, a PNG image of the triangulated polygon.
• triangle_output.txt, the output file.
• triangle_diagonals.txt, the output file of diagonal edges.
• triangle_elements.txt, the output file of triangles that make up the polygon.

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