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));
  
 }
}

Java Upload Servlet

This week I'm providing a simple example of a java servlet that can process uploaded files from a multi part web form post.

I'm using the FileUpload component provided by the Apache Commons project. I've tried a few other packages, but this appears to be the most straight forward technique I've found. Most of the heavy lifting has been abstracted for you by the Apache team.

The classes in use below are found in the commons-fileupload-X.X.X.jar (1.2.1 currently) library which can be downloaded from the FileUpload component page on the apache commons website. This library itself is dependent on the Apache Commons - IO component.

Here is the example Servlet:

package com.blogspot.codingitforward.servlets;

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;

import java.util.List;

import javax.servlet.*;
import javax.servlet.http.*;

import org.apache.commons.fileupload.FileItem;
import org.apache.commons.fileupload.FileItemFactory;
import org.apache.commons.fileupload.FileUploadException;
import org.apache.commons.fileupload.disk.DiskFileItemFactory;
import org.apache.commons.fileupload.servlet.ServletFileUpload;

public class FileUploadServlet extends HttpServlet {
  private static final String CONTENT_TYPE = "text/html; charset=windows-1252";

  public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, 
                                                                                      IOException {
    response.setContentType(CONTENT_TYPE);
    PrintWriter out = response.getWriter();
    response.setContentType(CONTENT_TYPE);

    //Simply getting the user's home directory so we have a place to write the files.
    String sUserDir = System.getProperty("user.home") + System.getProperty("file.separator");

    //Create a new instance of the file factory.
    FileItemFactory factory = new DiskFileItemFactory();
    //Initialize your file upload parser
    ServletFileUpload upload = new ServletFileUpload(factory);

    try {
      //Parse the request, it returns a List, containing FileItem objects
      List<FileItem> fileItems = upload.parseRequest(request);

      //process the files
      for (FileItem fileItem: fileItems) {
        //This is a simple way to save them to disk, but you
        //could also just process the files by getting the input stream right 
        //from FileItem
        File persistedFile = new File(sUserDir + fileItem.getName());
        fileItem.write(persistedFile);

        out.println("
Recieved file: " + fileItem.getName());
        out.println("Size: " + fileItem.getSize());
        out.println("Saved To: " + persistedFile.getPath() + "\n
");
      }
    } catch (FileUploadException fileEx) {
      fileEx.printStackTrace();
      throw new ServletException("Error parsing uploaded files", fileEx);
    } catch (Exception ex) {
      ex.printStackTrace();
      throw new ServletException("Error saving files on server", ex);
    }
  }
}

In order to test this servlet I created a simple HTML form to post the files:

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>

  <head>

    <title>uploadFile</title>

  </head>

  <body>

<form action="fileUploadServlet" method="post" enctype="multipart/form-data">

      

   <p>

   Upload File 1: <input type="file" name="fileTest"/><br/>

   Upload File 2: <input type="file" name="fileTest"/>

   <p>

   <input type="submit" />

    </form>  

  </body>

</html>

In my next blog entry, I'll be creating a process using a java client to push files using libraries from the latest HttpClient package - a project that has branched off from the apache commons project.

Forward

Coding it forward. In other words, I'm here to share what I've likely learned from others in this world of ones and zeros. I often find myself scouring the internet for solutions to problems that seem very complicated, but in the end the solution usually turns out to be very simple and straight forward.

This is of course after much frustration, lots of coffee, temper tantrums, and sometimes cursing which has probably caused my coworkers enough concern to arm themselves in preparation for cubicle defense. The solution is usually arrived at by assembling bits and pieces from several sources until it all becomes clear. Other times, it is just a matter of wading through thousands of bad solutions until the cleanest one is found.

Sometimes it even makes sense. Sometimes I don't understand it completely, but I do know that it works.

I like solving problems; it is why I'm in the IT field, just like many of you probably are. If you don't find the solution you're looking for feel free to ask me - post a question, make me work for your interest. Most of my posts will revolve around solutions in Java, JBoss, MySQL, Oracle, and Linux. These are the tools I'm currently the most active in, but I have a diverse exposure to many other technologies, such as ASP.NET, C#, perl, PHP, VB, PowerBuilder, etc... the list goes on.

So, my goal with this blog is to assemble these nuggets of genius (okay, I'm using that term very loosely), and "pay it forward", by presenting them for any of you frustrated geeks out there seeking answers with the infamous google search engine hoping to find those magic keywords that throw the solution back at you.

To christen this blog, I'm going to start it with a simple classic algorithm for randomizing a collection. I like to refer to it as the "shuffle" algorithm. I'll be doing the "HOW TO" example in Java, but you could easily transfer this same technique to any language. If you'd like it presented in another language feel free to post a comment, and if I'm capable I'll try to provide an example.

package com.blogspot.codingitforward;

import java.util.Random;

public class ShuffleExample {
 public ShuffleExample() {
  //Creating a sample int array
  int[] shuffledArray = new int[100];
  
  //setting up some values to randomize
  for(int ndx = 0; ndx < shuffledArray.length; ndx++) {
   shuffledArray[ndx] = ndx + 1;
  }
  
  //Initialize your random number generator
  Random random = new Random();
  
  //loop through the array, and "shuffle" the items by swapping them.
  //some items will be swapped several times, but you can be assurred that
  //every element will be moved at least once.  This allows you to very efficiently
  //randomize a set, and also keep the set finite.
  for(int ndx = 0; ndx < shuffledArray.length; ndx++) {
   //grab a random number between 0, and the size of your collection
   int iRand = random.nextInt(shuffledArray.length);
   
   //put the current value in a temporary holder
   int iTemp = shuffledArray[ndx];
   
   //set the value for your current index value to the random element
   shuffledArray[ndx] = shuffledArray[iRand];
   
   //set the value for the random element to what WAS the current one
   shuffledArray[iRand] = iTemp;
  }
  
  //For grins, lets output the random results
  for(int ndx = 0; ndx < shuffledArray.length; ndx++) {
   System.out.println("Element " + ndx + " = " + shuffledArray[ndx]);
  }
 }

 public static void main(String[] args) {
  ShuffleExample shuffleExample = new ShuffleExample();
 }
}

Stay tuned. I may provide an extended example which utilizes this technique to update database records with random values.

I know, it is quite riveting. I bet you're on the edge of your seat right now.