Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
272 views
in Technique[技术] by (71.8m points)

javascript - Find a point in a polyline which is closest to a latlng

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.

Question&Answers:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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); 
        }

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

1.4m articles

1.4m replys

5 comments

57.0k users

...