Triangulate a Polygonal Region

TRIANGULATE is a C program which triangulates a polygonal region, by Joseph O'Rourke.

The polygon is defined by an input file which gives the coordinates of the nodes of the polygon.

Because the calculation is to be exact, the coordinates are expected to be integers. This requirement may cause problems!

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, and the program will refuse to proceed.

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 PostScript file which shows the polygon and its triangulation. The text of the PostScript file includes comments that describe the triangulation in terms of the pairs of vertices that were connected to make each diagonal.


triangulate < input.txt >


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

Related Data and Programs:

POLYGON, a dataset directory which contains examples of polygons.

POLYGON_MOMENTS, a C library which computes arbitrary moments of a polygon.

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


Joseph ORourke


Source Code:

COMB generates a "comb" polygon, a somewhat tricky shape that can be used as an input to the triangulation program.

TRIANGULATE reads a file definining a polygon, and determines an appropriate triangulation.

Examples and Tests:

COMB10 is an example of a "comb" polygon of 10 vertices Files you may copy include:

I18 is an example of a complicated nonconvex polygon. Files you may copy include:

I19 is a copy of I18 with a pair of repeated vertices, which should cause the program to refuse to try to carry out the triangulation.

SNAKE is an example defining a "snake" polygon. Files you may copy include:

SQUARE is an example defining a square. Files you may copy include:

TRIANGLE is an example defining a triangle. Files you may copy include:

List of Routines:

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

Last revised on 11 April 2011.