Расстояние 3d-точки до алгоритма сегмента полилинии

Question

У меня есть путь, состоящий из n трехмерных координат, все соединены последовательно, что можно увидеть на этой диаграмме .

Я хочу найти кратчайшее расстояние между моей точкой и отрезком поли. Я могу рассчитать расстояние до точки от одного отрезка, но я хочу сделать это для более сложного пути.

Существует ли алгоритм для этого, который не основывается на тестировании каждого отрезка прямой до точечного расстояния и сохраняет минимальное значение? Любые указатели в правильном направлении были бы великолепны!

Это для игрового проекта, в котором я хочу вычислить расстояние игрока от реки, которая существует в игре. Река будет представлена ​​отрезками поли.

Спасибо

Answer 1

/**
 * Calculates the euclidean distance from a point to a line segmented path.
 *
 * @param v     the point from with the distance is measured
 * @param path  the array of points wich, when sequentialy joined by line segments, form a path
 * @return      distance from v to closest of the path forming line segments
 *
 * @author      Afonso Santos
 */
public static
double
distanceToPath( final R3 v, final R3[] path )
{
    double minDistance = Double.MAX_VALUE ;

    for (int pathPointIdx = 1  ;  pathPointIdx < path.length  ;  ++pathPointIdx)
    {
        final double d = distanceToSegment( v, path[pathPointIdx-1], path[pathPointIdx] ) ;

        if (d < minDistance)
            minDistance = d ;
    }

    return minDistance;
}


/**
 * Calculates the euclidean distance from a point to a line segment.
 *
 * @param v     the point
 * @param a     start of line segment
 * @param b     end of line segment
 * @return      distance from v to line segment [a,b]
 *
 * @author      Afonso Santos
 */
public static
double
distanceToSegment( final R3 v, final R3 a, final R3 b )
{
    final R3 ab = b.sub( a ) ;
    final R3 av = v.sub( a ) ;

    if (av.dot(ab) <= 0.0)              // Point is lagging behind start of the segment, so perpendicular distance is not viable.
        return av.modulus( ) ;          // Use distance to start of segment instead.

    final R3 bv = v.sub( b ) ;

    if (bv.dot(ab) >= 0.0)              // Point is advanced past the end of the segment, so perpendicular distance is not viable.
        return bv.modulus( ) ;          // Use distance to end of the segment instead.

    // Point is within the line segment's start/finish boundaries, so perpendicular distance is viable.
    return (ab.cross( av )).modulus() / ab.modulus() ;      // Perpendicular distance of point to segment.
}

Остальная часть (java-пакет векторной алгебры трехмерной векторной алгебры R3) находится здесь: https://gist.github.com/reciprocum/4e3599a9563ec83ba2a63f5a6cdd39eb

часть библиотеки с открытым исходным кодом https://sourceforge.net/projects/geokarambola/