triangulate: Triangulate a two-dimensional polygon

In rgl: 3D Visualization Using OpenGL

Triangulate a two-dimensional polygon

Description

This algorithm decomposes a general polygon into simple polygons and uses the “ear-clipping” algorithm to triangulate it. Polygons with holes are supported.

Usage

triangulate(x, y = NULL, z = NULL, random = TRUE, plot = FALSE, partial = NA)

Arguments

x, y, z	Coordinates of a two-dimensional polygon in a format supported by xyz.coords. See Details for a description of proper input and how z is handled.
random	Currently ignored, the triangulation is deterministic.
plot	Whether to plot the triangulation; mainly for debugging purposes.
partial	Currently ignored. Improper input will lead to undefined results.

Details

Normally triangulate looks only at the x and y coordinates. However, if one of those is constant, it is replaced with the z coordinate if present.

The algorithm works as follows. First, it breaks the polygon into pieces separated by NA values in x or y. Each of these pieces should be a simple, non-self-intersecting polygon, not intersecting the other pieces. (Though some minor exceptions to this rule may work, none are guaranteed). The nesting of these pieces is determined: polygons may contain holes, and the holes may contain other polygons.

Vertex order around the polygons does not affect the results: whether a polygon is on the outside or inside of a region is determined by nesting.

Polygons should not repeat vertices. An attempt is made to detect if the final vertex matches the first one. If so, it will be deleted with a warning.

The “outer” polygon(s) are then merged with the polygons that they immediately contain, and each of these pieces is triangulated using the ear-clipping algorithm from the references.

Finally, all the triangulated pieces are put together into one result.

Value

A three-by-n array giving the indices of the vertices of each triangle. (No vertices are added; only the original vertices are used in the triangulation.)

The array has an integer vector attribute "nextvert" with one entry per vertex, giving the index of the next vertex to proceed counter-clockwise around outer polygon boundaries, clockwise around inner boundaries.

Note

Not all inputs will succeed, though inputs satisfying the rules listed in the Details section should.

Author(s)

R wrapper code written by Duncan Murdoch; the earcut library has numerous authors.

References

This function uses the C++ version of the earcut library from https://github.com/mapbox/earcut.hpp.

See Also

extrude3d for a solid extrusion of a polygon, polygon3d for a flat display; both use triangulate.

Examples

theta <- seq(0, 2*pi, length.out = 25)[-25]
theta <- c(theta, NA, theta, NA, theta, NA, theta, NA, theta)
r <- c(rep(1.5, 24), NA, rep(0.5, 24), NA, rep(0.5, 24), NA, rep(0.3, 24), NA, rep(0.1, 24))
dx <- c(rep(0, 24), NA, rep(0.6, 24), NA, rep(-0.6, 24), NA, rep(-0.6, 24), NA, rep(-0.6, 24))
x <- r*cos(theta) + dx
y <- r*sin(theta)
plot(x, y, type = "n")
polygon(x, y)
triangulate(x, y, plot = TRUE)
open3d()
polygon3d(x, y, x - y, col = "red")

rgl documentation built on April 3, 2025, 5:49 p.m.