CODEWITHSUNDEEP
c++testingintersectionnumerical
justik
justik

Reputation: 4255

Line segments intersection, numerically stable test

I need a precise and numerically stable test for 2 line segments intersection in 2D. There is one possible solution detecting 4 postions, see bellow the code.

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;
 }

I am not sure whether all proposed conditions are designed properly (to avoid roundness errors).

Does it make sense to use the parameters s, t for testing or use it only for the computation of an intersection?

I am afraid that position 2 (segment intersect in one end point) may not be correctly detected (last remaining situation without any condition)...

Upvotes: 0

Views: 7261

Answers (2)

Andrue Konstantinov
Andrue Konstantinov

Reputation: 1

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;
    }
}

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

Upvotes: 0

Evgenia
Evgenia

Reputation: 268

This seems as a very common math problem. There's a good tutorial with formulas on topcoder that answers your question and it is easy to implement the fundamentals in whatever programming language you want: Line Intersection Tutorial

Regards, Evgenia

Upvotes: 5

Related Questions