算法导论之计算几何学小记 33.1

在USACO上做题时发现要判断两线段是否相交,表示不会,别人说算导上就有,于是找来看看

第一节主要3个小问题

1.有向线段p0p1,p0p2,如何判断p0p1在p0p2的顺时针还是逆时针

方法叉积

(p1-p0)x(p2-p0)=(x1-x0)(y2-y0)-(x2-x0)(y1-y0)

若>0，p0p1在p0p2的顺时针.<0则逆 ==0则共线...

2.p0-p1 ,p1-p2,如何判断p1-p2是向左转还是右转

还是采用上面的方法,不过判断的是p0p1-p0p2 (将p0p2连起来)

3.判断两线段是否相交。

思路是跨立测试，名字其实一看就懂，还是我脑子太麻木，我想一条线段能跨立另一条的直线（及一个点在逆时针，一个顺时针）不能表示一定相交啊，

那就反过来再来一次啊....

 1 struct node
 2 {
 3     int x,y;
 4 };
 5 
 6 bool segment-intersect(node n1,node n2,node,n3,node n4)
 7 {
 8     int d1=direction(n1,n2,n3);
 9     int d2=direction(n1,n2,n4);
10     int d3=direction(n3,n4,n1);
11     int d4=direction(n3,n4,n2);
12 
13     if((d1>0&&d2<0)||(d1<0&&d2>0)&&
14         ((d3>0&&d4<0)||(d3<0&&d4>0)))
15         return true;
16     //不考虑点在线段上的情况
17     return false;
18 
19 }
20 
21 
22 int direction(node ns,node n1,node n2)
23 {
24     int x1=n1.x-ns.x;
25     int y1=n1.y-ns.y;
26     int x2=n2.x-ns.x;
27     int y2=n2.y-ns.y;
28 
29     return x1*y2-x2*y1;
30 }