I don’t mind if I’m incomprehensible

Campus Map Part I (of I): Generating Tiles

leave a comment »

Wil has on a couple occasions encouraged me to give a presentation on at PDXPHP about the campus map project I worked on recently.  But I don’t think there are enough interesting and useful stuff for a talk.  So I do the next worse thing: write a bit about it on my blog.

When we first started the project, we wanted to use the Google Maps API as much as possible.  That means we used GPolyline and GPolygon to display all the elements on the map.  Unfortunately this produced a huge performance penalty.  Each element was rendered on the map with an image, so just to display all the buildings on campus, the map would have to load…well, a lot of images.

So we decided were forced to use tiles.  We’d lose the nice hover effect for the elements and have to move the click handling to PHP.  And of course, generate the tiles from the GIS data in MySQL.

The basic approach was:

  1. Get the layer from the database and turn its minimal bounding rectangle (MBR) from latitude/longititude into pixel units, per the current zoom level.  Then create a blank image with GD.
  2. Grab all the elements that belong to the layer and draw them on the image.
  3. Slice the master image into tiles and save them onto the appropriate locations on disk.  Since it’s unlikely that the layer’s width and height are perfectly divisible by 256 (did you read that tiles link??), we’ll have to do some arithmetic for offsets for the western and northern edges.  No big deal.

Simple and straight forward right?  Yes, it’s a simple and straight forward way to use up all the memory on the server.  At the higher zoom levels, the master image can get ginormous.

(Oh yeah, a layer is just a map with a grouped (logically, one hopes) set of things.  Buildings, student parking lots, dorms, etc.  A user can view just one layer or multiple simultaneously.)

Since generating an image for an entire layer is pretty much the same as generating an image for a part of it, recursive divide and conquer is the natural solution.  And that whole thing about the offsets with the edges was kinda dumb, or maybe just silly; we could simply make the master image’s dimensions a bit larger so they are divisible by 256.  No harm in pretending the MBR is a little bigger.

So now #1 above is now:

  1. Accept a MBR.
  2. If image is going to be too wide, slice vertically into halves.  If image is too tall, cut image(s) horizontally into halves, or quarters if it was also too wide.  Go back to the beginning with these pieces.
  3. Or, if the image isn’t too tall or too wide, then proceed.

This is of course slower.  Not because of the recursion (negligible really), but the increased number of database hits, especially at a high zoom level.  But compared to the drawing function calls and file writes… who cares.  :-P

There.  Done.  Not a single line of code, too.

Unfortunately, there isn’t a public preview of the project yet.  Jose and Montana are the other main developers on the project, maybe they’ll chime in on some of the stuff they’ve worked on.

Next time, I’ll bitch about GD and MySQL… except there isn’t a next time.  Lucky you.


Written by Barry

December 17, 2007 at 10:29 pm

Posted in Nerdy

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: