Как преобразовать в формат закодированного алгоритмом полилинии Google? - PullRequest
3 голосов
/ 15 февраля 2012

Формат полилинии для карт Google хранит информацию о широте и долготе, а также уровни масштабирования.

У меня огромный текстовый файл с парами широта / долгота, который я хочу преобразовать в этот формат и для различных секций полилиний (т.е. мне нужно выполнить пакетное преобразование)

Кто-нибудь знает код, выполняющий эту операцию?

Ответы [ 5 ]

7 голосов
/ 23 мая 2012

Окончательная ссылка на полилинии кодирования и декодирования дана профессором Марком МакКлюром по адресу http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/

. Содержит утилиты, обсуждение алгоритма и портов кода Javascript на Perl, Ruby, PHP, Java.и Mathematica.

Примечание: для Версии 3 вам не нужна строка levels, которая необходима для Версии 2. Версия 3 сама определяет уровни.

5 голосов
/ 23 мая 2012

Я не знаю, на каком языке он вам нужен. Вы можете получить общее представление от Google здесь .Однако я обнаружил, что инструкции не на 100% точны.Вот как я это понял, используя пример в том же тексте.Я реализовал его на Java, и его должно быть довольно легко преобразовать в JavaScript или PHP.

  public class MapMath {
    private final static double MULTIPLIER = 100000;
    private final static int FIVE_BIT_MASK = 0x1f;

    public MapMath() {
      double[][] coords = new double[][]{
        {-12.422187,130.854922},
          {-12.422445,130.854937},
          {-12.422234,130.854886}
      };

      StringBuilder encodedStrings = new StringBuilder();
      for (int i = 0; i < 3; i++){
        encodedStrings.append(
            encodeCoordinate(coords[i][0]) + 
            encodeCoordinate(coords[i][1]) + "\n"
            );
      }
      System.out.println(encodedStrings);
    }

    private String encodeCoordinate(double coordinate) {
      StringBuilder encodedCoordinate = new StringBuilder();
      boolean hasNext;

      coordinate *= MULTIPLIER;
      int value = (int) coordinate;
      value <<= 1;
      if(coordinate < 0) value = ~value;  

      do {
        int next = (value >> 5);
        hasNext = (next > 0);
        int encVal = value & FIVE_BIT_MASK;
        if(hasNext) encVal |= 0x20;
        encVal += 0x3f;
        value = next;
        encodedCoordinate.append((char)(encVal));
      } while (hasNext);

      return encodedCoordinate.toString();
    } 

    public static double toRadians(double degrees) {
      return (degrees*Math.PI)/180;
    }

    public static void main(String[] args){
      new MapMath();
    }
  }

Обратите внимание, что последовательные координаты должны быть смещены относительно предыдущей.Надеюсь, что это было полезно для вас, и, пожалуйста, дайте мне знать, если понадобится дополнительная помощь в этом.

2 голосов
/ 27 марта 2013

Здесь есть хорошая реализация на PHP:

https://github.com/tonydspaniard/Yii-extensions/blob/master/extensions/EGMap/EGMapPolylineEncoder.php

Он основан на некотором коде, доступном в http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/, но отшлифован до надлежащего класса.

2 голосов
/ 15 декабря 2012

Я также видел некоторые менее точные реализации алгоритма (с некоторым довольно плохим кодом тоже).Это моя функция кодирования (написана на VB.NET).Эта функция кодирует только одно переданное ей значение, поэтому вам придется выполнять все вычисления различий в другом месте.Возвращенные результаты в точности соответствуют результатам, показанным на странице Кодированного полилинейного алгоритма Google.(Часть моего кода могла быть сжатой и оптимизированной, но я попытался прояснить каждый шаг алгоритма).Я надеюсь, что кто-то найдет это полезным!

''' <summary>
''' Encodes a latitude or longitude value by using Google's Polyline algorithm
''' </summary>
''' <param name="ToEnc">Latitude or Longitude to encode (or a difference value) (Single)</param>
''' <returns>Polyline encoded point (String)</returns>
''' <remarks>This function doesn't care what value you pass it, whether it's an absolute coordinate or a difference.  Make sure you do all of the point difference calculations somewhere else before calling this method.</remarks>
Private Function Encode(ByVal ToEnc As Single) As String
    Dim Coord As Integer 'The integer version of the coordinate, as per steps 2 and 3
    Dim B(5) As Byte 'The 5-bit chunks, as per steps 6 and 7.  Note that all 6 bytes may not be used
    Dim I As Integer 'Generic counter
    Dim C(5) As Char 'The chunks converted from bytes to characters

    '2., 3. Take the decimal value and multiply is by 1e5, rounding the result.  Convert the decimal value to binary.
    Coord = Math.Sign(ToEnc) * Int(Math.Abs(ToEnc) * 100000.0)

    '4. Left-shift the binary value one bit
    Coord <<= 1

    '5. If the original decimal value is negative, invert this encoding
    If ToEnc < 0 Then Coord = Not Coord

    '6. Break the binary value out into 5-bit chunks (starting from the right hand side)
    '7. Place the 5-bit chunks in reverse order
    'Steps 6 and 7 are done at the same time
    B(0) = Coord And &H1F
    B(1) = (Coord And &H3E0) >> 5
    B(2) = (Coord And &H7C00) >> 10
    B(3) = (Coord And &HF8000) >> 15
    B(4) = (Coord And &H1F00000) >> 20
    B(5) = (Coord And &H3E000000) >> 25

    '8. OR each value with 0x20 if another bit chunk follows
    'Go through the 5-bit chunks looking for the first one that isn't zero
    'When we find it, that means the one BEFORE that is the last to get the 0x20 modification
    Dim E As Integer = -1 'Penultimate byte that contains data, the last one to get ORed by 0x20
    For I = 5 To 1 Step -1
        If B(I) <> 0 Then
            'This is the first nonzero value we've encountered, so keep track of this position and exit the loop
            E = I - 1
            Exit For
        End If
    Next
    'Apply the 0x20 modification
    For I = 0 To E
        B(I) = B(I) Or &H20
    Next

    '10. Add 63 to each value
    For I = 0 To 5
        If B(I) > 0 Then B(I) += 63
    Next

    '11. Convert each value to its ASCII equivalent
    For I = 0 To 5
        C(I) = Chr(B(I))
    Next

    'Turn the char array into a string and return it
    Return New String(C, 0, E + 2)
End Function
1 голос
/ 14 ноября 2013

Спасибо, Джонатан, с некоторыми изменениями, моя версия VBA здесь ... сдвиг битов, взятый отсюда ... http://www.excely.com/excel-vba/bit-shifting-function.shtml#.UoUFM8ZSiSo

   ''' <summary>
''' Encodes a latitude or longitude value by using Google's Polyline algorithm
''' </summary>
''' <param name="ToEnc">Latitude or Longitude to encode (or a difference value) (Single)</param>
''' <returns>Polyline encoded point (String)</returns>
''' <remarks>This function doesn't care what value you pass it, whether it's an absolute coordinate or a difference.  Make sure you do all of the point difference calculations somewhere else before calling this method.</remarks>
Function Encode(ByVal ToEnc As Single) As String
    Dim Coord As Double 'The integer version of the coordinate, as per steps 2 and 3
    Dim B(5) As Byte 'The 5-bit chunks, as per steps 6 and 7.  Note that all 6 bytes may not be used
    Dim i As Integer 'Generic counter
    Dim C(5) As String 'The chunks converted from bytes to characters
    Dim E As Integer
    E = -1 'Penultimate byte that contains data, the last one to get ORed by 0x20

    '2., 3. Take the decimal value and multiply is by 1e5, rounding the result.  Convert the decimal value to binary.
    Coord = Math.Sgn(ToEnc) * Int(Math.Abs(ToEnc) * 100000)

    '4. Left-shift the binary value one bit
    Coord = shl(Coord, 1)

    '5. If the original decimal value is negative, invert this encoding
    If ToEnc < 0 Then Coord = Not Coord

    '6. Break the binary value out into 5-bit chunks (starting from the right hand side)
    '7. Place the 5-bit chunks in reverse order
    'Steps 6 and 7 are done at the same time
    B(0) = Coord And &H1F
    B(1) = shr((Coord And &H3E0), 5)
    B(2) = shr((Coord And &H7C00), 10)
    B(3) = shr((Coord And &HF8000), 15)
    B(4) = shr((Coord And &H1F00000), 20)
    B(5) = shr((Coord And &H3E000000), 25)

    '8. OR each value with 0x20 if another bit chunk follows
    'Go through the 5-bit chunks looking for the first one that isn't zero
    'When we find it, that means the one BEFORE that is the last to get the 0x20 modification
    For i = 5 To 1 Step -1
        If B(i) <> 0 Then
            'This is the first nonzero value we've encountered, so keep track of this position and exit the loop
            E = i - 1
            Exit For
        End If
    Next
    'Apply the 0x20 modification
    For i = 0 To E
        B(i) = B(i) Or &H20
    Next

    '10. Add 63 to each value
    For i = 0 To 5
        If B(i) > 0 Then B(i) = B(i) + 63
    Next

    '11. Convert each value to its ASCII equivalent
    For i = 0 To 5
        C(i) = Chr(B(i))
    Encode = Encode + C(i)
    Next

    'Turn the char array into a string and return it
 End Function

Public Function shr(ByVal Value As Long, ByVal Shift As Byte) As Long
    Dim i As Byte
    shr = Value
    If Shift > 0 Then
        shr = Int(shr / (2 ^ Shift))
    End If
End Function
Public Function shl(ByVal Value As Long, ByVal Shift As Byte) As Long
    shl = Value
    If Shift > 0 Then
        Dim i As Byte
        Dim m As Long
        For i = 1 To Shift
            m = shl And &H40000000
            shl = (shl And &H3FFFFFFF) * 2
            If m <> 0 Then
                shl = shl Or &H80000000
            End If
        Next i
    End If
End Function
...