计算几何 --- 判断两条线段是否相交（平面内）

　　计算几何中，判断线段是否相交是最基本的题目。 所谓几何， 最基本的当然就是坐标， 从坐标中我们可以知道位置和方向，比如：一个点就是一个位置，两点确定一条直线，从某点指向另一点的有向线段所在的直线是一向量。要处理几何题，我们又不得不涉及到叉积和点积， 判断线段相交就要用到叉积。

　　下面先讲讲相交的形式：

　　说到线段， 我们很自然想到直线，判断两条直线是否相交只需判断它们斜率是否相等，相等就为平行或重合， 不等就相交（注：判断相交我们不采用除法，因为除法容易产生浮点误差，当两条直线斜率接近时，很容易出错。 事实上，几乎所有几何题都不建议采用除法）。

　　线段相交有两种形式：

　　　　规范相交和 非规范相交 。 区别就是交点是否是其中一条线段的端点，不是的是规范相交。

　　叉积的概念： 设向量 a(x1, y1) 、 b(x2, y2) ;

　　　　　　　　a x b = x1*y2 - x2*y1; (与数学中的叉积不太一样)

　　判断线段相交比较繁琐，主要就是判断异侧：

　　　　我们以一条线段的一端点为起点，沿着线段方向看去（一条射线），在左手边为逆时针方向，右手边为顺时针方向。如果另一线段两端点分别在这一线段的两侧，那么线段可能相交（也可能在线段外），否则不可能相交。对另一线段采用相同方法就可判断出是否相交了。

　　　  这个过程主要通过叉积来判断： 叉积大于 0 ，在点在向量的顺时针方向，小于 0 ， 在逆时针方向 ； 等于 0， 端点在直线上。

　　具体实现：

　　　　设：线段 a ：P1(x1, y1)、P2(x2, y2)　　　　　　线段 b: Q1(x3, y3)、Q2(x4, y4)

　　　　d1 ====>   (P2 - P1) x (Q1 - P1) (叉积)

　　　　d2 ====>   (P2 - P1) x (Q2 - P1) (叉积)

　　　　d3 ====>   (Q2 - Q1) x (P1 - Q1) (叉积)

　　　　d4 ====>   (Q2 - Q1) x (P2 - P1) (叉积)

　　首先，先判断端点是否在另一线段上。

　　然后，我们只需判断 d1 * d2 < 0  并且 d3 * d4 < 0 便可判断线段相交。

 1 #define cs const
 2 #define cp const P&
 3 #define op operator
 4 const  double eps = 1e-8;
 5 inline int sig(double x) {return (x>eps)-(x<-eps);}
 6 
 7 struct P{
 8     double x, y;
 9     void in() { scanf("%lf%lf", &x, &y); }
10     P(double x=0.0, double y=0.0) : x(x), y(y) {}
11 
12     P op-(cp a)cs { return P(x-a.x, y-a.y); }
13     double op^(cp a)cs { return x*a.y - y*a.x; }    //叉积
14     double op*(cp a)cs {return x*a.x + y*a.y;}
15 
16     double cross(P a, P b) { return (a-*this) ^ (b-*this); }
17     double dot(P a, P b)  { return (a-(*this)) * (b-(*this)); }
18     bool on_seg(P a, P b) { return !sig(cross(a, b)) && sig(dot(a, b)) <= 0; }//判断是否在点上
19 };
20 
21 bool seg(P a, P b, P c, P d) { //判断相交(a - b)线段 、(c - d)线段
22     if(a.on_seg(c, d) || b.on_seg(c, d) || c.on_seg(a, b) || d.on_seg(a, b))
23         return true;
24     return sig(a.cross(b, c)*a.cross(b, d)) < 0 && sig(c.cross(d, a)*c.cross(d, b)) < 0;
25 }

训练题：杭电oj 1086 ：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1086