ポリラインセグメントアルゴリズムへの3Dポイントの距離

Question

私は、n個の3d座標で構成されたパスをすべて直列に接続しました。これはthis diagramで見ることができます。

私のポイントとポリラインセグメントとの間の最短距離を探したいと思います。私は1つの線分から点の距離を計算することができますが、私はより複雑な経路でそれを行いたいと思います。

すべての線分と点の距離をテストすることに頼らず、最小値を格納するアルゴリズムがありますか？正しい方向のポインターは素晴らしいでしょう！

これは、ゲームに存在する川からのプレーヤーの距離を計算したいゲームプロジェクト用です。川はポリラインセグメントで表されます。

おかげ

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/