triangulate {tigers}

Triangulate a Polygon

Description

Performs the decomposition of a polygon into triangles.

Usage

triangulate(x, y = NULL, method = 1)

Arguments

x, y

the coordinates of the points given in the usual way in R.

method

an integer between 1 and 4 specifying the triangulation method.

Details

The following methods are available:

• 1: the triangles are created in successive order from the first appropriate angle (i.e., an ear) encountered in the polygon.

• 2: the triangles are created to favour thin triangles.

• 3: the triangles are created to favour fat triangles.

• 4: the triangles are created to favour regular-looking triangles based on their determinant.

These methods have different requirements: method 1 needs the polygon to be closed, whereas the other methods need it to be open; method 2 needs the polygon to be in counterclockwise order, and method 3 needs it to be in clockwise order (the other methods are not sensitive to this order). These requirements are checked before performing the triangulation and the polygon is changed internally (without warning since the original polygon is not modified) if necessary.

Value

a three-column matrix giving the indices of the vertices in each triangle (i.e., each row a is a triangle).

Note

The internal codes need to be checked and tested again.

Author(s)

Emmanuel Paradis

References

Toussaint, G. (1991) Efficient triangulation of simple polygons. Visual Computer, 7, 280–295. <doi:10.1007/BF01905693>

Examples

XY <- rbind(c(0, 0),
            c(1, 0),
            c(.25, .25),
            c(.5, .5),
            c(1.2, .8),
            c(1, .78),
            c(0, 1))
(tri <- triangulate(XY))
plot(XY, type = "n", asp = 1)
for (i in 1:nrow(tri))
    polygon(XY[tri[i, ], ], border = "white", col = "green", lwd = 2)
polygon(XY, lwd = 4, border = "lightgrey")
text(XY, labels = 1:nrow(XY), cex = 1.2)