# earcut: Constrained polygon triangulation In decido: Bindings for 'Mapbox' Ear Cutting Triangulation Library

## Description

Produce a triangulation index into x,y coordinates of a polygon that may include holes. Holes are specified by input argument `holes` which marks the starting index of each hole, if any.

## Usage

 ```1 2 3 4``` ```earcut(xy, holes = 0, ...) ## Default S3 method: earcut(xy, holes = 0L, ...) ```

## Arguments

 `xy` xy-coordinates, either a list, matrix, or data frame `holes` index of starting position of each hole in x,y, leave set to `0` if no holes `...` unused

## Details

Triangles are returned in counter-clockwise orientation, a common convention that ascribes a positive area to the triangle. (Orientation may be collinear or numerically ambiguous and so may be undetermined).

Ear cutting (or ear clipping) applies constrained triangulation by successively 'cutting' triangles from a polygon defined by path/s. Holes are supported, the earcut library works with single-island-with-holes polygons, analogous to the POLYGON type in simple features.

To understand the specification of holes, see the examples with comment starting "1) Notice how the hole begins ..." in relation to the example code.

## Value

integer vector of triangle index, in sets of three

plot_ears

## Examples

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45``` ```## single ring polygon 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))) plot_ears(cbind(x, y), ind) ## 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) ## 1) 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) ## 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") # simpler shape with more than one hole # the two inside holes are open to each other # (so we can use the same data for one hole or two) 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") plot_holes(cbind(x, y), holes = c(5, 9), col = "grey") ind <- decido::earcut(cbind(x, y), holes = 5) plot_ears(cbind(x, y), ind, col = "grey") plot_holes(cbind(x, y), holes = 5, col = "grey") ```

### Example output

``` [1] 2 1 7 7 6 5 5 4 3 2 7 5 5 3 2
```

decido documentation built on July 2, 2020, 3:11 a.m.