R/triangulate.polygon.R

In eggs: Distances and areas on the surface of an egg

triangulate.polygon = function(p) {
  # Uses the ear-trimming algorithm to triangulate a polygon
  clockwise = is.clockwise(p)
  t = c()
  nv = nrow(p)
  vid = 1:nv
  while(nv > 3) {
    for(i in 2:(nv+1)) {
      v = c(vid[nv], vid, vid[1])
      BAx = p[v[i-1],1] - p[v[i],1]
      BAy = p[v[i-1],2] - p[v[i],2]
      BCx = p[v[i+1],1] - p[v[i],1]
      BCy = p[v[i+1],2] - p[v[i],2]
      angle = BAx*BCy - BAy*BCx
      if((angle < 0 && !clockwise) || (angle > 0 && clockwise)) {
        t = rbind(t, c(v[i-1],v[i],v[i+1]))
        vid = vid[-which(vid==v[i])]
        nv = nv - 1
        break
      }
    }
  }
  t = rbind(t, c(vid[1],vid[2],vid[3]))
  return (t)
}