Пересечение отрезков, численно устойчивый тест - PullRequest
Новая
       40

Пересечение отрезков, численно устойчивый тест

0 голосов
/ 08 января 2012

Мне нужен точный и численно устойчивый тест для пересечения двух отрезков в 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 (сегмент пересекается в одной конечной точке)может быть не правильно определен (последняя оставшаяся ситуация без каких-либо условий) ...

Ответы [ 2 ]

4 голосов
/ 08 января 2012

Это кажется очень распространенной математической задачей. Существует хороший учебник с формулами для topcoder, который отвечает на ваш вопрос, и легко реализовать основы на любом языке программирования: Учебник по пересечению линий

С уважением, Evgenia

0 голосов
/ 07 февраля 2013 
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))

...