Как декодировать алгоритм полилинии 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

Поскольку это вопрос, не зависящий от языка, я добавлю это решение 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.

ex:

Шаг 5. Если ваше значение chunked (chunks of 5) имеет последний бит '0x1f', то оно отрицательное, и вы должныинвертировать его так: |= ($foo & 0x1f) << $shift;

00000010 00100101 01000011 11100001

4 Сдвиг двоичного значения вправо на один бит:

1111110111011010 10111100 00011110

3 Преобразуйте двоичное значение в десятичное. Помните, что если вы понимаете, что это отрицательное число, вы должны преобразовать его из дополнения до двух, Дополнение до двух : если он был положительным, то просто преобразовать двоичный файл как обычно :

11111110 11101101 01011110 00001111

11111110 11101101 01011110 00001110

00000001 00010010 10100001 11110001 <- наше исходное значение без знака </p>

2 Десятичное значение было умножено на 1e5, поэтому разделите его, чтобы получить начальное значение: 179.98321

1 Добавьте исходное значение к его знаку (если оно необходимо) -179.98321 (это небольшая потеря данных, но она совершенно не имеет значения)