Smoothing noisy GPS: Kalman + Douglas–Peucker in a running app

Raw GPS from an Apple Watch looks awful on a map. The runner went in a straight line down a street; the trace looks like they were dodging traffic. Here's the two-stage pipeline I use in iRunning to turn that mess into a route worth showing.

Every running app eventually hits the same wall: the line you draw on the map is only as good as the coordinates underneath it, and wrist GPS coordinates are noisy. The watch has a tiny antenna, it's strapped to an arm that swings, and it's sampling roughly once a second while the body wearing it moves through buildings, trees, and tunnels. Plot those points raw and you get a jagged zig-zag that crosses the road, doubles back on itself, and adds phantom distance.

Raw 1 Hz fixes Filtered & simplified

Two problems, two stages

It's tempting to reach for one clever algorithm, but "noisy GPS" is really two separate problems, and they want opposite things:

• Each point is wrong by a little. A fix lands a few metres off where you actually were. You fix this by denoising — nudging each point toward where it probably should be, using how confident the hardware is.
• There are far too many points. A 45-minute run is ~2,700 fixes. Most sit on near-straight segments and carry no information. You fix this by simplifying — dropping the points that don't change the shape.

So the pipeline is two stages, in order: a Kalman filter to denoise as fixes arrive, then Douglas–Peucker to simplify before you save or draw. Order matters — simplify first and you'd be throwing away points based on noise you haven't removed yet.

Stage 1 — a pragmatic Kalman filter

A full Kalman filter models position and velocity with matrices and gets intimidating fast. For a running route you don't need most of that. The insight that makes it cheap: treat latitude and longitude as two independent 1-D signals, and let horizontalAccuracy — which Core Location already gives you per fix — be the measurement variance.

The filter carries one number besides the position: its own uncertainty, in metres². Between fixes that uncertainty grows (you've moved, you're less sure where you are). Each new fix shrinks it. The ratio of the two decides how much you trust the new reading.

import CoreLocation

/// A lightweight Kalman filter for GPS positions.
/// Latitude and longitude are treated as independent 1-D signals whose
/// uncertainty grows with elapsed time and shrinks with each new fix.
final class GPSKalmanFilter {

    /// Expected movement per second, in metres. Higher trusts new fixes
    /// more (less smoothing); lower glues the track down (more smoothing).
    private let processNoise: Double

    private var variance: Double = -1          // metres²; < 0 == uninitialised
    private var timestamp: TimeInterval = 0
    private var lat = 0.0
    private var lon = 0.0

    init(processNoise: Double = 3.0) {
        self.processNoise = processNoise
    }

    func process(_ location: CLLocation) -> CLLocationCoordinate2D {
        let accuracy = max(location.horizontalAccuracy, 1)   // metres, ~1σ
        let measurementVariance = accuracy * accuracy

        // First fix: seed the filter and return it unchanged.
        guard variance >= 0 else {
            timestamp = location.timestamp.timeIntervalSince1970
            lat = location.coordinate.latitude
            lon = location.coordinate.longitude
            variance = measurementVariance
            return location.coordinate
        }

        // Predict: uncertainty grows with the time since the last fix.
        let now = location.timestamp.timeIntervalSince1970
        let dt = now - timestamp
        if dt > 0 {
            variance += dt * processNoise * processNoise
            timestamp = now
        }

        // Update: blend prediction and measurement by their variances.
        let gain = variance / (variance + measurementVariance)   // 0…1
        lat += gain * (location.coordinate.latitude  - lat)
        lon += gain * (location.coordinate.longitude - lon)
        variance *= (1 - gain)

        return CLLocationCoordinate2D(latitude: lat, longitude: lon)
    }
}

That's the whole filter. The one knob is processNoise: it's the answer to "how far could the runner realistically have moved in a second?" Around 3 m/s tracks a steady run nicely. Push it lower and the line gets glassy but lags on sharp turns; push it higher and you're barely filtering at all. Tune it against a few real GPX traces, not in the abstract.

Stage 2 — Douglas–Peucker

Now the points are honest but there are thousands of them. Ramer–Douglas–Peucker is the classic way to thin a polyline while keeping its shape. It's beautifully recursive:

1. Draw a straight line between the first and last point.
2. Find the point farthest from that line. If it's closer than epsilon, every point between the ends is redundant — drop them all.
3. If it's farther, that point is a real corner. Keep it, and recurse on the two halves it splits.

import CoreLocation

enum RouteSimplifier {

    /// Ramer–Douglas–Peucker. `epsilon` is the maximum deviation we'll
    /// tolerate, in metres — points closer to the line than this get dropped.
    static func simplify(_ points: [CLLocationCoordinate2D],
                         epsilon: Double = 3) -> [CLLocationCoordinate2D] {
        guard points.count > 2 else { return points }

        // Farthest point from the line between the two endpoints.
        var maxDistance = 0.0
        var index = 0
        for i in 1..<(points.count - 1) {
            let d = perpendicularDistance(points[i], from: points.first!, to: points.last!)
            if d > maxDistance { maxDistance = d; index = i }
        }

        // Beyond epsilon → it's a real corner: keep it and recurse.
        guard maxDistance > epsilon else {
            return [points.first!, points.last!]
        }
        let left  = simplify(Array(points[0...index]), epsilon: epsilon)
        let right = simplify(Array(points[index...]),  epsilon: epsilon)
        return Array(left.dropLast()) + right        // drop the shared join point
    }

    /// Distance from `p` to the segment a→b, in metres, via a local
    /// equirectangular projection — plenty accurate at running scale.
    private static func perpendicularDistance(_ p: CLLocationCoordinate2D,
                                              from a: CLLocationCoordinate2D,
                                              to b: CLLocationCoordinate2D) -> Double {
        let mPerLat = 111_320.0
        let mPerLon = 111_320.0 * cos(a.latitude * .pi / 180)

        let ax = a.longitude * mPerLon, ay = a.latitude * mPerLat
        let bx = b.longitude * mPerLon, by = b.latitude * mPerLat
        let px = p.longitude * mPerLon, py = p.latitude * mPerLat

        let dx = bx - ax, dy = by - ay
        let lenSq = dx * dx + dy * dy
        guard lenSq > 0 else { return hypot(px - ax, py - ay) }

        // Project p onto the segment, clamped to its endpoints.
        let t = max(0, min(1, ((px - ax) * dx + (py - ay) * dy) / lenSq))
        let cx = ax + t * dx, cy = ay + t * dy
        return hypot(px - cx, py - cy)
    }
}

The projection bit deserves a word: comparing distances in raw degrees is wrong, because a degree of longitude shrinks as you move away from the equator. Multiplying by metres-per-degree (and scaling longitude by cos(latitude)) puts both axes in metres, so epsilon means an actual physical distance. At the span of a single run the curvature of the Earth doesn't matter, so this flat approximation is fine.

Wiring it together

Live, the filter runs inside the location callback — denoise each fix the moment it arrives, so the in-progress line on the watch is already clean. The simplifier runs once, later, when you persist or export the run:

let filter = GPSKalmanFilter()
var track: [CLLocationCoordinate2D] = []

func locationManager(_ manager: CLLocationManager,
                     didUpdateLocations locations: [CLLocation]) {
    for fix in locations where (0...50).contains(fix.horizontalAccuracy) {
        track.append(filter.process(fix))       // gate, then denoise, live
    }
}

// On save / export: thin the track for storage and drawing.
let route = RouteSimplifier.simplify(track, epsilon: 3)

What it bought me

On a typical city run the two stages together cut the point count by 80–90% while the line stops crossing the road. Concretely, that's:

• A route that reads as the run you did — the headline feature, and the reason people screenshot it.
• Cheaper MKPolyline rendering. Fewer vertices means the overlay redraws without a hitch while you pan and zoom.
• Smaller payloads. The Strava export and anything you sync shrink with the point count — a free win on storage and bandwidth.

Two cautions from shipping it. Don't over-smooth: a low processNoise plus a fat epsilon will happily erase a real hairpin switchback. And keep the filter for the map — compute distance, pace, and splits from the raw, gated fixes, because simplification deliberately throws away the very wiggles that distance is measured from.

That's the whole pipeline: gate on accuracy, Kalman to denoise, Douglas–Peucker to simplify. Three small, independent pieces — each easy to test on a recorded GPX — that together turn a wrist into something you'd actually put on a map.