判断两线段是否相交模板

 1 struct point
 2 {
 3     double x, y;
 4     point( double _x = 0, double _y = 0 )
 5     {
 6         x = _x;
 7         y = _y;
 8     }
 9     point operator-( point t )
10     {
11         return point( x - t.x, y - t.y );
12     }
13     double operator*( point t )
14     {
15         return x * t.y - y * t.x;
16     }
17 };
18 
19 //快速排斥试验模板
20 bool quickExclude( point a, point b, point c, point d )
21 {
22     int x1 = a.x, x2 = b.x, x3 = c.x, x4 = d.x;
23     int y1 = a.y, y2 = b.y, y3 = c.y, y4 = d.y;
24     if (  min(x1,x2) <= max(x3,x4) && min(x3,x4) <= max(x1,x2) &&
25            min(y1,y2) <= max(y3,y4) && min(y3,y4) <= max(y1,y2)      )
26            return true;
27     else    return false;
28 }
29 
30 //跨立试验模板（两线段是否相交）
31 bool ifIntersect( point a, point b, point c, point d )
32 {
33     if ( quickExclude( a, b, c, d ) )
34     {
35         if (  ( ( a - c ) * ( c - d ) ) * ( ( b - c ) * ( c - d ) ) <= 0 && ( ( c - a ) * ( a - b ) ) * ( ( d - a ) * ( a - b ) ) <= 0  )
36         return true;
37     }
38     return false;
39 }
40 
41 //若已判断两线段相交求交点或者求两相交直线交点模板（四个点为a, b, c, d），a1, b1, c1, a2, b2, c2为方程系数，交点为x0和y0
42 double a1 = a.y - b.y;
43 double b1 = b.x - a.x;
44 double c1 = a.x * b.y - b.x * a.y;
45 double a2 = c.y - d.y;
46 double b2 = d.x - c.x;
47 double c2 = c.x * d.y - d.x*c.y;
48 double x0 = ( b1 * c2 - b2 * c1 ) / ( a1 * b2 - a2 * b1 );
49 double y0 = ( a2 * c1 - a1 * c2 ) / ( a1 * b2 - a2 * b1 );
View Code
判断两线段是否相交 模板

判断两线段是否相交模板
