如何解码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;
 }
}

Answer 2

由于这是一个与语言无关的问题，我将添加来自

Peter Chng 的 unitstep 博客

的 PHP 解决方案（因为 PHP 中不存在 >>> 运算符）：

function decodePolylineToArray($encoded)
{
  $length = strlen($encoded);
  $index = 0;
  $points = array();
  $lat = 0;
  $lng = 0;

  while ($index < $length)
  {
    $b = 0;
    $shift = 0;
    $result = 0;
    do
    {
      $b = ord(substr($encoded, $index++)) - 63;
      $result |= ($b & 0x1f) << $shift;
      $shift += 5;
    }
    while ($b >= 0x20);
    $dlat = (($result & 1) ? ~($result >> 1) : ($result >> 1));
    $lat += $dlat;

    $shift = 0;
    $result = 0;
    do
    {
      $b = ord(substr($encoded, $index++)) - 63;
      $result |= ($b & 0x1f) << $shift;
      $shift += 5;
    }
    while ($b >= 0x20);

    $dlng = (($result & 1) ? ~($result >> 1) : ($result >> 1));
    $lng += $dlng;

    $points[] = array($lat * 1e-5, $lng * 1e-5);
  }
  return $points;
}

Google 开发人员的其他说明

更新： 解码指令几乎很简单，为了找到原始值，您可以通过已从 ASCII 字符转换的每个值的最后一位来计算它是正数还是负数。

例如：

第 5 步。如果您的值分块（5 块）的最后一位为“0x1f”，那么它是负数，您应该将其反转 如：

|= ($foo & 0x1f) << $shift;

00000010 00100101 01000011 11100001

4 将二进制值右移一位：

11111101 11011010 10111100 00011110

3 将二进制值转换为十进制，请记住，如果您意识到这是一个负数，那么您必须将其从二进制补码转换为，二进制补码：如果它是正数，则像往常一样转换二进制：

11111110 11101101 01011110 00001111

11111110 11101101 01011110 00001110

00000001 00010010 10100001 11110001 <-- our original value unsigned

2 小数值乘以 1e5，除以得到初始值： 179.98321

1 添加原始值及其符号（如果需要） -179.98321 （这会丢失一点数据，但无关紧要）

Answer 3

这是我的（经过测试、有效的）C# 解决方案：

public static List<Point<double>> DecodeGooglePolyline(string s)
{
    // Decode the sequence of integers
    var integers = new List<long>();

    for (int i = 0; i < s.Length;) {
        long zzInteger = 0;

        for (int shift = 0; i < s.Length; shift += 5) {
            int sixBits = s[i++] - 63;
            if ((uint)sixBits > 63)
                throw new FormatException("Invalid character in Google polyline");

            zzInteger |= ((uint)sixBits & 0b0001_1111) << shift;

            if (sixBits < 32)
                break;
        }

        integers.Add((zzInteger & 1) != 0 ? ~(zzInteger >> 1) : zzInteger >> 1);
    }

    Debug.Assert((integers.Count & 1) == 0);

    // Convert the sequence of integers to points
    var points = new List<Point<double>>();
    var point = new Point<double>(0, 0);
    for (int i = 0; i + 1 < integers.Count; i += 2) {
        point = new Point<double>(point.X + integers[i + 1] / 1e5, point.Y + integers[i] / 1e5);
        points.Add(point);
    }

    return points;
}

注意：C# 缺少“标准”点类型，因此请替换为您选择的类型。