Campus Maps

The University of Washington Campus Maps were developed to make it as easy as possible for people to find buildings on the UW Seattle campus. User-visible features include:

This case study only covers the methods and algorithms used for the UW campus maps in general terms, rather than offering complete code; much of how the maps are implemented is specific to the particular needs for the application.

Map Graphics

The UW Campus maps were originally generated from Freehand files, but that is in a state of transition to files centrally-managed by Facilities Services. GIF images were generated of the six detail maps, as well as an overall map.

red circleThese seven GIFs were also converted to PPM format for use by the Netpbm tools, to support the red circle feature. Also to support circling, seven solid white PPM files were also generated, matching the sizes of the overall and detail map GIFs. Lastly, an image of a red circle (128 pixel diameter, 16 pixel stroke, shown to the right as a GIF) on a white background was converted to PPM format. This circle is scaled by the maps application to make a circle of the appropriate size. The circle starts out large so that scaling will preserve a smooth, anti-aliased curve. If a smaller circle were used, there may be cases where it needs to be greatly enlarged, causing a jagged edge.

All the maps which have circles are generated on-the-fly as needed, with generated images cached so they won't need to be generated the next time.

Map Coordinates

Once the images are generated, their layout is defined relative to the overall map. To do this, the detail maps are manually pieced together as a temporary image so they form one large, continuous map image. The top-left corner of the northwest map is assigned the coordinates 0,0, and the top-left corners of the other five detail maps are assigned coordinates relative to this origin point (i.e. the southeast map is assigned 901,508 since its position is 901 pixels to the right and 508 pixels below the northwest map's top left corner). This large map image is also used to find the position of circles for buildings, so is preserved.

The scale of the overall map is compared to the detail maps, and that ratio saved. For the UW maps, the detail maps are 3.4718 times the size of the overall map.

This information saved into a file which associates the map location, image name, and coordinates for each map, as well as the ratio for the overall map. In addition, the map grid coordinates for each detail map are also saved. For example, the south central map entry in this file is:

"South Central" southcentral 10-I:20-Q:451,508

south central map grid cornersThe first entry is the name used for links to this map, the second is the name of maps for the south central area (but not filenames; that conversion happens in the CGI scripts). Next come the grid coordinates; 10-I is the upper-left grid for the map, 20-Q the lower-right grid (as shown at the right; note that the 10 and I grid markers are obscured by the navigation leading to the maps to the north and west). Finally, 451,508 are the upper-left coordinates relative to the other detail maps.

Map Data

A single file contains all the information for each building listed on the maps pages. The first few lines are:

DSC 10-H;47,70,463,582 3941 Univ. Way
3LC 3-I;48,71,521,58 4545 Bldg
ACC 13-G;69,75,384,737 Academic Computer Center

The first entry is the building code, where 3LC is used for buildings which don't have codes (a carryover from the original data used to generate this file). Multiple building codes can be listed, separated by commas (but no spaces).

The second entry contains the grid coordinate of that building, as well as the size and position which should be used for red circles. Note the coordinates which are used correspond to the large, continuous map used to generate the detail map offsets.

After the building code and location on the map is the name of the building, which extends to the end of the line.

A script is run to convert these lines into HTML which is used on the map pages to show what buildings are visible on that map. The first few lines are:

<ul class="listcol">
    <li><span>10-H</span>
        <a href="/home/maps/?47,70,463,582">3941 Univ. Way (DSC)</a></li>
    <li><span>3-I</span>
        <a href="/home/maps/?48,71,521,58">4545 Bldg</a></li>
    <li><span>13-G</span>
        <a href="/home/maps/?69,75,384,737">Academic Computer Center (ACC)</a></li>

The building code, if available, is listed after the building name. The grid for the building is also listed. Note that the coordinates for the red circle are listed on the URL line itself; rewriting rules are used to change them into arguments to be used by the CGIs.

Since the map coordinates file lists grids visible on each detail map, the script generates HTML tables for the detail map pages too, only listing the buildings which are on that map. For example, the 4545 building is listed in the generated HTML for the north central and northwest maps.

Since map data changes don't happen very often, the script is just run by hand after the data file has been changed.

URL Rewriting

When the web server receives a request for a map page or an image, they are sent back to the user. However, if a request is made with coordinates (such as in the URLs listed in the HTML table above), Apache's mod_rewrite module is used to change the request to one which a CGI can use. To rewrite requests for HTML pages, the rules are:

RewriteEngine on
RewriteBase /home/maps
RewriteCond %{QUERY_STRING} !^([0-9]+,[0-9]+,[0-9]+,[0-9]+)$
RewriteRule .? - [L]
RewriteRule ^(index.html)?$ getpage.cgi?m=a&c=%{QUERY_STRING} [L]
RewriteRule ^([^.]+)\.html getpage.cgi?m=$1&c=%{QUERY_STRING} [L]

The first two lines enable the rewrite engine and tell it the path of the current directory. The next two lines prevent any rules from operating on URLs which don't look as if they have coordinates as the query string. The next line rewrites any access to the main maps page to calling getpage.cgi with two arguments. The last line converts all other html pages to a call to getpage.cgi which indicates that particular page.

Requests for images can also have coordinates (which is what causes the actual map image to have the red circle). The lines which handle those cases are:

RewriteRule ^graphics/HomeMap\.(jpg|gif) getmap.cgi?m=a&c=%{QUERY_STRING}&t=$1 [L]
RewriteRule ^graphics/(..)map\.(jpg|gif) getmap.cgi?m=$1&c=%{QUERY_STRING}&t=$2 [L]

The first line explicitly checks for the map image which shows all of campus, and the second one for the detail maps. Each rewrites the image request into a call to getmap.cgi.

getpage.cgi

This CGI will rewrite an HTML file so that the map image URL and links to detail maps will contain the coordinates.

When the UW maps were first brought online, the names of the images did not match the names of the HTML detail pages, so much of the UW getmap.cgi script maps the names back and forth. New applications can choose to normalize names so this does not need to be done.

After all necessary filename conversion is done, getmap.cgi searches the file for the link to the actual map page, and changes that URL to contain the coordinates which were passed to getmap.cgi.

The maps pages are coded so that most links contain at least one / character. However, imagemap links to the detail maps do not contain / characters, and getmap.cgi takes advantage of that fact to change those URLs to have the circle coordinates. What this does is let the user click on a section of the map which has a red circle and see a detail map which also has the red circle.

After the rewriting has been done, the resulting HTML file is sent back to the user.

getmap.cgi

This CGI is responsible for delivering a map with a red circle on it, as defined by the coordinates passed to it.

One of the first things done by this script is to check if the arguments passed to it are reasonable, as well as normalizing filenames (as done by getpage.cgi). If the coordinates do not lie within the current map section, then the original image is sent without modification.

If everything looks good, the maps cache is checked to see if we've already created a map with the requested red circle. If the file exists in the cache and is not older than the original image, we return the cached contents.

If the script is still running, then we know we need to generate an image with a red circle. The steps are:

  1. Use pnmscale to resize the 128x128 red circle to the needed size.
  2. Use pnmpaste to place this circle into the all-white ppm file which is the same size as the requested image. What we now have is an image the same size as the map image, but is all white with a red circle correctly positioned.
  3. Use pnmarith to do an arithmetic multiply over the map image. Since most of the overlay is white, no changes will be made to those parts of the map. However, the pixels which contain the circle are only red, so the blue and green components of those pixels will be changed to zero, while the red component will remain the same. The result is what looks like a red filter cut in the shape of a circle which has been layed on top of the map.
  4. The resulting PPM is converted to a GIF, saved into the cache, and returned to the user.

If the requested map is the overall campus map, then the size and location elements are scaled down by the factor defined in our coordinates file; the current factor is 3.4718.

It can take several seconds to process a map image, so the image cache greatly improves response time, as well as reducing load on the web servers.

Search

The UW Campus Maps has a search function, which allows people to find buildings by name, building code, or map grid. The search form invokes mapsearch.cgi, which handles all of the searching duties. It compares the search string with values in the map data file used to generate the HTML tables of building links.

If a building appears in more than one detail map page, each of those pages will be displayed as matches.