findBestQuadrilateral static method

DocumentCorners? findBestQuadrilateral(List<Offset> contour, int imageWidth, int imageHeight, { double minAreaRatio = 0.1, double maxAreaRatio = 0.95, })

Finds the best quadrilateral approximation from a contour.

Uses iterative Douglas-Peucker simplification with decreasing epsilon until a 4-vertex polygon is found, then validates convexity and area.

Returns null if no valid quadrilateral can be extracted.

Implementation

static DocumentCorners? findBestQuadrilateral(
  List<Offset> contour,
  int imageWidth,
  int imageHeight, {
  double minAreaRatio = 0.1,
  double maxAreaRatio = 0.95,
}) {
  if (contour.length < 4) return null;

  final totalArea = (imageWidth * imageHeight).toDouble();
  final minArea = totalArea * minAreaRatio;
  final maxArea = totalArea * maxAreaRatio;

  // Compute contour perimeter for epsilon scaling
  double perimeter = 0;
  for (int i = 0; i < contour.length; i++) {
    final next = (i + 1) % contour.length;
    perimeter += (contour[next] - contour[i]).distance;
  }

  // Try progressively tighter epsilon values to find a 4-sided polygon
  for (double epsilonFactor = 0.04;
      epsilonFactor >= 0.01;
      epsilonFactor -= 0.005) {
    final epsilon = perimeter * epsilonFactor;
    final simplified = simplifyPolygon(contour, epsilon);

    if (simplified.length == 4) {
      final corners = _sortCorners(simplified);
      if (corners == null) continue;

      final area = corners.area;
      if (area >= minArea && area <= maxArea && corners.isValidQuad) {
        return corners;
      }
    }
  }

  // Fallback: try convex hull → quad approximation
  final hull = convexHull(contour);
  if (hull.length >= 4) {
    final quadPoints = _approximateQuadFromHull(hull);
    if (quadPoints != null) {
      final corners = _sortCorners(quadPoints);
      if (corners != null) {
        final area = corners.area;
        if (area >= minArea && area <= maxArea && corners.isValidQuad) {
          return corners;
        }
      }
    }
  }

  return null;
}