simplify static method

List<Point<num>> simplify(List<Point<num>> poly, num 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.

return a simplified poly produced by the Douglas-Peucker algorithm

Implementation

static List<Point> simplify(List<Point> poly, num tolerance) {
  final int 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");
  }

  bool closedPolygon = isClosedPolygon(poly);
  Point? 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 num offset = 0.00000000001;
    lastPoint = poly[poly.length - 1];
    // Point.x and .y are immutable, so replace the last point
    poly.removeAt(poly.length - 1);
    poly.add(Point(lastPoint.x + offset, lastPoint.y + offset));
  }

  //  Here is is a big change code, had to use stack package from dart pub
  //  to solve this little bloc of code below, not sure if it is working

  int idx = 0;
  int maxIdx = 0;
  Stack<List<int>> stack = Stack();
  List<num> dists = List.generate(n, (index) => 0);
  dists[0] = 1;
  dists[n - 1] = 1;
  num maxDist = 0.0;
  num dist = 0.0;
  List<int> current = [];

  if (n > 2) {
    List<int> stackVal = [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;
        List<int> stackValCurMax = [current[0], maxIdx];
        stack.push(stackValCurMax);
        List<int> stackValMaxCur = [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;
  List<Point> simplifiedLine = [];
  for (final l in poly) {
    if (dists[idx] != 0) {
      simplifiedLine.add(l);
    }
    idx++;
  }
  return simplifiedLine;
}