Пересечение двух треугольников в плоскости

Question

Пересечение двух треугольников либо пустое, либо n-угольное (для n до 6).

В теории легко найти алгоритм вычисления площади пересечения. Можно вычислить возможные пересечения всех сегментов линии и объединить их с точками угловых точек треугольников.

На практике возникают некоторые числовые проблемы. Если сегменты линии (почти) параллельны, они могут иметь или не иметь точку пересечения, и ее вычисление может быть неточным (обычно делится на определитель матрицы, которая тогда равна нулю).

Любые предложения, чтобы избежать этих числовых неустойчивостей?

Answer 1

Я не знаю, как найти область пересечения, но если вам нужно только знать, пересекаются ли они, то алгоритм в статье "Faster Triangle-Triangle Intersection Tests" by Olivier Devillers and Philippe Guigue должен быть очень стабильным в соответствии с некоторой теорией полиномиального порядка. t вполне поняли и не подняли взгляда в ссылке.

Выполняет мою собственную реализацию JavaScript. Я не могу гарантировать, что это правильно, потому что он не видел достаточного действия в реальном мире.

function det3(a, b, c) 
{ 
    var a11 = a[0] - c[0]; var a12 = a[1] - c[1]; 
    var a21 = b[0] - c[0]; var a22 = b[1] - c[1]; 

    return a11 * a22 - a21 * a12; 
} 

function planar_intersect(vs, t1, t2) 
{ 
    var p1, q1, r1; 
    var p2, q2, r2; 

    // I am doing this weird unpacking of the vertices because 
    // originally they were on R³, and I had a code here to project 
    // them to some orthogonal plane on R². 
    p1 = t1.a; q1 = t1.b; r1 = t1.c; 
    p2 = t2.a; q2 = t2.b; r2 = t2.c; 

    // Ensure both triangles are counterclockwise 
    var tmp; 
    if(det3(p1, q1, r1) < 0) { 
     tmp = q1; 
     q1 = r1; 
     r1 = tmp; 
    } 
    if(det3(p2, q2, r2) < 0) { 
     tmp = q2; 
     q2 = r2; 
     r2 = tmp; 
    } 

    // Calculate signed areas of triangles 
    var s1 = Array(3); 

    // If 0, the vertex is on the edge of the other triangle 
    s1[0] = det3(p1, p2, q2); 
    if(s1[0] == 0) 
     return true; 

    s1[1] = det3(p1, q2, r2); 
    if(s1[1] == 0) 
     return true; 

    s1[2] = det3(p1, r2, p2); 
    if(s1[2] == 0) 
     return true; 

    // If all positive, the vertex is internal to the other triangle 
    if(s1[0] > 0 && s1[1] > 0 && s1[2] > 0) { 
     return true; 
    } 

    // Reorder t2 in order for a1 to be in the right area 
    for(var i = 0; i < 2; ++i) { 
     if(s1[0] > 0 && s1[2] <= 0) { 
      break; 
     } 

     tmp = s1[0]; 
     s1[0] = s1[1]; 
     s1[1] = s1[2]; 
     s1[2] = tmp; 

     tmp = p2; 
     p2 = q2; 
     q2 = r2; 
     r2 = tmp; 
    } 

    if(s1[1] > 0) { 
     // Follow Figure 9 tree. 
     if(det3(r2, p2, q1) >= 0) { 
      // II.a 
      if(det3(r2, p1, q1) >= 0) { 
       // III.a 
       if(det3(p1, p2, q1) >= 0) { 
        return true; 
       } else { 
        // IV.a 
        if(det3(p1, p2, r1) >= 0) { 
         // V 
         return det3(q1, r1, p2) >= 0; 
        } else { 
         return false; 
        } 
       } 
      } else { 
       return false; 
      } 
     } else { 
      // II.b 
      if(det3(r2, p2, r1) >= 0) { 
       // III.b 
       if(det3(q1, r1, r2) >= 0) { 
        // IV.b 
        return det3(p1, p2, r1) <= 0; 
       } else { 
        return false; 
       } 
      } else { 
       return false; 
      } 
     } 
    } else { 
     // Follow Figure 10 tree. 
     if(det3(r2, p2, q1) >= 0) { 
      // II.a 
      if(det3(q2, r2, q1) >= 0) { 
       // III.a 
       if(det3(p1, p2, q1) >= 0) { 
        // IV.a 
        return det3(p1, q2, q1) <= 0; 
       } else { 
        // IV.b 
        if(det3(p1, p2, r1) >= 0) { 
         // V.a 
         return det3(r2, p2, r1) >= 0; 
        } else { 
         return false; 
        } 
       } 
      } else { 
       // III.b 
       if(det3(p1, q2, q1) <= 0) { 
        // IV.c 
        if(det3(q2, r2, r1) >= 0) { 
         // V.b 
         return det3(q1, r1, q2) >= 0; 
        } else { 
         return false; 
        } 
       } else { 
        return false; 
       } 
      } 
     } else { 
      // II.b 
      if(det3(r2, p2, r1) >= 0) { 
       // III.c 
       if(det3(q1, r1, r2) >= 0) { 
        // IV.d 
        return det3(r1, p1, p2) >= 0; 
       } else { 
        // IV.c 
        if(det3(q1, r1, q2) >= 0) { 
         // V.c 
         return det3(q2, r2, r1) >= 0; 
        } else { 
         return false; 
        } 
       } 
      } else { 
       return false; 
      } 
     } 
    } 
}