선분 교차점, 수치 적으로 안정된 테스트

Question

2D에서 2 개의 선분 교차점에 대해 정밀하고 수치 적으로 안정적인 테스트가 필요합니다. 4 개의 포션을 감지하는 가능한 솔루션이 하나 있습니다. 코드를 참조하십시오.

getInters (double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, double & x_int, double & y_int ) 
{ 
    3: Intersect in two end points, 
    2: Intersect in one end point, 
    1: Intersect (but not in end points) 
    0: Do not intersect 

unsigned short code = 2; 

//Initialize intersections 
x_int = 0, y_int = 0; 

//Compute denominator 
    double denom = x1 * (y4 - y3) + x2 * (y3 - y4) + x4 * (y2 - y1) + x3 * (y1 - y2) ; 

    //Segments are parallel 
if (fabs (denom) < eps) 
    { 
      //Will be solved later 
    } 

//Compute numerators 
    double numer1 =  x1 * (y4 - y3) + x3 * (y1 - y4) + x4 * (y3 - y1); 
double numer2 = - (x1 * (y3 - y2) + x2 * (y1 - y3) + x3 * (y2 - y1)); 

//Compute parameters s,t 
    double s = numer1/denom; 
    double t = numer2/denom; 

    //Both segments intersect in 2 end points: numerically more accurate than using s, t 
if ((fabs (numer1) < eps) && (fabs (numer2) < eps) || 
    (fabs (numer1) < eps) && (fabs (numer2 - denom) < eps) || 
    (fabs (numer1 - denom) < eps) && (fabs (numer2) < eps) || 
    (fabs (numer1 - denom) < eps) && (fabs (numer2 - denom) < eps)) 
    { 
      code = 3; 
    } 

//Segments do not intersect: do not compute any intersection 
    else if ((s < 0.0) || (s > 1) || 
     (t < 0.0) || (t > 1)) 
    { 
      return 0; 
    } 

    //Segments intersect, but not in end points 
    else if ((s > 0) && (s < 1) && (t > 0) && (t < 1)) 
    { 
      code = 1; 
    } 

//Compute intersection 
x_int = x1 + s * (x2 - x1); 
y_int = y1 + s * (y2 - y1); 

//Segments intersect in one end point 
return code; 
} 

모든 제안 된 조건이 (둥근 오류를 피하기 위해) 제대로 설계되어 있는지 확실하지 않습니다.

매개 변수 s, t를 테스트에 사용하거나 교차 계산에만 사용하는 것이 합리적입니까?

나는

Answer 1

이것은 매우 일반적인 수학 문제로 보인다 ... 제대로 (어떤 조건없이 마지막 남은 상황) 검색되지 않을 수 있습니다 위치 2 (세그먼트가 하나의 종단점에 교차) 두렵다. 이 질문에 응답 탑 코더에 수식 좋은 튜토리얼 그리고 당신이 원하는대로 프로그래밍 언어의 기초 쉽게 구현할 수 : Line Intersection Tutorial

감사합니다, Evgenia

Answer 2

if(fabs(denom) < eps){ 
    if((fabs(len(x2, y2, x3, y3) + len(x2, y2, x4, y4) - len(x3, y3, x4, y4)) < eps) || (fabs(len(x1, y1, x3, y3) + len(x1, y1, x4, y4) - len(x3, y3, x4, y4)) < eps) || (fabs(len(x3, y3, x1, y1) + len(x3, y3, x2, y2) - len(x1, y1, x2, y2)) < eps) || (fabs(len(x4, y4, x1, y1) + len(x4, y4, x2, y2) - len(x1, y1, x2, y2)) < eps)){ 
     return 1; 
    }else{ 
     return 0; 
    } 
} 

어디 len = sqrt(sqr(c - a) + sqr(d - b))