---
title: "Getting started with cdtr"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{Getting started with cdtr}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r, include = FALSE}
knitr::opts_chunk$set(collapse = TRUE, comment = "#>", fig.width = 6,
                      fig.height = 3.2, dpi = 100)
```

cdtr triangulates a planar straight line graph (PSLG): vertices, and
constraint segments given as pairs of vertex indices. It binds the
header-only [CDT](https://github.com/artem-ogre/CDT) C++ library, and the
result is a plain list of matrices and data frames.

```{r setup}
library(cdtr)
```

## Input and output

A square with a square hole is two closed rings. Vertices are `x` and `y`,
and the segments are `s0` and `s1`, the 1-based start and end vertex of each.

```{r input}
x <- c(0, 1, 1, 0, 0.25, 0.75, 0.75, 0.25)
y <- c(0, 0, 1, 1, 0.25, 0.25, 0.75, 0.75)
s0 <- 1:8
s1 <- c(2, 3, 4, 1, 6, 7, 8, 5)

r <- cdt_triangulate(x, y, s0, s1)
names(r)
```

The main components are `P` (vertices, a two-column matrix), `T` (triangles,
1-based indices into `P`, wound counter-clockwise), `S` (the fixed edges) and
`depth`. An `RTriangle::pslg()` can be passed to `cdt_pslg()` instead.

A small plotting helper is used through this vignette.

```{r helper}
plot_mesh <- function(m, ...) {
  e <- cdt_edges(m)
  plot(m$P, asp = 1, axes = FALSE, xlab = "", ylab = "", pch = ".", ...)
  segments(m$P[e[, 1], 1], m$P[e[, 1], 2], m$P[e[, 2], 1], m$P[e[, 2], 2],
           col = "grey50")
  segments(m$P[m$S[, 1], 1], m$P[m$S[, 1], 2], m$P[m$S[, 2], 1], m$P[m$S[, 2], 2],
           lwd = 2)
}
op <- par(mar = c(0.5, 0.5, 0.5, 0.5))
plot_mesh(r)
par(op)
```

## Depth: where a triangle sits

`depth` counts the constraint boundaries crossed travelling in from outside.
Outside the outer ring is 0, inside it is 1, and the hole is 2. Nested rings
alternate odd (inside) and even (hole). It is found from the mesh alone, with
no point-in-polygon test.

```{r depth}
table(r$depth)
```

`erase` controls what is dropped. The default `"outer"` removes triangles
outside the outermost boundary (as Triangle's `-p` does), so **hole triangles
are kept** and have even depth. `"holes"` also removes the even depths, which
is what you want to get a polygon with its holes cut out. `"hull"` keeps the
whole convex hull.

```{r erase}
sapply(c("hull", "outer", "holes"), function(e) {
  nrow(cdt_triangulate(x, y, s0, s1, erase = e)$T)
})
```

Holes can also be given as points, as in an `RTriangle::pslg()`'s `H`. The
region around each point that is bounded by segments is erased, which is useful
when you know a point inside a hole but not the depth.

```{r holes}
rh <- cdt_triangulate(x, y, s0, s1, holes = cbind(0.5, 0.5))
table(rh$depth)
```

## Refinement

Ruppert refinement adds Steiner vertices to meet a maximum triangle area or a
minimum angle.

```{r refine}
r2 <- cdt_triangulate(x, y, s0, s1, max_area = 0.01, min_angle = 25,
                      erase = "holes")
table(r2$origin)
op <- par(mar = c(0.5, 0.5, 0.5, 0.5))
plot_mesh(r2)
par(op)
```

`origin` says where each vertex came from: `"input"`, `"crossing"` (added
where constraints cross) or `"steiner"` (added by refinement).

Refinement cannot always reach its targets, for example where two segments
meet at a sharp angle. Instead of stopping silently, the result reports what
was left undone in `unrefined`, and `min_edge_length` is the floor below which
an edge is not split. By default it is derived from the input; use
`min_edge_length = 0` to never give up.

```{r unrefined}
r2$min_edge_length
r2$unrefined
```

## Crossing constraints

Segments that cross are split at the crossing by default
(`intersect = "resolve"`), and the new vertex has origin `"crossing"`.

```{r cross}
xc <- c(0, 1, 0, 1)
yc <- c(0, 1, 1, 0)
rc <- cdt_triangulate(xc, yc, c(1, 3), c(2, 4))
rc$origin
```

`intersect = "error"` fails instead, and `"ignore"` skips the check.

## Which input made each edge

With `edge_sources = TRUE` the result has a data frame with a row for every
input segment that covers each fixed edge, tracked through crossings, splits
and refinement. This allows regions to be labelled by *which inputs* cover
them, which `depth` cannot do. Here two overlapping squares are
triangulated together.

```{r sources}
xs <- c(0, 2, 2, 0, 1, 3, 3, 1)
ys <- c(0, 0, 2, 2, 1, 1, 3, 3)
rs <- cdt_triangulate(xs, ys, 1:8, c(2, 3, 4, 1, 6, 7, 8, 5),
                      edge_sources = TRUE)
head(rs$edge_sources)
```

`segment` is the position of the input segment, `edge` the row of `S`, and
`forward` whether they run the same way. An edge shared by k input segments,
duplicates included, has k rows.

## Locating and interpolating

`cdt_locate()` returns the triangle containing each query point, using exact
orientation tests so a point on a shared edge is never lost between triangles.
A point on an edge goes to the lowest triangle index, and a point outside the
mesh is `NA`. With a triangle-to-feature table this is point-in-polygon for
many points.

```{r locate}
q <- cbind(c(0.1, 0.5, 0.9, 2), c(0.1, 0.5, 0.9, 2))
cdt_locate(r2$P, r2$T, q[, 1], q[, 2])
```

Values carried on vertices are interpolated linearly (barycentrically) with
`cdt_interpolate()`. `cdt_triangulate_attr()` does this for you, giving
Steiner vertices values from the unrefined triangulation.

```{r attr}
ra <- cdt_triangulate_attr(x, y, s0, s1, PA = cbind(z = 10 * x),
                           max_area = 0.02, erase = "holes")
all.equal(ra$PA[, "z"], 10 * ra$P[, 1])
```

See `vignette("wkpool", package = "cdtr")` for using cdtr with polygons from
any source.
