A Linear Clustering Algorithm for Virtual Earth

by Gong Liu May 22, 2009 05:12

Official Tracker for Katie Visco's Run Across America   

A while ago a friend showed me a piece of news about a girl named Katie Visco who is about to become the youngest female ever to run solo across America. I thought her story was very inspirational and contacted her about tracking her run on the internet. She was thrilled about the idea and I ended up hosting and maintaining the following tracker about her run. I update the tracker every day based on the mileage log published on her blog site Pave Your Lane

Technical Notes

Linear Clustering Algorithm  

The above tracker is very similar to my workout tracker. However, one key difference is that her tracker shows every day on the map while my tracker only shows my workout days. In her case, the running days are marked by a little red square  and the resting days by a little yellow square . On some resting days she may stay at the same location and thus the day markers overlap. If you hover the mouse cursor on overlapped markers, only the infobox of the top most marker is shown, no matter how closely you zoom in. In the above tracker I have solved the problem by representing overlapped markers with a bigger yellow square . When you hover the mouse cursor on the bigger marker, you will see a list of days it represents. Clicking on one of the days will show that day's infobox at the same location. The technique behind the solution is called pushpin clustering. Pushpin clustering is a process of representing several nearby pushpins with a single pushpin. The original purpose of this is to reduce overcrowded pushpins that may obscure the map underneath. We use pushpin clustering to gain access to overlapped pushpins or markers. Overcrowding is not much of a concern here. Before Virtual Earth 6.2, developers using the Virtual Earth map control would have to either divide groups of pushpins into shape layers and manually control which layers to show and hide at different zoom levels, or just not show pushpins at zoom levels if there were too many on the screen. With Virtual Earth 6.2, it becomes a lot easier to control which pushpins are clustered and how a cluster is displayed.

There are two overloaded methods related to pushpin clustering in VE 6.2:

VEShapeLayer.SetClusteringConfiguration(type, options)
VEShapeLayer.SetClusteringConfiguration(algorithm, options)

The first method allows you to choose one of the pre-defined clustering algorithms. In VE 6.2, there is only one pre-defined clustering algorithm - the grid clustering algorithm. The grid clustering algorithm divides map screen into grids and pushpins falling in one grid are represented by a single pushpin at the grid center. The second method allows you to define your own clustering algorithm. The second parameter in both methods, options, is a VEClusteringOptions object that specifies how a pushpin cluster is displayed in terms of an icon and a callback function where you put your own code to do something about each cluster, such as rendering an infobox.

In our case, the day markers are along some line features (roads), and we are only interested in making overlapped markers into clusters. So the pre-defined grid algorithm is not applicable. We have to roll out our own algorithm, which I call a linear clustering algorithm because of the unique spatial distribution of our markers.

Simply stated, any two or more consecutive markers that overlap or are close enough form a cluster. The following figures show when markers form a cluster and when they don't according to our linear clustering algorithm.
   

The current marker (black square) in A) does not belong to any cluster because none of its consecutive markers (markers immediately before and after it) is close enough to it. By close enough we mean within a pre-defined square area (or a circle). The side d of the square area is measured in degrees same as latitude/longitude, instead of pixels, and thus the clustering does not change with different zoom levels. By our definition the current marker in B) forms a cluster with its next marker. Backtracking and loop as shown in C) and D) do not form a cluster, because the two markers in the square are not consecutive.

Now let's take a look at some code snips.

    ......
    //load day markers to the third layer
    var layer3 = new VEShapeLayer(); 
    var co = new VEClusteringOptions();
    var customIcon = new VECustomIconSpecification();
    customIcon.CustomHTML = "<div style='margin-top: 10px; margin-left: 10px'><img src='images/yellowsquarelarge.gif' width='8' height='8'></div>";
    co.Icon = customIcon;
    co.Callback = ClusterCallback;
    layer3.SetClusteringConfiguration(LinearClusterAlgorithm, co);
    map.AddShapeLayer(layer3);
    var shapes = new Array();
    for (var i = 0; i < days.length; i++)
    {
        var sh = new VEShape(VEShapeType.Pushpin, days[i].CityCenter);
        sh.SetTitle(days[i].Date.toDateString() + " - Day " + (i + 1));
        if (days[i].RunningDay)
            sh.SetCustomIcon("<div style='margin-top: 11px; margin-left: 10px'><img src='images/redsquare.gif' width='5' height='5'></div>");
        else
            sh.SetCustomIcon("<div style='margin-top: 11px; margin-left: 10px'><img src='images/yellowsquare.gif' width='5' height='5'></div>");   
        sh.SetDescription(days[i].GetHTML());
        shapes[i] = sh;
    }
    layer3.AddShape(shapes);  
    ......

The above code snip shows that a shape layer is created for day markers. The SetClusteringConfiguration method indicates that the layer is configured to do clustering. The clustering algorithm is defined by a function called LinearClusterAlgorithm and any cluster is going to be dispayed according to the way specified in a VEClusteringOptions object, which includes a display icon (the bigger yellow square ) and a callback function ClusterCallback. The for loop creates day markers as an array of shapes, which is then added to the layer in a batch.

The function LinearClusterAlgorithm is defined as:

function LinearClusterAlgorithm(sLayer)
{
    var arrCSs = new Array();
    var n = sLayer.GetShapeCount();
    if (n > 0) 
    {
        var shape0 = sLayer.GetShapeByIndex(0);
        var pt0 = shape0.GetPoints()[0];
        var clusterSpec = null;
        for(var i = 1; i < n; i++)
        {
            var shape1 = sLayer.GetShapeByIndex(i);
            var pt1 = shape1.GetPoints()[0];
            if (Overlap(pt0, pt1))
            {
                if (clusterSpec == null)
                {
                    clusterSpec = new VEClusterSpecification();
                    clusterSpec.Shapes = new Array();
                    clusterSpec.Shapes.push(shape0);
                }
                clusterSpec.Shapes.push(shape1);
                clusterSpec.LatLong = pt1;
                if (i == n-1)
                    arrCSs.push(clusterSpec);   
            }
            else
            {
                if (clusterSpec != null)
                {
                    arrCSs.push(clusterSpec);
                    clusterSpec = null;
                }
            }
           
            shape0 = shape1;
            pt0 = pt1;     
        }
    }
    return arrCSs;
}

function Overlap(pt0, pt1)
{
    var dd = 0.0001;
    return (Math.abs(pt0.Latitude - pt1.Latitude) < dd && 
            Math.abs(pt0.Longitude - pt1.Longitude) < dd);
}

Here, sLayer is a VEShapeLayer object that the algorithm is going to apply to. The main part of the algorithm consists of a for loop that compares first two consecutive shape points, points 0 and 1, then points 1 and 2, and so on. If any two consecutive points overlap, they form a cluster and are added to the Shapes property of a VEClusterSpecification object. Otherwise, the VEClusterSpecification object is added to an array, which is returned to caller at the end of the loop. The function Overlap is used to determine if two points overlap. "Overlap" does not necessarily mean the two points have to have the same coordinates, but rather their differences are within a pre-defined range.

The ClusterCallback function is as follow:

function ClusterCallback(CSs)
{
    for (var i=0; i < CSs.length; ++i)
    {
        var clusterSpec = CSs[i];
        var clusterShape = clusterSpec.GetClusterShape();
        var shapes = clusterSpec.Shapes;
        clusterShape.SetTitle(shapes.length + " Days");
        var html = "";
        for (var j = 0; j < shapes.length; j++)
        {
            var shape = shapes[j];
            var icon = (shape.GetDescription().indexOf("alt='run'") > 0)? "redsquare.gif" : "yellowsquare.gif";
            html += "<img border='1' src=\"Images/" + icon + "\"> ";
            html += "<a href=\"Javascript: map.HideInfoBox(); ShowInfo('" + shape.GetID() + "')\">" + shape.GetTitle() + "</a><br>"
        }
        clusterShape.SetDescription(html);
    }
}

It accepts an array of VEClusterSpecification objects as parameter, each of which represents a cluster. Each cluster has at least two shape points. The inner for loop uses the info of these points to construct a html snip that is to be used as the description of the cluster's infobox.

When there are overlapped day markers, the touring feature is affected. This is because the ShowInfoBox method is normally called immediately after the map is panned from one point to the next (in the onendpan event handler). But if two or more points overlap, there is no pan action and the onendpan event will not fire, and thus the corresponding infoboxes will not show. To overcome this, we have to call the handler directly at the time an overlap is detected.

Image Overlay

The above tracker has a title image along the top side. Notice that the image is on top of the map layer but under the map control panel, and that the portion of the map that is under the image is still responsive to mouse drag. To overlay the image, I add an image tag just before the myMap div tag:

<img src="images/title.jpg" id="overlay" style="z-index:50; opacity: 0.7; filter: alpha(opacity=70); position:absolute; left:0px; top:0px" alt="pave your lane" />
<div id="myMap" style="width:800;height:600;position:relative;"></div> 

The style opacity: 0.7 works for Firefox and filter: alpha(opacity=70) works for IE 7.0+. So I use both. They make the image semi-transparent. z-index must be > 0, otherwise the image is put behind the map and thus can't be seen. 

The problem with the image tag itself is that it sits on top of both the map layer and the map control panel and make them not responsive to mouse actions. To solve this problem we have to add the image tag as a child node of the myMap div tag:

var veLayer = document.getElementById('myMap');
var imageOverlay = document.getElementById('overlay');
veLayer.appendChild(imageOverlay);  

Finally we have to make sure that the z-index of the image tag is between 1 and 99. A z-index value greater than 99 will put the title image above the map control panel, making it unusable.

Another possible way to overlay an image is to use a custom layer, a feature newly available in VE 6.2.  I tried this way but was unable to anchor the image to the top left corner - the image moves as the map is panned. If you know how to do this using custom layer, please let me know.

Forrest Gump Route

by Gong Liu April 22, 2009 04:45

Forrest Gump is one of my favorite movie characters. In the movie, among other things, he was portrayed as a man with incredible running ability. He constantly ran from bullies at a young age. He became a member of the All-American team at college because he could outran all other football players. He ran under heavy artillery to save his fellow soldiers during Vietnam War. And of course most famously, he ran across America back to back several times over a span of three years to get over the heartbreak of Jenny's leaving him.

Putting aside the symbolism of all his runs, I always wondered how realistic his ultramarathon run was (even though it's a fiction, you don't want to show too many goofs in the movie), what route he had completed, and how he measured up with real ultramarathon runners. So I watched the movie a few more times (especially the running part) and did some detective work on the topic. I came up these clues:

  • Forrest started his three-year-long run from his front porch in Greenbow, AL in the early morning of July 5, 1976. Greenbow, AL is fictional but according to the Forrest Gump novel Forrest's hometown is Mobile, AL.
  • Forrest headed to the west first. He ran clear the ocean and reached the west coast at Santa Monica Pier, Santa Monica, CA. He then turned around, kept on going and got to another ocean (Atlantic Ocean) at Marshall Point Lighthouse, Marshall Point Road, Port Clyde, ME. He only stopped for sleeping, eating and going to bathroom (see this 0:00:46 2.97MB movie clip . Sorry for the squeezed frames. Still haven't figured out how to adjust the aspect ratio in Adobe Premiere).
  • This 0:00:27 1.10BM movie clip shows that Forrest had run for more than two years and was about to cross the Mississippi River for the 4th time at somewhere near St. Louis, MO. Most amazingly, the TV screen actually showed a sketch of his route up to then.
  • We don't know what route Forrest took after he crossed Mississippi River for the 4th time, but we do know where and when he ended his run. Based on this 0:01:26 3.77MB movie clip, he ended his run at Monument Valley, UT on US Highway 163 near UT and AZ border in the evening of September 19, 1979. He had run for 3 years 2 months 14 days and 16 hours.

Obviously, the single most important clue is the sketch of the route on the TV screen. The following image shows a enlarged and sharpened frame of it.

   

From this sketch we know in more than two years he ran across America about 3.5 times. For the remaining a year or less, he probably kept running to the east, hit the east coast somewhere, turned around and started his fifth crossing from east to west. We know he ended the run in Utah. The question is: did he stop in Utah before he finished the fifth crossing or after he finished the fifth crossing and started the sixth crossing from the west coast? My guess is that he didn't finish the fifth crossing because he probably didn't have enough time otherwise, if he kept the same pace throughout his journey. The last movie clip indicates that just before he stopped at Monument Valley, UT, he was running from east to west because when he said "I'm pretty tired. I think I'll go home now", he went to the opposit direction, his home direction.   

Based on the sketch and fair amount of guesswork, I came out the following list of cities that he might went through:

Cross1 Cross2 Cross3 Cross4 Cross5
Mobile, AL Santa Monica Pier, Santa Monica, CA Marshall Point Rd, Port Clyde, ME San Francisco, CA Norfolk, VA
Dallas, TX Las Vegas, NV Burlington, VT Reno, NV Pittsburgh, PA
Alamogordo, NM St George, UT Watertown, NY Salt Lake City, UT Indianapolis, IN
Phoenix, AZ Albuquerque, NM Cleveland, OH Fort Duchesne, UT Lincoln, NE
Santa Monica Pier, Santa Monica, CA Oklahoma City, OK Lansing, MI Craig, CO Denver, CO
  Knoxville, TN Chicago, IL Denver, CO US-163, UT
  Harrisonburg, VA Rapid City, SD St Louis, MO  
  Washington, DC Boise, ID Richmond, VA  
  New York, NY Portland, OR Norfolk, VA  
  Boston, MA San Francisco, CA    
  Marshall Point Rd, Port Clyde, ME      

Using these cities as waypoints I was finally able to generate the Forrest Gump Route and this is what it looks like in Virtual Earth (click it to see live demo):

Notice that the route I generated does not match the sketch very closely. This is because 1) My route is entirely based on drivable roads. The route engine used tends to pick fast, major highways, while Forrest might pick any roads, including less important country roads; 2) The sketch is not very realistic in areas such as big mountain ranges and deserts, where there are simply no roads, assuming he always ran on some kind of roads. 

The following table compares Forrest Gump with some famous distance runners:

Runner Forrest Gump Jesper Olsen Dean Kamazes Mark Covert Frank Giannino
Duration
(days)
1169.7 660 50 14600 46.3
Distance
(miles)
15182 16156 1310 150000 3000
Speed
(miles/day)
13.0 24.5 26.2 10.3 64.8
Description Forrest Gump ran across America back-to-back for five times in a span of three years (1976 - 1979), covered a distance of some 15,000 miles. Jesper Olsen of Denmark is the record holder of world run. He ran around the world in 22 months, on a route consisting of: London-Copenhagen-Moscow-Vladivostok-(air)-Niigata-Tokyo-(air)-Sydney-Perth-(air)-Los Angeles-Vancouver-New York-(air)-Shannon-Dublin-(air)-Liverpool-London. It covers a land distance of some 26000 km. Dean Kamazes, the ultramarathan man, was ranked by a TIME magazine poll as one the "Top 100 Influential People in the World." One of his recent endeavors was running 50 marathons, in all 50 states, in 50 consecutive days. Mark Covert, a teacher of Lancaster, CA, is the longest streaker in the U.S., having run at least one mile a day everyday since July 23, 1968, which is more than 40 years and still counting! His lifetime total distance is over 150,000 miles so far. The trans USA ultramarathon record is 46 days 8 hours 36 minutes (San Francisco, CA - New York, NY) set by Frank Giannino in 1980.

By comparison Forrest Gump was more like a streak runner than a marathoner. He ran at a moderate rate everyday for a relatively long period of time. Keep in mind that he did not run for setting record. He did it for clearing his mind as he explained "My mama always said 'you got to put the past behind you before you can move on' and I think that's my run was all about."

Now I have figured out the Forrest Gump Route. The next thing is to form a "Forrest Gump 5X-Country Running Association" and have some crazy runners try it out. Laughing

Technical Notes

  • The movie captions are created using Microsoft Movie Maker
  • The code for numbered pushpins is taken from Keith Kinnan's Blog
  • The route shape data is generated using Google Earth
  • The shape data reduction was discussed in this post

Virtual Earth Workout Tracker - Part II

by Gong Liu March 31, 2009 00:45

In Part I, I decribed what the Virtual Earth Workout Tracker was, and how it could be a useful tool for tracking one's workout and motivating him to keep going. In this part, I'll describe how to implement the Workout Tracker with Virtual Earth SDK.

Generating the Route

Normally, you want to generate a route that is closely resembling the physical thing on the ground, whether it's a highway or things like the Greate Wall of China. There are basically two ways to generate a route: trace the route manually with the aid of some mapping tool, or generate it automatically with a route engine. The following screenshot shows how you could trace a stretch of highway, say Route 66, using Google Earth.

Google Earth will save the route you are tracing in KML format, which is just XML understandable by any XML parser. As to how many points you need, depending on the length and geometry of the route, a few hundread to a couple of thousand points seem to be a good number. You need more points to trace the route more closely, but it will take longer time to get it done and longer computing time to render the route.

If your route is along drivable roads, you could probably generate the route automatically using some route engine, such as the one in Virtual Earth or Google Earth. One issue with a route engine is that it has its own mind. The route it genetares may not include all the roads you want. In this case, you will need to set up a multi-waypoint route. The waypoints provide some sort of a guideline on how the route should be generated. In Virtual Earth, once a route is generated, you can get all the points that describe the shape of the route with the VERoute.ShapePoints property. Note that this property is only available to licensed Virtual Earth developers.

If you generate the route with Google Earth, you get all the details about the route in a KML file, something like:

<?xml version="1.0" encoding="UTF-8"?>
<kml xmlns="http://earth.google.com/kml/2.2">
<Document>
 <name>KmlFile</name>
 <Style id="roadStyle">
  <LineStyle>
   <color>7fcf0064</color>
   <width>6</width>
  </LineStyle>
 </Style>
 <Placemark>
  <name>Route</name>
  <description>
   <![CDATA[Distance: 3,034 mi Map data 2009 Maponics, Sanborn, Tele Atlas]]>
  </description>
  <styleUrl>#roadStyle</styleUrl>
  <MultiGeometry>
   <LineString>
    <coordinates>
      -118.38541,33.83817,0 -118.38331,33.83788,0 -118.38157,33.83755000000001,0 -118.38086,33.83751,0 ......
    </coordinates> 
   </LineString>
  </MultiGeometry>
 </Placemark>
</Document>
</kml>

Polyline Reduction and Douglas-Peucker Algorithm

For a long route generated with a route engine, the number of points can be huge. For example, a coast-to-coast cross country route generated with Google Earth contains some 12,500 points. To draw the route with so many points would cause significant delay when the Workout Tracker is started. To improve the performance, we need to reduce the number of points, but at the same time maintain the general shape of the route. This type of problem is called polyline reduction or polyline simplification. One of the best-known algorithms for polyline reduction is the Douglas-Peucker algorithm. The following series of diagrams from McNeel Wiki best illustrate how the algorithm works:   

 

 

 

I found a C# implementation of the algorithm here. I modified the code to accept latitude/longitude points instead of integer points. I also added to the algorithm an interface that reads a polyline (route) from a KML file and writes the reduced polyline to a javascript file in form of a javascript array: 

var route = new Array(
new VELatLong(33.83817,-118.38541),
new VELatLong(33.83748,-118.35352),
new VELatLong(33.85775,-118.35359),
......
);

The screenshot below is the interface to the polyline reduction algorithm:

The single parameter that controls which points are removed and how many points are removed is the tolerance, which is the maximum allowable distance from a point to the nearest line segment (the dashed blue lines in the above series of diagrams). The total route distance can also serve as a crude measurement about how well a reduction is. The following table shows the point count and total distance vs. the tolerance for my cross country route:

The data in the table shows that as the tolerance increases, the number of points needed to describe the shape of the route decreases. In extreme, when the tolerance is big enough, only 2 points, the starting point and the ending point, are needed. Notice that as the tolerance increases, the route distance becomes shorter and shorter as compared to the original route distance. In my case, I use the route with 614 points (tolerance = 0.005°). This represents a 95% point reduction, while the route distance is only about 32 miles shorter or 1% shorter than the original route. Even at this level of reduction, you won't notice the discrepancy between the orginal route and reduced route up to about zoom level 9 (Virtual Earth has total 19 zoom levels, with the zoom level 19 representing the closest level to the ground). If you zoom in closer, you will see the difference, though. 

You may prefer a route with less reduction and thus less discrepancy, but you need to strike a balance between accuracy and the loading speed.

Implementation

There are 4 layers of data on the map. The first layer contains the route (cyan color). The second layer contains the progress polyline (red color). The third layer contains the workout day markers (red little requares). The fourth layer contains the starting point (green pushpin) and the ending point (red pushpin).

The route is loaded on the map with this script:

function LoadRoute()
{
    var layer = new VEShapeLayer();   //layer 1
    map.AddShapeLayer(layer); 
    var shape = new VEShape(VEShapeType.Polyline, route);
    shape.HideIcon();
    shape.SetLineColor(new VEColor(0,255,255,0.5));
    shape.SetFillColor(new VEColor(0,255,255,0.5));
    shape.SetLineWidth(5);
    layer.AddShape(shape);        

Here, route is the javascript array generated by the polyline reduction program mentioned earlier.

For simplicity, we use the following 2D javascript array to hold our workout data:

var data = new Array(
//Date, Comment, Fitness Machine, Mileage, Calories, Fitness Machine, Mileage, Calories, ...
new Array("2/24/2009", "A Long Journey Begins with the First Step", "Stationary Bike", 9, 150, "Stair Master", 2.3, 280),
new Array("2/25/2009", "", "Stationary Bike", 10, 170, "Elliptical Trainer", 1.7, 168, "Treadmill", 3, 340),
new Array("2/26/2009", "", "Stationary Bike", 9, 150, "Stair Master", 2.3, 280),
new Array("2/27/2009", "", "Stationary Bike", 9, 150, "Treadmill", 3, 350),
......
);

Each row in the above array represents a workout day, and each workout day has a date field, a comment field, and one or more workout items with each workout item containing such information as fitness machine used, distance covered, and calories burned. Of course, in a real application the workout data is most likely stored in a backend database.

To facilitate the manipulation of the workout data, we further define the following two javascript objects, WorkoutDay and WorkoutItem:

function WorkoutDay(dt, comment, items) {
    this.Date = dt;
    this.Comment = comment;
    this.Items = items;
    this.Point = null;
    this.CumulatedDistance = 0;
    this.CumulatedCalories = 0;
    this.GetDayMiles = function() {
        var m = 0;
        for(var i = 0; i < items.length; i++)
            m += items[i].Miles;
        return m;
    };
    this.GetDayCalories = function() {
        var c = 0;
        for(var i = 0; i < items.length; i++)
            c += items[i].Calories;
        return c;
    };
    this.GetHTML = function() {
        var s = "<table cellspacing='0' cellpadding='2' border='0' width='200'>";
        for(var i = 0; i < items.length; i++)
        {
            s += "<tr>";
            s += "<td>Type:</td>";
            s += "<td><img src='Images/" + items[i].GetTypeImage() + "' alt='" + items[i].Type + "'></td>";
            s += "</tr>";
            s += "<tr>";
            s += "<td>Distance:</td>";
            s += "<td>" + items[i].Miles + " miles</td>";
            s += "</tr>";
            s += "<tr>";
            s += "<td>Calories:</td>";
            s += "<td>" + items[i].Calories + "</td>";
            s += "</tr>";
            s += "<tr>";
            s += "<td colspan='2'><hr></td>";
            s += "</tr>";
        }
        s += "</table>";
        s += "<table cellspacing='0' cellpadding='2' border='0' width='200'>";
        s += "<tr><td>Day total dist:</td><td>" + this.GetDayMiles() + " miles</td></tr>";
        s += "<tr><td>Day total calories:</td><td>" + this.GetDayCalories() + "</td></tr>";
        s += "<tr><td>Cumulated dist:</td><td>" + this.CumulatedDistance.toFixed(1) + " miles</td></tr>";
        s += "<tr><td>Cumulated calories:</td><td>" + this.CumulatedCalories.toFixed(1) + "</td></tr>";
        if (this.Comment != "")
        {
            s += "<tr><td colspan='2'><hr></td></tr>";
            s += "<tr><td colspan='2'>" + this.Comment + "</td></tr>";
        }
        s += "</table>";
        return s;
    };
}

function WorkoutItem(type, miles, calories) {
    this.Type = type;
    this.Miles = miles;
    this.Calories = calories;
    this.GetTypeImage = function() {
        // Replace " " with ""
        var re = / /g;
        var r = type.replace(re, "");
        return r.toLowerCase() + ".gif";
    };

The WorkoutDay.Items property is an array of WorkoutItem objects. The WorkoutDay.GetHTML method generates a HTML snip to be presented in the InfoBox of the workout day marker. It includes such info as the workout activities and statistics for the current workout day. The WorkoutDay.CumulatedDistance property represents the cumulated workout mileage from all previous workout days through the current workout day. The WorkoutDay.Point property is a VELatLong object that marks the position of the current workout day along the route.

Referring to the above diagram, P0 ... Pn are route points. Q is the WorkoutDay.Point, and its coordinates can be determined in the following way:

  • Calculate WorkoutDay.CumulatedDistance, which is denoted by cd
  • Calculate the cumulated route distance from P0 through Pi-1, which is denoted by cdr
  • Calculate the distance between Pi-1 and Pi, which is denoted by D
  • Whether Q is in between Pi-1 and Pi is determined by this condition: cdr < cd < cdr + D 
  • Calculate d = cd - cdr
  • Calculate the coordinates of Q by linear interpolation: 
      

Finally, we are ready to show the script for loading the second, third and fourth layers of data:

function LoadData()

    //populate an array of WorkoutDay objects with workout data
    workoutdays = new Array(data.length);
    for (var i = 0; i < data.length; i++)
    {
        var items = new Array();
        for (var j = 2; j < data[i].length; j += 3)
        {
            var item = new WorkoutItem(data[i][j], data[i][j+1], data[i][j+2]);
            items.push(item);
        }
        var dt = new Date(Date.parse(data[i][0]));
        var comment = data[i][1];
        var wd = new WorkoutDay(dt, comment, items);
        workoutdays[i] = wd;
    }
    //Calculate cumulated mileage, calories and workout day position
    for (var i = 0; i < workoutdays.length; i++)
    {
        if (i == 0)
        {
            workoutdays[i].CumulatedDistance = workoutdays[i].GetDayMiles();
            workoutdays[i].CumulatedCalories = workoutdays[i].GetDayCalories();
        }
        else
        {
            workoutdays[i].CumulatedDistance = workoutdays[i-1].CumulatedDistance + workoutdays[i].GetDayMiles();
            workoutdays[i].CumulatedCalories = workoutdays[i-1].CumulatedCalories + workoutdays[i].GetDayCalories();
        }
        workoutdays[i].Point = GetProgressPoint(workoutdays[i].CumulatedDistance);
    }
   
    //load progress polyline to the second layer
    var layer2 = new VEShapeLayer(); 
    map.AddShapeLayer(layer2);
    var points = new Array();
    for (var i = 0; i < lastDayIndex; i++)
        points[i] = route[i];
    points.push(workoutdays[workoutdays.length-1].Point);
    var shape = new VEShape(VEShapeType.Polyline, points);
    shape.HideIcon();
    shape.SetLineColor(new VEColor(255,0,0,0.5));
    shape.SetFillColor(new VEColor(255,0,0,0.5));
    shape.SetLineWidth(7);
    layer2.AddShape(shape);      
   
    //load workout day markers to the third layer
    var layer3 = new VEShapeLayer(); 
    map.AddShapeLayer(layer3);
    var shapes = new Array();
    for (var i = 0; i < workoutdays.length; i++)
    {
        var sh = new VEShape(VEShapeType.Pushpin, workoutdays[i].Point);
        sh.SetTitle(workoutdays[i].Date.toDateString() + " - Day: " + (i + 1));
        sh.SetCustomIcon("<div style='margin-top: 11px; margin-left: 10px'><img src='images/redsquare.gif' width='5' height='5'></div>");
        sh.SetDescription(workoutdays[i].GetHTML());
        shapes[i] = sh;
    }
    layer3.AddShape(shapes);
   
    //load starting and ending points to the fourth layer
    var layer4 = new VEShapeLayer(); 
    map.AddShapeLayer(layer4);
    var startPt = new VEShape(VEShapeType.Pushpin, route[0]);
    startPt.SetTitle(od[0][0]);
    startPt.SetCustomIcon("<div style='margin-top: -31px; margin-left: -5px'><img src='images/" + od[0][1] + "'></div>");
    startPt.SetDescription(od[0][2]);
    startPt.SetMoreInfoURL(od[0][3]);
    layer4.AddShape(startPt);
    var endPt = new VEShape(VEShapeType.Pushpin, route[route.length - 1]);
    endPt.SetTitle(od[1][0]);
    endPt.SetCustomIcon("<div style='margin-top: -32px; margin-left: 6px'><img src='images/" + od[1][1] + "'></div>");
    endPt.SetDescription(od[1][2]);
    endPt.SetMoreInfoURL(od[1][3]);
    layer4.AddShape(endPt);
}

function GetProgressPoint(cd)
{
    var pt1 = route[0];
    var pt2;
    var cdr = 0;
    for (var i = 1; i < route.length; i++)
    {
        pt2 = route[i];
        var D = GetDistance(pt1, pt2);
        if (cdr + D > cd)
        {
            var d = cd - cdr;
            var k = d/D;
            lastDayIndex = i;
            return new VELatLong(pt1.Latitude + k * (pt2.Latitude - pt1.Latitude), pt1.Longitude + k * (pt2.Longitude - pt1.Longitude));
        }
        cdr += D;
        pt1 = pt2;
    }
    lastDayIndex = route.length - 1;
    return pt2; //last route point or destination
}

function GetDistance(pt1, pt2)
{
    var EarthRadiusInMiles = 3963.23;
    var RadiansPerDegree = 0.017453292519943295;
    return EarthRadiusInMiles * RadiansPerDegree * Math.sqrt((pt2.Latitude - pt1.Latitude) * (pt2.Latitude - pt1.Latitude) +
            Math.pow((pt2.Longitude - pt1.Longitude) * Math.cos(RadiansPerDegree * 0.5 * (pt1.Latitude + pt2.Latitude)), 2));
}

The above formula is used in the function GetProgressPoint(). The distance formula in GetDistance() was discussed in this post.

The touring/slide show feature was discussed in this post.

Further Improvements

Here are some ideas for further improvements on the Workout Tracker:

  • Use a database to store the workout data
  • Provide a web interface to allow a user to enter his workout data into the database
  • Provide a mobile interface so that a user can capture his workout data in the gym and send it out to the server via his cell phone
  • Support a group of users

Virtual Earth Workout Tracker - Part I

by Gong Liu March 26, 2009 11:27

I picked up a 24 Hour Fitness membership last Thanksgiving, but I realized that I would need something to motivate myself to go to the gym as often as I could. I remembered when I was in junior high school we had a long-distance running event. The goal of the event was to cumulate the running mileage of all students in a class to reach a number that symbolized something. Of course, in that era of China, every event had to be political. We symbolized our running as the Long March led by Chairman Mao in 1934-35, which covered some 8000 miles. I remembered we had a paper map that highlighted our symbolized route. Each day our class monitor would advance a little flag pin along the route to show our collective progress. We were encouraged to compare our map with that of other classes throughout the school. Man, that little map motivated me so much that I would run 10 kilometers a day almost every day for the entire event!

So I set out to create an electronic version of the paper map I had in junior high. It will serve the purposes of tracking my workout and motivating me by showing my daily progress against my goals. The result is the Virtual Earth Workout Tracker, as shown below.

Main Features

The workout tracker has these features:

  • It clearly shows the symbolized route and my workout progress on Virtual Earth. I can zoom and pan the map any way I want.
  • At the bottom is a bar graph that shows my progress against my goals in terms of days passed (which include workout days and resting days), cumulated distance, and cumulated calories .
  • Each workout day is marked as a little red square along the route. Clicking a workout day marker will show me the workout activities and statistics for that day.
  • I can play a slide show about all my workout days with the controls at the bottom-left corner.

Goal Setting 

My primary goal is to go to the gym or do some kind of outdoor activities as often as I can so that fitness becomes part of my life style. My plan is to cross the US coast to coast in one year, symbolicly that is. The total distance is about 3000 miles. I can make it if I workout 300 days of the year at the rate of 10 miles per day. That leaves me one day of rest per week, plus some holidays. Of course running 10 miles per day is unrealistic for my condition. So I will have to "cheat" a little bit - every activity by any means counts. All the cardio machines in the gym count, treadmill, elliptical trainer, stairmaster, stationary bike, etc. All outdoor activities count, jogging, biking, hiking, swimming, etc. I'm allowed to collect about 9 miles a day simply by biking to and from my workplace, for example.

My secondary goal is to lost some weight and build strength. I intend to lost 20 pounds to reach my desired body weight, which means I need to burn at least 70,000 calories in one year. All cardio machines in the gym have calorie readings, even though they are not terribly accurate. By my experience elliptical trainers tend to over estimate calories burned, while treadmills and stairmasters tend to do the oppsite. Counting calories burned druing weight lifting is too tedious, so I'll simply ignore it. For outdoor activities, I will use the following table as reference:

   

These numbers are based on the Health Calculators found here. Calorie-intake and basic metabolic rate are also very important. But again they are too tedious to count. I'll simply multiply the original calorie goal by a factor of 2 to accomadate all the uncertainties. So my final calorie goal is 140,000 160,000 175,000 calories per year.

About the Route

The route I choose has no particular meaning other than the fact that it is cross country and about 3000 miles. It starts from Redondo Beach, CA and ends at Plymouth, MA. The route is actually a drivable route generated by Vertual Earth route engine. Of course, if you want, you can choose some famous historical route or a route that is meanful to you. Here are some ideas:

In Part II, I will disciss the technical aspect of the Virtual Earth Workout Tracker.

About

A seasoned computer professional. A tofu culture evangelist...
more >>

Tag Cloud

Calendar

<<  April 2017  >>
MoTuWeThFrSaSu
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

View posts in large calendar
Copyright © 2008-2011 Gong Liu. All rights reserved. | credits | contact me
The content on this site represents my own personal opinions, and does not reflect those of my employer in any way.