polygonHull function

List<List<num>>? polygonHull(List<List<num>> points)

Returns the convex hull of the specified points using Andrew’s monotone chain algorithm.

polygonHull(points) // [[3.0872864263338777, -1.300100095019402], [1.6559368816733773, -2.5092525689499605], …]

The returned hull is represented as an list containing a subset of the input points arranged in counterclockwise order. Returns null if points has fewer than three elements.

Implementation

List<List<num>>? polygonHull(List<List<num>> points) {
  var n = points.length;
  if ((n = points.length) < 3) return null;

  int i;
  var sortedPoints = List.filled(n, <num>[]),
      flippedPoints = List.filled(n, <num>[]);

  for (i = 0; i < n; ++i) {
    sortedPoints[i] = [points[i][0], points[i][1], i];
  }
  sortedPoints.sort(_lexicographicOrder);
  for (i = 0; i < n; ++i) {
    flippedPoints[i] = [sortedPoints[i][0], -sortedPoints[i][1]];
  }

  var upperIndexes = _computeUpperHullIndexes(sortedPoints),
      lowerIndexes = _computeUpperHullIndexes(flippedPoints);

  // Construct the hull polygon, removing possible duplicate endpoints.
  var skipLeft = lowerIndexes[0] == upperIndexes[0] ? 1 : 0,
      skipRight = lowerIndexes[lowerIndexes.length - 1] ==
              upperIndexes[upperIndexes.length - 1]
          ? 1
          : 0,
      hull = <List<num>>[];

  // Add upper hull in right-to-l order.
  // Then add lower hull in left-to-right order.
  for (i = upperIndexes.length - 1; i >= 0; --i) {
    hull.add(points[sortedPoints[upperIndexes[i]][2] as int]);
  }
  for (i = skipLeft; i < lowerIndexes.length - skipRight; ++i) {
    hull.add(points[sortedPoints[lowerIndexes[i]][2] as int]);
  }

  return hull;
}