Triangulation of self-intersecting polyons

self-intersecting-polygon-triangulation.R

  library(ggplot2)

  df <- data.frame(
    x = c(0, 1, 0, 1),
    y = c(0, 0, 1, 1)
  )

  p <- ggplot(df, aes(x, y)) +
    geom_polygon() +
    geom_point(colour = 'tomato', size = 3) +
    theme_bw()

  p



  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # the decido earcut triangulation. This is a *DIFFERENT* triangulation 
  # to the one done internally in 'ggplot2'.
  # i.e. it doesn't actually take into account that the polygon is 
  # self-intersecting, and there does not seem to be any application of 
  #  a 'winding' or 'even-ordd' fill rule.
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  idx <- decido::earcut(df[,c('x', 'y')])

  df2 <- df[idx, ]
  N <- nrow(df2)/3
  df2$idx <- rep(seq_len(N), each = 3)

  ggplot(df2, aes(x, y)) +
    geom_polygon(aes(group = idx)) +
    geom_point(colour = 'tomato', size = 3) +
    theme(legend.position = 'none') +
    theme_bw()

  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # RTriangle::Triangulate
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  library(RTriangle)
  v1 <- seq_len(nrow(df))
  v2 <- c(seq(2, nrow(df)), 1)
  S = matrix(c(v1, v2), ncol = 2, nrow = nrow(df))

  ps <- RTriangle::pslg(P = as.matrix(df), S = S)
  tt <- RTriangle::triangulate(ps)
  plot(tt)

  idx <- as.vector(t(tt$T))
  df3 <- as.data.frame(tt$P)
  colnames(df3) <- c('x', 'y')
  df3 <- df3[idx,]
  N <- nrow(df3)/3
  df3$idx <- rep(seq_len(N), each = 3)

  ggplot(df3) +
    geom_polygon(aes(x, y, group = idx, fill = as.factor(idx))) +
    theme_bw() +
    theme(legend.position = 'none')

I understand ;)

RTriangle needs the specification of S(egments) in the pslg

df <- data.frame(
  x = c(0, 1, 0, 1),
  y = c(0, 0, 1, 1)
)

ps <- RTriangle::pslg(as.matrix(df[c("x", "y")]), 
                      S = cbind(1:nrow(df), 
                                c(2:nrow(df), 1))) ## won't work for multiple polygons (hence silicate::PATH0)
plot(ps)
## *constrained triangles*, constrained by the input-edges S
plot(RTriangle::triangulate(ps))

## we can control mesh properties
plot(RTriangle::triangulate(ps, a = 0.1))


## we can control mesh properties
plot(RTriangle::triangulate(ps, a = 0.01, D = TRUE))