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

Deploy is complete. Come revel in new features

So, I have completed another deploy (well, two deploys actually) of Quicksilver.

You can reach it here, and you can read more about how it was built or how to view the code here

One of the new features is the "remembered zoom"... where the zoom for a selected region will be maintained if only the legend, timespan, or conditions change. Changing the region (from MD to IN, from MD to the 208 zip 3, the 208 zip3 to a view of all states) will revert to the default zoom level for that region type. But now, if you had to zoom in on Rhode Island... you won't have to zoom in again after selecting for a different condition or widening your search.

Another new feature is the adjustable legend... meaning that you can change the difference in the count numbers that determine the colors for polygons.

Finally the search dates default to the current week. This is not going to be that useful on the training node because we are using test data that only goes up to about October 2008, but when Quicksilver gets deployed to a production setting and starts getting access to more recent data, it will be much more helpful than a always starting on a random week in February 2008.

Meanwhile, lots of people had a good long look at the app today and came in with lots of feedback. It was both wonderful (because lots of people liked the application and thought it was neat and I got some ooohs and aaahs from things like flot) and terrifying (because I was worried it would break, people found ways to make the app do strange things, and because people tried things and thought of features that would be insanely cool to install that I never would have dreamed of). Having a bunch of users that are not that familiar with the application generates a LOT of very good feedback and questions. People were getting confused over things that, in retrospect, are not very clear at all. Today literally involved a large explosion of possibilities and potential, and it's as paralyzing as it is motivating. If anything because it's difficult to triage what should be done first.

So, next week will be a lot of implementations of little and big fixes. There are some very salient UI tweaks to be made (Like labeling more clearly, having "zip3: 208 // Total Count: 350" is a lot more handy than just "208 // 350") lots of little help pages and legend explanation (namely how the C2 algorythm means the blue average line and outlier status is based only on the average of the preceding 30 days (minus the closest two)) and finally, an attempt to make the polygon drawing much more streamlined to get rid of the really-quite-irritating "This script is taking a long time, do you want it to continue" error thrown by IE, which is exacerbated by having a not-bleeding-edge computer.

I think I have found a way to do that, and it's called polygon encoding, and I'll be detailing that in the next post.

Either way, I am elated and looking-forward to how nifty we can make this application.

Cheers,
Peter

Tomorrow: Flot with C2

Tomorrow I will be deploying Quicksilver with Flot running the C2 algorithm (if all goes as planned).

Then, it is a battle with the IE "Operation canceled" bug (although I will be trying something with this deploy) and a bunch of UI tweaks based on suggestions from multiple users. Things like click-through to new regions, and enabling better map functionality (scroll wheel zoom, mini-map). Also, some larger features like multiple zone select, combination of regions into counts, and multi-selected conditions will be considered.

Either way, I am just excited Flot is working. It's really pretty!

Oh, Internet Explorer... why do you not love GMap Polygon?

So, Internet Explorer seems to have a fickle relationship with GmapPolygon.

Sometimes, when it is loading a set of polygons, it will throw an error saying "The page at [address] cannot be loaded. Operation Aborted". This is a thoroughly unhelpful error, because it doesn't offer to show me the part of the code that broke or otherwise debug the issue. Furthermore, it's not re-create-able on demand. It tends to do it whenever it feels like it, for any given set of polygons... polygons which loaded fine not three seconds before.

Some of the blogs I checked (example) indicate that such errors arise because IE was processing some javascript, freaked out, and cancelled the page load... Usually because some spurious parent element is being referenced. The problem is that in the javascript I don't think any parent DOM elements are being referenced, just maps which are created inside the head script.

I'll admit, I am not that familiar with javascript, so nothing really stands out to me that makes me go "oh, that's what is making it blow up sometimes." So I invite anyone to look at the source of polygon pulls (I suggest poking the site with firefox) to see if anything stands out.

Otherwise, I imagine a lot of the problems involve the fact that a polygon is represented by a metric ton of text... especially polygons that border rivers and coastlines... such sweeping, beautiful crenulations that only nature can carve out are represented digitally by thousands of vertices. which all need to be pulled back from a database somewhere and then provided to google maps.

Meanwhile, I am attempting to make Gmap-Polygon get those back end database connections to be more robust and reliable, and improve caching so that the database doesn't even have to be hit that often... but we are also just looking at getting simpler polygons so that there is less data to pull, transfer, and store, which should have the biggest impact.