线段相交，数值稳定测试

我需要一个精确和数值稳定的测试，用于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

线段相交，数值稳定测试

回答

相关问题