method triangulate

Source

List<int> triangulate() {

  int i = 0;
  int al = points.length;
  List<int> result = new List<int>();
  List<int> available = new List<int>();

  for(int p = 0; p < points.length; p++) {
    available.add(p);
  }

  while(al > 3) {

    int i0 = available[(i + 0) % al];
    int i1 = available[(i + 1) % al];
    int i2 = available[(i + 2) % al];

    num ax = points[i0].x;
    num ay = points[i0].y;
    num bx = points[i1].x;
    num by = points[i1].y;
    num cx = points[i2].x;
    num cy = points[i2].y;

    bool earFound = false;

    if(_convex(ax, ay, bx, by, cx, cy)) {
      earFound = true;

      for(int j = 0; j < al; j++) {
        int vi = available[j];
        if(vi == i0 || vi == i1 || vi == i2) continue;
        if(_pointInTriangle(points[vi].x, points[vi].y, ax, ay, bx, by, cx, cy)) {
          earFound = false;
          break;
        }
      }
    }

    if(earFound) {
      result.add(i0);
      result.add(i1);
      result.add(i2);
      available.removeAt((i + 1) % al);
      al--;
      i = 0;
    } else if(i++ > 3 * al) {
      break; // no convex angles :(
    }
  }

  result.add(available[0]);
  result.add(available[1]);
  result.add(available[2]);

  // http://dartbug.com/10489
  return result.toList(growable: false);
}