计算几何在程序设计竞赛中比较臭名昭著的原因是,其本质上存在较多异常情况。 退化图形 设计几何算法时的常见失误是,只考虑图像的“一般位置”(general position)。一般位置指的是图形相对位置的一般情况。与其对应的异常情况称为退化(degenerate)图形,如下所示。 同一直线上的3个以上的点 相互平行或重叠的直线/线段 面积为0的多边形 多边形的边相互重叠的情况 本章介绍的代码中也考虑过这种特殊情况。确认线段相交问题中,考虑过线段平行时是重叠还是共享1个点。求凸包时,考虑过相对于当前点,最左侧的向量存在两个以上的情况(3个点处在同一直线上的情况)。 很多题目其实并不会在输入的数据中包含这些特殊情况,所以题目中没有明确表明输入数据不包含这些情况时,需要考虑自己编写的代码能否应对。 直角坐标系与屏幕坐标系 还有一个常见失误是,误将不同坐标系视为相同坐标系。本章使用的坐标系是直角坐标系,又称笛卡儿坐标系(Cartesian coordinate system)。此坐标系中,越往上y坐标值越大,越向右x坐标值越大。不过,表示数组元素位置或计算机屏幕的像素位置时,使用的屏幕坐标系其最上端的y坐标是0,越往下y值越大。虽然这种不同的表示方法并不会让问题变得更难,但会带来诸如顺时针/逆时针、左侧/右侧翻转的麻烦。因此,若要使用这种代码,就需要在接收到坐标时尽快将其变换成熟悉的坐标系上的坐标。 其他失误 令人意外的是,可以只使用整数解决许多几何问题 。解题时如果感到数值上不稳定,就应该使用整数或分数运算解决问题。 acos()、asin()、atan()等函数不仅数值上不稳定,而且非常缓慢,所以尽量不要使用。 acos()和asin()函数只接受±1范围的实数。如果发生运算误差,向函数传递了1+107左右的数值,那么函数将会返回NaN。因此,需要养成将函数输入范围限定至max(1.0, min(1.0, x))的习惯。 同样,向sqrt()函数传递0时,经常误传为很小的负数。因此,调用sqrt()函数时,应当以sqrt(max(0.0, x))这种形式限制取值范围。