triangulate method

List<int> triangulate()

Implementation

List<int> triangulate() {
  var i = 0;
  var al = points.length;
  final result = <int>[];
  final available = <int>[];

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

  while (al > 3) {
    final i0 = available[(i + 0) % al];
    final i1 = available[(i + 1) % al];
    final i2 = available[(i + 2) % al];

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

    var earFound = false;

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

      for (var j = 0; j < al; j++) {
        final 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);
}