学步园

判断线段与多边形是否相交。

模板：

#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;
#define Pi 3.14159265358979
#define PRECISION 1e-8

//点
typedef struct {
    double x,y;
} POINT;

//直线两点的表达
struct LINE{
    POINT p1,p2;
};

//多边形结构体
struct POLY{
    int n;
    double area;
    POINT plist[15];
};

//与0作比较，小于精度则认为是和0相等
int cmpzero(double d){
    return (fabs(d) < PRECISION)?0:(d>0?1:-1);
}

//向量点积
double dotdet(double x1,double y1,double x2,double y2){
    return x1*x2 + y1 * y2;
}

//向量叉积
double cross_det(double x1,double y1,double x2,double y2){
    return x1*y2 - x2*y1;
}

//右手螺旋定则，1：a在cd右侧；-1：a在cd左侧；0：三点共线
int cross(POINT &a,POINT &c,POINT &d){
    return cmpzero(cross_det(a.x - c.x,a.y - c.y,d.x - c.x,d.y - c.y));
}

//在cross(a,c,d) == 0的基础上，可判断点a是否在cd内部
int between(POINT &a,POINT &c,POINT &d){
    return cmpzero(dotdet(c.x - a.x,c.y - a.y, d.x - a.x, d.y - a.y)) != 1;
}

//两线段相交情况：0：不想交，1：规范相交，-1：不规范相交（交于端点或重合）
int seg_intersect(POINT &a,POINT &b,POINT &c,POINT &d){
    int a_cd = cross(a,c,d);
    if(a_cd == 0 && between(a,c,d)){return 2;}
    int b_cd = cross(b,c,d);
    if(b_cd == 0 && between(b,c,d)){return 2;}
    int c_ab = cross(c,a,b);
    if(c_ab == 0 && between(c,a,b)){return 2;}
    int d_ab = cross(d,a,b);
    if(d_ab == 0 && between(d,a,b)){return 2;}
    if((a_cd^b_cd) == -2 && (c_ab ^ d_ab) == -2){
        return 1;
    }
    return 0;
}

//使用有向面积法判断点是否在多边形内
int point_in_poly(POLY &p,POINT &pt){
    double s = 0.0;
    for(int i = 0; i < p.n; i++){
        s += fabs(cross_det(p.plist[i].x - pt.x,p.plist[i].y - pt.y,p.plist[(i+1)%p.n].x - pt.x,p.plist[(i+1)%p.n].y - pt.y));
    }
    if(cmpzero(s - p.area) == 0 ){
        return 1;
    }
    return 0;
}

//计算多边形面积
void area(POLY &p){
    double s = p.plist[0].y * (p.plist[p.n - 1].x - p.plist[1].x);
    for(int i = 1; i < p.n; i++){
        s += p.plist[i].y * (p.plist[i - 1].x - p.plist[(i+1)%p.n].x);
    }
    p.area = s;
}

//判断线段是否与多边形相交
int rec_seg_intersect(POLY &p,LINE &l){
    if(point_in_poly(p,l.p1) && point_in_poly(p,l.p2)){return 1;}
    else if(seg_intersect(l.p1,l.p2,p.plist[0],p.plist[1])
            || seg_intersect(l.p1,l.p2,p.plist[1],p.plist[2])
            || seg_intersect(l.p1,l.p2,p.plist[2],p.plist[3])
            || seg_intersect(l.p1,l.p2,p.plist[3],p.plist[0]))
            return 1;
    return 0;
}

int main() {
    int n,m,i,min;
    int T;
    POLY rec;
    LINE l;
    double xleft,ytop,xright,ybottom;
    scanf("%d",&T);
    while(T--){
        scanf("%lf%lf%lf%lf",&l.p1.x,&l.p1.y,&l.p2.x,&l.p2.y);
        scanf("%lf%lf%lf%lf",&xleft,&ytop,&xright,&ybottom);
        if(xleft > xright){swap(xleft,xright);}
        if(ytop < ybottom){swap(ytop,ybottom);}
        rec.n = 4;
        rec.plist[0].x = xleft, rec.plist[0].y = ytop;
        rec.plist[1].x = xleft, rec.plist[1].y = ybottom;
        rec.plist[2].x = xright, rec.plist[2].y = ybottom;
        rec.plist[3].x = xright, rec.plist[3].y = ytop;
        area(rec);
        puts(rec_seg_intersect(rec,l)?"T":"F");
    }
    return 0;
}

参考文章：

http://hi.baidu.com/novosbirsk/item/cbce6f06174e1e16cc34ea13