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

Setting up the locational library.

Well, right before I went off for the holidays, I completed the part of the gmap polygon libraries that would easily provide javascript for an array of polygons.

Now, I am in the process of building lists so that any application that wants to provide locations will be able to get lists of states, zip3's in said states, and zip5s in said zip3s. That, and improving the graphic awareness to be able to center on given areas after they are selected.

This of course means massaging large KML lists, and discussions on what would be most useful to someone trying to build their own databases on their own systems. Right now it seems the best answer would be "Comma delimited files", considering every database has a way to very quickly ingest such files.

I also am happy to have gotten some examples of text massaging using macros, and am once again making sure to earmark some time in the new year for basic scripting niftiness, namely because there are just some times when creative uses of grep and regular expressions will do so much more with a file than trying to create a SAX parser.