如何轉換爲Google編碼的折線算法格式？

Question

谷歌地圖的encoded polyline format存儲緯度/經度信息以及縮放級別。

我有，我要轉換爲這個格式和折線的不同部分經/緯度對一個巨大的文本文件（即我需要進行批量轉換）

有誰知道的代碼，執行此操作？

Answer 1

的權威參考編碼和解碼折線是由馬克·麥克盧爾教授，http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/

它包含水電費，算法和Javascript代碼的端口轉換爲Perl和Ruby，PHP，Java和數學的討論。

注意：對於版本3，您不需要版本2所需的levels字符串。版本3爲其自身計算出等級。

Answer 2

我不知道你需要什麼語言。你可以從Google here得到大致的想法。但是，我發現這些說明不是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(); 
    } 
    } 

請注意，連續座標應該是從前一個偏移量。 希望它對你有用，請讓我知道是否需要任何進一步的援助。

Answer 3

我也看到了一些算法不夠精確的實現（也有一些非常糟糕的代碼）。這是我的編碼功能（用VB.NET編寫）。此函數僅對傳遞給它的一個值進行編碼，因此您必須在其他地方執行所有差異計算。返回的結果與Google的Encoded Polyline Algorithm Format頁面上顯示的結果完全一致。 （我的一些代碼可以被壓縮和優化，但我試圖使算法的每一步都清楚）。我希望有人認爲這有用！

''' <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 

Answer 4

有一個在PHP的一個好點的實現：

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

它是基於一些可在http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/但打磨的代碼放到一個適當的類。

Answer 5

感謝喬納森， 一些調整，我的VBA版本在這裏.... bitshifting取自這裏... 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