線段相交，數值穩定測試

我需要一個精確和數值穩定的測試，用於2D中兩條線段相交。有一種可能的解決方案檢測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進行測試或僅將其用於計算交叉點有意義嗎？

恐怕位置2（段一個終點相交）可能無法正確檢測（最後剩餘的情況下，沒有任何條件）...

來源

2012-01-08 justik

想法：第一次檢查退化病例（並行，事件或不相交）。第二個計算交點。第三次檢查交叉點是否位於任一段上，如果是，則在哪裏。如果你有能力使用理性而不是實質，你甚至可以得到確切的答案。 – 2012-01-08 18:26:45

這似乎是一個很普通的數學題。有與TopCoder的公式一個很好的教程，回答你的問題，很容易實現在任何編程語言你想要的基本面：Line Intersection Tutorial

問候，葉夫根

來源

2012-01-08 18:46:53 Evgenia

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))

來源

2013-02-07 08:17:10

線段相交，數值穩定測試

回答

相關問題