## Constrained triangulation of polygons

Decido aims to provide very fast constratined triangulations for polygons in R using a robust C++ library created by Mapbox.

Constrained triangulation of polygons by ear clipping is an important low-cost method for decomposing a polygon into triangles. Polygon triangulation is necessary for 3D visualization and many analytical techniques. Here constrained means shape-preserving, in the sense that every edge of the polygon will be include as the edge of a triangle in the result.

Ear clipping (or cutting) must be applied to a path-based polygon that consists of only one island, with zero or more holes. Any multiple island polygons must be triangulation separately by this method.

The better-known Delaunay triangulation is generally not shape-preserving as it works only on points, without knowledge of input line segments or polygon edges. Shape-preserving Delaunay or more commonly near-Delaunay triangulation is performed on a set of edges rather than paths, and can be performed on multiple polygons at once. Holes require careful trimming of triangles after the decomposition is performed in this approach.

## Example

This is a basic example of triangulating a single-ring polygon. The output is a vector of triplet indices defining each triangle.

library(decido)
x <- c(0, 0, 0.75, 1, 0.5, 0.8, 0.69)
y <- c(0, 1, 1, 0.8, 0.7, 0.6, 0)
(ind <- earcut(cbind(x, y)))
#>  [1] 2 1 7 7 6 5 5 4 3 2 7 5 5 3 2

plot_ears(cbind(x, y), ind)

Support for holes is provided by the argument holes. The values are the starting index of each hole, here in R’s 1-based convention.

## polygon with a hole
x <- c(0, 0, 0.75, 1, 0.5, 0.8, 0.69,
0.2, 0.5, 0.5, 0.3, 0.2)
y <- c(0, 1, 1, 0.8, 0.7, 0.6, 0,
0.2, 0.2, 0.4, 0.6, 0.4)
ind <- earcut(cbind(x, y), holes = 8)
plot_ears(cbind(x, y), ind)

The hole-specification is a little subtle, since usually R’s functions (polygon and polypath, and others) expect NA values to separate paths.

Notice how the hole begins at index 8, hence holes = 8 above, and holes = c(8, 13) below.

plot_ears(cbind(x, y), ind, col = "grey", border = NA)
text(x, y, labels = seq_along(x), pos = 2)

The method is subtle, and it’s also not the only way to do it, the grid package uses a grouping vector rather than a sparse index like this. The spatial packages sp and sf explicitly use structural hierarchies rather than more abstract specifications. The fortify-approach in ggplot2 is more like the grid one. A sparse representation is closer to what is needed for topological operations and visualization, consider that when we have triangles there are no need for “holes”, we can identify which triangles will be plotted and how (or not), and an index into the vertices available becomes a key efficiency feature. (See silicate for a lot more on this topic).

This example adds a third polygon, a second hole in the island.

## add another hole
x <- c(0, 0, 0.75, 1, 0.5, 0.8, 0.69,
0.2, 0.5, 0.5, 0.3, 0.2,
0.15, 0.23, 0.2)
y <- c(0, 1, 1, 0.8, 0.7, 0.6, 0,
0.2, 0.2, 0.4, 0.6, 0.4,
0.65, 0.65, 0.81)
ind <- earcut(cbind(x, y), holes = c(8, 13))
plot_ears(cbind(x, y), ind, col = "grey")

## Comparing paths and triangles

This example defines a much simpler shape, the minimal shape able to be decomposed to triangles (and not stay a triangle).

A quadrilateral, with two holes that are open to each other allows the use of the same data, and we can tweak whether we wanted one hole or two. This is an important example used for validating early versions of this package.

x <- c(0, 0, 1, 1,
0.4, 0.2, 0.2, 0.4,
0.6, 0.8, 0.8, 0.6
)
y <- c(0, 1, 1, 0,
0.2, 0.2, 0.4, 0.4,
0.6, 0.6, 0.4, 0.4
)
ind <- decido::earcut(cbind(x, y), holes = c(5, 9))
plot_ears(cbind(x, y), ind, col = "grey")
title("triangle plot, two holes")

plot_holes(cbind(x, y), holes = c(5, 9), col = "grey")
title("path plot, two holes")


ind <- decido::earcut(cbind(x, y), holes = 5)
plot_ears(cbind(x, y), ind, col = "grey")
title("triangle plot, two holes as one")

plot_holes(cbind(x, y), holes = 5, col = "grey")
title("path plot, two holes as one")

## A geographic example

For good measure we include a geographic example, a triangulation of the mainland part of Tasmania from the oz package.

library(oz)
oz_ring <- oz::ozRegion(states = FALSE)