【计算几何】半平面交

半平面交算法

对于平面上的所有有向边（角度范围​）

• 将向量按照角度排序(atan2(y,x))
• 按顺序扫描所有向量，用双端队列维护双平面交轮廓
  • 只要队尾的两个线和队头的两个线的交点在当前直线的右侧（因为保存左侧），将队尾或者队头删除
• 用直线的参数方程存储直线
• 时间复杂度

int cnt;
struct Line{
    PDD st,ed;
}line[N];
int q[N];
PDD pg[N],ans[N];

int sign(double x){
    if (fabs(x) < eps)    return 0;
    if (x < 0)    return -1;
    return 1;
}

int dcmp(double a,double b){
    if (fabs(a - b) < eps)    return 0;
    if (a < b)    return -1;
    return 1;
}

double get_angle(const Line& a){
    return atan2(a.ed.y - a.st.y,a.ed.x - a.st.x);
}


PDD operator - (PDD a,PDD b){
    return {a.x - b.x,a.y - b.y};
}

double cross(PDD a,PDD b){
    return a.x * b.y - a.y * b.x;
}

double area(PDD a,PDD b,PDD c){
    return cross(b - a,c - a);
}

bool cmp(const Line& a,const Line& b){
    double A = get_angle(a), B = get_angle(b);
    if (!dcmp(A,B))    return sign(area(a.st,a.ed,b.ed)) < 0;
    return A < B;
}

PDD get_line_intersection(PDD p,PDD v,PDD q,PDD w){
    auto u = p - q;
    double t = cross(w,u) / cross(v,w);
    return {p.x + v.x * t,p.y + v.y * t};
}

PDD get_line_intersection(Line a,Line b){
    return get_line_intersection(a.st,a.ed - a.st,b.st,b.ed - b.st);
}

bool on_right(Line& a,Line& b,Line& c){
    auto o = get_line_intersection(b,c);
    return sign(area(a.st,a.ed,o)) <= 0;
}

double half_plane_intersection(){
    sort(line,line + cnt,cmp);
    int head = 0,tail = -1;
    for (int i = 0;i < cnt;++i){
        if (i && !dcmp(get_angle(line[i]),get_angle(line[i-1])))    continue;
        while (head + 1 <= tail && on_right(line[i],line[q[tail - 1]],line[q[tail]]))    tail--;
        while (head + 1 <= tail && on_right(line[i],line[q[head]],line[q[head + 1]]))    head++;
        q[++tail] = i;
    }
    while (head + 1 <= tail && on_right(line[q[head]],line[q[tail - 1]],line[q[tail]])) tail--;
    while (head + 1 <= tail && on_right(line[q[tail]],line[q[head]],line[q[head + 1]])) head++;
}