simplifyPolygon static method

List<Offset> simplifyPolygon(List<Offset> contour, double epsilon)

Simplifies a contour using the Douglas-Peucker algorithm.

Reduces the number of points in a polyline while preserving shape. epsilon controls approximation accuracy (higher = more simplification).

Inspired by OpenCV's cv::approxPolyDP().

Implementation

static List<Offset> simplifyPolygon(List<Offset> contour, double epsilon) {
  if (contour.length <= 2) return List.from(contour);

  // Find the point with maximum perpendicular distance from the line
  // connecting the first and last points
  double maxDist = 0;
  int maxIdx = 0;
  final first = contour.first;
  final last = contour.last;

  for (int i = 1; i < contour.length - 1; i++) {
    final dist = _perpendicularDistance(contour[i], first, last);
    if (dist > maxDist) {
      maxDist = dist;
      maxIdx = i;
    }
  }

  if (maxDist > epsilon) {
    // Recursively simplify both halves
    final left = simplifyPolygon(contour.sublist(0, maxIdx + 1), epsilon);
    final right = simplifyPolygon(contour.sublist(maxIdx), epsilon);

    // Concatenate (removing duplicate junction point)
    return [...left.sublist(0, left.length - 1), ...right];
  }

  // All points are within epsilon — return just endpoints
  return [first, last];
}