1.5 线段相交
(Segment Intersection)

1.5.1 对角线(Diagnoals)

我们的目标是编写一个对多边形进行三角分割的程序。问题的关键就是，找到多边形的一条对角线，即连接两个顶点 \(v_i, v_j\) 的线段。 如果线段 \(v_i v_j\) 被多边形边界的一部分挡住，那么它就不是对角线。被挡住的线段 \(v_i v_j\) 一定与多边形的一条边相交。 注意即使线段 \(v_i v_j\) 仅与边 \(e\) 的某个端点相交，可能只是一点点擦边，它也是有效地遮挡，因为对角线必须具有清晰的可见性(clear visibility)。

根据对角线的定义，有一个直接的推论:

该引理的条件(1)的表述方式，意味着我们不需要找到 \(s\) 与 \(e\) 的实际交点，仅需一个布尔类型的线段是否相交，从定性分析就可以确定线段的"对角性diagonalhood"。 注意，如果采用更直接的定义方式——对角线仅在其端点处与多边形边相交，则无法达到此目的。这种表述方式需要算出交点，然后将其与端点进行比较。 条件(2)的目的是，区分内部对角线和外部对角线，并排除与关联边共线重叠的情况。 我们将在 1.6.2 节中再次讨论它，现在我们要编写代码来检查非相交条件。

1.5.2 斜率问题(Problems with Slopes)

设 \(v_iv_j = ab\) 且 \(e = cd\)。面对 \(ab\) 和 \(cd\) 是否相交这一问题，一个常见的思路是，找到这两条线段对应的直线 \(L_1\) 和 \(L_2\) 的交点。 通常做法是，求解斜截式线性方程组，然后检查该交点是否在线段上。显然这种方法是可行，而且编代也并不难。但是，代码混乱且容易出错，需要相当细致才能使其完全正确。 这里需要处理两种特殊情况 ① 垂直线段斜率无穷大 ② 平行线段不相交。这两种情况都会导致计算中出现除以零的情况，必须通过特殊处理代码来避免。 此外，检查交点是否在线段上也存在数值精度问题。

为了避免这些问题，我们就不计算斜率。

1.5.3 左边(Left)

两条线段是否相交可以通过函数 Left 来判断，该函数是要确定一个点是否位于有向线的左侧。我们将在下一节中展示如何使用函数 Left 来判断相交情况，这里重点讨论函数 Left 本身。

按照特定顺序排列两个点\((a, b)\)可以确定一条带有方向的直线。如果点 \(c\) 位于由 \((a, b)\) 确定的直线左侧，那么三点 \((a, b, c)\) 构成一个逆时针回路，这就是点位于线左侧的意义。 如图 1.22 所示。

现在与有符号面积的联系终于清晰了。\(c\) 在 \((a, b)\) 的左侧，当且仅当逆时针三角形的面积 \(\mathcal{A}(a, b, c)\) 为正数。 因此，我们可以通过调用 Area2 函数来实现函数 Left，如下 Code 1.6 所示。

        bool Left(tPointi a, tPointi b, tPointi c)
        {
            retrun Area2(a,b,c) > 0;
        }

        bool LeftOn(tPointi a, tPointi b, tPointi c)
        {
            return Area2(a,b,c) >= 0;
        }

        bool Collinear(tPointi a, tPointi b, tPointi c)
        {
            return Area2(a,b,c) == 0;
        }

当然我们也可以，先求过点 \(a\) 和 \(b\) 的直线方程，再将点 \(c\) 的坐标代入该方程，来判定它是否在直线的左侧。 这种方法虽然直接，但会受到之前提到的特殊情况的限制。相比之下，面积的计算不存在特殊情况。

当 \(c\) 与 \(ab\) 共线时会发生什么? 此时得到的三角形面积为零。因此，面对这种特殊的几何情况，我们很幸运的得到了特殊的数值结果。 由于判定是否共线是个很有用的功能，我们为此编写了一个单独的函数 Collinear，以及 LeftOn。再看 Code 1.6 的三个函数，等价于 <、≤、= 的表达式。

请注意，在这些例程中，我们是用面积的两倍与零比较的，而不是面积本身。原因是面积可能不是整数，我们不希望超出整数的取值范围。

1.5.4 布尔相交(Boolean Intersection)

如果两个线段 \(ab\) 和 \(cd\) 相交，那么 \(c\) 和 \(d\) 就会被 \(ab\) 所在的直线 \(L_1\) 分隔在左右两侧。 类似的 \(ab\) 会被 \(cd\) 所在的直线 \(L_2\) 分隔，如图 1.23(a) 所示。

如图 1.23(b) 所示，这两个条件单独一个成立，不足以保证相交。只有两个同时满足，才能保证。 根据这两个条件，我们可以直接写出一段代码，来判定已知四个端点中任意三个不共线时线段是否正常相交(proper intersection)。 如 Code 1.7 所示，我们可以通过显式地调用 Collinear 来检查不共线的条件是否成立。

        bool IntersectProp(tPointi a, tPointi b, tPointi c, tPointi d)
        {
            // 排除不满足条件的情况
            if (Collinear(a,b,c) || Collinear(a,b,d) || Collinear(c,d,a) || Collinear(c,d,b))
                return FALSE;
            return Xor(Left(a,b,c), Left(a,b,d)) && Xor(Left(c,d,a), Left(c,d,b));
        }

        //! 异或, x,y 中有且只有一个为 TRUE
        bool Xor(bool x, bool y)
        {
            // 对输入的参数取反，保证它们都是 0/1
            return !x ^ !y;
        }

这段代码存在冗余，因为四个相关的三角形面积都被计算了两次。可以通过计算面积并将其存储在局部变量中，或者设计其他更适合问题的原语来消除这种冗余。 我不建议存储面积，因为那样代码就不透明了。但或许可以围绕其他原语更自然地设计代码。事实证明，对于三角分割而言，第一个 if 语句可以完全移除。 尽管这样一来，该例程就无法计算 proper intersection(也无法计算 improper intersection)。这一点在练习 1.6.4[2] 中进行了探讨。 我倾向于牺牲效率来换取代码的清晰度，因此保留 IntersectProp 函数不变，这对于除了当前编程任务之外的其它用途可能很有帮助。 在本例中，IntersectProp 函数正是计算清晰可见性所需的函数( 1.1.2 节)。

这里有个细节。人们可能会想通过要求面积的乘积严格为负来替代这里的异或运算，从而确保它们的符号相反，并且两者都不为零。

        Area2(a,b,c) * Area2(a,b,d) < 0
     && Area2(c,d,a) * Area2(c,d,b) < 0;

这种写法的缺陷在于，面积的乘积可能会导致整数溢出！因此，为了节省几行代码而采用的巧妙编码技巧可能会掩盖一个严重的错误。 也可以通过让 Area2 返回 +1、0 或 -1 而不是实际面积来避免这种溢出问题(Sedgewick 1992, p.350)。目前我倾向于返回实际面积，因为这在其他情况下很有用——例如，计算多边形的面积！ 在第 4 章中，当我们讨论溢出这一通用问题时(Code 4.23)，我们将重新考虑这一决定。

非正常的相交(Improper Intersection)

我们必须处理两条线段非正常相交的"特殊情况"，因为引理 1.5.1 要求线段为对角线时，其交点必须完全为空。而非正常相交恰好发生在一条线段的端点 \(c\) 位于另一条线段 \(ab\) 的中间某个位置时。 参见图 1.24(a)。这种情况仅在 \(a,b,c\) 共线时才会发生。但共线并非相交的充分条件，如图 1.24(b) 所示。我们需要判断的是 \(c\) 是否在 \(a\) 和 \(b\) 之间。

之间(Betweenness)

我们希望实现一个函数，能够在不计算斜率的情况下，判定"之间"，因为使用斜率需要处理很多特殊情况。仅在已知 \(c\) 位于包含 \(ab\) 的直线上时，才有必要检查 \(c\) 是否出于 \(ab\) 之间。 我们可以利用这一信息。如果 \(ab\) 不是垂直的，那么 \(c\) 位于 \(ab\) 上，当且仅当 \(c\) 的 \(x\) 坐标落在由 \(a\) 和 \(b\) 的 \(x\) 坐标确定的区间内。 如果 \(ab\) 是垂直的，则对 \(y\) 坐标进行类似的检查。参见 Code 1.8。

        bool Between(tPointi a, tPointi b, tPointi c)
        {
            tPointi ba, ca;
            if (!Collinear(a,b,c))
                return FALSE;

            // 如果 ab 不垂直，检查 x 坐标，否则 y 坐标
            if (a[X] != b[X])
                return ((a[X] <= c[X]) && (c[X] <= b[X])) ||
                       ((a[X] >= c[X]) && (c[X] >= b[X]));
            else
                return ((a[Y] <= c[Y]) && (c[Y] <= b[Y])) ||
                       ((a[Y] >= c[Y]) && (c[Y] >= b[Y]));
        }

1.5.5 线段相交的代码(Segment Intersection Code)

我们终于可以写出判定线段相交的代码了。两条线段相交，当且仅当它们正常相交，或者一条线段的一个端点位于另一条线段的两个端点之间。 对非正常相交的检查是通过四次调用 Between 函数实现的。参见 Code 1.9。练习 1.6.4[3] 要求分析此例程的效率低下之处。

        bool Intersect(tPointi a, tPointi b, tPointi c, tPointi d)
        {
            if (IntersectProp(a,b,c,d))
                return TRUE;
            else if (Between(a,b,c) || Between(a,b,d) || Between(c,d,a) || Between{c,d,b))
                return TRUE;
            else
                return FALSE;
        }