rapidgeo-polyline

Fast Google Polyline Algorithm encoding/decoding for geographic coordinates.

Installation

[dependencies]
rapidgeo-polyline = "0.1"

For batch processing with parallel support:

[dependencies]
rapidgeo-polyline = { version = "0.1", features = ["batch"] }

Quick Start

use rapidgeo_polyline::{encode, decode};
use rapidgeo_distance::LngLat;

let coords = vec![
    LngLat::new_deg(-120.2, 38.5),
    LngLat::new_deg(-120.95, 40.7),
];

let encoded = encode(&coords, 5).unwrap();
let decoded = decode(&encoded, 5).unwrap();

What This Does

Implements Google's Polyline Algorithm for encoding sequences of geographic coordinates into compact ASCII strings. Commonly used in mapping applications, route optimization, and GPS data storage.

Coordinate Order: All functions use longitude, latitude ordering (x, y).

Examples

Basic Encoding/Decoding

use rapidgeo_polyline::{encode, decode};
use rapidgeo_distance::LngLat;

// Google's test vector
let coords = vec![
    LngLat::new_deg(-120.2, 38.5),
    LngLat::new_deg(-120.95, 40.7),
    LngLat::new_deg(-126.453, 43.252),
];

let polyline = encode(&coords, 5).unwrap();
assert_eq!(polyline, "_p~iF~ps|U_ulLnnqC_mqNvxq`@");

let decoded = decode(&polyline, 5).unwrap();
assert_eq!(decoded.len(), 3);

Route Simplification

Uses the Douglas-Peucker algorithm to reduce coordinate density while preserving route shape:

use rapidgeo_polyline::{encode_simplified, simplify_polyline};
use rapidgeo_simplify::SimplifyMethod;
use rapidgeo_distance::LngLat;

let detailed_route = vec![
    LngLat::new_deg(-122.0, 37.0),
    LngLat::new_deg(-122.01, 37.01),  // Close intermediate point
    LngLat::new_deg(-122.02, 37.02),  // Close intermediate point
    LngLat::new_deg(-122.1, 37.1),
];

// Encode with 1km simplification tolerance
let simplified = encode_simplified(
    &detailed_route,
    1000.0, // meters
    SimplifyMethod::GreatCircleMeters,
    5
).unwrap();

Batch Processing

Process multiple polylines in parallel (requires batch feature):

#[cfg(feature = "batch")]
use rapidgeo_polyline::batch::{encode_batch, decode_batch};

#[cfg(feature = "batch")]
{
    let routes = vec![
        vec![LngLat::new_deg(-120.2, 38.5), LngLat::new_deg(-120.95, 40.7)],
        vec![LngLat::new_deg(-126.453, 43.252), LngLat::new_deg(-122.4194, 37.7749)],
    ];
    
    let encoded = encode_batch(&routes, 5).unwrap();
    let decoded = decode_batch(&encoded, 5).unwrap();
}

API

Core Functions

• encode(coords, precision) - Encode coordinates to polyline string
• decode(polyline, precision) - Decode polyline string to coordinates
• encode_simplified(coords, tolerance, method, precision) - Encode with simplification
• simplify_polyline(polyline, tolerance, method, precision) - Simplify existing polyline

Batch Functions (feature = "batch")

• encode_batch() - Parallel encoding of multiple coordinate sequences
• decode_batch() - Parallel decoding of multiple polylines
• encode_simplified_batch() - Parallel encoding with simplification

Precision

• 5 (default): ~1 meter accuracy, standard for most mapping applications
• 6: ~10 centimeter accuracy, used for high-precision applications

Valid range: 1-11

Performance

• Encoding: ~2-4 million coordinates/second
• Decoding: ~3-5 million coordinates/second
• Memory: O(n) where n = number of coordinates
• Batch processing automatically uses parallel processing for >100 polylines

Limitations

• Coordinates must be within valid WGS84 bounds (±180° longitude, ±90° latitude)
• No support for 3D coordinates (elevation)
• Precision limited to 11 decimal places
• Does not handle coordinate reference system transformations

Algorithm References

• Google Polyline Algorithm Specification
• Douglas-Peucker Line Simplification

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.