# High Quality Constrained Triangulation for Simple Features

#### Michael D. Sumner

#### 2024-01-09

## Example

This is a basic example which shows you how to decompose a MULTIPOLYGON `sf` data frame object into a GEOMETRYCOLLECTION `sf` data frame object made of triangles:

    library(sf)

    ## Linking to GEOS 3.10.2, GDAL 3.4.3, PROJ 8.2.0; sf_use_s2() is TRUE

    library(sfdct)
    nc <- read_sf(system.file("shape/nc.shp", package="sf"), quiet = TRUE)
    nc_triangles <- ct_triangulate(nc)

    plot(st_geometry(nc_triangles),   col = viridisLite::viridis(nrow(nc_triangles)))

We can use the underlying `RTriangle::triangulate` arguments to hone the triangles we get.

    i_feature <- 25
    nc1 <- nc[c(i_feature, unlist(st_touches(nc[i_feature, ], nc))), ]
    plot(st_geometry(nc1),col = viridisLite::viridis(nrow(nc1)))

    ## subvert st_area because we really don't want m^2
    st_crs(nc1) <- NA
    areas <- st_area(nc1)
    st_crs(nc1) <- st_crs(nc)
    nc1_triangles <- ct_triangulate(nc1, a = min(areas)/5)
    bcol <- viridisLite::viridis(nrow(nc1_triangles))
    plot(st_geometry(nc1_triangles), col = NA, border = bcol)

    nc2_triangles <- ct_triangulate(nc1, a = min(st_area(st_set_crs(nc1, NA)))/25)
    plot(st_geometry(nc2_triangles), col = NA, border = bcol)

Get a grouped triangulated set from a MULTIPOINT. Note how these aren’t constrained by the edges of the input polygons (because we threw those away!) but these are controlled to have a smaller maximum area.

Area is calculated in the native coordinates, assuming “planar coordinates”, with no respect to the real world.

    ## manual cast to MULTIPOINT originally required
    #st_geometry(nc1) <- st_sfc(lapply(unlist(unlist(st_geometry(nc1), recursive = FALSE), recursive = FALSE), st_multipoint), crs = st_crs(nc1))
    mp_nc1 <- st_cast(nc1, "MULTIPOINT")
    mtriangs <- ct_triangulate(nc1, a = 0.0005)
    plot(st_geometry(mtriangs), col = viridisLite::viridis(nrow(mtriangs)), border = "#00000033")

    plot(nc[4, ]$geometry)
    ## q, minimum angle
    ## D, Delaunay criterion is met
    plot(ct_triangulate(nc[4, ]$geometry, q = 35, D = TRUE), add = TRUE, col = "transparent")

## Geometry collection is in development

POLYGON triangles in GEOMETRYCOLLECTION will be re-triangulated. All vertices in the GC will be included, as well as all edges of all component geometries, but each component is triangulated individually, not with reference to the entire set.

## Chaining together operations

We can use piping to chain things together.

    data("map_world", package= "sfdct")
    library(dplyr)

    ##
    ## Attaching package: 'dplyr'

    ## The following objects are masked from 'package:stats':
    ##
    ##     filter, lag

    ## The following objects are masked from 'package:base':
    ##
    ##     intersect, setdiff, setequal, union

    g <-  map_world %>% dplyr::filter(startsWith(ID, "Indonesia")) %>% ct_triangulate() %>% st_geometry()

    ## old-style crs object detected; please recreate object with a recent sf::st_crs()

    plot(g, col = "aliceblue", main = "")

    nc_triangles[1:2, c(1, 5)] %>% st_transform("+proj=laea") %>% ct_triangulate(a = 2e6) %>% plot()

## Holes better work (or else)

    data("antarctica")
    plot(antarctica[0])

    a <- ct_triangulate(st_difference(antarctica[1], antarctica[2, ]), a = 5e10)

    ## Warning: attribute variables are assumed to be spatially constant throughout
    ## all geometries

    plot(a[0], col = "firebrick")

The output of `ct_triangulate` can be the input to another call to it.

    m <- map_world %>% dplyr::filter(startsWith(ID, "Papua New Guinea"))

    ## old-style crs object detected; please recreate object with a recent sf::st_crs()

    plotme <- function(x) {plot(st_geometry(x), col = "aliceblue"); x}
    m %>% ct_triangulate(a = 0.2, D = TRUE) %>% plotme()

    ## Simple feature collection with 1 feature and 1 field
    ## Geometry type: GEOMETRYCOLLECTION
    ## Dimension:     XY
    ## Bounding box:  xmin: 140.8623 ymin: -11.63057 xmax: 155.9576 ymax: -1.353223
    ## Geodetic CRS:  WGS 84
    ##                         geometry               ID
    ## 1 GEOMETRYCOLLECTION (POLYGON... Papua New Guinea