如何计算一个球体上一个点到一条线段的距离？ [英] How to calculate distance from a point to a line segment, on a sphere?

问题描述

我在地球上有一个线段（大圆圈部分）。线段由其端点的坐标定义。显然，两点定义了两条线段，所以假设我对较短的线段感兴趣。

我给了第三点，我正在寻找线和点之间的（最短）距离。

所有坐标均以经度\\海拔（WGS 84）给出。

我如何计算距离？

使用任何合理编程语言的解决方案都可以。

解决方案

这是我自己的解决方案，基于问Math博士。我很乐意看到您的反馈。

首先声明。这个解决方案对球体是正确的。地球不是一个球体，而坐标系统（WGS 84）并不认为它是一个球体。所以这只是一个近似值，我不能真正估计是错误。另外，对于非常小的距离，通过假定所有东西都是共面的，也可能得到好的近似值。再次，我不知道距离有多小。

现在开始营业。我将调用A行，B行和C行的结束。基本上，算法是：

1. 先转换坐标到笛卡儿坐标（以原点为中心） - 例如在这里。
   

2. 使用以下3个向量产品计算T，即AB线上离C最近的点：
   
   G = A x B
   
   F = C x G
   
   T = G x F




3. 标准化T并乘以地球半径。



4. 将T转换回经度\海拔。


5. 计算T和C之间的距离 - 例如这里。
   

如果你正在寻找C和由A和A定义的大圆之间的距离，这些步骤就足够了。 B.如果像我这样对C和较短线段之间的距离感兴趣，则需要采取额外步骤来验证T确实在这个线段上。如果不是，则最近的点必然是A或B的一端 - 最简单的方法是检查哪一个。一般而言，三种矢量产品的理念如下。第一个（G）给我们A和B的大圆的平面（所以包含A，B和原点的平面）。第二个（F）给出我们通过C的大圆并且垂直于G.然后T是由F和G定义的大圆的交点，通过归一化和乘以R得到正确的长度。 p>

以下是一些不完整的Java代码。

查找大圆上最近的点。输入和输出是长度为2的数组。中间数组的长度为3.

  double [] nearestPointGreatCircle（double [] a，double [] b，double c [ ]）
 {
 double [] a_ = toCartsian（a）; 
 double [] b_ = toCartsian（b）; 
 double [] c_ = toCartsian（c）; 
 
 double [] G = vectorProduct（a_，b_）; 
 double [] F = vectorProduct（c_，G）; 
 double [] t = vectorProduct（G，F）; 
 normalize（t）; 
 multiplyByScalar（t，R_EARTH）; 
从凯基亚（t）回报; 
} 
  

寻找细分受众群最近的点：

  double [] nearestPointSegment（double [] a，double [] b，double [] c）
 {
 double [] t = nearestPointGreatCircle（A，b，C）; 
 if（onSegment（a，b，t））
 return t; 
 return（distance（a，c）< distance（b，c））？ a：c; 
 
 
 
 
 
 $ b 
这是一个简单的方法来测试我们知道的点T与A和B相同的大圆圈就在这个大圆的较短部分。然而，有更有效的方法来做到这一点：
  boolean onSegment（double [] a，double [] b，double [] t）
 {
 //应该是返回距离（a，t）+距离（b，t）==距离（a，b），
 //但由于舍入错误， （a，b） - 距离（a，t） - 距离精确; 
} 
  
 
I have a line segment (great circle part) on earth. The line segment is defined by the coordinates of its ends. Obviously, two points define two line segments, so assume I am interested in the shorter one. 

I am given a third point, and I am looking for the (shortest) distance between the line and the point. 

All the coordinates are given in longitude\latitude (WGS 84). 

How do I calculate the distance? 

A solution in any reasonable programming language will do. 
解决方案
Here's my own solution, based on the idea in ask Dr. Math. I'd be happy to see your feedback.

Disclaimer first. This solution is correct for spheres. Earth isn't a sphere, and the coordinates system (WGS 84) doesn't assume it's a sphere. So this is just an approximation, and I can't really estimate is error. Also, for very small distances, it's probably also possible to get good approximation by assuming everything is a just a coplanar. Again I don't know how "small" the distances have to be.

Now to business. I will call the ends of the lines A,B and the third point C. Basically, the algorithm is to:

convert the coordinates first to Cartesian coordinates (with the origin at the center of earth) - e.g. here.
Calculate T, the point on the line AB that is nearest to C, using the following 3 vector products:

G = A x B

F = C x G

T = G x F
Normalize T and multiply by the radius of earth.
Convert T back to longitude\latitude.
Calculate the distance between T and C - e.g. here.
These steps are enough if you are looking for the distance between C and the great circle defined by A and B. If like me you are interested in the distance between C and the shorter line segment, you need to take the extra step of verifying that T is indeed on this segment. If it isn't, then necessarily the nearest point is one of the ends A or B - the easiest way is to check which one. 

In general terms, the idea behind the three vector products is the following. The first one (G) gives us the the plane of the great circle of A and B (so the plane containing A,B and the origin). The second (F) gives us the great circle the goes through C and is perpendicular to the G. Then T is the intersection of the great circles defined by F and G, brought to the correct length by normalization and multiplication by R.

Here's some partial Java code for doing it.

Finding the nearest point on the great circle. The inputs and output are length-2 arrays. The intermediate arrays are of length 3.  
double[] nearestPointGreatCircle(double[] a, double[] b, double c[])
{
    double[] a_ = toCartsian(a);
    double[] b_ = toCartsian(b);
    double[] c_ = toCartsian(c);

    double[] G = vectorProduct(a_, b_);
    double[] F = vectorProduct(c_, G);
    double[] t = vectorProduct(G, F);
    normalize(t);
    multiplyByScalar(t, R_EARTH);
    return fromCartsian(t);
}
Finding the nearest point on the segment:
double[] nearestPointSegment (double[] a, double[] b, double[] c)
{
   double[] t= nearestPointGreatCircle(a,b,c);
   if (onSegment(a,b,t))
     return t;
   return (distance(a,c) < distance(b,c)) ? a : c;
} 
This is a simple method of testing if point T, which we know is on the same great circle as A and B, is on the shorter segment of this great circle. However there are more efficient methods to do it:
   boolean onSegment (double[] a, double[] b, double[] t)
   {
     // should be   return distance(a,t)+distance(b,t)==distance(a,b), 
     // but due to rounding errors, we use: 
     return Math.abs(distance(a,b)-distance(a,t)-distance(b,t)) < PRECISION;
   }    


                        
这篇关于如何计算一个球体上一个点到一条线段的距离？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！