earClipping function

List<List<List<double>>> earClipping(List<List<double>> polygon)

Triangulates a polygon using the Ear Clipping method.

This function takes a convex or concave polygon and returns a list of triangles that fully cover the area of the original polygon.

The polygon is defined by a list of points. Each point is represented as a list of two doubles (x, y). The polygon is assumed to be simple (does not intersect itself or have holes).

If the input polygon is already a triangle, the function will return a list containing the original polygon.

Throws ArgumentError if the polygon has less than 3 points.

Example:

var polygon = [
  [0.0, 0.0],
  [1.0, 0.0],
  [1.0, 1.0],
  [0.0, 1.0]
];
var result = earClipping(polygon);
print(result);

polygon: A list of points representing the polygon. Each point is represented as a list of two doubles (x, y).

Returns a list of triangles that represent the triangulation of the polygon. Each triangle is represented as a list of three points. Each point is represented as a list of two doubles (x, y).

Implementation

List<List<List<double>>> earClipping(List<List<double>> polygon) {
  // Check if the polygon is valid.
  if (polygon.length < 3) {
    throw ArgumentError("A polygon must have at least 3 points.");
  }

  List<List<List<double>>> result = [];

  // Create a copy of the points to avoid modifying the original polygon.
  List<List<double>> points = List.from(polygon);

  while (points.length > 3) {
    for (int i = 0; i < points.length; i++) {
      int prev = (i - 1 + points.length) % points.length;
      int next = (i + 1) % points.length;

      var a = points[prev];
      var b = points[i];
      var c = points[next];

      // Check if angle ABC is convex.
      double crossProduct =
          (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
      if (crossProduct < 0) continue;

      // Check if any point lies inside triangle ABC.
      bool isEar = true;
      for (var p in points) {
        if (p == a || p == b || p == c) continue;
        double areaABC = ((a[0] * (b[1] - c[1]) +
                    b[0] * (c[1] - a[1]) +
                    c[0] * (a[1] - b[1]))
                .abs()) /
            2;
        double areaABP = ((a[0] * (b[1] - p[1]) +
                    b[0] * (p[1] - a[1]) +
                    p[0] * (a[1] - b[1]))
                .abs()) /
            2;
        double areaBCP = ((b[0] * (c[1] - p[1]) +
                    c[0] * (p[1] - b[1]) +
                    p[0] * (b[1] - c[1]))
                .abs()) /
            2;
        double areaCAP = ((c[0] * (a[1] - p[1]) +
                    a[0] * (p[1] - c[1]) +
                    p[0] * (c[1] - a[1]))
                .abs()) /
            2;
        if (areaABC == areaABP + areaBCP + areaCAP) {
          isEar = false;
          break;
        }
      }

      if (isEar) {
        // Remove the ear from the polygon.
        points.removeAt(i);

        // Add the ear to the result.
        result.add([a, b, c]);
        break;
      }
    }
  }

  // Add the remaining triangle to the result.
  if (points.length == 3) {
    result.add(points);
  }

  return result;
}