線分の交差、数値的に安定したテスト

Question

2次元の2つの線分の交点に対して、正確で数値的に安定したテストが必要です。 4つのポーションを検出する可能性のあるソリューションが1つあります。コードを参照してください。

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をテストに使用するか、または交差点の計算にのみ使用することは理にかなっていますか？

私は（任意の条件なしで最後に残った状況）、2位が（セグメントは1つのエンドポイントで交差する）を正しく検出できない可能性が怖いです...

Answer 1

これは非常に一般的な数学の問題としてそうです。 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))