我有一个polyine,我用从google maps方向服务获得的latlng绘制了一个polyine。 现在我想找到最接近给定点的折线上的一个点。在最接近latlng的多段线中找到一个点
对我而言,显而易见的方式是循环遍历多段线中的所有点,并找出它们与给定点之间的距离,但这是无效的,因为多段线上的点可能很大。
我很高兴听到任何替代方案。 在此先感谢。
我有一个polyine,我用从google maps方向服务获得的latlng绘制了一个polyine。 现在我想找到最接近给定点的折线上的一个点。在最接近latlng的多段线中找到一个点
对我而言,显而易见的方式是循环遍历多段线中的所有点,并找出它们与给定点之间的距离,但这是无效的,因为多段线上的点可能很大。
我很高兴听到任何替代方案。 在此先感谢。
见比尔·查德威克的例子在这里:
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);
}
我不认为你可以避免检查所有的点。 如果未检查的点是最近的点,该怎么办?
如果您必须多次执行此操作,则可以选择针对此搜索进行了优化的数据结构,例如四叉树。 请注意,您不应该使用lat lng作为笛卡儿坐标。
又见Finding nearest point in an efficient way 这是2D平面,而不是纬度和经度,但可以近似:https://stackoverflow.com/a/16271669/59019
这个答案是找到折线最近的节点,如果只LAT LONS中给出。如果您对多段线最近线的最近像素感兴趣,那是另一回事。 – jmihalicza 2013-05-07 22:43:16
受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的数组以用于上述函数(最接近)。
这只会返回最接近该点的多段线的顶点,而不会返回折线本身上最近的点。 – ParoX 2015-05-29 01:36:28
任何想法如何解决这个问题? – 2015-05-30 13:29:39
即使新顶点不添加空间信息,也会在多段线上的每对顶点之间插入更多顶点。做到这一点,无论你觉得满意的决议。 – 2016-04-21 20:53:14
我需要一个被移植到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 };
}
该代码完美适用于v3。 distanceToLines方法特别有趣,如果结果有点让人望而生畏。你应该把它变成一个图书馆。我已经将它包含在我的代码库中,并引用了此URL。谢谢! – brendan 2016-06-05 05:58:21
谢谢!这工作得很好。我没有使用gmaps,所以我只使用getClosestPointOnLines函数。 – 2016-10-25 17:49:06
第一个链接的演示不再适用(v3 API)。 – heltonbiker 2014-09-05 03:21:43
第一个例子是找到从一个点到一条线的距离。第二个链接通过查找最接近的点来回答问题。第一个示例不适用于v2的v3包装(不支持地图控件)。将这些库移植到v3并不难,只有几个地方使用v2特定的语法,并将其更改为v3非常简单。 – geocodezip 2014-09-07 03:10:36