Triangulate function

List<int>? Triangulate(List<Vector2> contour)

Implementation

List<int>? Triangulate(List<VM.Vector2> contour) {
  assert(contour.length >= 3);
  List<int> triangles = <int>[];

  List<int> available = <int>[];
  for (int p = 0; p < contour.length; p++) {
    available.add(p);
  }

  do {
    final int al = available.length;
    // Note, for simple polygons we should not really iterate much here.
    bool foundTriangle = false;
    for (int i = 0; i < al; ++i) {
      int i0 = i;
      int i1 = i + 1;
      if (i1 >= al) i1 -= al;
      int i2 = i + 2;
      if (i2 >= al) i2 -= al;

      i0 = available[i0];
      i1 = available[i1];
      i2 = available[i2];
      if (_isGoodEar(contour, available, i0, i1, i2)) {
        //print("GOOD ${i0}  ${i1}  ${i2}");
        triangles.add(i0);
        triangles.add(i1);
        triangles.add(i2);
        // discard middle point
        int eliminate = i + 1;
        if (eliminate >= al) eliminate -= al;
        available.removeAt(eliminate);
        foundTriangle = true;
        break;
      }
    }
    if (!foundTriangle) {
      print("ERROR: Could not triangulate");
      return null;
    }
  } while (available.length >= 3);

  return triangles;
}