算法问题实战策略——15.3　相交、距离、面积

直线与直线相交 确认两条直线是否相交并求出交点的问题在几何题中很常见。求两条直线交点的数学问题并不难，不过，要编写出没有异常的代码就比较困难了。解出x坐标后代入方程求出y坐标的程序，会无法应对水平线和垂直线等特殊的情况。因此，无论用何种方法编写程序，都要考虑到特殊情况。 表示相交直线的最好方法是，将直线表示成一个点和方向向量，即a+p•b的形式。那么，解方程a+p•b=c+q•d就能求出a+p•b和c+q•d的交点。将方程按照各坐标的形式表示出来，就能得到如下两个联立方程式。 求解p就能得到如下等式。 此时，分母为0的唯一情况是，两个向量a和b相互平行，此时当然不会存在交点。简化p就能得到如下等式。 最后把求出的p代入a+p•b就能求出两条直线的交点。代码15-3是实现这种方法的算法源代码。此代码除了将平行情况处理为异常外，没有其他异常情况，短而简洁。 代码15-3　计算两条直线交点的lineIntersection()函数 // 返回包含(a, b)的直线和包含(c, d)的直线的交点x。 // 两条直线相互平行（包含重叠的情况）时，返回假，否则返回真。 bool lineIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& x) { double det = (b - a).cross(d - c); // 两条直线相互平行时 if(fabs(det) < EPSILON) return false; x = a + (b - a) * ((c - a).cross(d - c) / det); return true; } 线段与线段相交 也许各位会想，既然已经求出了直线与直线相交，那么线段与线段相交也很容易判断。因为，先算出两条直线的交点后，再判断该点是否在线段上，就能判断出两条线段是否相交。不过，此时需要注意同一直线上存在两条线段的情况。如果一条直线包含两条线段，那么这两条线段会具有如下4种关系之一。 1. 两条线段不相互重叠 2. 两条线段相接于一点 3. 两条线段相互重叠 4. 一条线段包含于另一条线段 图15-4表示这4种情况。lineIntersection()函数对这4种情况全都返回假，(a)以外的其他3种情况均可视为相交。除了特性上可以不考虑这几种情况的问题以外，其他问题中都应考虑。代码15-4是已考虑这几种情况的算法源代码。 图15-4　同一直线上的两条线段 代码15-4　计算两条线段交点的segmentIntersection()函数 // 如果(a, b)和(c, d)是相互平行的线段，就确认两条线段是否相接于一点。 bool parallelSegments(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p) { if(b < a) swap(a, b); if(d < c) swap(c, d); // 先选出两条线段不在同一直线上的情况，以及两条线段不重叠的情况。 if(ccw(a, b, c) != 0 || b < c || d < a) return false; // 两条线段确实重叠，就找出1个交点。 if(a < c) p = c; else p = a; return true; } // 判断p是否在包含(a, b)且各边平行于x轴、y轴的最小四边形内部。 // 假设a、b、p在同一直线上。 bool inBoundingRectangle(vector2 p, vector2 a, vector2 b) { if(b < a) swap(a, b); return p == a || p == b || (a < p && p < b); } // 将线段(a, b)和(c, d)的交点返回p。 // 存在多个交点时，返回任一交点。 // 两条线段不相交时，返回false。 bool segmentIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p) { // 将两条线段平行的情况处理为异常。 if(!lineIntersection(a, b, c, d, p)) return parallelSegments(a, b, c, d, p); // 只对两条线段都包含p情况返回真。 return inBoundingRectangle(p, a, b) && inBoundingRectangle(p, c, d); } 两条线段平行的情况下，代码为了区分图15-4中的3种情况而进行了单独处理。此时可利用已编写的比较向量的函数。同一直线上存在3个以上的点时，通过比较函数对这些点排序，这样就能保证这些点始终能够依序存在于该直线上。因此，如果a<p<b成立，就能判断出p存在于连接这两个点的线段上。 线段与线段相交：不需要交点时 不需求出交点，只需判断两条线段是否相交时，就可以使用更简单的方法——ccw()函数。 图15-5表示两条相交的线段 和 。此时，对于a来说，c和d一个在b的逆时针方向上，另一个在顺时针方向上。相反，对于c来说，a和b一个在d的逆时针方向上，另一个在顺时针方向上。这两个条件其实相当于判断线段是否相交的一种标准。利用ccw()函数就能对这些条件进行简单确认。ccw(a, b, c)和ccw(a, b, d)必须一正一负，所以这两个函数返回值的相乘结果必定是负数。另外，ccw(c, d, a)和ccw(c, d, b)相乘的结果也必定是负数。 图15-5　利用ccw()判断两条线段是否相交 代码15-5是利用这种性质判断线段是否相交的算法源代码。代码将两条线段位于同一直线的情况处理为异常。进行这种处理时，同样需要用到比较运算符。比较运算符使得a<b且c<d的4个点a、b、c、b在一条直线上时，为了不使两条线段重叠，必须满足b<c或d<a。此外，为了判断两条线段没有相交而是相连的情况，ab或cd之一为0时，也将返回真。 代码15-5　简单确认两条线段是否相交的segmentIntersects()函数 // 返回两条线段是否相交。 bool segmentIntersects(vector2 a, vector2 b, vector2 c, vector2 d) { double ab = ccw(a, b, c) * ccw(a, b, d); double cd = ccw(c, d, a) * ccw(c, d, b); // 两条线段在同一直线上或端点相互重叠时 if(ab == 0 && cd == 0) { if(b < a) swap(a, b); if(d < c) swap(c, d); return !(b < c || d < a); } return ab <= 0 && cd <= 0; } 点和线之间的距离 同样，求点和线之间的距离问题也比较常见，利用向量可以很容易地求解。给出两个包含于同一直线上的点a和b时，求此直线和另一个点p之间的距离。可采用的一种方法是，先计算出从p点投影到此直线的垂足（perpendicular foot）后，算出p到直线的距离。利用向量的内积就能很容易地实现这种方法。如图15-6所示，可以利用向量pa到向量ba的投影算出直线上与p点最近的点q。代码15-6是先算出垂足后，再计算点与垂足之间的距离，并由此算出点和直线之间距离的算法源代码。 图15-6　利用向量的投影求出点投影到直线的垂足 代码15-6　计算点和线之间距离的pointToLine()函数 // 求点p在直线(a, b)上的垂足。 vector2 perpendicularFoot(vector2 p, vector2 a, vector2 b) { return a + (p - a).project(b - a); } // 点p和直线(a, b)之间的距离。 double pointToLine(vector2 p, vector2 a, vector2 b) { return (p - perpendicularFoot(p, a, b)).norm(); } 计算点和线之间距离的方法常用于求点和线段之间的距离、线段和线段之间的距离。首先考虑求点和线段之间的距离。从点到线段所在直线上的垂线正好落在线段上时，垂足和点之间的距离就会成为点与线段之间的距离。如果垂线没有落到线段上，那么线段的两个端点中，离点最近的端点和点之间的距离就会成为点与线段之间的距离。知道了点与线段之间的距离，就能很容易地求出线段与线段之间的距离，因为连接两条线段的最短线段至少会从二者中的一个端点起始。