三角形面积并
cpp
Point get_line_intersection(Point p,Vector v,Point q,Vector w){//两直线的交点
//使用前提，直线必须有交点
//cross(v, w) == 0则两直线平行或者重合
if(!sign(cross(v,w))) return {INF,INF};
Vector u=p-q;
double t=cross(w,u)/cross(v,w);
Point o=p+v*t;
auto on_segment=[&](Point p,Point a,Point b){
return sign(dot(p-a,p-b))<=0;
};
//若判断线段/射线是否相交 还需判断交点是否在线段/射线上
if(!on_segment(o,p,p+v)||!on_segment(o,q,q+w))return {INF,INF};
return o;
}
//-------------三角形面积并(n^3logn)--------------------------
double line_area(double a, int side,vector<vector<Point>> &tr){
vector<Point> q;
for (int i = 0; i < tr.size(); i ++ ){
auto t = tr[i];
if (cmp(t[0].x, a) > 0 || cmp(t[2].x, a) < 0) continue;
if (!cmp(t[0].x, a) && !cmp(t[1].x, a)){
if (side) q.emplace_back(t[0].y, t[1].y);
}
else if (!cmp(t[2].x, a) && !cmp(t[1].x, a)){
if (!side) q.emplace_back(t[2].y, t[1].y);
}
else{
static double d[3];
int u = 0;
for (int j = 0; j < 3; j ++ ){
auto o = get_line_intersection(t[j], t[(j + 1) % 3] - t[j], {a, -INF}, {0,INF * 2});
if (cmp(o.x, INF))d[u++] = o.y;
}
if (u){
sort(d, d + u);
q.emplace_back(d[0], d[u - 1]);
}
}
}
if(!q.size())return 0;
for (int i = 0; i < q.size(); i ++ ){
if (q[i].x > q[i].y)swap(q[i].x, q[i].y);
}
sort(q.begin(),q.end());
double res = 0, st = q[0].x, ed = q[0].y;
for (int i = 1; i < q.size(); i ++ ){
if (q[i].x <= ed) ed = max(ed, q[i].y);
else{
res += ed - st;
st = q[i].x, ed = q[i].y;
}
}
res += ed - st;
return res;
}
double range_area(double a, double b,vector<vector<Point>> &tr){
return (line_area(a, 1, tr) + line_area(b, 0, tr)) * (b - a) / 2;
}
double triangle_union_area(vector<vector<Point>> &tr){
vector<double> xs;
for(int i=0;i<tr.size();i++){
for(int j=0;j<3;j++){
xs.push_back(tr[i][j].x);
}
sort(tr[i].begin(),tr[i].begin()+3);
}
for(int i=0;i<tr.size();i++){
for(int j=i+1;j<tr.size();j++){
for(int x=0;x<3;x++){
for(int y=0;y<3;y++){
auto o=get_line_intersection(tr[i][x],tr[i][(x+1)%3]-tr[i][x],tr[j][y],tr[j][(y+1)%3]-tr[j][y]);
if(cmp(o.x,INF))xs.push_back(o.x);
}
}
}
}
sort(xs.begin(),xs.end());
double res=0;
for(int i=0;i+1<xs.size();i++){
if(cmp(xs[i],xs[i+1]))res+=range_area(xs[i],xs[i+1],tr);
}
return res;
}