Google Maps Line Encoder

So, I made a few cheesy posts to this cheesy blog when I started it, and then haven't done anything since. I figured I'd post something useful and see what happens. The below is a class I created some time ago in java for encoding google line objects for the google maps api. It compresses them to a more efficient version that can be directly added to a google map using the JavaScript API. The algorithm is specific to google, and I believe it was published somewhere by google and is pasted in the code comments below. Originally I was pulling the line objects as Lat/Long arrays from a GPS unit, and I would then convert them the the encoded size to save on bandwidth when pulling them to the page to display on the map. I haven't messed with this for a couple years, but maybe it will be of value to someone.

import freemarker.template.utility.StringUtil;
import lambo.gis.Point;   //this point class is very basic, just a lat/long deciaml values.

/**
 * 
 * @author Scott Lambeth
 *
 * Creating an encoder for the google maps GPolyLine class, from their API here
 * is the algorithm for performing the encoding:
 * 
 * The steps for encoding such a signed value are specified below.
 *
 *  1. Take the initial signed value:
 *     -179.9832104
 *  2. Take the decimal value and multiply it by 1e5, rounding the result:
 *     -17998321
 *  3. Convert the decimal value to binary. Note that a negative value must be calculated using its two's complement by inverting the binary value and adding one to the result:
 *     00000001 00010010 10100001 11110001
 *     11111110 11101101 01011110 00001110
 *     11111110 11101101 01011110 00001111
 *  4. Left-shift the binary value one bit:
 *     11111101 11011010 10111100 00011110
 *  5. If the original decimal value is negative, invert this encoding:
 *     00000010 00100101 01000011 11100001
 *  6. Break the binary value out into 5-bit chunks (starting from the right hand side):
 *     00001 00010 01010 10000 11111 00001
 *  7. Place the 5-bit chunks into reverse order:
 *     00001 11111 10000 01010 00010 00001
 *  8. OR each value with 0x20 if another bit chunk follows:
 *     100001 111111 110000 101010 100010 000001
 *  9. Convert each value to decimal:
 *     33 63 48 42 34 1
 * 10. Add 63 to each value:
 *     96 126 111 105 97 64
 * 11. Convert each value to its ASCII equivalent:
 *     `~oia@

 */
public class LineEncoder {
 
 
 public static String encodeTrack(Point[] points) {
  String sEncVal = "";
  long lLastLat = 0;
  long lLastLng = 0;
  
  for(Point point : points) {
   
   //the encoded line expects to only represent change from point to point
   long lLat = Math.round(point.getLat() * 1e5);
   long lLng = Math.round(point.getLng() * 1e5);
   long lLatChange = lLat - lLastLat;
   long lLngChange = lLng - lLastLng;
   
   //System.out.println(lLastLat + ", " + lLastLng);
   //only calculate change
   
   
   sEncVal += (encodeLong(lLatChange) + encodeLong(lLngChange));
   /*
   String sTest = (PolylineEncoder.encodeNumber((int)lLatChange) + PolylineEncoder.encodeNumber((int)lLngChange));
   if(sTest.equals(sEncVal)) {
    System.err.printf("%s does not equal %s", sEncVal, sTest);
   }
   */
   
   lLastLat = lLat;
   lLastLng = lLng;
  }  
  return sEncVal;
 }
 
 public static String encodeLong(long Value) {
  
  //Steps 2-4 of the encoding algorithm can be accomplished with this:
  Value = Value << 1;

  //Step 5 can be accomplished with the XOR operator
  if(Value < 0) {
   Value = ~Value;
  }

  //Convert the shifted integer to its binary representation
  String binary = Long.toBinaryString(Value);
  
  //6. Break the binary value out into 5-bit chunks (starting from the right hand side):
  //We'll accmoplish this by simply padding the start of the string with leading 0s to get an even multiplier of 5
  int iRemainder = binary.length() % 5;
  if(iRemainder > 0) {
   int iMinLen = binary.length() + (5 - (binary.length() % 5));
   binary = StringUtil.leftPad(binary, iMinLen, '0');
  }
  
  //So, we've evenly padded it to multiples of 5, lets clear any leading 0 bytes that are not needed.
  int iFirst1 = binary.indexOf("1");
  //step back from the first 0 bit to a position which will get even 5 bit bytes to the end of the string
  int iStartNDX = iFirst1 - (iFirst1 % 5);
  binary = binary.substring(iStartNDX, binary.length());
  //System.out.println(binary);
  
  //Steps 7, 8, and 9, reverse the 5 bit chunks, convert to number, add 63, then convert to char.
  char[] cEncodedChars = new char[(int)binary.length()/5];
  
  boolean b5BitByteRem = false;
  int iCharNDX=0;
  for(int ndx = binary.length() - 5; ndx >=0; ndx -= 5) {
   String s5BitByte = binary.substring(ndx, ndx + 5);

   long lVal = Long.parseLong(s5BitByte, 2);
   //8. OR each value with 0x20 if another bit chunk follows (with we don't OR the last one)
   if(iCharNDX < cEncodedChars.length-1) { 
    lVal = (lVal|0x20);
   }
   
   cEncodedChars[iCharNDX] = (char)(lVal+63); 
   //System.out.println(s5BitByte + " = " + Long.toBinaryString(lVal) + " = " + lVal + " + 63 = " + (lVal+63) +  " = " + cEncodedChars[iCharNDX]);
   iCharNDX++;
  }
  
  String sEncodedStr = String.valueOf(cEncodedChars);
   
  return sEncodedStr;
 }
 
 public static void main(String[] args) {
  LineEncoder encoder = new LineEncoder();
  
  Point[] points = new Point[3];
  points[0] = new Point(38.5, -120.2);
  points[1] = new Point(40.7, -120.95);
  points[2] = new Point(43.252, -126.453);
  
  
  System.out.println(encoder.encodeTrack(points));
  
  
  //System.out.println(encoder.encodeLong(-12020000));
  
 }
}