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 the 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^2), so take care that you do not call this algorithm too frequently in your code.

poly polyline or polygon to be simplified. Polygon should be closed (i.e., first and last points should have the same x and y).

tolerance in meters. Increasing the tolerance will result in fewer points in the simplified poly.

Returns a simplified poly produced by the Douglas-Peucker algorithm

Implementation

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

  final closedPolygon = isClosedPolygon(poly);
  Point<double>? lastPoint = null;

  // Check if the provided poly is a closed polygon
  if (closedPolygon) {
    // Add a small offset to the last point for Douglas-Peucker on polygons (see #201)
    final offset = 0.00000000001;
    lastPoint = poly[poly.length - 1];
    // Point<double>.x and .y are immutable, so replace the last point
    poly.removeAt(poly.length - 1);
    poly.add(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>.generate(n, (index) => 0);
  dists[0] = 1;
  dists[n - 1] = 1;
  double maxDist = 0.0;
  double dist = 0.0;
  List<int> current = [];

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

  if (closedPolygon && lastPoint != null) {
    // Replace last point w/ offset with the original last point to re-close the polygon
    poly.removeAt(poly.length - 1);
    poly.add(lastPoint);
  }

  // Generate the simplified line
  idx = 0;
  final simplifiedLine = <Point<double>>[];
  for (final l in poly) {
    if (dists[idx] != 0) {
      simplifiedLine.add(l);
    }
    idx++;
  }
  return simplifiedLine;
}