Google maps distance approximation

Question

I've started to create a website where it's users are effectively tracked (they know they are being tracked). Users will walk a particular route (around Manchester, UK. to be more precise) of which there are 10 checkpoints. A checkpoint is a static position on the map. Using the Google Maps API I know that I can plot a position on a map i.e. a checkpoint. I am also storing the time at which a user reaches said checkpoint. Taking the distance between checkpoints I am then able to calculate their average speed using basic math.

Now what I would like to do is plot their estimated position based on their speed. The difficulty that I am having is plotting a new position x miles/meters (any unit) from the current position along the route.

Had it been a straight line, this would have been simple.

• Is there a way to calculate a distance from the current position along the route?
• Are there any restrictions on the number of points?
• Are there specific ways of doing this that should be avoided?

To expand my example with an image:

Imagine that a user reached the first place marker at 07:00am and it's estimated they would reach the second place marker at 09:00am. The time now (for example) is 08:00am meaning that (estimated) the user should be about half way between the markers. I would then calculate the distance they have walked (again, estimated) and plot their position on the map "distance" away from the first place marker.

Hopefully I have explained the scenario clear enough for people to understand.

I'm relatively new to the Google maps API so any thoughts would be helpful. Other similar questions have been asked on SO but from what I can see, none have been answered or have requested as many details as I have.

Thanks in advance.

UPDATE: Having spent a lot of time trying to work it out I failed miserably. Here is what I know:

• I should create the path using a PolyLine (I can do this, I have a list of lat/lng)
• There is a JS extension called epoly.js but this isn't compatible with V3
• Using spherical.interpolate wont work because it doesn't follow the path.

Answer 1

I used to do a lot of this stuff in a past life as a cartographer. Your polyline is made up of a succession of points (lat/long coordinates). Between each successive point you calculate the distance, adding it up as you go along until you get to the desired distance.

The real trick is calculating the distance between two lat/long points which are spherical coordinates (ie points on a curved surface). Since you are dealing with fairly small distances you could feasibly convert the lat/long coordinates to the local map grid system (which is flat). The distance between two points is then straight forward right angle pythagoras (sum of the squares and all that). Movable Type website has a lot of good (javascript) code on this here.

The second way would be to do the spherical distance calculation - not pretty but you can see it here

Personally I'd go the route of converting the coordinates to the local grid system which in the UK should be OSGB. Its the least contorted method.

Hope this helps

Edit: I've assumed that you can extract your polyline coordinates using the google api. I havn't done this in version 3 of the api, but it should be straight forward. Also, the polyline coordinates should be fairly close together that you don't need to interpolate intermediate points - just grab the nearest polyline coordinate (saves you having to do a bearing and distance calculation).

Edit2 - With Code

I've had a go at putting some code together, but probably won't have time to finish it within your time limit (I do have a job). You should be able to get the jist. The coordinate conversion code is lifted from the movable type web site and the basic google maps stuff from one of google's examples. Basically it draws a polyline with mouse clicks, puts the lat/long of each mouse click in table field, converts the coordinate to OSGB and then to OS Grid (see here). After the first click it then calculates the distance between each subsequent point. Hope this gets you on the road.

<!DOCTYPE html>
<html>
  <head>
    <meta name="viewport" content="initial-scale=1.0, user-scalable=no" />
    <style type="text/css">
      html { height: 100% }
      body { height: 100%; margin: 0; padding: 0 }
      #map_canvas { height: 100% }
    </style>
    <script type="text/javascript"
      src="http://maps.googleapis.com/maps/api/js?sensor=false">
    </script>

      <script src="Map.js" type="text/javascript"></script>
  </head>
  <body onload="initialize()" style="width:100%;height:100%">
  <div style="margin-right:auto;margin-left:auto;margin-top:100px;width:900px;">
    <div id="map_canvas" style="width:600px; height:500px;float:left;"></div>
      <div style="float:right;">
  <table>
  <tr>
    <td align="right">Latitude:</td>
    <td><input id="txtLatitude" maxlength="11" type="text" class="inputField"/></td>
  </tr>
  <tr>
    <td align="right">Longitude:</td>
    <td><input id="txtLongitude" maxlength="11" type="text" class="inputField"/></td>
  </tr>

  <tr>
    <td align="right">Eastings:</td>
    <td><input id="txtEast" maxlength="11" type="text" class="inputField"/></td>
  </tr>
  <tr>
    <td align="right">Northings:</td>
    <td><input id="txtNorth" maxlength="11" type="text" class="inputField"/></td>
  </tr>

   <tr>
    <td align="right">Distance:</td>
    <td><input id="txtDistance" maxlength="11" type="text" class="inputField"/></td>
  </tr>

  <tr>
    <td colspan=2 align="right">

    </td>
  </tr>
</table>
</div>
  </div>



  </body>
</html>

Map.js:

function initialize() {

    var myOptions = {
        center: new google.maps.LatLng(53.43057, -2.14727),
        zoom: 18,
        mapTypeId: google.maps.MapTypeId.ROADMAP
    };
    var map = new google.maps.Map(document.getElementById("map_canvas"), myOptions);
    var tempIcon = new google.maps.MarkerImage(
    "http://labs.google.com/ridefinder/images/mm_20_green.png",
    new google.maps.Size(12, 20),
    new google.maps.Size(6, 20)
    );
    var newShadow = new google.maps.MarkerImage(
    "http://labs.google.com/ridefinder/images/mm_20_shadow.png",
    new google.maps.Size(22, 20),
    new google.maps.Point(13, 13)
    );

    var tempMarker = new google.maps.Marker();
    tempMarker.setOptions({
        icon: tempIcon,
        shadow: newShadow,
        draggable: true
    });
    var latlngs = new google.maps.MVCArray();
    var displayPath = new google.maps.Polyline({
        map: map,
        strokeColor: "#FF0000",
        strokeOpacity: 1.0,
        strokeWeight: 2,
        path: latlngs
    });
    var lastEast;
    var lastNorth;
    function showTempMarker(e) {
        //Pythagorean distance calculates the length of the  hypotenuse (the sloping side)
        //of a right angle triangle. Plain (cartesian) coordinates are all right angle triangles.
        //The length of the hypotenuse is always the distance between two coordinates.
        //One side of the triangle is the difference in east coordinate and the other is
        //the difference in north coordinates
        function pythagorasDistance(E, N) {
            if (lastEast) {
                if (lastEast) {
                    //difference in east coordinates. We don't know what direction we are going so
                    //it could be a negative number - so just take the absolute value (ie - get rid of any minus sign)
                    var EastDistance = Math.abs(E - lastEast);
                    //difference in north coordinates
                    var NorthDistance = Math.abs(N - lastNorth);
                    //take the power
                    var EastPower = Math.pow(EastDistance, 2);
                    var NorthPower = Math.pow(NorthDistance, 2);
                    //add them together and take the square root
                    var pythagorasDistance = Math.sqrt(EastPower + NorthPower );
                    //round the answer to get rid of ridiculous decimal places (we're not measuring to the neares millimetre)
                    var result = Math.floor(pythagorasDistance);

                    document.getElementById('txtDistance').value = result;
                }
            }

        }

        function calcCatesian(degLat, degLng) {
            var OSGBLL = LL.convertWGS84toOSGB36(new LatLon(degLat, degLng));
            var EN = LL.LatLongToOSGrid(OSGBLL);

            document.getElementById('txtEast').value = EN.east;
            document.getElementById('txtNorth').value = EN.north;
            pythagorasDistance(EN.east, EN.north);
            lastEast = EN.east;
            lastNorth = EN.north;

        }

        tempMarker.setPosition(e.latLng);
        var lat = e.latLng.lat();
        var lng = e.latLng.lng();
        document.getElementById('txtLatitude').value = lat;
        document.getElementById('txtLongitude').value = lng;
        calcCatesian(lat, lng);

        google.maps.event.addListener(tempMarker, "drag", function() {
            document.getElementById('txtLatitude').value = tempMarker.getPosition().lat();
            document.getElementById('txtLongitude').value = tempMarker.getPosition().lng();
            calcCatesian(lat, lng);
        });
        tempMarker.setMap(map);

        var newLocation = new google.maps.LatLng(lat, lng);
        latlngs.push(newLocation);
        displayPath.setPath(latlngs);

    }

    google.maps.event.addListener(map, "click", showTempMarker);
}

// ---- the following are duplicated from LatLong.html ---- //

/*
 * construct a LatLon object: arguments in numeric degrees & metres
 *
 * note all LatLong methods expect & return numeric degrees (for lat/long & for bearings)
 */
function LatLon(lat, lon, height) {
    if (arguments.length < 3)
        height = 0;
    this.lat = lat;
    this.lon = lon;
    this.height = height;
}

function setPrototypes() {

    /*
     * represent point {lat, lon} in standard representation
     */
    LatLon.prototype.toString = function() {
        return this.lat.toLat() + ', ' + this.lon.toLon();
    }
    // extend String object with method for parsing degrees or lat/long values to numeric degrees
    //
    // this is very flexible on formats, allowing signed decimal degrees, or deg-min-sec suffixed by
    // compass direction (NSEW). A variety of separators are accepted (eg 3º 37' 09"W) or fixed-width
    // format without separators (eg 0033709W). Seconds and minutes may be omitted. (Minimal validation
    // is done).

    String.prototype.parseDeg = function() {
        if (!isNaN(this))
            return Number(this);                 // signed decimal degrees without NSEW

        var degLL = this.replace(/^-/, '').replace(/[NSEW]/i, '');  // strip off any sign or compass dir'n
        var dms = degLL.split(/[^0-9.]+/);                     // split out separate d/m/s
        for (var i in dms)
            if (dms[i] == '')
                dms.splice(i, 1);
        // remove empty elements (see note below)
        switch (dms.length) {                                  // convert to decimal degrees...
            case 3:
                // interpret 3-part result as d/m/s
                var deg = dms[0] / 1 + dms[1] / 60 + dms[2] / 3600;
                break;
            case 2:
                // interpret 2-part result as d/m
                var deg = dms[0] / 1 + dms[1] / 60;
                break;
            case 1:
                // decimal or non-separated dddmmss
                if (/[NS]/i.test(this))
                    degLL = '0' + degLL;       // - normalise N/S to 3-digit degrees
                var deg = dms[0].slice(0, 3) / 1 + dms[0].slice(3, 5) / 60 + dms[0].slice(5) / 3600;
                break;
            default:
                return NaN;
        }
        if (/^-/.test(this) || /[WS]/i.test(this))
            deg = -deg; // take '-', west and south as -ve
        return deg;
    }
    // note: whitespace at start/end will split() into empty elements (except in IE)

    // extend Number object with methods for converting degrees/radians

    Number.prototype.toRad = function() {  // convert degrees to radians
        return this * Math.PI / 180;
    }
    Number.prototype.toDeg = function() {  // convert radians to degrees (signed)
        return this * 180 / Math.PI;
    }
    // extend Number object with methods for presenting bearings & lat/longs

    Number.prototype.toDMS = function(dp) {  // convert numeric degrees to deg/min/sec
        if (arguments.length < 1)
            dp = 0;      // if no decimal places argument, round to int seconds
        var d = Math.abs(this);  // (unsigned result ready for appending compass dir'n)
        var deg = Math.floor(d);
        var min = Math.floor((d - deg) * 60);
        var sec = ((d - deg - min / 60) * 3600).toFixed(dp);
        // fix any nonsensical rounding-up
        if (sec == 60) {
            sec = (0).toFixed(dp);
            min++;
        }
        if (min == 60) {
            min = 0;
            deg++;
        }
        if (deg == 360)
            deg = 0;
        // add leading zeros if required
        if (deg < 100)
            deg = '0' + deg;
        if (deg < 10)
            deg = '0' + deg;
        if (min < 10)
            min = '0' + min;
        if (sec < 10)
            sec = '0' + sec;
        return deg + '\u00B0' + min + '\u2032' + sec + '\u2033';
    }
    Number.prototype.toLat = function(dp) {  // convert numeric degrees to deg/min/sec latitude
        return this.toDMS(dp).slice(1) + (this < 0 ? 'S' : 'N');  // knock off initial '0' for lat!
    }
    Number.prototype.toLon = function(dp) {  // convert numeric degrees to deg/min/sec longitude
        return this.toDMS(dp) + (this > 0 ? 'E' : 'W');
    }
    /*
     * extend Number object with methods for converting degrees/radians
     */
    Number.prototype.toRad = function() {  // convert degrees to radians
        return this * Math.PI / 180;
    }
    Number.prototype.toDeg = function() {  // convert radians to degrees (signed)
        return this * 180 / Math.PI;
    }
    /*
     * pad a number with sufficient leading zeros to make it w chars wide
     */
    Number.prototype.padLZ = function(w) {
        var n = this.toString();
        for (var i = 0; i < w - n.length; i++)
            n = '0' + n;
        return n;
    }
};

setPrototypes();

LL = function() {

    // ellipse parameters
    var e = {
        WGS84: {
            a: 6378137,
            b: 6356752.3142,
            f: 1 / 298.257223563
        },
        Airy1830: {
            a: 6377563.396,
            b: 6356256.910,
            f: 1 / 299.3249646
        }
    };

    // helmert transform parameters
    var h = {
        WGS84toOSGB36: {
            tx: -446.448,
            ty: 125.157,
            tz: -542.060,   // m
            rx: -0.1502,
            ry: -0.2470,
            rz: -0.8421,  // sec
            s: 20.4894
        },                               // ppm
        OSGB36toWGS84: {
            tx: 446.448,
            ty: -125.157,
            tz: 542.060,
            rx: 0.1502,
            ry: 0.2470,
            rz: 0.8421,
            s: -20.4894
        }
    };

    return {

        convertOSGB36toWGS84: function(p1) {
            var p2 = this.convert(p1, e.Airy1830, h.OSGB36toWGS84, e.WGS84);
            return p2;
        },
        convertWGS84toOSGB36: function(p1) {
            var p2 = this.convert(p1, e.WGS84, h.WGS84toOSGB36, e.Airy1830);
            return p2;
        },
        convert: function(p1, e1, t, e2) {
            // -- convert polar to cartesian coordinates (using ellipse 1)

            p1.lat = p1.lat.toRad();
            p1.lon = p1.lon.toRad();

            var a = e1.a, b = e1.b;

            var sinPhi = Math.sin(p1.lat), cosPhi = Math.cos(p1.lat);
            var sinLambda = Math.sin(p1.lon), cosLambda = Math.cos(p1.lon);
            var H = p1.height;

            var eSq = (a * a - b * b) / (a * a);
            var nu = a / Math.sqrt(1 - eSq * sinPhi * sinPhi);

            var x1 = (nu + H) * cosPhi * cosLambda;
            var y1 = (nu + H) * cosPhi * sinLambda;
            var z1 = ((1 - eSq) * nu + H) * sinPhi;

            // -- apply helmert transform using appropriate params

            var tx = t.tx, ty = t.ty, tz = t.tz;
            var rx = t.rx / 3600 * Math.PI / 180;  // normalise seconds to radians
            var ry = t.ry / 3600 * Math.PI / 180;
            var rz = t.rz / 3600 * Math.PI / 180;
            var s1 = t.s / 1e6 + 1;              // normalise ppm to (s+1)

            // apply transform
            var x2 = tx + x1 * s1 - y1 * rz + z1 * ry;
            var y2 = ty + x1 * rz + y1 * s1 - z1 * rx;
            var z2 = tz - x1 * ry + y1 * rx + z1 * s1;

            // -- convert cartesian to polar coordinates (using ellipse 2)

            a = e2.a, b = e2.b;
            var precision = 4 / a;  // results accurate to around 4 metres

            eSq = (a * a - b * b) / (a * a);
            var p = Math.sqrt(x2 * x2 + y2 * y2);
            var phi = Math.atan2(z2, p * (1 - eSq)), phiP = 2 * Math.PI;
            while (Math.abs(phi - phiP) > precision) {
                nu = a / Math.sqrt(1 - eSq * Math.sin(phi) * Math.sin(phi));
                phiP = phi;
                phi = Math.atan2(z2 + eSq * nu * Math.sin(phi), p);
            }
            var lambda = Math.atan2(y2, x2);
            H = p / Math.cos(phi) - nu;

            return new LatLon(phi.toDeg(), lambda.toDeg(), H);
        },
        /*
        * convert numeric grid reference (in metres) to standard-form grid ref
        */
        gridrefNumToLet: function(e, n, digits) {
            // get the 100km-grid indices
            var e100k = Math.floor(e / 100000), n100k = Math.floor(n / 100000);

            if (e100k < 0 || e100k > 6 || n100k < 0 || n100k > 12)
                return '';

            // translate those into numeric equivalents of the grid letters
            var l1 = (19 - n100k) - (19 - n100k) % 5 + Math.floor((e100k + 10) / 5);
            var l2 = (19 - n100k) * 5 % 25 + e100k % 5;

            // compensate for skipped 'I' and build grid letter-pairs
            if (l1 > 7)
                l1++;
            if (l2 > 7)
                l2++;
            var letPair = String.fromCharCode(l1 + 'A'.charCodeAt(0), l2 + 'A'.charCodeAt(0));

            // strip 100km-grid indices from easting & northing, and reduce precision
            e = Math.floor((e % 100000) / Math.pow(10, 5 - digits / 2));
            n = Math.floor((n % 100000) / Math.pow(10, 5 - digits / 2));

            var gridRef = letPair + e.padLZ(digits / 2) + n.padLZ(digits / 2);

            return gridRef;
        },
        LatLongToOSGrid: function(p) {
            var lat = p.lat.toRad(), lon = p.lon.toRad();

            var a = 6377563.396, b = 6356256.910;          // Airy 1830 major & minor semi-axes
            var F0 = 0.9996012717;                         // NatGrid scale factor on central meridian
            var lat0 = (49).toRad(), lon0 = (-2).toRad();  // NatGrid true origin
            var N0 = -100000, E0 = 400000;                 // northing & easting of true origin, metres
            var e2 = 1 - (b * b) / (a * a);                      // eccentricity squared
            var n = (a - b) / (a + b), n2 = n * n, n3 = n * n * n;

            var cosLat = Math.cos(lat), sinLat = Math.sin(lat);
            var nu = a * F0 / Math.sqrt(1 - e2 * sinLat * sinLat);              // transverse radius of curvature
            var rho = a * F0 * (1 - e2) / Math.pow(1 - e2 * sinLat * sinLat, 1.5);  // meridional radius of curvature
            var eta2 = nu / rho - 1;

            var Ma = (1 + n + (5 / 4) * n2 + (5 / 4) * n3) * (lat - lat0);
            var Mb = (3 * n + 3 * n * n + (21 / 8) * n3) * Math.sin(lat - lat0) * Math.cos(lat + lat0);
            var Mc = ((15 / 8) * n2 + (15 / 8) * n3) * Math.sin(2 * (lat - lat0)) * Math.cos(2 * (lat + lat0));
            var Md = (35 / 24) * n3 * Math.sin(3 * (lat - lat0)) * Math.cos(3 * (lat + lat0));
            var M = b * F0 * (Ma - Mb + Mc - Md);              // meridional arc

            var cos3lat = cosLat * cosLat * cosLat;
            var cos5lat = cos3lat * cosLat * cosLat;
            var tan2lat = Math.tan(lat) * Math.tan(lat);
            var tan4lat = tan2lat * tan2lat;

            var I = M + N0;
            var II = (nu / 2) * sinLat * cosLat;
            var III = (nu / 24) * sinLat * cos3lat * (5 - tan2lat + 9 * eta2);
            var IIIA = (nu / 720) * sinLat * cos5lat * (61 - 58 * tan2lat + tan4lat);
            var IV = nu * cosLat;
            var V = (nu / 6) * cos3lat * (nu / rho - tan2lat);
            var VI = (nu / 120) * cos5lat * (5 - 18 * tan2lat + tan4lat + 14 * eta2 - 58 * tan2lat * eta2);

            var dLon = lon - lon0;
            var dLon2 = dLon * dLon, dLon3 = dLon2 * dLon, dLon4 = dLon3 * dLon, dLon5 = dLon4 * dLon, dLon6 = dLon5 * dLon;

            var N = I + II * dLon2 + III * dLon4 + IIIA * dLon6;
            var E = E0 + IV * dLon + V * dLon3 + VI * dLon5;

            E = Math.floor(E * 100) / 100;
            N = Math.floor(N * 100) / 100;

            //return this.gridrefNumToLet(E, N, 8);
            return { east: E, north: N }
        ;
        }
    }

} ();