我想UVA 11275这道题一定会令我很难忘。因为它不仅让我因为一个错的算法栽进去了三天，而且它还带领我走进了三维几何题的大门。题意很简单，给出两个三维空间中的三角形（也就是一个平面上用三条边包围起来的部分），问它们是否相交（有任何的公共点皆可）。
    算法是这样的，要分两种情况：两个三角形所在的平面相交还是平行（重合暂且也算平行）。怎么判定这一点呢？只要看两个平面的法向量（就是和平面垂直的向量。法向量的求法也很简单，把三角形的任意两条边当作两个向量，求它们的叉积即可。）是否平行（两个向量如果平行，则它们的叉积为0向量。）即可，如果平行则两个平面平行。下面我们分别来讨论这两种情况下的算法：

    一、两个三角形所在的平面相交

    1. 求出两个平面的交线

    要确定一条直线，只要求出它所在的向量和上面的任何一个点即可。求这条直线的向量很简单，两个平面的法向量的叉积就是。
    求两个平面的交线上的任意一点的方法是这样的：一个平面的方程是ax + by + cz + d = 0，其中{a, b, c}是平面的法向量，而d = -ax₀ - by₀ - cz₀，(x₀, y₀, z₀)是平面上的任何一点的坐标皆可（我们不是知道平面上一个三角形的三个顶点吗，随便拿一个点即可。）。对于两个平面，我们就有了两个方程：

        a₁x + b₁y + c₁z + d₁ = 0
        a₂x + b₂y + c₂z + d₂ = 0

    我们再任意定一个z的值，设它为z₀，则我们就得到了一个二元一次方程组：

        a₁x + b₁y = -c₁z₀ - d₁
        a₂x + b₂y = -c₂z₀ - d₂

    在程序中解二元一次方程组，可以事先算好公式。对于一般的二元一次方和组

        a₁x + b₁y = c₁
        a₂x + b₂y = c₂

    它的解为

        x = (b₂c₁ - b₁c₂) / (a₁b₂ - a₂b₁)
        y = (a₁c₂ - a₂c₁) / (a₁b₂ - a₂b₁)

    可见，若a₁b₂ - a₂b₁ = 0，则解不出（无解或者没有唯一解）。

    解出了这个方程组，我们就得到了在这条直线上与z₀对应的x、y值，直线上的一点就找到了。但是如果方程组解不出呢（如果这条直线与z轴垂直，则直线上的点的z坐标是常数，那么你指定的z₀也许根本不可能在直线上。）？那我们就转而任意指定一个x₀，然后解一个关于y和z的方程组，或者指定一个y₀，然后解一个关于x和z的方程组。三个方程组总归有一个解得出的，为什么我就不证明了，请自己思考。
   
    2. 求出两个三角形的边与两平面的交线的所有交点

    现在有三个三角形，共有6条边，也就是6个线段。我们刚才知道了两个平面的交线，现在要求出这条交线与6条线段分别的交点（如果有交点的话）。那么我们就要解决两个问题：怎么判定一条直线是否与一条线段相交？如果相交，怎么求出交点？

    2.1. 判定直线是否与线段相交

    直线由一个点和一个向量来决定，线段则由两个端点决定。解决这个问题我们需要三个向量：直线本身的向量v，从直线上的任意一点分别指向线段的两个端点的向量a、b。如图1、2、3所示，蓝色的是直线，红色的是线段。


    我们知道两个向量可以决定一个平面，两个向量的叉积就是该平面的法向量。若直线与线段相交，则平面av和平面vb应该是同一个平面，因此它们的单位法向量一定相同，也就是(a × v) / |a × v| = (v × b) / |v × b|。如果出现了图2中的情况，平面av和平面vb的法向量一定不相同。如果出现图3中的情况，虽然av和vb是同一个平面，但是由于右手规则，a × v和v × b方向是相反的，因此前面所说的单位法向量也不相同。或者更简单地说，向量v一定要夹在向量a、b的中间，直线才会穿过线段。
    如果a × v和v × b有一个为0向量，则说明直线正好经过线段的一个端点，这时也可以算作相交。但是如果a × v和v × b都为0，则说明直线经过线段的两个端点，也就是和线段重合，这时一般不算作相交，因为直线和线段没有唯一的交点。
    综上所述，直线与线段相交的充要条件是：

        (a × v) / |a × v| = (v × b) / |v × b|，或者a × v和v × b只有一个为0向量。

    2.2. 求直线与线段（其实就是直线与直线）的交点

    已知了直线上的一点(x₁, y₁)和直线所在的向量{a, b, c}，我们就可以写出直线的参数方程：

        x = x₁ + at, y = y₁ + bt, z = z₁ + ct

    其中t是一个参数，它任取一个值就可以决定直线上的一点。
    两条直线就有两个方程：

        x = x₁ + at₁, y = y₁ + bt₁, z = z₁ + ct₁
        x = x₂ + at₂, y = y₂ + bt₂, z = z₂ + ct₂

    既然要求两条直线的交点，我们就可以把两条直线的方和合并成这样一个方程组：

        x₁ + a₁t₁ = x₂ + a₂t₂
        y₁ + b₁t₁ = y₂ + b₂t₂
        z₁ + c₁t₁ = z₂ + c₂t₂

    我们只要取这三个方程中的两个，就可以解出t₁和t₂了。当然，就像前面求平面的交线时一样，也有可能选出的两个方程解不出，但是三个方程中总归有两个合起来是解得出的，为什么我也不证明了，请自己思考。
   
    其实我们只要求出t₁和t₂中的任何一个，把它代入直线的参数方程中，就可以求出两直线的交点了。

    2.3. 如果有任何一个三角形的边与 两平面的交线 的交点落在另一个三角形内部 或边上，则两三角形相交

    上面这个标题就是最终的算法。为什么是这样我也不证明了，应该很容易想通的。现在我们面临的主要问题是：如何判定一个点是否在一个三角形内、如何判定一个点是否在三角形的边上（也就是如何判定一个点是否在一条线段上）。

    给出一个三角形，由三个点决定，再给出另外一个点，用下面的算法可以判定该点是否在三角形所在的平面上并且位于三角形内部。（其实这个算法可以扩展到任何平面内的凸多边形。）

    从已知点分别指向三角形的三个顶点（三个顶点按照顺、逆时针顺序皆可），有三个向量，a、b和c。这三个向量两两都可以决定一个平面。若点在三角形内，则平面ab、bc和ca应该都是同一个平面，也就是说它们的单位法向量相同。这和我们前面讲的判定直线与线段是否相交的原理基本相同，也就是要 (a × b) / |a × b| = (b × c) / |b × c| = (c × a) / |c × a|。图5中，平面ac、bc和ca显然不同，它们的单位法向量肯定也不同；图6中，虽然三个向量在同一平面内，但是c × a的方向和b × c相反，因此我们求出的单位法向量的方向也不同。更通俗地说，向量a、b和c要顺时针或逆时针转一圈才能判定点在三角形内。