triangulate.js

/**
This code is a quick port of code written in C++ which was submitted to 
flipcode.com by John W. Ratcliff  // July 22, 2000 
See original code and more information here:
http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

ported to actionscript by Zevan Rosser
www.actionsnippet.com
*/

var EPSILON = 0.0000000001;

function process(contour) {
  var result = [],
      n = contour.length,
      verts = [],
      v,
      nv = n,
      m,
      count = 2 * nv;  /* error detection */

  if (n < 3) {
    return null;
  }

  /* we want a counter-clockwise polygon in verts */

  if (0.0 < area(contour)) {
    for (v = 0; v < n; v++) {
      verts[v] = v;
    }
  } else {
    for (v = 0; v < n; v++) {
      verts[v] = (n - 1) - v;
    }
  }

  /*  remove nv-2 vertsertices, creating 1 triangle every time */
  for (m = 0, v = nv - 1; nv > 2;) {
    /* if we loop, it is probably a non-simple polygon */
    if (0 >= (count--)) {
      //** Triangulate: ERROR - probable bad polygon!
      // console.log("bad poly");
      return null;
    }

    /* three consecutive vertices in current polygon, <u,v,w> */
    var u = v;
    if (nv <= u) {
      u = 0; /* previous */
    }

    v = u + 1;
    if (nv <= v) {
      v = 0; /* new v */
    }

    var w = v + 1;
    if (nv <= w) {
      w = 0; /* next */
    }

    if (snip(contour, u, v, w, nv, verts)) {
      var a, b, c, s, t;

      /* true names of the vertices */
      a = verts[u];
      b = verts[v];
      c = verts[w];

      /* output Triangle */
      result.push(contour[a]);
      result.push(contour[b]);
      result.push(contour[c]);

      m++;

      /* remove v from remaining polygon */
      for (s = v, t = v + 1; t < nv; s++, t++) {
        verts[s] = verts[t];
      }

      nv--;

      /* resest error detection counter */
      count = 2 * nv;
    }
  }

  return result;
}

// calculate area of the contour polygon
function area(contour) {
  var n = contour.length,
      a = 0.0;

  for (var p = n - 1, q = 0; q < n; p = q++) {
    a += contour[p].x * contour[q].y - contour[q].x * contour[p].y;
  }

  return a * 0.5;
}

// see if p is inside triangle abc
function insideTriangle(ax, ay, bx, by, cx, cy, px, py) {
  var aX, aY, bX, bY,
      cX, cY, apx, apy,
      bpx, bpy, cpx, cpy,
      cCROSSap, bCROSScp, aCROSSbp;

  aX = cx - bx;
  aY = cy - by;
  bX = ax - cx;
  bY = ay - cy;
  cX = bx - ax;
  cY = by - ay;
  apx = px - ax;
  apy = py - ay;
  bpx = px - bx;
  bpy = py - by;
  cpx = px - cx;
  cpy = py - cy;

  aCROSSbp = aX * bpy - aY * bpx;
  cCROSSap = cX * apy - cY * apx;
  bCROSScp = bX * cpy - bY * cpx;

  return ((aCROSSbp >= 0.0) && (bCROSScp >= 0.0) && (cCROSSap >= 0.0));
}

function snip(contour, u, v, w, n, verts) {
  var p,
      ax, ay, bx, by,
      cx, cy, px, py;

  ax = contour[verts[u]].x;
  ay = contour[verts[u]].y;

  bx = contour[verts[v]].x;
  by = contour[verts[v]].y;

  cx = contour[verts[w]].x;
  cy = contour[verts[w]].y;

  if (EPSILON > (((bx - ax) * (cy - ay)) - ((by - ay) * (cx - ax)))) {
    return false;
  }

  for (p = 0; p < n; p++) {
    if ((p == u) || (p == v) || (p == w)) {
      continue;
    }

    px = contour[verts[p]].x
    py = contour[verts[p]].y

    if (insideTriangle(ax, ay, bx, by, cx, cy, px, py)) {
      return false;
    }
  }

  return true;
}