Как вычислить расстояние от точки до линейного сегмента на сфере?

Вот мое собственное решение, основанное на идее из , спросите доктора Матема . Буду рад увидеть ваш отзыв.

Сначала отказ от ответственности. Это решение подходит для сфер. Земля не является сферой, и система координат (WGS 84) не предполагает, что это сфера. Так что это всего лишь приближение, и я не могу точно оценить ошибку. Кроме того, для очень малых расстояний, вероятно, также можно получить хорошее приближение, если предположить, что все является просто компланарностью. Опять же, я не знаю, насколько «маленькими» должны быть расстояния.

Теперь к делу. Я назову концы линий A, B и третью точку C. По сути, алгоритм заключается в следующем:

1. сначала преобразовать координаты в декартовы координаты (с началом в центре Земли) - например, здесь .

2. Вычислить T, точка на прямой AB, ближайшая к C, используя следующие 3 векторных произведения:

   G = A x B

   F = C x G

   T = G x F

3. Нормализовать T и умножить на радиус Земли.

4. Преобразуйте T обратно в долготу \ широту.
5. Вычислите расстояние между T и C - например, здесь .

Этих шагов достаточно, если вы ищете расстояние между C и большим кругом, определяемым A и B. Если, как и меня, вас интересует расстояние между C и более коротким отрезком линии, вам нужно сделать дополнительный шаг, чтобы убедиться, что T действительно находится на этом отрезке. Если это не так, то ближайшей точкой обязательно будет один из концов A или B - проще всего проверить, какой из них.

В общем, идея трех векторных произведений заключается в следующем. Первый (G) дает нам плоскость большого круга A и B (т.е. плоскость, содержащую A, B и начало координат). Второй (F) дает нам большую окружность, проходящую через C и перпендикулярную G. Тогда T - это пересечение больших окружностей, определяемых F и G, полученное до правильной длины путем нормализации и умножения на R.

] Вот часть кода 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);
    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, на более короткий отрезок этого большого круга. Однако есть более эффективные методы для этого:

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