simplify static method

List<LatLng> simplify(
  1. List<LatLng> poly,
  2. 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 latitude and longitude (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.

@param poly polyline or polygon to be simplified. Polygon should be closed (i.e., first and last points should have the same latitude and longitude). @param 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<LatLng> simplify(List<LatLng> poly, num tolerance) {
  final n = poly.length;
  if (n < 1) {
    throw const FormatException('Polyline must have at least 1 point');
  }
  if (tolerance <= 0) {
    throw const FormatException('Tolerance must be greater than zero');
  }

  final closedPolygon = isClosedPolygon(poly);
  late final LatLng lastPoint;

  // 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)
    const offset = 0.00000000001;
    lastPoint = poly.last;
    // LatLng.latitude and .longitude are immutable, so replace the last point
    poly.removeLast();
    poly.add(
        LatLng(lastPoint.latitude + offset, lastPoint.longitude + offset));
  }

  int idx;
  var maxIdx = 0;
  final stack = Queue<List<int>>();
  final dists = List<num>.filled(n, 0);
  dists[0] = 1;
  dists[n - 1] = 1;
  num maxDist;
  num dist = 0.0;
  List<int> current;

  if (n > 2) {
    final stackVal = [0, (n - 1)];
    stack.add(stackVal);
    while (stack.isNotEmpty) {
      current = stack.removeLast();
      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 = [current[0], maxIdx];
        stack.add(stackValCurMax);
        final stackValMaxCur = [maxIdx, current[1]];
        stack.add(stackValMaxCur);
      }
    }
  }

  if (closedPolygon) {
    // Replace last point w/ offset with the original last point to re-close
    // the polygon
    poly.removeLast();
    poly.add(lastPoint);
  }

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

  return simplifiedLine;
}