Пересечение сегментов линий, численно стабильный тест

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

Идея: 1-я проверка для вырожденных случаев (параллельная, падающая или непересекающаяся). 2-й вычислите точку пересечения. 3-я проверка, если пересечение лежит на любом сегменте, и если да, то где. Если вы можете позволить себе использовать рациональные методы, а не реалы, вы даже можете получить точный ответ. –

Это кажется, очень распространенная проблема математики. Там хороший учебник с формулами на 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

Пересечение сегментов линий, численно стабильный тест

ответ

Смежные вопросы