rapidgeo-simplify

Polyline simplification using the Douglas-Peucker algorithm with pluggable distance backends.

Installation

[dependencies]
rapidgeo-simplify = "0.1"

# For parallel processing support
rapidgeo-simplify = { version = "0.1", features = ["batch"] }

Quick Start

use rapidgeo_distance::LngLat;
use rapidgeo_simplify::{simplify_dp_into, SimplifyMethod};

let points = vec![
    LngLat::new_deg(-122.4194, 37.7749), // San Francisco
    LngLat::new_deg(-122.0, 37.5),       // Detour
    LngLat::new_deg(-121.5, 37.0),       // Another point
    LngLat::new_deg(-118.2437, 34.0522), // Los Angeles
];

let mut simplified = Vec::new();
let count = simplify_dp_into(
    &points,
    50000.0, // 50km tolerance
    SimplifyMethod::GreatCircleMeters,
    &mut simplified,
);

println!("Simplified from {} to {} points", points.len(), count);

Why This Exists

The Douglas-Peucker algorithm simplifies polylines by removing points that don't significantly change the shape. Points are kept only if they deviate more than the specified tolerance from the simplified line. This implementation provides multiple distance calculation backends:

GreatCircleMeters: Spherical distance calculations for global accuracy
PlanarMeters: ENU projection for regional work with better performance
EuclidRaw: Raw coordinate differences for non-geographic data

Examples

Basic Simplification

use rapidgeo_distance::LngLat;
use rapidgeo_simplify::{simplify_dp_mask, SimplifyMethod};

let points = vec![
    LngLat::new_deg(-122.0, 37.0),
    LngLat::new_deg(-121.5, 37.5),
    LngLat::new_deg(-121.0, 37.0),
];

let mut mask = Vec::new();
simplify_dp_mask(
    &points,
    1000.0, // 1km tolerance
    SimplifyMethod::GreatCircleMeters,
    &mut mask,
);

// mask[i] is true if points[i] should be kept
for (i, &keep) in mask.iter().enumerate() {
    if keep {
        println!("Keep point {}: {:?}", i, points[i]);
    }
}

Batch Processing

use rapidgeo_simplify::batch::simplify_batch;

let polylines = vec![
    vec![/* first polyline points */],
    vec![/* second polyline points */],
];

let simplified = simplify_batch(
    &polylines,
    100.0,
    SimplifyMethod::GreatCircleMeters,
);

Parallel Processing (requires `batch` feature)

use rapidgeo_simplify::batch::simplify_batch_par;

let simplified = simplify_batch_par(
    &polylines,
    100.0,
    SimplifyMethod::GreatCircleMeters,
);

Distance Methods

GreatCircleMeters

Uses spherical distance calculations. Best for:

Global datasets
High accuracy requirements
Cross-country or intercontinental paths

PlanarMeters

Projects to East-North-Up coordinates around the polyline's midpoint. Best for:

Regional datasets (city/state level)
Better performance than great circle
Reasonable accuracy for smaller areas

EuclidRaw

Direct coordinate subtraction. Best for:

Non-geographic coordinate systems
Screen coordinates
Already-projected data

API

Core Functions

simplify_dp_into(points, tolerance, method, output) - Simplify into output vector
simplify_dp_mask(points, tolerance, method, mask) - Generate keep/drop mask

Batch Functions (feature = "batch")

simplify_batch(polylines, tolerance, method) - Process multiple polylines
simplify_batch_par(polylines, tolerance, method) - Parallel batch processing
simplify_dp_into_par(points, tolerance, method, output) - Parallel single polyline

Algorithm

Implements the Douglas-Peucker algorithm:

Draw line between first and last points
Find point with maximum perpendicular distance to this line
If distance > tolerance, keep the point and recurse on both segments
Otherwise, drop all intermediate points

The algorithm guarantees that:

First and last points are always preserved
No point deviates more than tolerance from the simplified line
Shape characteristics are maintained

Performance

Single-threaded: ~1M points/second for typical GPS traces
Memory: O(n) for input, O(log n) stack depth
Parallel processing available for large datasets with batch feature

Limitations

Requires at least 2 points (endpoints always preserved)
GreatCircleMeters doesn't handle antimeridian crossing optimally
PlanarMeters accuracy decreases for very large regions

License

Licensed under either of:

Apache License, Version 2.0 (LICENSE-APACHE)
MIT license (LICENSE-MIT)

at your option.

rapidgeo-simplify 0.1.2