二维计算几何

概念

平面向量的叉积

double cross(Point a1,Point a2,Point b1,Point b2){
    return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}

判断点是否在线段上

bool isOnSeg(Point p,Point A,Point B){
    if(dcmp(cross(p,A,p,B)))return 0;
    return dcmp(min(A.x,B.x)-p.x)<=0&&
           dcmp(p.x-max(A.x,B.x))<=0&&
           dcmp(min(A.y,B.y)-p.y)<=0&&
           dcmp(p.y-max(A.y,B.y))<=0;
}

判断点是否在多边形里

int isInPolygon(Point p,Point* s,int m){
    int wn=0;
    for(int i=1;i<=m;i++){
        if(isOnSeg(p,s[i],s[i+1]))return -1;
        int k=dcmp(cross(s[i],s[i+1],s[i],p));
        int d1=dcmp(s[i].y-p.y);
        int d2=dcmp(s[i+1].y-p.y);
        if(k>0&&d1<=0&&d2>0)wn++;
        if(k<0&&d2<=0&&d1>0)wn--;
    }
    return wn!=0;
}

判断线段是否有公共点

bool isSegsIntersect(Point A,Point B,Point C,Point D){
    int d1=dcmp(cross(A,B,A,C));
    int d2=dcmp(cross(A,B,A,D));
    int d3=dcmp(cross(C,D,C,A));
    int d4=dcmp(cross(C,D,C,B));
    if(d1*d2<0&&d3*d4<0)return 1;
    if(d1==0&&isOnSeg(C,A,B))return 1;
    if(d2==0&&isOnSeg(D,A,B))return 1;
    if(d3==0&&isOnSeg(A,C,D))return 1;
    if(d4==0&&isOnSeg(B,C,D))return 1;
    return 0;
}

凸包

凸包是平面上能包含所有给定点的凸多边形。凸包的周长最小。

Andrew 算法求凸包

将所有点按横坐标排序，首先从横坐标最小的点向右（逆时针）出发，使用一个单调栈来维护下凸壳，然后同理从右向左维护上凸壳。

int Andrew(int n,Point *p,Point *s){
    int m=0;
    sort(p+1,p+n+1,[&](Point a,Point b){
        return a.x<b.x||(a.x==b.x&&a.y<b.y);
    });
    for(int i=1;i<=n;i++){
        while(m>=2&&cross(s[m-1],s[m],s[m],p[i])<=0)m--;
        s[++m]=p[i];
    }
    int k=m;
    for(int i=n-1;i>=1;i--){
        while(m>k&&cross(s[m-1],s[m],s[m],p[i])<=0)m--;
        s[++m]=p[i];
    }
    if(m>1)m--;
    s[m+1]=s[1];
    return m;
}

半平面交