## Triangulate polygon

### Description

Function `triangulate` decomposes a simple polygon (optionally having holes) into contiguous triangles.

### Usage

```triangulate(outer.poly, holes)
```

### Arguments

 `outer.poly` a list with two component vectors `x` and `y` giving vertex coordinates of the polygon or a vector `(xmin,ymin,xmax,ymax)` giving coordinates (ximn,ymin) and (xmax,ymax) of the origin and the opposite corner of a rectangle sampling window (see `swin`). `holes` (optional) a list (or a list of list) with two component vectors `x` and `y` giving vertices coordinates of inner polygon(s) delineating hole(s) within the `outer.poly`.

### Details

In argument `outer.poly`, the vertices must be listed following boundary of the polygon without any repetition (i.e. do not repeat the first vertex). Argument `holes` may be a list of vertices coordinates of a single hole (i.e. with x and y component vectors) or a list of list for multiple holes, where each `holes[[i]]` is a list with x and y component vectors. Holes' vertices must all be inside the `outer.poly` boundary (vertices on the boundary are considered outside). Multiple holes do not overlap each others.

### Value

A list of 6 variables, suitable for using in `swin` and `spp`, and giving the vertices coordinates (ax,ay,bx,by,cx,cy) of the triangles that pave the polygon. For a polygon with t holes totaling n vertices (outer contour + holes), the number of triangles produced is (n-2)+2t, with n<200 in this version of the program.

### References

Goreaud, F. and P?Pelissier, R. 1999. On explicit formula of edge effect correction for Ripley's K-function. Journal of Vegetation Science, 10:433-438.

Narkhede, A. & Manocha, D. 1995. Fast polygon triangulation based on Seidel's algorithm. Pp 394-397 In A.W. Paeth (Ed.) Graphics Gems V. Academic Press. http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html.

`spp`, `swin`

### Examples

```  data(BPoirier)
BP <- BPoirier
plot(BP\$poly1\$x, BP\$poly1\$y)

## Not run: a single polygon triangulation
tri1 <- triangulate(BP\$poly1)
plot(swin(BP\$rect, tri1))

## Not run: a single polygon with a hole
tri2 <- triangulate(c(-10,-10,120,100), BP\$poly1)
plot(swin(c(-10,-10,120,100), tri2))

## Not run: the same with narrower outer polygon
tri3 <- lapply(BP\$poly2,triangulate)
tri3<-do.call(rbind,tri3)
xr<-range(tri3\$ax,tri3\$bx,tri3\$cx)
yr<-range(tri3\$ay,tri3\$by,tri3\$cy)
plot(swin(c(xr,yr,xr,yr), tri3))
```