How to test if a geographic location has been visi

Question

OK, so I already have the answer to this question but it took me a long time to reach it so I thought I would share it, particularly since someone asked me but under an unrelated question

I created a Phonegap-based navigation app for guided walks that tracks the user's location around a predefined route using GPS. My routes have triggers placed at specific geo-locations around the route which give instructions to the user based on their current location. The problem is that GPS is not super accurate or reliable, so even though I allowed a "visiting radius" around those locations of around 20 metres, real-world testing resulted in those triggers sometimes being missed because a GPS position update would occur slightly before the user entered the visiting radius and slightly afterwards. I tried increasing the radius but this meant that the trigger fired too early to be relevant to the user's current position.

So how do I solve this in a way that works using “real-world” GPS data?

Answer 1

I stumbled upon this fantastic page by Movable Type of formulae for geospatial calculations. Even better, most of the formulae are already written in Javascript which was super-cool for my Phonegap app. However, the formula that caught my attention was this one for calculating the cross-track distance between two points. In terms of my app and real-world use, this means that even if the GPS updates are infrequent enough to miss the radius of my target location, I can calculate if the user visited the target based on the path between the most recent position and its predecessor.

EDIT 24/04/15: I've fixed a bug in the constrainedCrossTrackDistance function, so anyone using it should update their implementation to the one in this answer.

The JS library didn’t include this formula, so I extended the Movable Type library to implement it:

/**
 * Calculates distance of a point from a great-circle path (also called cross-track distance or cross-track error)
 * 
 * Formula: dxt = asin(sin(d13/R)*sin(b13-b12)) * R
 * where 
 *  d13 is distance from start point to third point
 *  b13 is (initial) bearing from start point to third point
 *  b12 is (initial) bearing from start point to end point
 *  R is the earth's radius
 * 
 * @param {LatLon} startPoint - Point denoting the start of the great-circle path
 * @param {LatLon} endPoint - Point denoting the end of the great-circle path
 * @param {Number} [precision=4] - no of significant digits to use for calculations and returned value
 * @return {Number} - distance in km from third point to great-circle path
 */
LatLon.prototype.crossTrackDistance = function(startPoint, endPoint, precision){
    var R = this._radius;
    var d13 = startPoint.distanceTo(this, 10);
    var b13 = startPoint.bearingTo(this).toRad();
    var b12 = startPoint.bearingTo(endPoint).toRad();
    var d = Math.asin(Math.sin(d13/R)*Math.sin(b13-b12)) * R;
    return d.toPrecisionFixed(precision);
}

However, real-world testing again showed this didn’t quite do the job. The problem was that this function was giving false positives because it didn’t take it into consideration the bounding box formed by the two end points and the radius. This led me to add a further function to constrain the crosstrack distance to within that bounding box:

/**
 * Calculates distance of a point from a great-circle path if the point is within the bounding box defined by the path.
 * Otherwise, it returns the distance from the point to the closest end of the great-circle path.
 * 
 * @param {LatLon} startPoint - Point denoting the start of the great-circle path
 * @param {LatLon} endPoint - Point denoting the end of the great-circle path
 * @param {Number} [precision=4] - no of significant digits to use for calculations and returned value
 * @return {Number} - distance in km from third point to great-circle path
 */
LatLon.prototype.constrainedCrossTrackDistance = function(startPoint, endPoint, precision){

  var bAB = startPoint.bearingTo(endPoint);
  var bAB_plus_90 = Geo.adjustBearing(bAB, 90);
  var bAB_minus_90 = Geo.adjustBearing(bAB, -90);
  var bAC = startPoint.bearingTo(this);
  var bBC = endPoint.bearingTo(this);
  var dAC = startPoint.distanceTo(this, 10);
  var dBC = endPoint.distanceTo(this, 10);
  if(Geo.differenceInBearings(bAC, bBC) > 90 && ((bBC > bAB_plus_90 && bAC < bAB_plus_90) || (bAC > bAB_minus_90 && bBC < bAB_minus_90))){
    return Math.abs(this.crossTrackDistance(startPoint, endPoint, precision));
  }else if((bBC < bAB_plus_90 && bAC < bAB_plus_90) || (bBC > bAB_minus_90 && bAC > bAB_minus_90)){
    return Math.abs(dBC);
  }else if((bBC > bAB_plus_90 && bAC > bAB_plus_90) || (bBC < bAB_minus_90 && bAC < bAB_minus_90)){
    return Math.abs(dAC);
  }else{
    return (Math.abs(dBC) < Math.abs(dAC) ? Math.abs(dBC) : Math.abs(dAC));
  }
}

This can then be used to determine if the target position has been visited in a real-world scenario:

// Calculate if target location visited
    if(
        currentPos.distanceTo(targetPos)*1000 < tolerance ||
        (prevPos && Math.abs(targetPos.constrainedCrossTrackDistance(prevPos, currentPos)*1000) < tolerance)
    ){
        visited = true;
    }else{
        visited = false;
    }

Here's a fiddle illustrating a use case

It took me a long time and lot of testing to come up with this so I hope it can be of help to other people :-)