Javascript – Find a point in a polyline which is closest to a latlng

google-maps-api-3javascript

i have a polyine which i have drawn with latlngs obtained from google maps directions service.
Now i want to find a point on the polyline that is closest to a given point.

The obvious way (to me) is to kind of loop through all the points in the polyline and find the distance between them and the given point, however this is inefficient because the points on the polyline can potentially be large.

I would be glad to hear any alternatives of doing this.
Thanks in advance.

Best Answer

See Bill Chadwick's example here:

http://www.bdcc.co.uk/Gmaps/BdccGmapBits.htm

above example ported to v3 (code at bottom of this answer)

on his page under:

DISTANCE POINT TO POLYLINE OR POLYGON

from that post:

There is a similar, better demo here http://wtp2.appspot.com/cSnapToRouteDemo.html

It is finding the closest point on the line to the mouse. Also note that it is a Google Maps API v2 example (but the principle with v3 would be the same).

// Code to find the distance in metres between a lat/lng point and a polyline of lat/lng points
// All in WGS84. Free for any use.
//
// Bill Chadwick 2007
// updated to Google Maps API v3, Lawrence Ross 2014

        // Construct a bdccGeo from its latitude and longitude in degrees
        function bdccGeo(lat, lon) 
        {
            var theta = (lon * Math.PI / 180.0);
            var rlat = bdccGeoGeocentricLatitude(lat * Math.PI / 180.0);
            var c = Math.cos(rlat); 
            this.x = c * Math.cos(theta);
            this.y = c * Math.sin(theta);
            this.z = Math.sin(rlat);        
        }
        bdccGeo.prototype = new bdccGeo();

        // internal helper functions =========================================

        // Convert from geographic to geocentric latitude (radians).
        function bdccGeoGeocentricLatitude(geographicLatitude) 
        {
            var flattening = 1.0 / 298.257223563;//WGS84
            var f = (1.0 - flattening) * (1.0 - flattening);
            return Math.atan((Math.tan(geographicLatitude) * f));
        }

         // Returns the two antipodal points of intersection of two great
         // circles defined by the arcs geo1 to geo2 and
         // geo3 to geo4. Returns a point as a Geo, use .antipode to get the other point
        function bdccGeoGetIntersection( geo1,  geo2,  geo3,  geo4) 
        {
            var geoCross1 = geo1.crossNormalize(geo2);
            var geoCross2 = geo3.crossNormalize(geo4);
            return geoCross1.crossNormalize(geoCross2);
        }

        //from Radians to Meters
        function bdccGeoRadiansToMeters(rad)
        {
            return rad * 6378137.0; // WGS84 Equatorial Radius in Meters
        }

        //from Meters to Radians
        function bdccGeoMetersToRadians(m)
        {
            return m / 6378137.0; // WGS84 Equatorial Radius in Meters
        }

        // properties =================================================


        bdccGeo.prototype.getLatitudeRadians = function() 
        {
            return (bdccGeoGeographicLatitude(Math.atan2(this.z,
                Math.sqrt((this.x * this.x) + (this.y * this.y)))));
        }

        bdccGeo.prototype.getLongitudeRadians = function() 
        {
            return (Math.atan2(this.y, this.x));
        }

        bdccGeo.prototype.getLatitude = function() 
        {
            return this.getLatitudeRadians()  * 180.0 / Math.PI;
        }

        bdccGeo.prototype.getLongitude = function() 
        {
            return this.getLongitudeRadians()  * 180.0 / Math.PI ;
        }

        // Methods =================================================

        //Maths
        bdccGeo.prototype.dot = function( b) 
        {
            return ((this.x * b.x) + (this.y * b.y) + (this.z * b.z));
        }

        //More Maths
        bdccGeo.prototype.crossLength = function( b) 
        {
            var x = (this.y * b.z) - (this.z * b.y);
            var y = (this.z * b.x) - (this.x * b.z);
            var z = (this.x * b.y) - (this.y * b.x);
            return Math.sqrt((x * x) + (y * y) + (z * z));
        }

      //More Maths
        bdccGeo.prototype.scale = function( s) 
        {
            var r = new bdccGeo(0,0);
            r.x = this.x * s;
            r.y = this.y * s;
            r.z = this.z * s;
            return r;
        }

        // More Maths
        bdccGeo.prototype.crossNormalize = function( b) 
        {
            var x = (this.y * b.z) - (this.z * b.y);
            var y = (this.z * b.x) - (this.x * b.z);
            var z = (this.x * b.y) - (this.y * b.x);
            var L = Math.sqrt((x * x) + (y * y) + (z * z));
            var r = new bdccGeo(0,0);
            r.x = x / L;
            r.y = y / L;
            r.z = z / L;
            return r;
        }

      // point on opposite side of the world to this point
        bdccGeo.prototype.antipode = function() 
        {
            return this.scale(-1.0);
        }






        //distance in radians from this point to point v2
        bdccGeo.prototype.distance = function( v2) 
        {
            return Math.atan2(v2.crossLength(this), v2.dot(this));
        }

      //returns in meters the minimum of the perpendicular distance of this point from the line segment geo1-geo2
      //and the distance from this point to the line segment ends in geo1 and geo2 
        bdccGeo.prototype.distanceToLineSegMtrs = function(geo1, geo2)
        {            

            //point on unit sphere above origin and normal to plane of geo1,geo2
            //could be either side of the plane
            var p2 = geo1.crossNormalize(geo2); 

            // intersection of GC normal to geo1/geo2 passing through p with GC geo1/geo2
            var ip = bdccGeoGetIntersection(geo1,geo2,this,p2); 

            //need to check that ip or its antipode is between p1 and p2
            var d = geo1.distance(geo2);
            var d1p = geo1.distance(ip);
            var d2p = geo2.distance(ip);
            //window.status = d + ", " + d1p + ", " + d2p;
            if ((d >= d1p) && (d >= d2p)) 
                return bdccGeoRadiansToMeters(this.distance(ip));
            else
            {
                ip = ip.antipode(); 
                d1p = geo1.distance(ip);
                d2p = geo2.distance(ip);
            }
            if ((d >= d1p) && (d >= d2p)) 
                return bdccGeoRadiansToMeters(this.distance(ip)); 
            else 
                return bdccGeoRadiansToMeters(Math.min(geo1.distance(this),geo2.distance(this))); 
        }

        // distance in meters from GLatLng point to GPolyline or GPolygon poly
        function bdccGeoDistanceToPolyMtrs(poly, point)
        {
            var d = 999999999;
            var i;
            var p = new bdccGeo(point.lat(),point.lng());
            for(i=0; i<(poly.getPath().getLength()-1); i++)
                 {
                    var p1 = poly.getPath().getAt(i);
                    var l1 = new bdccGeo(p1.lat(),p1.lng());
                    var p2 = poly.getPath().getAt(i+1);
                    var l2 = new bdccGeo(p2.lat(),p2.lng());
                    var dp = p.distanceToLineSegMtrs(l1,l2);
                    if(dp < d)
                        d = dp;    
                 }
             return d;
        }

        // get a new GLatLng distanceMeters away on the compass bearing azimuthDegrees
        // from the GLatLng point - accurate to better than 200m in 140km (20m in 14km) in the UK

        function bdccGeoPointAtRangeAndBearing (point, distanceMeters, azimuthDegrees) 
        {
             var latr = point.lat() * Math.PI / 180.0;
             var lonr = point.lng() * Math.PI / 180.0;

             var coslat = Math.cos(latr); 
             var sinlat = Math.sin(latr); 
             var az = azimuthDegrees* Math.PI / 180.0;
             var cosaz = Math.cos(az); 
             var sinaz = Math.sin(az); 
             var dr = distanceMeters / 6378137.0; // distance in radians using WGS84 Equatorial Radius
             var sind = Math.sin(dr); 
             var cosd = Math.cos(dr);

            return new google.maps.LatLng(Math.asin((sinlat * cosd) + (coslat * sind * cosaz)) * 180.0 / Math.PI,
            (Math.atan2((sind * sinaz), (coslat * cosd) - (sinlat * sind * cosaz)) + lonr) * 180.0 / Math.PI); 
        }

Related Solutions

Javascript – Which “href” value should I use for JavaScript links, “#” or “javascript:void(0)”

I use javascript:void(0).

Three reasons. Encouraging the use of # amongst a team of developers inevitably leads to some using the return value of the function called like this:

function doSomething() {
    //Some code
    return false;
}

But then they forget to use return doSomething() in the onclick and just use doSomething().

A second reason for avoiding # is that the final return false; will not execute if the called function throws an error. Hence the developers have to also remember to handle any error appropriately in the called function.

A third reason is that there are cases where the onclick event property is assigned dynamically. I prefer to be able to call a function or assign it dynamically without having to code the function specifically for one method of attachment or another. Hence my onclick (or on anything) in HTML markup look like this:

onclick="someFunc.call(this)"

onclick="someFunc.apply(this, arguments)"

Using javascript:void(0) avoids all of the above headaches, and I haven't found any examples of a downside.

So if you're a lone developer then you can clearly make your own choice, but if you work as a team you have to either state:

Use href="#", make sure onclick always contains return false; at the end, that any called function does not throw an error and if you attach a function dynamically to the onclick property make sure that as well as not throwing an error it returns false.

Use href="javascript:void(0)"

The second is clearly much easier to communicate.

Javascript – Which equals operator (== vs ===) should be used in JavaScript comparisons

The strict equality operator (===) behaves identically to the abstract equality operator (==) except no type conversion is done, and the types must be the same to be considered equal.

Reference: Javascript Tutorial: Comparison Operators

The == operator will compare for equality after doing any necessary type conversions. The === operator will not do the conversion, so if two values are not the same type === will simply return false. Both are equally quick.

To quote Douglas Crockford's excellent JavaScript: The Good Parts,

JavaScript has two sets of equality operators: === and !==, and their evil twins == and !=. The good ones work the way you would expect. If the two operands are of the same type and have the same value, then === produces true and !== produces false. The evil twins do the right thing when the operands are of the same type, but if they are of different types, they attempt to coerce the values. the rules by which they do that are complicated and unmemorable. These are some of the interesting cases:
'' == '0'           // false
0 == ''             // true
0 == '0'            // true

false == 'false'    // false
false == '0'        // true

false == undefined  // false
false == null       // false
null == undefined   // true

' \t\r\n ' == 0     // true

The lack of transitivity is alarming. My advice is to never use the evil twins. Instead, always use === and !==. All of the comparisons just shown produce false with the === operator.

Update:

A good point was brought up by @Casebash in the comments and in @Phillipe Laybaert's answer concerning objects. For objects, == and === act consistently with one another (except in a special case).

var a = [1,2,3];
var b = [1,2,3];

var c = { x: 1, y: 2 };
var d = { x: 1, y: 2 };

var e = "text";
var f = "te" + "xt";

a == b            // false
a === b           // false

c == d            // false
c === d           // false

e == f            // true
e === f           // true

The special case is when you compare a primitive with an object that evaluates to the same primitive, due to its toString or valueOf method. For example, consider the comparison of a string primitive with a string object created using the String constructor.

"abc" == new String("abc")    // true
"abc" === new String("abc")   // false

Here the == operator is checking the values of the two objects and returning true, but the === is seeing that they're not the same type and returning false. Which one is correct? That really depends on what you're trying to compare. My advice is to bypass the question entirely and just don't use the String constructor to create string objects from string literals.

Reference
http://www.ecma-international.org/ecma-262/5.1/#sec-11.9.3

Best Answer

Related Solutions

Javascript – Which “href” value should I use for JavaScript links, “#” or “javascript:void(0)”

Javascript – Which equals operator (== vs ===) should be used in JavaScript comparisons

Update:

Related Topic