mapserv31

Olson code timezones geekery

Geek warning: This post is a bit of a total geek out but in any case here’s a bit of code that some of you might find useful. For the rest of youzes here is a pretty picture:
mapserv31

Yesterday I ended up writing a small piece of code to determine what timezone code a person is in.  This was not as trivial as it sounds.

In fact it was a learning experience about how complex our organization of time is – living on a sphere and all.  Timezone maps are not country maps, in fact time-zone maps are a complicated politic cleaving apart regions that have a minimum number of people – like some kind of crazy voronoi diagram of clusters of human populations.  Country boundaries play a strong role, but timezones are more like a mold that has grown over the existing history of a landscape. Alberta has a time zone that juts into Saskatchewan just to capture one town. Argentina slices timezones horizontally towards the South Pole to conserve sunlight for farmers. Chile doesn’t give a damn and puts all of Chile in one gigantic vertical strip of a timezone – so that in the winter it is dark at 6:00 in Santiago but sunny at 6:00 in Tierra Del Fuego. In other places of the world things like small islands show up more clearly than in country maps because each island tends to be a well defined separation of human populations and thus a good opportunity to have a single time zone code. A lost history is left traced in palimpsests here of residual boundaries.

voronoi are invading

help the voronoi are invading

If you look at the zoneinfo article on Wikipedia you can get a sense of what is going on here : http://en.wikipedia.org/wiki/Zoneinfo

The backstory is that the OpenBSD folks wanted help to automate configuration of timezones for installs. What we did was take the geolocation of their IP and use it to look up a timezone code.

There are 27000+ polygonal boundaries that make up the timezones. And there an odd 370+ timezones including all the various cases.

The goals were:

  • We wanted an extremely fast computation.
  • We wanted it to be static ( not require a database ).
  • Accuracy
  • Return Olson posix string like “Europe/Paris” .

I did fix one bug which was that in asking MapServer to spit out .png files it was palettizing the colors into an 8 bit deep image – whereas I needed 9 bits… So I had to ask mapserver to print out a tiff. If you see any other bugs….

Here are the source files in any case:

You can build it by typing

gcc timezones.c

And you can test it running with a longitude, latitude pair – for example:

./a.out -114 53

Which should return to you a string showing the time zone you are in.

The way it works is that I read in a timezone shape file from this place

http://koordinates.com/layer/751-world-time-zones/

This was piped to the following program:

http://civicmaps.org/maps/layers.rb

Which instructed my mapserver to generate a special kind of cloropleth map – which can be seen here ( but don’t bother because it chews my machine ) :

http://civicmaps_dontbother.org/cgi-bin/mapserv?map=/www/sites/civicmaps.org/maps/x.map&service=WMS&WMTVER=1.0.0&REQUEST=map&SRS=EPSG:4326&LAYERS=lowboundaries0&FORMAT=image/png&STYLES=&WIDTH=2048&HEIGHT=1024&BBOX=-180,-90,180,90

This data file can now be used as a bitmapped query interface for discovery of unique time zone codes as done above – or as done in ruby here :

http://civicmaps.org/maps/longlat.rb

You need ImageMagick installed.

If you wish, you can convert the image into a ppm file or something and embed it directly in the C program. Or memory map it and have a query gateway to it… that would be fastest.

4 Comments

  1. Ralf
    Posted May 20, 2009 at 2:09 pm | #

    wow. i like your solution with the colorpleth. did you run any benchmarks on this? how long does a lookup take? i was struggling exactly the same problem a few days ago. i am using a prtree and feed it with the timezones polygons.

    i am using the same shapefile, which is sometimes kinda inaccurate (check this lat/lon: 28.4051872, -80.6058589). do you get the same error? for this, i use a function that calculates the standard time zone (not political, no DST!):

    http://home.tiscali.nl/~t876506/Multizones.html#iw

    nice work! ralf

  2. Posted May 20, 2009 at 2:20 pm | #

    Thanks! I have a hard time imagining how to make it faster – it is just a bitmap peek….

  3. Ralf
    Posted May 20, 2009 at 3:25 pm | #

    yeah, me too. did you benchmark a little? Your solution sounds so interesting. That’s why i am interested in the average speed of your look up. I am on a 2.8 GHz Intel and once the tree is build up, a look up takes appr. 0.102279 milliseconds.

    And, do you get the same error for some locations around coastlines? The above given location is not in any time zone from the shapefile!???

    Thanks! Ralf

  4. Posted May 20, 2009 at 3:53 pm | #

    Didn’t benchmark. I guess it would be something on the order of 50 instructions in assembler? There might be a page fault or two if the entire thing was memory mapped… It operates in linear time… It won’t be as accurate as a vector test unless the resolution of the raster exceeds that of the vectors… I’d benchmark it if there was any conceivable contender for a faster solution :-). Note I should credit Theo Deraadt for suggesting the approach.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>