TRIANGULATE, a MATLAB program which triangulates a polygon.
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.
triangulate ( 'prefix', 'animate' )where
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
TRIANGULATE is available in a C version and a MATLAB version.
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.