线段相交、数值稳定测试

Question

我需要对二维中的 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 进行测试是否有意义，还是仅用于计算交集？

我担心位置 2（线段在一个端点相交）可能无法正确检测到（最后剩下的情况没有任何条件）...

Answer 1

这似乎是一个非常常见的数学问题。 topcoder 上有一个很好的教程，其中包含公式，可以回答您的问题，并且可以轻松地以您想要的任何编程语言实现基础知识：线相交教程

问候，
叶夫根尼娅

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