半平面交

傷城~ 2022-06-10 11:28 242阅读 0赞

半平面是指平面上的一条直线及其一侧的部分，半平面交则是用来求解多边形内核的一种方法。多边形的核指的就是该多边形内部的一个点集，该点集中任意一点与多边形边界上一点的连线都处于这个多边形内部。通俗地说，就是一个在一个房子里面放一个摄像头，能将所有的地方监视到的放摄像头的地点的集合即为多边形的核。经常会遇到让你判定一个多边形是否有核的问题。

http://blog.csdn.net/accry/article/details/6070621这个文章解释很好。

半平面交的模板

struct POINT
    {
    	double x;
    	double y;
    	POINT(double a = 0, double b = 0) { x = a; y = b; } //constructor 
    };
    
    /*半平面相交（直线切割多边形）（点标号从1开始）*/
    POINT points[MAXN], p[MAXN], q[MAXN];
    int n;
    double r;
    int cCnt, curCnt;
    inline void getline(POINT x, POINT y, double &a, double &b, double &c) {
    	a = y.y - x.y;
    	b = x.x - y.x;
    	c = y.x * x.y - x.x * y.y;
    }
    inline void initial() {
    	for (int i = 1; i <= n; ++i)p[i] = points[i];
    	p[n + 1] = p[1];
    	p[0] = p[n];
    	cCnt = n;
    }
    inline POINT intersect(POINT x, POINT y, double a, double b, double c) {
    	double u = fabs(a * x.x + b * x.y + c);
    	double v = fabs(a * y.x + b * y.y + c);
    	return POINT((x.x * v + y.x * u) / (u + v), (x.y * v + y.y * u) / (u + v));
    }
    inline void cut(double a, double b, double c) {
    	curCnt = 0;
    	for (int i = 1; i <= cCnt; ++i) {
    		if (a*p[i].x + b*p[i].y + c >= eps)q[++curCnt] = p[i];
    		else {
    			if (a*p[i - 1].x + b*p[i - 1].y + c > eps) {
    				q[++curCnt] = intersect(p[i], p[i - 1], a, b, c);
    			}
    			if (a*p[i + 1].x + b*p[i + 1].y + c > eps) {
    				q[++curCnt] = intersect(p[i], p[i + 1], a, b, c);
    			}
    		}
    	}
    	for (int i = 1; i <= curCnt; ++i)p[i] = q[i];
    	p[curCnt + 1] = q[1]; p[0] = p[curCnt];
    	cCnt = curCnt;
    }
    inline void solve() {
    	//注意：默认点是顺时针，如果题目不是顺时针，规整化方向  
    	initial();
    	for (int i = 1; i <= n; ++i) {
    		double a, b, c;
    		getline(points[i], points[i + 1], a, b, c);
    		cut(a, b, c);
    	}
    	/*
    	如果要向内推进r，用该部分代替上个函数
    	for(int i = 1; i <= n; ++i){
    	Point ta, tb, tt;
    	tt.x = points[i+1].y - points[i].y;
    	tt.y = points[i].x - points[i+1].x;
    	double k = r / sqrt(tt.x * tt.x + tt.y * tt.y);
    	tt.x = tt.x * k;
    	tt.y = tt.y * k;
    	ta.x = points[i].x + tt.x;
    	ta.y = points[i].y + tt.y;
    	tb.x = points[i+1].x + tt.x;
    	tb.y = points[i+1].y + tt.y;
    	double a,b,c;
    	getline(ta,tb,a,b,c);
    	cut(a,b,c);
    	}
    	*/
    	//多边形核的面积  
    	double area = 0;
    	for (int i = 1; i <= curCnt; ++i)
    		area += p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;
    	area = fabs(area / 2.0);
    	//此时cCnt为最终切割得到的多边形的顶点数，p为存放顶点的数组  
    }
    inline void GuiZhengHua() {
    	//规整化方向，逆时针变顺时针，顺时针变逆时针  
    	for (int i = 1; i < (n + 1) / 2; i++)
    		swap(points[i], points[n - i]);//头文件加iostream  
    }
    inline void init() {
    	for (int i = 1; i <= n; ++i)
    		scanf("%lf%lf", &points[i].x, &points[i].y);
    	points[n + 1] = points[1];
    }