valhalla_client/
shapes.rs

1use serde::{Deserialize, Serialize};
2
3/// Specifies the optional format for the path shape of each connection
4#[derive(Serialize, Debug, Clone, Copy, PartialEq, Eq)]
5pub enum ShapeFormat {
6    #[serde(rename = "polyline6")]
7    /// A polyline with 6 degrees of precision
8    Polyline6,
9
10    #[serde(rename = "polyline5")]
11    /// A polyline with 5 degrees of precision
12    Polyline5,
13
14    #[serde(rename = "geojson")]
15    /// A GeoJSON shape
16    GeoJSON,
17
18    #[serde(rename = "no_shape")]
19    /// No shape
20    NoShape,
21}
22
23#[derive(Serialize, Deserialize, Debug, Clone, PartialEq)]
24/// A point in a shape
25pub struct ShapePoint {
26    /// Longitude
27    pub lon: f64,
28
29    /// Latitude
30    pub lat: f64,
31}
32
33impl From<&ShapePoint> for geo_types::Point {
34    fn from(p: &ShapePoint) -> Self {
35        debug_assert!((-90.0..90.0).contains(&p.lat));
36        debug_assert!((-180.0..180.0).contains(&p.lon));
37        Self::new(p.lon, p.lat)
38    }
39}
40
41impl From<ShapePoint> for super::Coordinate {
42    fn from(p: ShapePoint) -> Self {
43        debug_assert!((-90.0..90.0).contains(&p.lat));
44        debug_assert!((-180.0..180.0).contains(&p.lon));
45        (p.lon as f32, p.lat as f32)
46    }
47}
48
49/// decodes polyline6 to [`ShapePoint`]s
50///
51/// Algorithm based on https://valhalla.github.io/valhalla/decoding/#python
52fn decode_shape_polyline6(encoded: &str) -> Vec<ShapePoint> {
53    debug_assert!(encoded.is_ascii());
54    debug_assert!(!encoded.is_empty());
55    // six degrees of precision in valhalla
56    let inv = 1.0 / 1e6;
57    let mut decoded = Vec::new();
58    let mut previous = [0, 0];
59    let mut i = 0;
60
61    while i < encoded.len() {
62        // for each coord (lat, lon)
63        let mut ll = [0, 0];
64        for j in [0, 1] {
65            let mut shift = 0;
66            let mut byte = 0x20;
67            // keep decoding bytes until you have this coord
68            while byte >= 0x20 {
69                byte = i32::from(encoded.as_bytes()[i]) - 63;
70                i += 1;
71                ll[j] |= (byte & 0x1f) << shift;
72                shift += 5;
73            }
74            // get the final value adding the previous offset and remember it for the next
75            ll[j] = previous[j]
76                + if (ll[j] & 1) != 0 {
77                    !(ll[j] >> 1)
78                } else {
79                    ll[j] >> 1
80                };
81            previous[j] = ll[j];
82        }
83        // scale by the precision
84        let lon = f64::from(ll[1]) * inv;
85        let lat = f64::from(ll[0]) * inv;
86        debug_assert!((-90.0..90.0).contains(&lat));
87        debug_assert!((-180.0..180.0).contains(&lon));
88        decoded.push(ShapePoint { lon, lat });
89    }
90
91    decoded
92}
93pub(crate) fn deserialize_shape<'de, D>(deserializer: D) -> Result<Vec<ShapePoint>, D::Error>
94where
95    D: serde::Deserializer<'de>,
96{
97    let s = String::deserialize(deserializer)?;
98    Ok(decode_shape_polyline6(s.as_str()))
99}
100#[cfg(test)]
101mod tests {
102    use super::*;
103    #[test]
104    fn decode_shape_works_america() {
105        // shape from https://valhalla1.openstreetmap.de/optimized_route?json=%7B%22locations%22%3A%5B%7B%22lat%22%3A40.042072%2C%22lon%22%3A-76.306572%7D%2C%7B%22lat%22%3A39.991889%2C%22lon%22%3A-76.781939%7D%2C%7B%22lat%22%3A39.984460%2C%22lon%22%3A-76.695075%7D%2C%7B%22lat%22%3A39.996900%2C%22lon%22%3A-76.768704%7D%2C%7B%22lat%22%3A39.983901%2C%22lon%22%3A-76.707604%7D%5D%2C%22costing%22%3A%22auto%22%2C%22units%22%3A%22kilometers%22%7D
106        let shape = decode_shape_polyline6("}c|gkAlvkmqCkg@zf@_IbJaP`XoXq^aCwDyByGkAyGI}H?iFZeH`AuFfB}HxBaG~xAiaBtFgHtPqWfCeDpMsNva@px@rRp_@|s@vvAd{@tbBpiAfzBjNuw@lGo`@bAwHz@}I|@cQ^gNf@_OB_NJ}[BeJH{c@X{[SaK_@{S]}Q_@cJUgLAgJ?iUBoB^eMFoA`BsXbLgxAzK_{CpD}oA`@wUlBegAvAmh@fGcr@lGur@zGu]jGeSv@_BdNiYdCaDhHaJx^_[f^}Qre@cXjOgJtJ}HjIqKjEkHzD{HpDaIrB_GvA}EpAoFfAaGlA}H|@yHbAwK~Le{A|@yHv@{Ft@cEfBiHdCsHjCkF|ByDxQaYlE}GrCmEjR{Yp^al@nMgM|C_Fb]_j@xLwR~Ro[`DiElDsD~GmGlNmMpEwDkAwGcDwR_EkUmDuV{CmTiPwaAsc@{kCwL_t@{d@wmCqZkiB{NkcAcGwa@aAgHyJ_t@uI_q@_Kyp@aEgYqBqL}M_v@_Q{n@sVw}@gV{r@kLs\\sCeIqXmw@eFk]W{]dCic@Dw@vIsb@p@gD~Oiw@hAkGtBaLd@gFjAwc@GiGOeKs@ce@i@_HeEci@_@eFyDsh@gEsr@a@eZqAuaAo@cnAb@}JhAwpAnCq|CpCocBHcDZiNrAcp@`Biz@x@}m@bAgl@x@cWrHycAbGyi@tNe~@rAsIjDqTlDwS|G_g@vGyd@fGes@~DynAZ}nAXc~BoGeB}HsIaL}CqMeDmDbBwBe@iF}@wMkCkSuFsA_@");
107        // generated via http://valhalla.github.io/demos/polyline/
108        let expected = [
109            [-76.781943, 39.991887],
110            [-76.782581, 39.992533],
111            [-76.782759, 39.992692999999996],
112            [-76.78316, 39.992965999999996],
113            [-76.78265499999999, 39.993373999999996],
114            [-76.782563, 39.993438999999995],
115            [-76.782422, 39.9935],
116            [-76.782281, 39.993538],
117            [-76.782122, 39.993542999999995],
118            [-76.782005, 39.993542999999995],
119            [-76.781858, 39.993528999999995],
120            [-76.781735, 39.993496],
121            [-76.781576, 39.993444],
122            [-76.781447, 39.993383],
123            [-76.77987399999999, 39.991943],
124            [-76.779726, 39.99182],
125            [-76.779333, 39.991537],
126            [-76.77924999999999, 39.991468999999995],
127            [-76.779, 39.991236],
128            [-76.779921, 39.99068],
129            [-76.780442, 39.990366],
130            [-76.781846, 39.989519],
131            [-76.783441, 39.988555999999996],
132            [-76.78541299999999, 39.987362999999995],
133            [-76.784506, 39.987117],
134            [-76.78397, 39.986982],
135            [-76.78381399999999, 39.986948],
136            [-76.783639, 39.986917999999996],
137            [-76.783349, 39.986886999999996],
138            [-76.78310499999999, 39.986871],
139            [-76.782849, 39.986851],
140            [-76.782609, 39.986849],
141            [-76.782146, 39.986843],
142            [-76.781967, 39.986841],
143            [-76.78137699999999, 39.986836],
144            [-76.780915, 39.986823],
145            [-76.780722, 39.986833],
146            [-76.780388, 39.986849],
147            [-76.780085, 39.986864],
148            [-76.779907, 39.98688],
149            [-76.77969499999999, 39.986891],
150            [-76.779515, 39.986892],
151            [-76.779158, 39.986892],
152            [-76.779102, 39.986889999999995],
153            [-76.778875, 39.986874],
154            [-76.778835, 39.986869999999996],
155            [-76.778425, 39.986821],
156            [-76.776997, 39.986610999999996],
157            [-76.774501, 39.986405],
158            [-76.773206, 39.986315999999995],
159            [-76.772842, 39.986298999999995],
160            [-76.771687, 39.986244],
161            [-76.771024, 39.9862],
162            [-76.770206, 39.986067999999996],
163            [-76.769379, 39.985932999999996],
164            [-76.76888799999999, 39.985791],
165            [-76.768565, 39.985656999999996],
166            [-76.768517, 39.985628999999996],
167            [-76.768096, 39.985386],
168            [-76.76801499999999, 39.985319],
169            [-76.767838, 39.98517],
170            [-76.76738999999999, 39.984660999999996],
171            [-76.767087, 39.984161],
172            [-76.766685, 39.983543],
173            [-76.766505, 39.983281],
174            [-76.766346, 39.983094],
175            [-76.766145, 39.982928],
176            [-76.76599499999999, 39.982825999999996],
177            [-76.76583699999999, 39.982732],
178            [-76.765676, 39.982642999999996],
179            [-76.765548, 39.982585],
180            [-76.76543699999999, 39.982541],
181            [-76.765317, 39.9825],
182            [-76.765188, 39.982464],
183            [-76.765029, 39.982425],
184            [-76.764872, 39.982394],
185            [-76.764668, 39.98236],
186            [-76.763193, 39.982136],
187            [-76.763036, 39.982105],
188            [-76.76290999999999, 39.982077],
189            [-76.762812, 39.98205],
190            [-76.762663, 39.981998],
191            [-76.762509, 39.981930999999996],
192            [-76.762391, 39.981860999999995],
193            [-76.762298, 39.981798],
194            [-76.761881, 39.981497],
195            [-76.761738, 39.981394],
196            [-76.761635, 39.98132],
197            [-76.76120499999999, 39.98101],
198            [-76.76048399999999, 39.980505],
199            [-76.760256, 39.980273],
200            [-76.760144, 39.980194],
201            [-76.759456, 39.979712],
202            [-76.75914, 39.979490999999996],
203            [-76.758684, 39.979171],
204            [-76.758583, 39.97909],
205            [-76.758493, 39.979003],
206            [-76.758358, 39.978859],
207            [-76.758127, 39.978612],
208            [-76.75803499999999, 39.978507],
209            [-76.75789499999999, 39.978545],
210            [-76.75757899999999, 39.978626999999996],
211            [-76.757221, 39.978722999999995],
212            [-76.75684199999999, 39.978809999999996],
213            [-76.75649899999999, 39.978888],
214            [-76.755431, 39.979164999999995],
215            [-76.753177, 39.979751],
216            [-76.752329, 39.979971],
217            [-76.750045, 39.980577],
218            [-76.74834299999999, 39.981018],
219            [-76.747249, 39.981272],
220            [-76.746693, 39.981401999999996],
221            [-76.746545, 39.981435],
222            [-76.74569699999999, 39.981624],
223            [-76.744897, 39.981795],
224            [-76.7441, 39.981987],
225            [-76.74368, 39.982084],
226            [-76.74346299999999, 39.982141],
227            [-76.742583, 39.98238],
228            [-76.741817, 39.982668],
229            [-76.740813, 39.983046],
230            [-76.739983, 39.983418],
231            [-76.739509, 39.983632],
232            [-76.739346, 39.983706],
233            [-76.73844299999999, 39.984114999999996],
234            [-76.737957, 39.98423],
235            [-76.73746299999999, 39.984241999999995],
236            [-76.736882, 39.984175],
237            [-76.736854, 39.984172],
238            [-76.736284, 39.983999999999995],
239            [-76.7362, 39.983975],
240            [-76.735299, 39.983703],
241            [-76.735165, 39.983666],
242            [-76.734956, 39.983607],
243            [-76.73483999999999, 39.983588],
244            [-76.734252, 39.98355],
245            [-76.73411899999999, 39.983554],
246            [-76.733924, 39.983562],
247            [-76.733314, 39.983588],
248            [-76.73317, 39.983609],
249            [-76.732496, 39.983708],
250            [-76.73238099999999, 39.983723999999995],
251            [-76.731715, 39.983816999999995],
252            [-76.73088899999999, 39.983917],
253            [-76.730454, 39.983934],
254            [-76.729387, 39.983975],
255            [-76.728121, 39.983999],
256            [-76.72793, 39.983981],
257            [-76.72662199999999, 39.983944],
258            [-76.72410099999999, 39.983872],
259            [-76.722493, 39.983799],
260            [-76.722411, 39.983793999999996],
261            [-76.722166, 39.983779999999996],
262            [-76.72138, 39.983737999999995],
263            [-76.72043099999999, 39.983689],
264            [-76.71968, 39.98366],
265            [-76.71895599999999, 39.983626],
266            [-76.71857, 39.983596999999996],
267            [-76.717469, 39.983443],
268            [-76.71678399999999, 39.983312999999995],
269            [-76.715773, 39.983062],
270            [-76.715603, 39.983019999999996],
271            [-76.71525799999999, 39.982934],
272            [-76.71492599999999, 39.982847],
273            [-76.714286, 39.982704],
274            [-76.713681, 39.982563999999996],
275            [-76.712846, 39.982431999999996],
276            [-76.711569, 39.982336],
277            [-76.71029, 39.982321999999996],
278            [-76.70825599999999, 39.982309],
279            [-76.70820499999999, 39.982445],
280            [-76.708035, 39.982603999999995],
281            [-76.707956, 39.982813],
282            [-76.70787299999999, 39.983046],
283            [-76.707923, 39.983132999999995],
284            [-76.707904, 39.983193],
285            [-76.70787299999999, 39.983309999999996],
286            [-76.707803, 39.983546],
287            [-76.70768, 39.983872],
288            [-76.707664, 39.983914],
289        ];
290        let expected = expected
291            .into_iter()
292            .map(|[lon, lat]| ShapePoint { lat, lon })
293            .collect::<Vec<_>>();
294        assert_eq!(shape, expected);
295    }
296    #[test]
297    fn decode_shape_works_germany() {
298        let shape = decode_shape_polyline6("czaa{AythgU}K_CgFeAiB]mDq@uRoD_Ca@|@aOb@uHd@eIb@gHh@wI`@cHNmChBa[|Cih@fA_RzB^fm@fK~AVbLlBpHnAvMfCvDt@hMzBrOjCtGfArEz@dJvAdC^bC@jH~B^bBXjARvZnFzV|EpNjCrRnDpS~D`Dd@bK`BjEp@lCd@jLxBlI~A~F|QT`Ag@~Ga@pEYrCa@fExA`@~IfCzIjCj{@|Up}@hWlTpHpAbB^`C}Czh@}FgBmCy@sOqEwEjb@o@rFoAdLeAa@yIaDcFiBYdC");
299        // generated via http://valhalla.github.io/demos/polyline/
300        let expected = [
301            [11.670365, 48.268722],
302            [11.670428999999999, 48.268929],
303            [11.670463999999999, 48.269045],
304            [11.670479, 48.269098],
305            [11.670504, 48.269185],
306            [11.670592, 48.2695],
307            [11.670608999999999, 48.269563999999995],
308            [11.670866, 48.269532999999996],
309            [11.671021, 48.269515],
310            [11.671184, 48.269496],
311            [11.671332, 48.269478],
312            [11.671503999999999, 48.269456999999996],
313            [11.67165, 48.269439999999996],
314            [11.671721, 48.269431999999995],
315            [11.67217, 48.269379],
316            [11.672830999999999, 48.2693],
317            [11.673135, 48.269264],
318            [11.673119, 48.269202],
319            [11.672922999999999, 48.268462],
320            [11.672911, 48.268414],
321            [11.672856, 48.268204],
322            [11.672816, 48.268051],
323            [11.672748, 48.267815],
324            [11.672721, 48.267723],
325            [11.672659, 48.267494],
326            [11.672589, 48.267227999999996],
327            [11.672552999999999, 48.267089],
328            [11.672523, 48.266982999999996],
329            [11.672479, 48.266804],
330            [11.672462999999999, 48.266737],
331            [11.672467, 48.266670999999995],
332            [11.672317, 48.26667],
333            [11.672301, 48.266605999999996],
334            [11.672288, 48.266556],
335            [11.672277999999999, 48.266518],
336            [11.672158, 48.266073999999996],
337            [11.672047, 48.265691999999994],
338            [11.671977, 48.265443],
339            [11.671889, 48.265128999999995],
340            [11.671793, 48.2648],
341            [11.671774, 48.264719],
342            [11.671725, 48.264525],
343            [11.6717, 48.264423],
344            [11.671681, 48.264351999999995],
345            [11.671619999999999, 48.264137999999996],
346            [11.671572, 48.263971],
347            [11.671268999999999, 48.263842999999994],
348            [11.671235999999999, 48.263832],
349            [11.671092, 48.263852],
350            [11.670987, 48.263869],
351            [11.670912999999999, 48.263881999999995],
352            [11.670812999999999, 48.263898999999995],
353            [11.670796, 48.263853999999995],
354            [11.670727999999999, 48.263678],
355            [11.670658, 48.263504],
356            [11.670290999999999, 48.262538],
357            [11.669901999999999, 48.261537],
358            [11.669749, 48.261193999999996],
359            [11.669699, 48.261153],
360            [11.669634, 48.261137],
361            [11.668963999999999, 48.261216],
362            [11.669016, 48.261343],
363            [11.669044999999999, 48.261413999999995],
364            [11.66915, 48.26168],
365            [11.668584, 48.261787999999996],
366            [11.668462, 48.261812],
367            [11.668251, 48.261852],
368            [11.668268, 48.261886999999994],
369            [11.668349, 48.26206],
370            [11.668401999999999, 48.262173999999995],
371            [11.668334999999999, 48.262187],
372        ];
373        let expected = expected
374            .into_iter()
375            .map(|[lon, lat]| ShapePoint { lat, lon })
376            .collect::<Vec<_>>();
377        assert_eq!(shape, expected);
378    }
379}
valhalla_client/shapes.rs

valhalla_client/
shapes.rs
