The encoded polyline format for Google maps stores lat/lon information as well as zoom levels.
I have a huge text file with lat/lon pairs that i want to convert to this format and for different sections of polylines (i.e. i need to perform a batch conversion)
Does anyone know of a code that performs this operation ?
The definitive reference to encoding and decoding polylines is by Professor Mark McClure, at http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/
It contains utilities, a discussion of the algorithm and ports of the Javascript code into Perl, Ruby, PHP, Java and Mathematica.
Note: for Version 3, you don't need the levels string which is needed for Version 2. Version 3 works out the levels for itself.
I do not know what language you need it in. You can get the general idea from Google here. However, I found the instructions not being 100% accurate. This is how I understood it, using the example in the same text. I implemented it in Java, and it should be quite easy to convert to JavaScript or 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();
}
}
Note that consecutive coordinates should be an offset from the previous one. Hope it was useful to you, and please let me know if need any further assistance with this.
I've also seen some less-than accurate implementations of the algorithm (with some pretty bad code, too). This is my encoding function (written in VB.NET). This function only encodes one value passed to it, so you'll have to do all of the difference calculations elsewhere. The results returned exactly match those shown on Google's Encoded Polyline Algorithm Format page. (Some of my code could be condensed and optimized, but I tried to make each step of the algorithm clear). I hope that someone finds this useful!
''' <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
There's a nice implementation in PHP here:
It's based on some of the code available on http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/ but polished into a proper class.
Thanks Jonathan, With some tweaks, my VBA Version here.... bitshifting taken from here... 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
