convexHull static method

List<Offset> convexHull(List<Offset> points)

Computes the convex hull of a set of points using the Graham scan algorithm.

Returns the convex hull vertices in counter-clockwise order.

Implementation

static List<Offset> convexHull(List<Offset> points) {
  if (points.length <= 3) return List.from(points);

  // Find the lowest point (ties broken by leftmost)
  int lowestIdx = 0;
  for (int i = 1; i < points.length; i++) {
    if (points[i].dy > points[lowestIdx].dy ||
        (points[i].dy == points[lowestIdx].dy &&
            points[i].dx < points[lowestIdx].dx)) {
      lowestIdx = i;
    }
  }

  // Swap lowest point to front
  final sorted = List<Offset>.from(points);
  final pivot = sorted[lowestIdx];
  sorted[lowestIdx] = sorted[0];
  sorted[0] = pivot;

  // Sort by polar angle relative to pivot
  sorted.sort((a, b) {
    if (a == pivot) return -1;
    if (b == pivot) return 1;
    final cross = _crossProduct(pivot, a, b);
    if (cross == 0) {
      // Collinear: sort by distance
      return (a - pivot).distanceSquared.compareTo((b - pivot).distanceSquared);
    }
    return cross > 0 ? -1 : 1;
  });

  // Graham scan
  final hull = <Offset>[];
  for (final p in sorted) {
    while (hull.length >= 2 &&
        _crossProduct(hull[hull.length - 2], hull.last, p) <= 0) {
      hull.removeLast();
    }
    hull.add(p);
  }

  return hull;
}