3d 点到多段线段的距离算法

Question

我有一条路径，由 n 个 3d 坐标组成，全部串联连接，可以在 此图。

我想找到我的点和多段线段之间的最短距离。我可以计算一个点到一条线段的距离，但我想为更复杂的路径执行此操作。

是否有一种算法不依赖于测试每个线段到点的距离并存储最小值？任何指向正确方向的指针都会很棒！

这是一个游戏项目，我想计算玩家与游戏中存在的河流的距离。河流将用多段线段表示。

谢谢

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

R3 3D 矢量代数 java 包的其余部分（自包含，无外​​部依赖项）位于此处：
https://gist.github.com/reciprocum/4e3599a9563ec83ba2a63f5a6cdd39eb

开源库的一部分
https://sourceforge.net/projects/geokarambola/