폴리 라인 세그먼트 (segment) 알고리즘에 대한 3d 점의 거리

Question

나는 모두 3 차원 좌표로 구성된 경로가 있습니다.이 경로는 모두 this diagram에서 볼 수 있습니다.

내 포인트와 폴리 라인 세그먼트 사이의 최단 거리를 찾고 싶습니다. 단일 선분에서 한 점의 거리를 계산할 수 있지만 더 복잡한 경로에 대해 수행하려고합니다.

모든 선분을 점 거리로 테스트하고 최소값을 저장하지 않는 알고리즘이 있습니까? 올바른 방향으로 어떤 포인터가 좋을 것입니다!

이것은 게임에 존재하는 강에서 플레이어의 거리를 계산하려는 게임 프로젝트 용입니다. 강은 폴리 라인 세그먼트로 표시됩니다.

감사

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 벡터 대수 자바 패키지는 여기에 있습니다 : 오픈 소스 라이브러리의 https://gist.github.com/reciprocum/4e3599a9563ec83ba2a63f5a6cdd39eb

부분 https://sourceforge.net/projects/geokarambola/