I've always liked maps, but I've always been disappointed with the content. Sure, knowing road names and where to find a gas station is great. But I'm an outdoors kind of guy, and what I really want to see is cool biking and hiking routes. That's why I'm so excited about Keyhole Markup Language (KML) and the MapQuest Platform; the combination of the two lets users, as opposed to mapmakers, supply map content. Overlaying a map with KML data opens up many possibilities for uploading, sharing, and finding user-generated content. Couple this ability to share data with the vast number of people carrying GPS-enabled devices and you have a perfect storm for sharing off-road routes.

In this article, I show how to read KML files and create map features by using the MapQuest JavaScript API. The example I'm presenting is a KML file that describes the route for the Appalachian Trail (AT) and the location of shelters hikers use for overnight stays. I've focused on my favorite part of the trail, which is the section between Front Royal, VA, and Harper's Ferry, West Virginia. The source code for the example is listed at the end of this article. The following screen shot shows my custom AT map in action:

Figure 1. The AT from Front Royal, VA, to Harper's Ferry, WV, showing the location of the trail and overnight shelters

The trail route is shown in red. The overnight shelters are shown as Point of Interest (POI) stars. Clicking a star opens an information window that lists more details about the shelter:

Figure 2. Clicking the POI marker opens an information window that lists details about the shelter

The last screen shot shows the map after zooming in and changing to an aerial image view:

Figure 3. Aerial view of the David Lesser shelter

This screen shot shows that the David Lesser shelter is located east of the trail. The screen shot gives just a suggestion of the excellent view from the shelter's porch looking out over the farmlands of Northern Virginia. Just in case you can't tell, I think the David Lesser shelter is the nicest one in this section of the AT.

In the remainder of this article, I cover some background on KML and the KML files I used to prepare the maps shown here. The following section covers the code and the experiences, some good and some bad, that I had while developing my custom AT map.

KML

Wikipedia describes KML as an XML-based schema for expressing geographic annotations of online maps in two or three dimensions. KML is just one of many file formats for interchanging map annotations, which also includes formats for data recorded by GPS-enabled devices. The nice thing about KML is that it is widely supported and has been submitted to the Open Geospatial Consortium for standardization.

A couple of examples of widespread KML use are 1) searching KML files on AOL if you are interested in a particular topic and 2) aggregation sites that syndicate user-generated content in KML format such as virtualglobetrotting.com, mapufacture.com, and bikely.com. If you have data in a particular format, you can use GPSBabel to convert to and from KML and other data file formats.

A KML file typically contains elements that describe features, such as camera viewing angles and elevation, that are not relevant for the two-dimensional maps generated with the MapQuest Platform. My approach was to ignore these elements. The code in this article recognizes KML Placemark elements that have a child Point geometry or a LineString geometry. This is best explained by looking an extract from the KML file for the AT data:

0172 <kml xmlns="http://earth.google.com/kml/2.1">
0173 <Document>
0174   <name>Appalachian Trail Centerline</name>
0175   <description>Exported from at_centerline.shp 3/12/02 downloaded from
0176     http://www.appalachiantrail.org using City of Portland's Export to
	   KML 2.3.5
0177     Go Hokies!
0178   </description>
0179   <LookAt>
0180     <longitude>-78.92943061782194</longitude>
0181     <latitude>37.87708055555556</latitude>
0182     <altitude>0</altitude>
0183     <range>1067501.314867445</range>
0184     <tilt>32.73615635179154</tilt>
0185     <heading>1.815747767697585</heading>
0186   </LookAt>
0187   <Folder>
0188     <name>Features</name>
0189
0190 <!-- Routes -->
0191
0192 <Placemark>
0193       <name>1778</name>
0194       <styleUrl>#FEATURES_copy18</styleUrl>
0195       <LineString>
0196         <tessellate>1</tessellate>
0197         <coordinates>
0198 -78.0494085970235,38.9169067777347,0 -78.0494323854585,38.9169149040082,0 ...
	 </coordinates>
0199       </LineString>
0200     </Placemark>

...

1004 <!-- Shelters -- >
1005
1006     <Placemark >
1007       <description>Notes:  Sheltered picnic table, fireplace, and privy;
1008       spring
1009
1010 Fee:  No
1011
1012 Capacity:  6
1013
1014 Maintained By:  Potomac Appalachian Trail Club</description>
1015       <name>David Lesser Shelter</name>
1016       <View>
1017         <longitude>-77.77954</longitude>
1018         <latitude>39.22718</latitude>
1019         <range>999.9999999999999</range>
1020         <tilt>0</tilt>
1021         <heading>0</heading>
1022       </View>
1023       <visibility>1</visibility>
1024       <styleUrl>#cloned1</styleUrl>
1025       <Point>
1026         <coordinates>-77.77954,39.22718,607.9747496823218</coordinates>
1027       </Point>
1028       <styleURL>#cloned0</styleURL>
1029     </Placemark>

...

1182   </Folder>
1183 </Document>
1184 </kml>

Lines 179-186 describe a viewing angle for a three-dimensional viewer. Lines 192-200 are a Placemark that describes a section of the trail route. The example code maps this Placemark to a line overlay on the map. The second Placemark, on lines 1006-1026, describes a shelter and associated three-dimensional location coordinates (on lines 1025-1027). I mapped these elements to a POI and used the longitude and latitude elements of the coordinates.

There are a few features of KML to keep in mind when writing code to consume KML. The first is that the file can be quite large and KML files are often stored in a zipped file with a .kmz extension. The file for the AT trail route is close to 15 MB. Therefore, the code to traverse KML needs to be as efficient as possible. The other feature of KML worth noting is that container elements such as Folder can be nested. KML document object model (DOM) tree-traversal routines need to be ready for arbitrary nesting of elements.

The AT trail data I used came in two files: one for shelter locations and one for the center line of the trail route. The trail route file was just too large to handle with client-side JavaScript. To construct a reasonable-size sample, I extracted features lying between Front Royal and Harper's Ferry using the Perl XML::XPath library and consolidated the extracted features into one shorter file. The following listing shows the Perl code I used to extract Placemark elements for my region of interest:

#!/usr/bin/perl -w

use strict;
use XML::XPath;
use XML::XPath::XMLParser;

my $xp = XML::XPath->new(filename => 'doc.kml');
my $placemarks = $xp->find('/kml/Document/Folder/Placemark');
foreach my $placemark ($placemarks->get_nodelist) {
  my $coordinates = $xp->find('./LineString/coordinates', $placemark);
  foreach my $c ($coordinates->get_nodelist) {
    my $text_nodes = $xp->find('child::text()', $c);
    my $sv = '';
    foreach my $t ($text_nodes->get_nodelist) {
      $sv .=  $t->string_value;
    }
    $sv =~ s/^\s*//;
    my @coords = split /\s+/, $sv;
    my ($lng, $lat, @rest) = split ',', $coords[0];

    #harpersFerry - (39.32, -77.72) - frontRoyal - (38.90, -78.05);
    if( (38.90 <= $lat) and ($lat <= 39.32) and
        (-78.05 <= $lng) and ($lng <= -77.72)) {
      print XML::XPath::XMLParser::as_string($placemark) . "\n";
    }
  }
}

KML Import JavaScript Code

I broke the task of reading the KML DOM document into two classes: TreeWalker (lines 28-61) and MapMediator (lines 64-159). The TreeWalker class is responsible for traversing the DOM tree and passing MapMediator interesting KML nodes. The MapMediator class is responsible for creating MapQuest objects on the map for the corresponding KML elements.

As I mentioned earlier, KML files can be quite large, so I made a couple of optimizations for efficient KML DOM tree traversal. The processing model I use here is client-side JavaScript, so there will be limits to the reasonable file size; however, I aimed to accommodate large files.

To support large files, the first decision I made was to make only one pass through the KML DOM. This choice is opposed to a pull type of model in which one queries the DOM for interesting elements. (Examples of pull processing might include calls such as document.getElemntByTagName() or JavaScript Prototype Framework methods like $('Placemark Point');.) Each pull query might involve traversing all or part of the tree multiple times, which a one-pass approach avoids.

To support a one-pass model, I implemented a depth-first, document-order traversal that scans the KML DOM in the same order as I tend to read the XML (top to bottom). The algorithm is as follows: 1) visit the first node (and send the node to MapMediator), 2) push the node's children onto a stack in reverse document order, and 3) pop the stack and repeat from step 1. The main route for the traversal is:

0050         while(this.stack.size() > 0) {
0051           var node = this.stack.pop();
0052           this.handler.handleElement(node);
0053           if(this.handler.prune(node)) continue;
0054           if(node.hasChildNodes()) {
0055             for(var i = node.childNodes.length; i > 0; i--) {
0056               this.pushIfElement(node.childNodes.item(i - 1));
0057             }
0058           }
0059         }

The second optimization I made was to pass only element nodes to MapMediator (see MapMediator pushIfElement() on Line 37). This approach avoids many method calls for text and attribute nodes. MapMediator can always directly query for these types of nodes when it receives a DOM element.

The final optimization I made for traversing the tree involves the idea of pruning the tree traversal. When processing elements such as a KML Placemark, I noticed that there are many child elements that are not relevant for a map. It looked to be more efficient for MapMediator to query directly for the relevant children when passed a Placemark element. After TreeWalker allows MapMediator to visit an element, it calls the MapMediator.prune(element) (line 53). If MapMediator returns true, the tree traversal is pruned at that element.

The time to traverse the 300 Placemarks in the AT shelter file was less than half a second. I wasn't able to traverse the full AT route file in a reasonable amount of time. That's fine, because processing a 15 MB XML file in the browser doesn't make much sense.

The callback from TreeWalker to MapMediator is handleElement():

0070       // callback from TreeWalker
0071       handleElement: function (node) {
0072         if (node.nodeType == Node.ELEMENT_NODE) {
0073           if('Placemark'.toLowerCase() == node.nodeName.toLowerCase()) {
0074             this.placemark(node);
0075           }
0076         }
0077       },

As I mentioned earlier, MapMediator creates MapQuest objects for Placemarks elements only. The code for creating MapQuest objects from KML elements is contained in the method placemark():


0088       // Create map objects for place marks
0089       placemark: function(node) {
0090
0091         // find interesting children of placemark
0092         var name = this.getChildText(this.getFirstChild(node, 'name'));
0093         var description = this.getChildText(this.getFirstChild(node,
		 'description'));
0094         var point = this.getFirstChild(node, 'Point');
0095         var lineString = this.getFirstChild(node, 'lineString');
0096         var rawCoordinates = this.getChildText(
0097           this.getFirstChild(point ? point : lineString, 'coordinates')
0098         );
0099         var coordinates = this.parseCoordinates(rawCoordinates);
0100
0101         // Create a MQ POI for KML points and MQ line overlay for KML
		 LineStrings
0102         // KML is (lng,lat), MQ is (lat,lng)
0103         if(point) {
0104           var poi = new MQPoi(new MQLatLng(coordinates[1], coordinates[0]));
0105           poi.setInfoTitleHTML(name ? name : '');
0106           poi.setInfoContentHTML(description ? description : '');
0107           this.map.addPoi(poi);
0108         } else if(lineString) {
0109           var points = new MQLatLngCollection();
0110           for(var i = 0; i < coordinates.length; i = i + 3) {
0111             points.add(new MQLatLng(coordinates[i + 1],coordinates[i]));
0112           }
0113           var lineOverlay = this.getLineOverlay();
0114           lineOverlay.setShapePoints(points);
0115           this.map.addOverlay(lineOverlay);
0116         }
0117       },

Lines 92-99 pull the child elements of the Placemark element that will be used when creating the corresponding MapQuest object. For POIs, the name and description are used to populate the information window. In both cases, the coordinates are fetched for locating the MapQuest object. For a lineString element, the coordinates are an array of (longitude, latitude, and altitude) tuples. POI markers are generated for KML points in lines 104-107. Lines 109-115 add a line overlay for the AT route information.

The balance of the MapMediator class is given over to utility routines. The method getLineOverlay() returns a template MQLineOverlay with styling information and no location information. The method parseCoordinates() converts the text contained within the KML coordinates elements into a flat list of floats; each set of three elements in the list corresponds to a KML location tuple.

The Long Story

When I started this project, I envisioned that I would load the KML file using an Asynchronous JavaScript and XML (AJAX) call after the map was created. This means that MapQuest would show the map first, then add in POI markers and line overlays after the map was rendered. I figured this would keep the user happy during a potentially long KML parsing cycle.

I started with adding the POI markers for the shelters first. I used the Prototype AJAX class to fetch the KML file. After configuring my server's content-type header for KML files to ''application/vnd.google-earth.kml+xml" the AJAX parsing worked well. The main stumbling block I had was that Prototype's DOM traversal routines didn't seem to work if the XML DOM tree was not made part of the document DOM tree. I got past this problem by not using the Prototype routines and instead using the standard DOM API.

Then, I included code to add the AT route as a series of MapQuest line overlays and found out that my AJAX fetching of the KML wouldn't work anymore. The reason for this problem is tied to MapQuest's use of Dojo for maps with overlays. Map creation happens during a callback from Dojo (see MQInitDojo() on line 165). Dojo is loaded by the MapQuest API, so calling my server for the KML file from Dojo event callbacks was not possible. Without using Dojo event callbacks, I couldn't be sure of when the map was created and initialized.

One solution might be to fetch and parse the KML and store an intermediate representation in the browser before loading the map. Then, in the map creation callback, use the stored representation to populate the map. Another solution might involve loading Dojo from your server and possibly a proxy to call out for KML files in other domains.

In the example code, I simply included the KML in a hidden <div> in the HTML document. This solution seemed to work well enough and is a reasonable approach, especially if you have fixed content that can be included via server-side templates. I did observe that some Prototype functions failed to match XML element names. Inspection in Firebug showed that the reported tag names were uppercase for some KML elements. This was strange; in any case, I resorted to String.toLowerCase() for tag name comparison.

Conclusions

I've demonstrated how to use the MapQuest JavaScript API to load basic map features from a KML file and create corresponding map objects. However, KML is a rich language and there are many more features that can be rendered on a MapQuest map. There are a few more features in KML for which consumption would be a straightforward extension of what I've presented here.

I've covered the handling of basic KML elements for point and line annotations. There are several different geometries that could be handled with map overlays, such as linear rings and polygons. KML also has several elements for specifying style information, such as the color or weight of lines, and even the icons used for map elements.

Even with the minimal amount of KML elements that I've processed, I'm very happy with the maps I was able to create. I look at the AT maps I created and have to say, "Those are my kind of maps." Have fun with the new API and enjoy your own custom map.

Full Source Code Listing

0001 <html>
0002   <head>
0003     <title>MapQuest KML Import</title>
0004     <link rel="stylesheet" href="kml.css" type="text/css"/>
0005     <script
	src="http://btilelog.access.mapquest.com/tilelog/transaction?transaction
	=script&key=mjtd%7Clu6y290rn9%2C22%3Do5-0utn1&ipr=false&itk=true&v=5.2.0"
	 type="text/javascript"></script>
0006     <script src='prototype-1.6.0.2.js' type='text/javascript'></script>
0007     <script language="javascript">
0008
0009       function initMap()
0010       {
0011         var mapCenter = new MQLatLng(39.11, -77.89);
0012         var map = new MQTileMap(document.getElementById('mapWindow'), 7,
		 mapCenter, "map");
0013
0014         map.addControl(new MQLargeZoomControl(map));
0015         var vc = new MQViewControl(map);
0016         map.addControl(vc, new MQMapCornerPlacement(
0017           MQMapCorner.BOTTOM_RIGHT, new MQSize(20,20)
0018         ));
0019
0020         try {
0021           new TreeWalker($('kml'),  new MapMediator(map)).depthFirstWalk();
0022         } catch (e) {
0023           alert(e);
0024         }
0025       }
0026
0027     // Class to traverse KML DOM
0028     function TreeWalker(startNode, handler){
0029       this.startNode = startNode;
0030       this.handler = handler;
0031     }
0032
0033     TreeWalker.prototype = {
0034       stack: null,
0035
0036       // process only element nodes
0037       pushIfElement: function(node) {
0038         if(node.nodeType == Node.ELEMENT_NODE) this.stack.push(node);
0039       },
0040
0041       // Depth first, document order traversal of DOM
0042       depthFirstWalk: function() {
0043         this.stack = [];
0044         this.handler.handleElement(this.startNode);
0045         if(this.startNode.hasChildNodes()) {
0046           for(var ci = this.startNode.childNodes.length; ci > 0; ci--) {
0047             this.pushIfElement(this.startNode.childNodes.item(ci - 1));
0048           }
0049         }
0050         while(this.stack.size() > 0) {
0051           var node = this.stack.pop();
0052           this.handler.handleElement(node);
0053           if(this.handler.prune(node)) continue;
0054           if(node.hasChildNodes()) {
0055             for(var i = node.childNodes.length; i > 0; i--) {
0056               this.pushIfElement(node.childNodes.item(i - 1));
0057             }
0058           }
0059         }
0060       }
0061     }
0062
0063     // Class to create MQ objects from KML elements
0064     function MapMediator(map) {
0065       this.map = map;
0066     }
0067
0068     MapMediator.prototype = {
0069
0070       // callback from TreeWalker
0071       handleElement: function (node) {
0072         if (node.nodeType == Node.ELEMENT_NODE) {
0073           if('Placemark'.toLowerCase() == node.nodeName.toLowerCase()) {
0074             this.placemark(node);
0075           }
0076         }
0077       },
0078
0079       // stop tree walk at placemarks
0080       prune: function(node) {
0081         var shouldPrune = false;
0082         if('Placemark' == node.nodeName) {
0083           shouldPrune = true;
0084         }
0085         return shouldPrune;
0086       },
0087
0088       // Create map objects for place marks
0089       placemark: function(node) {
0090
0091         // find interesting children of placemark
0092         var name = this.getChildText(this.getFirstChild(node, 'name'));
0093         var description = this.getChildText(this.getFirstChild(node,
		 'description'));
0094         var point = this.getFirstChild(node, 'Point');
0095         var lineString = this.getFirstChild(node, 'lineString');
0096         var rawCoordinates = this.getChildText(
0097           this.getFirstChild(point ? point : lineString, 'coordinates')
0098         );
0099         var coordinates = this.parseCoordinates(rawCoordinates);
0100
0101         // Create a MQ POI for KML points and MQ line overlay for KML
			LineStrings
0102         // KML is (lng,lat), MQ is (lat,lng)
0103         if(point) {
0104           var poi = new MQPoi(new MQLatLng(coordinates[1], coordinates[0]));
0105           poi.setInfoTitleHTML(name ? name : '');
0106           poi.setInfoContentHTML(description ? description : '');
0107           this.map.addPoi(poi);
0108         } else if(lineString) {
0109           var points = new MQLatLngCollection();
0110           for(var i = 0; i < coordinates.length; i = i + 3) {
0111             points.add(new MQLatLng(coordinates[i + 1],coordinates[i]));
0112           }
0113           var lineOverlay = this.getLineOverlay();
0114           lineOverlay.setShapePoints(points);
0115           this.map.addOverlay(lineOverlay);
0116         }
0117       },
0118
0119       // convert KML coordinate string to a flat array of floats.
0120       parseCoordinates: function(coordinateString) {
0121         var coordinates = [];
0122         var tuples =
0123           coordinateString.replace(/^\s*/, '').replace(/\s*$/,
		 '').split(/\s+/);
0124         for(var i = 0; i < tuples.length; i++) {
0125           var strs = tuples[i].split(',');
0126           for(var j = 0; j < 3; j++) {
0127             if(j < strs.length) {
0128               coordinates.push(parseFloat(strs[j]));
0129             } else {
0130               // elevation is optional in KML
0131               coordinates.push(undefined);
0132             }
0133           }
0134         }
0135         return coordinates;
0136       },
0137
0138       // return a line overlay without points
0139       getLineOverlay: function() {
0140           var lineOverlay = new MQLineOverlay();
0141           lineOverlay.setColor('#FF0000');
0142           lineOverlay.setColorAlpha(1.0);
0143           lineOverlay.setBorderWidth(2);
0144           return lineOverlay;
0145       },
0146
0147       // fetch text nodes contained by node
0148       getChildText: function (node) {
0149           return node
0150             ? Element.cleanWhitespace(node).firstChild.nodeValue
0151             : undefined;
0152       },
0153
0154       // find a child element by tag name
0155       getFirstChild: function(node, tagName) {
0156         var found = node.getElementsByTagName(tagName).item(0);
0157         return found;
0158       }
0159     }
0160
0161     </script>
0162   </head>
0163   <body>
0164     <script>
0165       MQInitDojo(initMap);
0166     </script>
0167     <h1>MapQuest KML Import</h1>
0168     <hr>
0169     <div id="mapWindow" style=""></div>
0170     <hr>
0171     <div id="kml">
0172 <kml xmlns="http://earth.google.com/kml/2.1">
0173 <Document>
0174   <name>Appalachian Trail Centerline</name>
0175   <description>Exported from at_centerline.shp 3/12/02 downloaded from
0176     http://www.appalachiantrail.org using City of Portland's Export to
		 KML 2.3.5
0177     Go Hokies!
0178   </description>
0179   <LookAt>
0180     <longitude>-78.92943061782194</longitude>
0181     <latitude>37.87708055555556</latitude>
0182     <altitude>0</altitude>
0183     <range>1067501.314867445</range>
0184     <tilt>32.73615635179154</tilt>
0185     <heading>1.815747767697585</heading>
0186   </LookAt>
0187   <Folder>
0188     <name>Features</name>
0189
0190 <!-- Routes -->
0191
0192 <Placemark>
0193       <name>1778</name>
0194       <styleUrl>#FEATURES_copy18</styleUrl>
0195       <LineString>
0196         <tessellate>1</tessellate>
0197         <coordinates>
0198 -78.0494085970235,38.9169067777347,0 -78.0494323854585,38.9169149040082,0 ...
	 </coordinates>
0199       </LineString>
0200     </Placemark>

...

1004 <!-- Shelters -- >
1005
1006     <Placemark >
1007       <description>Notes:  Sheltered picnic table, fireplace, and privy;
1008  spri
1009
1010 Fee:  No
1011
1012 Capacity:  6
1013
1014 Maintained By:  Potomac Appalachian Trail Club</description>
1015       <name>David Lesser Shelter</name>
1016       <View>
1017         <longitude>-77.77954</longitude>
1018         <latitude>39.22718</latitude>
1019         <range>999.9999999999999</range>
1020         <tilt>0</tilt>
1021         <heading>0</heading>
1022       </View>
1023       <visibility>1</visibility>
1024       <styleUrl>#cloned1</styleUrl>
1025       <Point>
1026         <coordinates>-77.77954,39.22718,607.9747496823218</coordinates>
1027       </Point>
1028       <styleURL>#cloned0</styleURL>
1029     </Placemark>

...

1182   </Folder>
1183 </Document>
1184 </kml>
1185     <div>
1186   </body>
1187 </html>