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    // Estimate capacity: polyline6 typically needs 5-10 bytes per coordinate pair
58    let estimated_points = encoded.len() / 8;
59    let mut decoded = Vec::with_capacity(estimated_points);
60    let mut previous = [0, 0];
61    let mut i = 0;
62
63    while i < encoded.len() {
64        // for each coord (lat, lon)
65        let mut ll = [0, 0];
66        for j in [0, 1] {
67            let mut shift = 0;
68            let mut byte = 0x20;
69            // keep decoding bytes until you have this coord
70            while byte >= 0x20 {
71                byte = i32::from(encoded.as_bytes()[i]) - 63;
72                i += 1;
73                ll[j] |= (byte & 0x1f) << shift;
74                shift += 5;
75            }
76            // get the final value adding the previous offset and remember it for the next
77            ll[j] = previous[j]
78                + if (ll[j] & 1) != 0 {
79                    !(ll[j] >> 1)
80                } else {
81                    ll[j] >> 1
82                };
83            previous[j] = ll[j];
84        }
85        // scale by the precision
86        let lon = f64::from(ll[1]) * inv;
87        let lat = f64::from(ll[0]) * inv;
88        debug_assert!((-90.0..90.0).contains(&lat));
89        debug_assert!((-180.0..180.0).contains(&lon));
90        decoded.push(ShapePoint { lon, lat });
91    }
92
93    decoded
94}
95pub(crate) fn deserialize_shape<'de, D>(deserializer: D) -> Result<Vec<ShapePoint>, D::Error>
96where
97    D: serde::Deserializer<'de>,
98{
99    let s = String::deserialize(deserializer)?;
100    Ok(decode_shape_polyline6(&s))
101}
102#[cfg(test)]
103mod tests {
104    use super::*;
105
106    #[test]
107    fn shapepoint_to_geo_types_point() {
108        let sp = ShapePoint {
109            lon: 11.670365,
110            lat: 48.268722,
111        };
112        let pt: geo_types::Point = (&sp).into();
113        assert_eq!(pt.x(), 11.670365);
114        assert_eq!(pt.y(), 48.268722);
115    }
116
117    #[test]
118    fn shapepoint_to_coordinate() {
119        let sp = ShapePoint {
120            lon: 11.670365,
121            lat: 48.268722,
122        };
123        let coord: super::super::Coordinate = sp.into();
124        assert_eq!(coord.0, 11.670365_f32);
125        assert_eq!(coord.1, 48.268722_f32);
126    }
127
128    #[test]
129    fn decode_shape_works_america() {
130        // 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
131        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_@");
132        // generated via http://valhalla.github.io/demos/polyline/
133        let expected = [
134            [-76.781943, 39.991887],
135            [-76.782581, 39.992533],
136            [-76.782759, 39.992692999999996],
137            [-76.78316, 39.992965999999996],
138            [-76.78265499999999, 39.993373999999996],
139            [-76.782563, 39.993438999999995],
140            [-76.782422, 39.9935],
141            [-76.782281, 39.993538],
142            [-76.782122, 39.993542999999995],
143            [-76.782005, 39.993542999999995],
144            [-76.781858, 39.993528999999995],
145            [-76.781735, 39.993496],
146            [-76.781576, 39.993444],
147            [-76.781447, 39.993383],
148            [-76.77987399999999, 39.991943],
149            [-76.779726, 39.99182],
150            [-76.779333, 39.991537],
151            [-76.77924999999999, 39.991468999999995],
152            [-76.779, 39.991236],
153            [-76.779921, 39.99068],
154            [-76.780442, 39.990366],
155            [-76.781846, 39.989519],
156            [-76.783441, 39.988555999999996],
157            [-76.78541299999999, 39.987362999999995],
158            [-76.784506, 39.987117],
159            [-76.78397, 39.986982],
160            [-76.78381399999999, 39.986948],
161            [-76.783639, 39.986917999999996],
162            [-76.783349, 39.986886999999996],
163            [-76.78310499999999, 39.986871],
164            [-76.782849, 39.986851],
165            [-76.782609, 39.986849],
166            [-76.782146, 39.986843],
167            [-76.781967, 39.986841],
168            [-76.78137699999999, 39.986836],
169            [-76.780915, 39.986823],
170            [-76.780722, 39.986833],
171            [-76.780388, 39.986849],
172            [-76.780085, 39.986864],
173            [-76.779907, 39.98688],
174            [-76.77969499999999, 39.986891],
175            [-76.779515, 39.986892],
176            [-76.779158, 39.986892],
177            [-76.779102, 39.986889999999995],
178            [-76.778875, 39.986874],
179            [-76.778835, 39.986869999999996],
180            [-76.778425, 39.986821],
181            [-76.776997, 39.986610999999996],
182            [-76.774501, 39.986405],
183            [-76.773206, 39.986315999999995],
184            [-76.772842, 39.986298999999995],
185            [-76.771687, 39.986244],
186            [-76.771024, 39.9862],
187            [-76.770206, 39.986067999999996],
188            [-76.769379, 39.985932999999996],
189            [-76.76888799999999, 39.985791],
190            [-76.768565, 39.985656999999996],
191            [-76.768517, 39.985628999999996],
192            [-76.768096, 39.985386],
193            [-76.76801499999999, 39.985319],
194            [-76.767838, 39.98517],
195            [-76.76738999999999, 39.984660999999996],
196            [-76.767087, 39.984161],
197            [-76.766685, 39.983543],
198            [-76.766505, 39.983281],
199            [-76.766346, 39.983094],
200            [-76.766145, 39.982928],
201            [-76.76599499999999, 39.982825999999996],
202            [-76.76583699999999, 39.982732],
203            [-76.765676, 39.982642999999996],
204            [-76.765548, 39.982585],
205            [-76.76543699999999, 39.982541],
206            [-76.765317, 39.9825],
207            [-76.765188, 39.982464],
208            [-76.765029, 39.982425],
209            [-76.764872, 39.982394],
210            [-76.764668, 39.98236],
211            [-76.763193, 39.982136],
212            [-76.763036, 39.982105],
213            [-76.76290999999999, 39.982077],
214            [-76.762812, 39.98205],
215            [-76.762663, 39.981998],
216            [-76.762509, 39.981930999999996],
217            [-76.762391, 39.981860999999995],
218            [-76.762298, 39.981798],
219            [-76.761881, 39.981497],
220            [-76.761738, 39.981394],
221            [-76.761635, 39.98132],
222            [-76.76120499999999, 39.98101],
223            [-76.76048399999999, 39.980505],
224            [-76.760256, 39.980273],
225            [-76.760144, 39.980194],
226            [-76.759456, 39.979712],
227            [-76.75914, 39.979490999999996],
228            [-76.758684, 39.979171],
229            [-76.758583, 39.97909],
230            [-76.758493, 39.979003],
231            [-76.758358, 39.978859],
232            [-76.758127, 39.978612],
233            [-76.75803499999999, 39.978507],
234            [-76.75789499999999, 39.978545],
235            [-76.75757899999999, 39.978626999999996],
236            [-76.757221, 39.978722999999995],
237            [-76.75684199999999, 39.978809999999996],
238            [-76.75649899999999, 39.978888],
239            [-76.755431, 39.979164999999995],
240            [-76.753177, 39.979751],
241            [-76.752329, 39.979971],
242            [-76.750045, 39.980577],
243            [-76.74834299999999, 39.981018],
244            [-76.747249, 39.981272],
245            [-76.746693, 39.981401999999996],
246            [-76.746545, 39.981435],
247            [-76.74569699999999, 39.981624],
248            [-76.744897, 39.981795],
249            [-76.7441, 39.981987],
250            [-76.74368, 39.982084],
251            [-76.74346299999999, 39.982141],
252            [-76.742583, 39.98238],
253            [-76.741817, 39.982668],
254            [-76.740813, 39.983046],
255            [-76.739983, 39.983418],
256            [-76.739509, 39.983632],
257            [-76.739346, 39.983706],
258            [-76.73844299999999, 39.984114999999996],
259            [-76.737957, 39.98423],
260            [-76.73746299999999, 39.984241999999995],
261            [-76.736882, 39.984175],
262            [-76.736854, 39.984172],
263            [-76.736284, 39.983999999999995],
264            [-76.7362, 39.983975],
265            [-76.735299, 39.983703],
266            [-76.735165, 39.983666],
267            [-76.734956, 39.983607],
268            [-76.73483999999999, 39.983588],
269            [-76.734252, 39.98355],
270            [-76.73411899999999, 39.983554],
271            [-76.733924, 39.983562],
272            [-76.733314, 39.983588],
273            [-76.73317, 39.983609],
274            [-76.732496, 39.983708],
275            [-76.73238099999999, 39.983723999999995],
276            [-76.731715, 39.983816999999995],
277            [-76.73088899999999, 39.983917],
278            [-76.730454, 39.983934],
279            [-76.729387, 39.983975],
280            [-76.728121, 39.983999],
281            [-76.72793, 39.983981],
282            [-76.72662199999999, 39.983944],
283            [-76.72410099999999, 39.983872],
284            [-76.722493, 39.983799],
285            [-76.722411, 39.983793999999996],
286            [-76.722166, 39.983779999999996],
287            [-76.72138, 39.983737999999995],
288            [-76.72043099999999, 39.983689],
289            [-76.71968, 39.98366],
290            [-76.71895599999999, 39.983626],
291            [-76.71857, 39.983596999999996],
292            [-76.717469, 39.983443],
293            [-76.71678399999999, 39.983312999999995],
294            [-76.715773, 39.983062],
295            [-76.715603, 39.983019999999996],
296            [-76.71525799999999, 39.982934],
297            [-76.71492599999999, 39.982847],
298            [-76.714286, 39.982704],
299            [-76.713681, 39.982563999999996],
300            [-76.712846, 39.982431999999996],
301            [-76.711569, 39.982336],
302            [-76.71029, 39.982321999999996],
303            [-76.70825599999999, 39.982309],
304            [-76.70820499999999, 39.982445],
305            [-76.708035, 39.982603999999995],
306            [-76.707956, 39.982813],
307            [-76.70787299999999, 39.983046],
308            [-76.707923, 39.983132999999995],
309            [-76.707904, 39.983193],
310            [-76.70787299999999, 39.983309999999996],
311            [-76.707803, 39.983546],
312            [-76.70768, 39.983872],
313            [-76.707664, 39.983914],
314        ];
315        let expected = expected
316            .into_iter()
317            .map(|[lon, lat]| ShapePoint { lat, lon })
318            .collect::<Vec<_>>();
319        assert_eq!(shape, expected);
320    }
321    #[test]
322    fn decode_shape_works_germany() {
323        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");
324        // generated via http://valhalla.github.io/demos/polyline/
325        let expected = [
326            [11.670365, 48.268722],
327            [11.670428999999999, 48.268929],
328            [11.670463999999999, 48.269045],
329            [11.670479, 48.269098],
330            [11.670504, 48.269185],
331            [11.670592, 48.2695],
332            [11.670608999999999, 48.269563999999995],
333            [11.670866, 48.269532999999996],
334            [11.671021, 48.269515],
335            [11.671184, 48.269496],
336            [11.671332, 48.269478],
337            [11.671503999999999, 48.269456999999996],
338            [11.67165, 48.269439999999996],
339            [11.671721, 48.269431999999995],
340            [11.67217, 48.269379],
341            [11.672830999999999, 48.2693],
342            [11.673135, 48.269264],
343            [11.673119, 48.269202],
344            [11.672922999999999, 48.268462],
345            [11.672911, 48.268414],
346            [11.672856, 48.268204],
347            [11.672816, 48.268051],
348            [11.672748, 48.267815],
349            [11.672721, 48.267723],
350            [11.672659, 48.267494],
351            [11.672589, 48.267227999999996],
352            [11.672552999999999, 48.267089],
353            [11.672523, 48.266982999999996],
354            [11.672479, 48.266804],
355            [11.672462999999999, 48.266737],
356            [11.672467, 48.266670999999995],
357            [11.672317, 48.26667],
358            [11.672301, 48.266605999999996],
359            [11.672288, 48.266556],
360            [11.672277999999999, 48.266518],
361            [11.672158, 48.266073999999996],
362            [11.672047, 48.265691999999994],
363            [11.671977, 48.265443],
364            [11.671889, 48.265128999999995],
365            [11.671793, 48.2648],
366            [11.671774, 48.264719],
367            [11.671725, 48.264525],
368            [11.6717, 48.264423],
369            [11.671681, 48.264351999999995],
370            [11.671619999999999, 48.264137999999996],
371            [11.671572, 48.263971],
372            [11.671268999999999, 48.263842999999994],
373            [11.671235999999999, 48.263832],
374            [11.671092, 48.263852],
375            [11.670987, 48.263869],
376            [11.670912999999999, 48.263881999999995],
377            [11.670812999999999, 48.263898999999995],
378            [11.670796, 48.263853999999995],
379            [11.670727999999999, 48.263678],
380            [11.670658, 48.263504],
381            [11.670290999999999, 48.262538],
382            [11.669901999999999, 48.261537],
383            [11.669749, 48.261193999999996],
384            [11.669699, 48.261153],
385            [11.669634, 48.261137],
386            [11.668963999999999, 48.261216],
387            [11.669016, 48.261343],
388            [11.669044999999999, 48.261413999999995],
389            [11.66915, 48.26168],
390            [11.668584, 48.261787999999996],
391            [11.668462, 48.261812],
392            [11.668251, 48.261852],
393            [11.668268, 48.261886999999994],
394            [11.668349, 48.26206],
395            [11.668401999999999, 48.262173999999995],
396            [11.668334999999999, 48.262187],
397        ];
398        let expected = expected
399            .into_iter()
400            .map(|[lon, lat]| ShapePoint { lat, lon })
401            .collect::<Vec<_>>();
402        assert_eq!(shape, expected);
403    }
404}
valhalla_client/shapes.rs

valhalla_client/
shapes.rs
