https://developers.google.com/maps/documentation/utilities/polylinealgorithm
| 35 | |
| 36 | // https://developers.google.com/maps/documentation/utilities/polylinealgorithm |
| 37 | std::int32_t decode_polyline_integer(std::string::const_iterator &first, |
| 38 | std::string::const_iterator last) |
| 39 | { |
| 40 | // varint coding parameters |
| 41 | const std::uint32_t bits_in_chunk = 5; |
| 42 | const std::uint32_t continuation_bit = 1 << bits_in_chunk; |
| 43 | const std::uint32_t chunk_mask = (1 << bits_in_chunk) - 1; |
| 44 | |
| 45 | std::uint32_t result = 0; |
| 46 | for (std::uint32_t value = continuation_bit, shift = 0; |
| 47 | (value & continuation_bit) && (shift < CHAR_BIT * sizeof(result) - 1) && first != last; |
| 48 | ++first, shift += bits_in_chunk) |
| 49 | { |
| 50 | value = *first - 63; // convert ASCII coding [?..~] to an integer [0..63] |
| 51 | result |= (value & chunk_mask) << shift; |
| 52 | } |
| 53 | |
| 54 | // change "zig-zag" sign coding to two's complement |
| 55 | result = ((result & 1) == 1) ? ~(result >> 1) : (result >> 1); |
| 56 | return static_cast<std::int32_t>(result); |
| 57 | } |
| 58 | } // namespace osrm::engine::detail |