如何在地图上计算线段交点 [英] How to compute line segment intersections on a map

问题描述

我正在谷歌地图中使用纬度/经度坐标。

我有两行：

行A：48.31508162629726，-2.591741396838972至48.40216156645915，-2.2218462112093404

行B：48.383816077371215，-2.274292940053768至48.66103546935337，-1.7066197241571377

然后，我们使用以下公式找出交叉点。

  var XAsum = A.LngStart  -  A.LngEnd; 
 var XBsum = B.LngStart  -  B.LngEnd; 
 var YAsum = A.LatStart  -  A.LatEnd; 
 var YBsum = B.LatStart  -  B.LatEnd; 
 
 var LineDenominator = XAsum * YBsum  -  YAsum * XBsum; 
 if（LineDenominator == 0.0）
 return false; 
 
 var a = A.LngStart * A.LatEnd  -  A.LatStart * A.LngEnd; 
 var b = B.LngStart * B.LatEnd  -  B.LatStart * B.LngEnd; 
 
 var x =（a * XBsum  -  b * XAsum）/ LineDenominator; 
 var y =（a * YBsum  -  b * YAsum）/ LineDenominator; 
  

这告诉我，这些行确实是交叉的，并返回x和y值。

但是，当绘制返回点时，它与实际交叉点偏移（不太多）。

是否有我可以使用更好和一样快速的算法，这将使我返回正确的交点？

需要快速迭代遍历大量的行（〜

编辑：注意这是给我一个大约7.5米的错误偏移量

解决方案

我假设您使用的算法是在笛卡尔坐标系（即平面）上找到线路交叉点的算法。不幸的是，地球不是一个平面（甚至是球体），所以使用该算法会引入误差。 Google Maps使用椭球（特别是WGS84）近似地球表面，因此您需要一个算法来查找椭圆上弧线的交点。

页面可能包含一些有用的信息：
http：// mathhelpforum。 com / calculus / 90196-point-intersection-two-lines.html

I am working with Latitude / Longitude coordinates in a google map.

I have two lines :

• Line A : 48.31508162629726, -2.591741396838972 to 48.40216156645915, -2.2218462112093404
• Line B : 48.383816077371215, -2.274292940053768 to 48.66103546935337, -1.7066197241571377

I then use the following formula to find the point where they cross.

var XAsum = A.LngStart - A.LngEnd;
var XBsum = B.LngStart - B.LngEnd;
var YAsum = A.LatStart - A.LatEnd;
var YBsum = B.LatStart - B.LatEnd;

var LineDenominator = XAsum * YBsum - YAsum * XBsum;
if(LineDenominator == 0.0)
    return false;

var a = A.LngStart * A.LatEnd - A.LatStart * A.LngEnd;
var b = B.LngStart * B.LatEnd - B.LatStart * B.LngEnd;

var x = (a * XBsum - b * XAsum) / LineDenominator;
var y = (a * YBsum - b * YAsum) / LineDenominator;

This tells me that the lines do indeed cross and returns the x and y values.

However, when I plot the returned point, it is offset (not much) from the real intersection.

Is there a better and just as fast algorithm I could use which will return me the correct intersection point ?

It needs to be fast as I am iterating over a large number of lines (~1000).

EDIT : Note this is giving me an error offset of around 7.5 meters

解决方案

I'm assuming the algorithm you're using is the one for finding line intersections on a Cartesian coordinate system (i.e. a plane). Unfortunately, the earth is not a plane (or even a sphere) so using that algorithm will introduce error. Google Maps uses an ellipsoid (specifically WGS84) to approximate the surface of the earth, so you'll need an algorithm for finding the intersections of arcs on an ellipsoid.

This page might contains some helpful information: http://mathhelpforum.com/calculus/90196-point-intersection-two-lines.html

这篇关于如何在地图上计算线段交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！