TRIANGULATE
Triangulate a Polygonal Region

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

The region need not be convex. The polygon is defined by an input file which gives the coordinates of the nodes of the polygon, in counterclockwise order. The coordinates are expected to be integers.

No consecutive pair of vertices should be equal.

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.

Usage:

triangulate < input.txt > output.ps

• input.txt lists the (integer) vertex coordinates;
• output.ps is a PostScript image of the triangulation.

Languages:

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

Related Data and Programs:

POLYGON, a dataset directory which contains examples of polygons.

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

Author:

Joseph ORourke

Reference:

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

Source Code:

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

• comb.c, the source code;
• comb.sh, a shell script to compile, link and load the source code.

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

• triangulate.c, the source code;
• triangulate.sh, a shell script to compile, link and load the source code.

Examples and Tests:

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

• comb10.in, the input file defining the polygon
• comb10.png, a PNG image of the polygon.
• comb10_triangulated.png, a PNG image of the triangulated polygon.

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

• i18.in, the input file defining the polygon
• i18.png, a PNG image of the polygon.
• i18_triangulated.png, a PNG image of the triangulated polygon.

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.

• i19.in, the input file defining the polygon

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

• snake5.in, the input file defining the polygon
• snake5.png, a PNG image of the polygon.
• snake5_triangulated.png, a PNG image of the triangulated polygon.

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

• square.in, the input file defining the polygon
• square.png, a PNG image of the polygon.
• square_triangulated.png, a PNG image of the triangulated polygon.

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

• triangle.in, the input file defining the polygon
• triangle.png, a PNG image of the polygon.
• triangle_triangulated.png, a PNG image of the triangulated polygon.

List of Routines:

• MAIN is the main program for TRIANGULATE.
• AREA_POLY2 returns the area of a polygon.
• AREA_SIGN returns the sign of the area defined by three points.
• AREA2 returns twice the signed area of a triangle.
• BETWEEN returns TRUE iff point C lies on the closed segement AB.
• COLLINEAR is TRUE if the points A, B and C are collinear.
• DIAGONAL returns TRUE iff (A,B) is a proper internal diagonal of the polygon.
• DIAGONALIE returns TRUE iff (A,B) is a proper diagonal of a polygon.
• EAR_INIT initializes the data structures, and calls Triangulate2 to clip ears.
• IN_CONE returns TRUE iff the diagonal (A,B) is strictly internal.
• INTERSECT returns TRUE iff segments AB and CD intersect.
• INTERSECT_PROP returns true if and only if AB properly intersects CD.
• LEFT is TRUE if C is on the left side of the line from A to B.
• LEFT_ON is TRUE if C is to the left side, or on, the line from A to B.
• MAKE_NULL_VERTEX makes a vertex.
• PRINT_POLY prints the polygon data.
• PRINT_VERTICES prints the vertices.
• READ_VERTICES reads the polygon vertice from standard input.
• SCALE_DATA determines the scale for the polygonal data.
• TRIANGULATE prints N-3 diagonals which triangulate the polygon.
• XOR returns the exclusive OR of two values.

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