Polygon encoding; or how to make your map of the US load faster

So, the problem we have right now that is causing a lot of slowdown (and annoying "this script is taking forever... continue?" errors) on a lot of browsers is that the polygons we have are too complex.

Things like Colorado or some city zipcode are simple enough... but states with long coastlines (California, Florida) or bordering rivers (Mississippi, Illinois) tend to have polygons with hundreds or thousands of vertices because of all the little crenelations that nature happens to draw on the country. Furthermore, even things like Colorado have zips that border rivers, and the end result is a browser having to download and process a LOT of javascript. At least 95% of the massive page draw is arrays of longitude/latitudes.

Google, however, represents these lovely little things called encoded polygons that take these thousands of points and turn them into two simple lines of text. I think they are the key to removing errors and speeding everything up. There are very in-depth summaries of encoded polygons and how to make them from lists of points here. I will try and explain my perspective anyways.

First off, the encoding is two dimensional in the data they store (hence two strings). The first string is a compressed representation of the points that make up the polygon, which saves lots of space because numbers are very easy for computers to de/compress. The second string is an indicator of which points should be displayed at what zoom levels. Thus, if you are zoomed way out (viewing all of the US) you don't need all the individual points on a river because, well, there could be 15 of them in one pixel of your monitor.

There is also a very neat algorithm that automatically determines the levels, and it is demonstrated here.

The best part, Google understands encoded polygons. Thus, less javascript processing for the browser, and since it's simple compression and algorithms, the server shouldn't have to spend many milliseconds converting the data on the fly. (and even if it does, it will only need to be done once and then cached).

I am hoping I can get this implemented Monday. They even have java ports of the encoding algorythm. I just hope it's rather straightforward, there are a lot of little extra usability tweaks to be made too and the deadline for this version of Quicksilver is relatively soon. And who knows, it might not help speed or errors that much.

But I have great hopes, and I think it will.

Cheers