polygon_triangulate


polygon_triangulate, a MATLAB code which triangulates a polygon in 2D.

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 function will refuse to operate on the data.

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

This function cannot triangulate a polygon which includes one or more "holes". That is actually a significantly more difficult task.

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 in the usual sense. However, the function may not realize this, in which case it will return what it thinks is a reasonable triangulation of the (unreasonable) data.

The output of the program is a list of the N-3 triples of nodes that form the triangles of the triangulation.

Usage:

triangles = polygon_triangulate ( n, x, y )
where returning

Licensing:

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

Languages:

polygon_triangulate is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

convex_hull, a MATLAB code which demonstrates the computation of the convex hull of a set of 2D points.

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

polygon_integrals, a MATLAB code which returns the exact value of the integral of any monomial over the interior of a polygon in 2D.

polygon_monte_carlo, a MATLAB code which applies a Monte Carlo method to estimate the integral of a function over the interior of a polygon in 2D.

polygon_properties, a MATLAB code which computes properties of an arbitrary polygon in the plane, defined by a sequence of vertices, including interior angles, area, centroid, containment of a point, convexity, diameter, distance to a point, inradius, lattice area, nearest point in set, outradius, uniform sampling.

polygon_triangulate_test

Author:

Based on a C function by Joseph ORourke; MATLAB version by John Burkardt.

Reference:

Source Code:


Last revised on 26 February 2019.