triangulate method

Int16List triangulate(Float32List verticesArray)

Implementation

Int16List triangulate(Float32List verticesArray) {
  final Float32List vertices = verticesArray;
  int vertexCount = verticesArray.length >> 1;

  final List<int> indices = indicesArray..length = 0;
  for (int i = 0; i < vertexCount; i++) {
    indices[i] = i;
  }

  final List<bool> isConcave = isConcaveArray..length = 0;
  final int n = vertexCount;
  for (int i = 0; i < n; ++i) {
    isConcave[i] = Triangulator._isConcave(
        i, vertexCount, vertices, Int16List.fromList(indices));
  }

  final List<int> triangles = this.triangles..length = 0;

  while (vertexCount > 3) {
    // Find ear tip.
    int previous = vertexCount - 1, i = 0, next = 1;
    for (;;) {
      outer:
      if (!isConcave[i]) {
        final int p1 = indices[previous] << 1,
            p2 = indices[i] << 1,
            p3 = indices[next] << 1;
        final double p1x = vertices[p1], p1y = vertices[p1 + 1];
        final double p2x = vertices[p2], p2y = vertices[p2 + 1];
        final double p3x = vertices[p3], p3y = vertices[p3 + 1];
        for (int ii = (next + 1) % vertexCount;
            ii != previous;
            ii = (ii + 1) % vertexCount) {
          if (!isConcave[ii]) continue;
          final int v = indices[ii] << 1;
          final double vx = vertices[v], vy = vertices[v + 1];
          if (Triangulator.positiveArea(p3x, p3y, p1x, p1y, vx, vy)) {
            if (Triangulator.positiveArea(p1x, p1y, p2x, p2y, vx, vy)) {
              if (Triangulator.positiveArea(p2x, p2y, p3x, p3y, vx, vy)) {
                break outer;
              }
            }
          }
        }
        break;
      }

      if (next == 0) {
        do {
          if (!isConcave[i]) break;
          i--;
        } while (i > 0);
        break;
      }

      previous = i;
      i = next;
      next = (next + 1) % vertexCount;
    }

    // Cut ear tip.
    triangles
      ..add(indices[(vertexCount + i - 1) % vertexCount])
      ..add(indices[i])
      ..add(indices[(i + 1) % vertexCount]);
    indices.removeAt(i);
    isConcave.removeAt(i);
    vertexCount--;

    final int previousIndex = (vertexCount + i - 1) % vertexCount;
    final int nextIndex = i == vertexCount ? 0 : i;
    isConcave[previousIndex] = Triangulator._isConcave(
        previousIndex, vertexCount, vertices, Int16List.fromList(indices));
    isConcave[nextIndex] = Triangulator._isConcave(
        nextIndex, vertexCount, vertices, Int16List.fromList(indices));
  }

  if (vertexCount == 3) {
    triangles
      ..add(indices[2])
      ..add(indices[0])
      ..add(indices[1]);
  }

  return Int16List.fromList(triangles);
}