在最接近latlng的多段線中找到一個點

Question

我有一個polyine，我用從google maps方向服務獲得的latlng繪製了一個polyine。 現在我想找到最接近給定點的折線上的一個點。

對我而言，顯而易見的方式是循環遍歷多段線中的所有點，並找出它們與給定點之間的距離，但這是無效的，因爲多段線上的點可能很大。

我很高興聽到任何替代方案。 在此先感謝。

Answer 1

見比爾·查德威克的例子在這裏：

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

above example ported to v3（代碼在這個答案的底部）

在他的頁面下：

分離點TO折線或多邊形

從該職位：

有一個類似的，更好的演示在這裏http://wtp2.appspot.com/cSnapToRouteDemo.html

這是找到就行了鼠標的最近點。另請注意，這是一個Google Maps API v2示例（但v3的原理是相同的）。

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

Answer 2

我不認爲你可以避免檢查所有的點。 如果未檢查的點是最近的點，該怎麼辦？

如果您必須多次執行此操作，則可以選擇針對此搜索進行了優化的數據結構，例如四叉樹。 請注意，您不應該使用lat lng作爲笛卡兒座標。

又見Finding nearest point in an efficient way 這是2D平面，而不是緯度和經度，但可以近似：https://stackoverflow.com/a/16271669/59019

Answer 3

受jmihalicza答案的啓發，我想出了這個函數來找到LatLng數組中最接近的點到給定的LatLng。

功能最接近LatLng（lng）和一個LatLngs（listData）數組，並找出數組中每個latlng和給定latlng之間的距離，然後找到最小距離並從提供的列表返回Latlng那個距離。

function closest(llng, listData) { 
    var arr  = listData; 
    var pnt  = llng; 
    var distArr = []; 
    var dist = google.maps.geometry.spherical.computeDistanceBetween; 


    for (index in arr) 
     distArr.push([arr[index], dist(pnt, arr[index])]); 

    return distArr.sort(function(a,b){ 
     return a[1]-b[1]; 
    })[0][0]; 
} 

編輯

如果您沒有訪問LatLngs從而彌補了折線的陣列，但有機會獲得折線本身，你可以使用折線的getPath method拿到這是一個路徑MVC數組，因此您可以使用.getArray（）返回LatLng的數組以用於上述函數（最接近）。

Answer 4

我需要一個被移植到V3清潔版本，所以在這裏它是：

/** 
* Snap marker to closest point on a line. 
* 
* Based on Distance to line example by 
* Marcelo, maps.forum.nu - http://maps.forum.nu/gm_mouse_dist_to_line.html 
* Then 
* @ work of Björn Brala - Swis BV who wrapped the algorithm in a class operating on GMap Objects 
* And now 
* Bill Chadwick, who factored the basic algorithm out of the class (removing much intermediate storage of results) 
*  and added distance along line to nearest point calculation 
* Followed by 
* Robert Crowe, who ported it to v3 of the Google Maps API and factored out the marker to make it more general. 
* 
* Usage: 
* 
* Create the class 
*  var oSnap = new cSnapToRoute(); 
* 
* Initialize the subjects 
*  oSnap.init(oMap, oPolyline); 
* 
**/ 

function cSnapToRoute() { 

    this.routePoints = Array(); 
    this.routePixels = Array(); 
    this._oMap; 
    this._oPolyline; 

    /** 
    * @desc Initialize the objects. 
    * @param Map object 
    * @param GPolyline object - the 'route' 
    **/ 
    this.init = function (oMap, oPolyline) { 
     this._oMap = oMap; 
     this._oPolyline = oPolyline; 

     this.loadRouteData(); // Load needed data for point calculations 
    } 

    /** 
    * @desc internal use only, Load route points into RoutePixel array for calculations, do this whenever zoom changes 
    **/ 
    this.loadRouteData = function() { 
     this.routePixels = new Array(); 
     var proj = this._oMap.getProjection(); 
     for (var i = 0; i < this._oPolyline.getPath().getLength(); i++) { 
      var Px = proj.fromLatLngToPoint(this._oPolyline.getPath().getAt(i)); 
      this.routePixels.push(Px); 
     } 
    } 

    /** 
    * @desc Get closest point on route to test point 
    * @param GLatLng() the test point 
    * @return new GLatLng(); 
    **/ 
    this.getClosestLatLng = function (latlng) { 
     var r = this.distanceToLines(latlng); 
     var proj = this._oMap.getProjection(); 
     return proj.fromPointToLatLng(new google.maps.Point(r.x, r.y)); 
    } 

    /** 
    * @desc Get distance along route in meters of closest point on route to test point 
    * @param GLatLng() the test point 
    * @return distance in meters; 
    **/ 
    this.getDistAlongRoute = function (latlng) { 
     var r = this.distanceToLines(latlng); 
     return this.getDistToLine(r.i, r.fTo); 
    } 

    /** 
    * @desc internal use only, gets test point xy and then calls fundamental algorithm 
    **/ 
    this.distanceToLines = function (thisLatLng) { 
     var tm = this._oMap; 
     var proj = this._oMap.getProjection(); 
     var thisPx = proj.fromLatLngToPoint(thisLatLng); 
     var routePixels = this.routePixels; 
     return getClosestPointOnLines(thisPx, routePixels); 
    } 

    /** 
    * @desc internal use only, find distance along route to point nearest test point 
    **/ 
    this.getDistToLine = function (iLine, fTo) { 

     var routeOverlay = this._oPolyline; 
     var d = 0; 
     for (var n = 1 ; n < iLine ; n++) { 
      d += routeOverlay.getPath().getAt(n - 1).distanceFrom(routeOverlay.getPath().getAt(n)); 
     } 
     d += routeOverlay.getPath().getAt(iLine - 1).distanceFrom(routeOverlay.getPath().getAt(iLine)) * fTo; 

     return d; 
    } 


} 

/* desc Static function. Find point on lines nearest test point 
    test point pXy with properties .x and .y 
    lines defined by array aXys with nodes having properties .x and .y 
    return is object with .x and .y properties and property i indicating nearest segment in aXys 
    and property fFrom the fractional distance of the returned point from aXy[i-1] 
    and property fTo the fractional distance of the returned point from aXy[i] */ 


function getClosestPointOnLines(pXy, aXys) { 

    var minDist; 
    var fTo; 
    var fFrom; 
    var x; 
    var y; 
    var i; 
    var dist; 

    if (aXys.length > 1) { 

     for (var n = 1 ; n < aXys.length ; n++) { 

      if (aXys[n].x != aXys[n - 1].x) { 
       var a = (aXys[n].y - aXys[n - 1].y)/(aXys[n].x - aXys[n - 1].x); 
       var b = aXys[n].y - a * aXys[n].x; 
       dist = Math.abs(a * pXy.x + b - pXy.y)/Math.sqrt(a * a + 1); 
      } 
      else 
       dist = Math.abs(pXy.x - aXys[n].x) 

      // length^2 of line segment 
      var rl2 = Math.pow(aXys[n].y - aXys[n - 1].y, 2) + Math.pow(aXys[n].x - aXys[n - 1].x, 2); 

      // distance^2 of pt to end line segment 
      var ln2 = Math.pow(aXys[n].y - pXy.y, 2) + Math.pow(aXys[n].x - pXy.x, 2); 

      // distance^2 of pt to begin line segment 
      var lnm12 = Math.pow(aXys[n - 1].y - pXy.y, 2) + Math.pow(aXys[n - 1].x - pXy.x, 2); 

      // minimum distance^2 of pt to infinite line 
      var dist2 = Math.pow(dist, 2); 

      // calculated length^2 of line segment 
      var calcrl2 = ln2 - dist2 + lnm12 - dist2; 

      // redefine minimum distance to line segment (not infinite line) if necessary 
      if (calcrl2 > rl2) 
       dist = Math.sqrt(Math.min(ln2, lnm12)); 

      if ((minDist == null) || (minDist > dist)) { 
       if (calcrl2 > rl2) { 
        if (lnm12 < ln2) { 
         fTo = 0;//nearer to previous point 
         fFrom = 1; 
        } 
        else { 
         fFrom = 0;//nearer to current point 
         fTo = 1; 
        } 
       } 
       else { 
        // perpendicular from point intersects line segment 
        fTo = ((Math.sqrt(lnm12 - dist2))/Math.sqrt(rl2)); 
        fFrom = ((Math.sqrt(ln2 - dist2))/Math.sqrt(rl2)); 
       } 
       minDist = dist; 
       i = n; 
      } 
     } 

     var dx = aXys[i - 1].x - aXys[i].x; 
     var dy = aXys[i - 1].y - aXys[i].y; 

     x = aXys[i - 1].x - (dx * fTo); 
     y = aXys[i - 1].y - (dy * fTo); 

    } 

    return { 'x': x, 'y': y, 'i': i, 'fTo': fTo, 'fFrom': fFrom }; 
}