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

问题描述

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

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.

所有坐标均以经度纬度 (WGS 84) 给出.

All the coordinates are given in longitudelatitude (WGS 84).

如何计算距离?

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

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.

首先声明.此解决方案适用于球体.地球不是球体，坐标系 (WGS 84) 也不假定它是球体.所以这只是一个近似值，我无法真正估计是错误.此外，对于非常小的距离，通过假设一切都是共面的，也可能获得很好的近似值.同样，我不知道距离必须有多小".

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.

现在开始吧.我将把线的末端称为 A、B 和第三点 C.基本上，算法是:

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

1. 首先将坐标转换为笛卡尔坐标(原点位于地球中心) - 例如在这里.

2. 使用以下 3 个向量积计算 T，即 AB 线上最接近 C 的点:

1. convert the coordinates first to Cartesian coordinates (with the origin at the center of earth) - e.g. here.

2. 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

归一化 T 并乘以地球半径.

Normalize T and multiply by the radius of earth.

如果您正在寻找C与A和B定义的大圆之间的距离，这些步骤就足够了.如果您像我一样对C与较短线段之间的距离感兴趣，您需要采取额外的步骤验证 T 确实在该段上.如果不是，那么最近的点必然是端点 A 或 B 之一——最简单的方法是检查哪一个.

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.

一般来说，三个向量积背后的思想如下.第一个 (G) 给了我们 A 和 B 的大圆的平面(因此包含 A、B 和原点的平面).第二个 (F) 给了我们穿过 C 并垂直于 G 的大圆.然后 T 是由 F 和 G 定义的大圆的交点，通过归一化和乘以 R 得到正确的长度.

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.

这里有一些部分 Java 代码.

Here's some partial Java code for doing it.

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

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

找到段上最近的点:

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

这是一种简单的方法来测试点 T(我们知道它与 A 和 B 在同一个大圆上)是否在这个大圆的较短段上.但是有更有效的方法来做到这一点:

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屋！