simplify static method

List<Point<double>> simplify(List<Point<double>> poly, double tolerance)

Simplifies the given poly (polyline or polygon) using the Douglas-Peucker decimation algorithm. Increasing the tolerance will result in fewer points in the simplified polyline or polygon.

When providing a polygon as input, the first and last point of the list MUST have the same x and y (i.e., the polygon must be closed). If the input polygon is not closed, the resulting polygon may not be fully simplified.

The time complexity of Douglas-Peucker is O(n²), so take care that you do not call this algorithm too frequently in your code.

Returns a simplified poly produced by the Douglas-Peucker algorithm.

Note: this method does not mutate the input list.

Implementation

static List<Point<double>> simplify(
    List<Point<double>> poly, double tolerance) {
  final n = poly.length;
  if (n < 1) {
    throw ArgumentError('Polyline must have at least 1 point');
  }
  if (tolerance <= 0) {
    throw ArgumentError('Tolerance must be greater than zero');
  }

  final closedPolygon = isClosedPolygon(poly);

  // Work on a copy to avoid mutating the caller's list.
  final working = List<Point<double>>.of(poly);

  if (closedPolygon) {
    // Add a small offset to the last point for Douglas-Peucker on polygons
    // (see android-maps-utils #201).
    final lastPoint = working[working.length - 1];
    const offset = 0.00000000001;
    working[working.length - 1] =
        Point(lastPoint.x + offset, lastPoint.y + offset);
  }

  // Douglas-Peucker, iterative (stack-based) to avoid deep recursion.
  int idx = 0;
  int maxIdx = 0;
  final stack = Stack<List<int>>();
  final dists = List<double>.filled(n, 0.0);
  dists[0] = 1;
  dists[n - 1] = 1;
  double maxDist = 0.0;
  double dist = 0.0;
  List<int> current = [];

  if (n > 2) {
    stack.push([0, n - 1]);
    while (stack.isNotEmpty) {
      current = stack.pop();
      maxDist = 0;
      for (idx = current[0] + 1; idx < current[1]; ++idx) {
        dist = distanceToLine(
            working[idx], working[current[0]], working[current[1]]);
        if (dist > maxDist) {
          maxDist = dist;
          maxIdx = idx;
        }
      }
      if (maxDist > tolerance) {
        dists[maxIdx] = maxDist;
        stack.push([current[0], maxIdx]);
        stack.push([maxIdx, current[1]]);
      }
    }
  }

  // If the polygon was closed, restore the exact original last point.
  if (closedPolygon) {
    working[working.length - 1] = poly[poly.length - 1];
  }

  // Generate the simplified line.
  final simplifiedLine = <Point<double>>[];
  for (int i = 0; i < n; i++) {
    if (dists[i] != 0) {
      simplifiedLine.add(working[i]);
    }
  }
  return simplifiedLine;
}