triangulate: 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, random = TRUE, plot = FALSE, partial = NA)

Arguments

x, y

Coordinates of a two-dimensional polygon in a format supported by xy.coords.

random

Whether to use a random or deterministic triangulation.

plot

Whether to plot the triangulation; mainly for debugging purposes.

partial

If the triangulation fails, should partial results be returned?

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.

Details

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, separate from the other pieces. (Though some minor exceptions to this rule may work, none are guaranteed). The nesting of these pieces is determined. 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. Finally, all the triangulated pieces are put together into one result.

References

See the Wikipedia article polygon triangulation for a description of the ear-clipping algorithm.

Examples

Run this code

theta <- seq(0, 2*pi, len=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")

Run the code above in your browser using DataLab

Get 50% off unlimited learning