polyline_codec/
lib.rs

1use std::{error::Error, fmt};
2
3/// LatLng is a tuple composed of latitude and longitude.
4#[derive(Debug, Clone, Copy)]
5pub struct LatLng(pub f64, pub f64);
6
7/// `Point` contains accessors for a coordinate's latitude (`lat`) and longitude
8/// (`lng`).
9///
10/// Note: `Point` is not implemented for `&[f64; 2]` due to geojson's format
11/// being `[longitude, latitude]` rather than `[latitude, longitude]` which is
12/// expected by this algorithm.
13pub trait Point: fmt::Debug {
14    fn lat(&self) -> f64;
15    fn lng(&self) -> f64;
16}
17
18impl<P: Point> PartialEq<P> for LatLng {
19    fn eq(&self, other: &P) -> bool {
20        self.0 == other.lat() && self.1 == other.lng()
21    }
22}
23
24impl Point for LatLng {
25    fn lat(&self) -> f64 {
26        self.0
27    }
28    fn lng(&self) -> f64 {
29        self.1
30    }
31}
32
33impl Point for (f64, f64) {
34    fn lat(&self) -> f64 {
35        self.0
36    }
37    fn lng(&self) -> f64 {
38        self.1
39    }
40}
41
42#[derive(Debug)]
43pub struct InvalidEncodingError {
44    pub encoded_path: String,
45}
46
47impl fmt::Display for InvalidEncodingError {
48    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
49        write!(f, "error: invalid encoding: {}", self.encoded_path)
50    }
51}
52impl Error for InvalidEncodingError {}
53
54#[derive(Debug)]
55pub struct InvalidLatLngError {
56    pub lat: f64,
57    pub lng: f64,
58}
59impl fmt::Display for InvalidLatLngError {
60    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
61        write!(f, "error: invalid lat lng: ({}, {})", self.lat, self.lng)
62    }
63}
64
65/// Decodes an encoded path string into a sequence of LatLngs.
66///
67/// See https://developers.google.com/maps/documentation/utilities/polylinealgorithm
68///
69///  #### Example
70/// ```rust
71/// let encoded = "_p~iF~ps|U_ulLnnqC_mqNvxq`@";
72/// assert_eq!(polyline_codec::decode(encoded, 5).unwrap(), vec![
73///     (38.5, -120.2),
74///     (40.7, -120.95),
75///     (43.252, -126.453)
76/// ]);
77/// ```
78pub fn decode(encoded_path: &str, precision: u32) -> Result<Vec<LatLng>, InvalidEncodingError> {
79    let factor = 10_i32.pow(precision) as f64;
80    // let encoded_path = encoded_path.encode_utf16();
81    // TODO: need to see if I can just use the str len
82    // let len = encoded_path.clone().count();
83    let len = encoded_path.len();
84    let mut path = Vec::with_capacity(len / 2);
85    let mut index = 0;
86    let mut lat = 0.0;
87    let mut lng = 0.0;
88
89    while index < len {
90        let mut result: i32 = 1;
91        let mut shift = 0;
92        let mut b: i32;
93        loop {
94            // b = (encoded_path.clone().nth(index).unwrap() as i32) - 63 - 1;
95            b = (encoded_path
96                .chars()
97                .nth(index)
98                .ok_or(InvalidEncodingError {
99                    encoded_path: encoded_path.into(),
100                })? as i32)
101                - 63
102                - 1;
103            index += 1;
104            result += (b << shift) as i32;
105            shift += 5;
106            if b < 0x1f {
107                break;
108            }
109        }
110        lat += (if result & 1 != 0 {
111            !(result >> 1)
112        } else {
113            result >> 1
114        }) as f64;
115        result = 1;
116        shift = 0;
117        loop {
118            b = (encoded_path.chars().nth(index).unwrap() as i32) - 63 - 1;
119            index += 1;
120            result += (b << shift) as i32;
121            shift += 5;
122            if b < 0x1f {
123                break;
124            }
125        }
126
127        lng += (if result & 1 != 0 {
128            !(result >> 1)
129        } else {
130            result >> 1
131        }) as f64;
132        path.push(LatLng(lat / factor, lng / factor));
133    }
134    path.shrink_to_fit();
135    Ok(path)
136}
137
138/// Polyline encodes an array of objects having lat and lng properties.
139///
140/// See https://developers.google.com/maps/documentation/utilities/polylinealgorithm
141///
142/// #### Example
143/// ```rust
144/// let path = vec![
145///     (38.5, -120.2),
146///     (40.7, -120.95),
147///     (43.252, -126.453),
148/// ];
149/// assert_eq!(polyline_codec::encode(&path, 5).unwrap(), "_p~iF~ps|U_ulLnnqC_mqNvxq`@");
150///
151/// ```
152pub fn encode<P: Point>(path: &[P], precision: u32) -> Result<String, InvalidLatLngError> {
153    let factor = 10_f64.powi(precision as i32);
154    let transform = |p: &P| LatLng((p.lat() * factor).round(), (p.lng() * factor).round());
155    polyline_encode_line(path, transform)
156}
157
158///
159/// Encodes a generic polyline, optionally performing a transform on each point
160/// before encoding it.
161#[doc(hidden)]
162pub fn polyline_encode_line<P, F>(array: &[P], transform: F) -> Result<String, InvalidLatLngError>
163where
164    P: Point,
165    F: Fn(&P) -> LatLng,
166{
167    let mut v: Vec<String> = Vec::new();
168    let mut start = LatLng(0.0, 0.0);
169    let mut end;
170    for p in array {
171        validate(p)?;
172        end = transform(p);
173        encode_signed(
174            end.lat().round() as i64 - start.lat().round() as i64,
175            &mut v,
176        ); // lat
177        encode_signed(
178            end.lng().round() as i64 - start.lng().round() as i64,
179            &mut v,
180        ); // lng
181        start = end;
182    }
183    Ok(v.join(""))
184}
185
186pub(crate) fn validate<P: Point>(p: &P) -> Result<(), InvalidLatLngError> {
187    if p.lat() < -90.0 || p.lat() > 90.0 || p.lng() < -180.0 || p.lng() > 180.0 {
188        Err(InvalidLatLngError {
189            lat: p.lat(),
190            lng: p.lng(),
191        })
192    } else {
193        Ok(())
194    }
195}
196
197/// Encodes the given value in the compact polyline format, appending the
198/// encoded value to the given array of strings.
199fn encode_signed(value: i64, v: &mut Vec<String>) {
200    encode_unsigned(if value < 0 { !(value << 1) } else { value << 1 }, v)
201}
202
203fn encode_unsigned(value: i64, v: &mut Vec<String>) {
204    let mut value = value;
205    while value >= 0x20 {
206        let s = vec![((0x20 | (value & 0x1f)) + 63) as u16];
207        v.push(String::from_utf16(&s).expect("failed to encode utf16"));
208        value >>= 5;
209    }
210
211    v.push(String::from_utf16(&[(value + 63) as u16]).unwrap());
212}
213
214#[cfg(test)]
215mod tests {
216    use super::*;
217    use proptest::*;
218
219    #[test]
220    fn test_decodes_to_an_empty_array() {
221        let v: Vec<LatLng> = vec![];
222        assert_eq!(decode("", 5).unwrap(), v);
223    }
224    #[test]
225    fn test_decodes_a_string_into_a_vec_of_lat_lng_pairs() {
226        assert_eq!(
227            decode("_p~iF~ps|U_ulLnnqC_mqNvxq`@", 5).unwrap(),
228            &[(38.5, -120.2), (40.7, -120.95), (43.252, -126.453)]
229        );
230        dbg!(decode("_p~iF~ps|U_ulLnnqC_mqNvxq`@", 5).unwrap());
231    }
232
233    #[test]
234    fn test_decodes_with_precision_0() {
235        assert_eq!(
236            decode("mAnFC@CH", 0).unwrap(),
237            &[(39.0, -120.0), (41.0, -121.0), (43.0, -126.0)]
238        );
239    }
240    #[test]
241    fn test_encodes_an_empty_vec() {
242        let v: Vec<LatLng> = vec![];
243        assert_eq!(encode(&v, 5).unwrap(), "");
244    }
245
246    #[test]
247    fn encodes_a_vec_of_lat_lng_pairs_into_a_string() {
248        assert_eq!(
249            encode(&[(38.5, -120.2), (40.7, -120.95), (43.252, -126.453)], 5).unwrap(),
250            "_p~iF~ps|U_ulLnnqC_mqNvxq`@"
251        );
252    }
253
254    proptest! {
255            #[test]
256            fn test_random_roundtrip(path: Vec<(f64, f64)>) {
257
258                let should_error = path.iter().any(|p| p.0 > 90.0 || p.0 < -90.0 || p.1 > 180.0 || p.1 < -180.0);
259                if should_error {
260                    prop_assert!(encode(&path, 5).is_err());
261                } else {
262                    let encoded = encode(&path, 5).unwrap();
263                    let decoded = decode(&encoded, 5).unwrap();
264                    prop_assert_eq!(encoded, encode(&decoded, 5).unwrap());
265                }
266
267                // let encoded = encode(&[path], 5);
268                // if should_err {
269                //     assert!(encoded.is_err());
270                // } else {
271                //     let encoded = encoded.upwrap();
272                // }
273
274                // let decoded = decode(&encoded, 5).unwrap();
275                // prop_assert_eq!(path, decoded);
276        }
277    }
278    proptest! {
279        #[test]
280        fn test_valid_roundtrip(p0 in -90.0..90.0, p1 in -180.0..180.0) {
281            // TODO: need to learn proptest better. I need a strategy that
282            // generates a Vec<(f64,f64)> within the specified ranges
283
284            let path = vec![(p0, p1)];
285            dbg!(&path);
286            let encoded = encode(&path, 5).unwrap();
287            dbg!(&encoded);
288            let decoded = decode(&encoded, 5).unwrap();
289            prop_assert_eq!(encoded, encode(&decoded, 5).unwrap());
290        }
291    }
292}
polyline_codec/lib.rs

polyline_codec/
lib.rs
