javascript 在折线中找到最接近 latlng 的点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16429562/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find a point in a polyline which is closest to a latlng
提问by T. Rex
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.
我有一个polyine，我用从谷歌地图方向服务获得的latlngs 绘制了它。现在我想在折线上找到最接近给定点的点。
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.
我很高兴听到这样做的任何替代方案。提前致谢。
采纳答案by geocodezip
See Bill Chadwick's example here:
在此处查看比尔查德威克的示例：
http://www.bdcc.co.uk/Gmaps/BdccGmapBits.htm
http://www.bdcc.co.uk/Gmaps/BdccGmapBits.htm
above example ported to v3(code at bottom of this answer)
上面的示例移植到 v3（此答案底部的代码）
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
这里有一个类似的更好的演示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).
它正在寻找线上距离鼠标最近的点。另请注意，这是一个 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);
}
回答by RCrowe
I needed a cleaner version that was ported to V3, so here it is:
我需要一个移植到 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 };
}
回答by T. Rex
Inspired by jmihalicza's answer, i came up with this function to find the closest point in an array of LatLngs to a given LatLng.
受到 jmihalicza 的回答的启发，我想出了这个函数来找到 LatLng 数组中与给定 LatLng 最接近的点。
function closest takes a LatLng(llng) and an array of LatLngs (listData) and finds the distance between each latlng in the array and the given latlng, it then finds the least distance and returns the Latlng from the list which provided that distance.
函数最接近接受一个 LatLng(llng) 和一个 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];
}
EDIT
编辑
If you don't have access to the array of LatLngs which make up the polyline, but have access to the polyline itself, you can use polyline's getPath methodto get the path which is an MVC array so you can use .getArray() to return an array of LatLngs to use with the above function (closest).
如果您无权访问构成折线的 LatLngs 数组，但可以访问折线本身，则可以使用折线的getPath 方法来获取 MVC 数组的路径，以便您可以使用 .getArray()返回一个 LatLngs 数组以与上述函数一起使用（最接近）。
回答by jmihalicza
I do not think you can avoid checking all the points. What if the not checked point is the nearest one?
我认为您无法避免检查所有要点。如果未选中的点是最近的点怎么办？
If you have to do this operation many times, you can choose a data structure that is optimized for such a search, quadtree for example. Note that you should not use lat lng as Descartes coordinates.
如果您必须多次执行此操作，则可以选择针对此类搜索进行优化的数据结构，例如四叉树。请注意，您不应使用 lat lng 作为笛卡尔坐标。
See also Finding nearest point in an efficient wayThat is for the 2D plane, and not for lat lng, but you can approximate: https://stackoverflow.com/a/16271669/59019
另请参阅以有效的方式寻找最近的点这适用于 2D 平面，而不适用于 lat lng，但您可以近似：https: //stackoverflow.com/a/16271669/59019
