如何解码Google的折线算法？

Question

Google 的编码折线算法格式：

你如何解码这个？

也许向后运行算法；但我陷入了第 5 步：没有初始值，我如何知道它是正值还是负值？

Answer 1

如果为负，其编码左移然后反转，例如：

1: 0000_0001 =>0000_0010
2: 0000_0010 =>0000_0100
3: 0000_0011 =>0000_0110
4: 0000_0100 =>0000_1000
5: 0000_0101 =>0000_1010
6: 0000_0110 =>0000_1100
7: 0000_0111 =>0000_1110
8: 0000_1000 =>0001_0000

-1: 1111_1111 =>1111_1110 =>0000_0001
-2: 1111_1110 =>1111_1100 =>0000_0011
-3: 1111_1101 =>1111_1010 =>0000_0101
-4: 1111_1100 =>1111_1000 =>0000_0111
-5: 1111_1011 =>1111_0110 =>0000_1001
-6: 1111_1010 =>1111_0100 =>0000_1011
-7: 1111_1001 =>1111_0010 =>0000_1101
-8: 1111_1000 =>1111_0000 =>0000_1111

因此，如果最后一位是0，则解码为 ，则初始为正，如果最后一位为1，则初始为负。

附录：

完整解码演示：

public class Test {
 public static void main(String args[]) {
  for (int point : Decode("_p~iF~ps|U_ulLnnqC_mqNvxq`@",10)) {
   System.out.println(point); // Be aware that point is in E5
  }
 }

 private static java.util.List<java.lang.Integer> Decode(String encoded_polylines, int initial_capacity) {
  java.util.List<java.lang.Integer> trucks = new java.util.ArrayList<java.lang.Integer>(initial_capacity);
  int truck = 0;
  int carriage_q = 0;
  for (int x = 0, xx = encoded_polylines.length(); x < xx; ++x) {
   int i = encoded_polylines.charAt(x);
   i -= 63;
   int _5_bits = i << (32 - 5) >>> (32 - 5);
   truck |= _5_bits << carriage_q;
   carriage_q += 5;
   boolean is_last = (i & (1 << 5)) == 0;
   if (is_last) {
    boolean is_negative = (truck & 1) == 1;
    truck >>>= 1;
    if (is_negative) {
     truck = ~truck;
    }
    trucks.add(truck);
    carriage_q = 0;
    truck = 0;
   }
  }
  return trucks;
 }
}