simplify method

List<ILatLong> simplify(List<ILatLong> points, double tolerance)

Simplifies a polyline using the Douglas-Peucker algorithm.

Reduces the number of points in the input polyline while preserving its essential shape within the specified tolerance.

points Input polyline as list of coordinates tolerance Maximum allowed perpendicular distance for point removal Returns simplified polyline with fewer points

Implementation

List<ILatLong> simplify(List<ILatLong> points, double tolerance) {
  if (points.length <= 2) {
    return points;
  }

  final double toleranceSquared = tolerance * tolerance;

  // Use a more efficient stack structure with pre-allocated capacity
  final Queue<_Segment> stack = Queue<_Segment>();
  stack.add(_Segment(0, points.length - 1));

  // Track which points to keep using a boolean array for O(1) lookup
  final List<bool> keepPoint = List<bool>.filled(points.length, false);
  keepPoint[0] = true; // Always keep first point
  keepPoint[points.length - 1] = true; // Always keep last point

  while (stack.isNotEmpty) {
    final _Segment segment = stack.removeFirst();
    final int start = segment.start;
    final int end = segment.end;

    // Early exit for adjacent points
    if (end - start <= 1) {
      continue;
    }

    double maxDistanceSquared = 0.0;
    int maxDistanceIndex = start;

    // Cache start and end points to avoid repeated array access
    final ILatLong startPoint = points[start];
    final ILatLong endPoint = points[end];

    // Find the point with maximum perpendicular distance
    for (int i = start + 1; i < end; i++) {
      final double distanceSquared = _perpendicularDistanceSquared(points[i], startPoint, endPoint);
      if (distanceSquared > maxDistanceSquared) {
        maxDistanceSquared = distanceSquared;
        maxDistanceIndex = i;
      }
    }

    // If the maximum distance exceeds tolerance, subdivide
    if (maxDistanceSquared > toleranceSquared) {
      keepPoint[maxDistanceIndex] = true;
      // Process larger segment first for better cache locality
      if (maxDistanceIndex - start > end - maxDistanceIndex) {
        stack.addFirst(_Segment(start, maxDistanceIndex));
        stack.addFirst(_Segment(maxDistanceIndex, end));
      } else {
        stack.addFirst(_Segment(maxDistanceIndex, end));
        stack.addFirst(_Segment(start, maxDistanceIndex));
      }
    }
  }

  // Build result list from kept points
  final List<ILatLong> result = <ILatLong>[];
  points.forEachIndexed((index, point) {
    if (keepPoint[index]) {
      result.add(point);
    }
  });

  return result;
}