平面中两个三角形的交点

Question

两个三角形的交点为空或n-gon（n至6）。

理论上，很容易想出一个算法来计算交集区域。可以计算所有线段的可能交点并将它们与三角形的角点的点相结合。

在实践中，有一些数值问题。如果线段是（几乎）平行的，它们可能会或可能不会有交点，并且其计算可能不准确（通常由矩阵的行列式分割，然后大致为零）。

任何建议，以避免这些数值不稳定？

Answer 1

我不知道如何找到相交区域，但如果你想要的只是知道它们是否相交，文章"Faster Triangle-Triangle Intersection Tests" by Olivier Devillers and Philippe Guigue中的算法应该是非常稳定的，根据一些多项式阶数理论，不是很明白，也没有抬头看。

遵循我自己的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; 
      } 
     } 
    } 
}