首页 > 其他分享 >二维计算几何全家桶

二维计算几何全家桶

时间:2024-08-03 20:16:38浏览次数:12  
标签:return Point int double sgn 全家 二维 Vector 几何

快网络赛了但是计算几何还一点不会,所以最近狠狠恶补了一下计算几何的知识,但是由于本人实力有限,暂时还没有学会三维的计算几何,所以本文只介绍二维计算几何中一些比较常用到的知识

符号函数

符号函数是计算几何中经常用到的一个函数,它虽然很简单,但是在帮助我们判断几何中的位置和方向时有着重要的作用

int sgn(double x){
	if(fabs(x) < eps)return 0;
	else return x<0?-1:1;
}

点和向量

定义二维平面的点

struct Point{
	double x,y;
	Point(){};
	Point(double x,double y):x(x),y(y){}
};

用库函数hypot()计算直角三角形的斜边长

double Distance(Point A,Point B){return hypot(A.x-B.x,A.y-B.y);}

计算两点之间的距离

double Dist(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}

向量的基本运算

Point operator + (Point B){return Point(x+B.x,y+B.y);}//向量的加法  
Point operator - (Point B){return Point(x-B.x,y-B.y);}//向量的减法
Point operator * (double k){return Point(x*k,y*k);}//向量与实数相乘
Point operator / (double k){return Point(x/k,y/k);}//向量与实数相除
Point operator == (Point B){return sgn(x-B.x) == 0&&sgn(y-B.y) == 0;}//向量相等

求向量A与B的点积

double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}

求向量A的长度

double Len(Vector A){return sqrt(Dot(A,A));}

由于在开根号的时候可能会造成精度的丢失,所以我们更经常去求向量A长度的平方

double Len2(Vector A){return Dot(A,A);}

求向量A与B的夹角

double Angle(Vector A,Vector B){return acos(Dot(A,B)/Len(A)/Len(B));}

求向量A与B的叉积

叉积有一个很重要的作用就是帮助我们判断位置关系,若 \(A×B>0\),B在A的逆时针方向;若\(A×B<0\),B在A的顺时针方向;若\(A×B=0\),B与A共线

double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

利用叉积我们也可以计算两个向量构成的平行四边形的有向面积

double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}

利用叉积,我们也可以检查两个向量是否平行或重合

bool Parallel(Vector A,Vector B){return sgn(Cross(A,B)) == 0;}//返回true表示平行或重合

向量A逆时针旋转角度rad

Vector Rotate(Vector A,double rad){
	return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}

求单位法向量,即逆时针旋转90°,然后取单位值

Vector Normal(Vector A){return Vector(-A.y/Len(A),A.x/Len(A));}

直线

直线的表示

struct Line{
	Point p1,p2;
	Line(){}
	Line(Point p1,Point p2):p1(p1),p2(p2){}
	//根据一个点和倾斜角确定直线
	Line(Point p,double angle){
		p1=p;
		if(sgn(angle-pi/2) == 0){p2 = (p1 + Point(0,1));}
		else{p2 = (p1 + Point(1,tan(angle)));}
	}
	//ax+by+c=0
	Line(double a,double b,double c){
		if(sgn(a) == 0){
			p1 = Point(0,-c/b);
			p2 = Point(1,-c/b);
		}
		else if(sgn(b) == 0){
			p1 = Point(-c/a,0);
			p2 = Point(-c/a,1);
		}
		else{
			p1 = Point(0,-c/b);
			p2 = Point(1,(-c-a)/b);
		}
	}
}

线段的表示

可以用两个点表示线段,起点P1,终点P2

typedef Line Segment;

点和直线的位置关系

int Point_Line_relation(Point p,Line v){
	int c = sgn(Cross(p-v.p1,v-p2-v.p1));
	if(c<0)return 1;//1:p在v的左侧
	if(c>0)return 2;//2:p在v的右侧
	return 0;//0:p在v上
}

点和线段的位置关系

bool Point_on_seg(Point p,Line v){//0:点p不在线段v上;1:点p在线段v上
	return sgn(Cross(p-v.p1,v.p2-v.p1)) == 0&&sgn(Dot(p-v.p1,p-v.p2) <= 0);
}

点到直线的距离

double Dis_point_line(Point p,Line v){
	return fabs(Cross(p-v.p1,v.p2-v.p1))/Distance(v.p1,v.p2);
}

点在直线上的投影

Point Point_line_proj(Point p,Line v){
	double k = Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
	return v.p1+(v.p2-v.p1)*k;
}

点关于直线的对称点

Point Point_line_symmetry(Point p,Line v){
	Point q = Point_line_proj(p,v);
		return Point(2*q.x-p.x,2*q.y-p.y);
}

点到线段的距离

double Dis_point_seg(Point p,Segment v){
	if(sgn(Dot(p-v.p1,v.p2-v.p1) < 0) || sgn(Dot(p-v.p2,v.p1-v.p2)) < 0)
		return min(Dsitance(p,v.p1),Distance(p,v.p2));
		return Dis_point_line(p,v);
}

两条直线的位置关系

int Line_relation(Point p,Segment v){
	if(sgn(Cross(v1.p2-v1.p1,v2.p2-v2.p1)) == 0){
		if(Point_line_relation(v1.p1,v2) == 0)return 1;//1:重合
		else return 0;//0:平行
	}
	return 2;//2:相交
}

两条直线的交点

Point Cross_point(Point a,Point b,Point c,Point d){//线段1:ab,线段2:cd
		double s1 = Cross(b-a,c-a);
		double s2 = Cross(b-a,d-a);
		return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}

判断两条线段是否相交

bool Cross_segment(Point a,Point b,Point c,Point d){
	double c1 = Cross(b-a,c-a),c2 = Cross(b-a,d-a);
	double d1 = Cross(d-c,a-c),d2 = Cross(d-c,b-c);
	return sgn(c1)*sgn(c2) < 0 && sgn(d1)*sgn(d2) < 0;
}

多边形

判断点和多边形的位置关系

int Point_in_polygon(Point pt,Point *p,int n){//点pt,多边形Point *p
	for(int i = 0;i < n;i++){
		if(p[i] == pt)return 3;//3:点在多边形的顶点上
	}
	for(int i = 0;i < n;i++){
		Line v = Line(p[i],p[(i+1)%n]);
		if(Point_on_seg(pt,v))return 2;//2:在多边形的边上
	}
	int num = 0;
	for(int i = 0;i < n;i++){
		int j = (i+1)%n;
		int c = sgn(Cross(pt-p[j],p[i]=p[j]));
		int u = sgn(p[i].y-pt.y);
		int v = sgn(p[j].y-pt.y);
		if(c > 0 && u < 0 && v >= 0)num++;
		if(c < 0 && u >= 0 && v < 0)num--;
	}
	return num != 0;//1:点在内部;0:点在外部
}

多边形的面积

double Polygon_area(Point *p,int n){
	double area = 0;
	for(int i = 0;i < n;i++)
		area += Cross(p[i],p[i+1]%n);
	return area/2;
}

多边形的重心

Point Polygon_center(Point *p,int n){
	Point ans(0,0);
	if(Polygon_area(p,n) == 0)return ans;
	for(int i = 0;i < n;i++)
		ans = ans+(p[i] + p[(i+1)%n])*Cross(p[i],p[(i+1)%n]);
	return ans/Polygon_area(p,n)/6;
}

凸包

struct node{
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
	Point operator + (Point B){return Point(x+B.x,y+B.y);}
	Point operator - (Point B){return Point(x-B.x,y-B.y);}
	Point operator == (Point B){return sgn(x-B.x) == 0 && sgn(y-B.y) == 0;}
	bool operator < (Point B){
		return sgn(x-B.x) < 0 ||(sgn(x-B.x) == 0 && sgn(y-B.y) < 0);}
};
typedef Point Vector;
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double Distance(Point A,Point B){return hypot(A.x-B.x,A.y-B.y);}
//Convex_hull 函数求凸包,凸包顶点放在ch中,返回值是凸包的顶点数
int Convex_hull(Point *p,int n,Point *ch){
	n=unique(p,p+n)-p;//去掉重复点
	sort(p,p+n);//对点排序:按x从小到大排序,如果x相同按y排序
	int v=0;
	//求下凸包,如果p[i]是右拐弯的,这个点就不在凸包上,退回
	for(int i = 0;i < n;i++){
		while(v > 1 && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1])) <= 0)
			v--;
		ch[v++]=p[i];
	}
	int j=v;
	//求上凸包
	for(int i= n-2 ;i >= 0;i--){
		while(v > j && sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1])) <= 0)
			v--;
		ch[v++]=p[i];
	}
	if(n>1)v--;
	return v;
	}

平面最近点对

struct Point{double x,y;};
double Distance(Point A,Point B){return hypot(A.x-B.x,A.y-B.y);}
bool cmpxy(Point A,Point B){return sgn(A.x-B.x)<0||(sgn(A.x-B.x)==0&&sgn(A.y-B.y)<0);}//排序:先对x坐标排序,再对y坐标排序
bool cmpy(Point A,Point B){return sgn(A.y-B.y)<0;}
Point p[maxn],tmp_p[maxn];
double Closest_Pair(int left,int right){
	double dis=INF;
	if(left==right)return dis;//只剩一个点
	if(left+1==right)return Distance(p[left],p[right]);//只剩两个点
	int mid=(left+right)/2;
	double d1=Closest_Pair(left,mid);//求s1内的最近点对
	double d2=Closest_Pair(mid+1,right);//求s2内的最近点对
	dis=min(d1,d2);
	int k=0;
	for(int i=left;i<=right;i++)//在s1和s2中间附近找可能的最小点对
		if(fabs(p[mid].x-p[i].x)<=dis)//按x坐标查找
			tmp_p[k++]=p[i];
		sort(tmp_p,tmp_p+k,cmpy);//按y坐标排序,用于剪枝,这里不能按x坐标排序
		for(int i=0;i<k;i++)
			for(int j=i+1;j<k;j++){
				if(tmp_p[j].y-tmp_p[i].y>=dis)break;//剪枝
				dis=min(dis,Distance(tmp_p[i],tmp_p[j]));
			}
	return dis;//返回最小距离
	}

旋转卡壳

struct Point{
	double x,y;
	Point(double x = 0,double y = 0):x(x),y(y){}
}point[MAXN]; 
typedef Point Vector; 
	Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);} 
	Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);} 
	Vector operator * (Vector A,double x) {return Vector(A.x*x,A.y*x);} 
	Vector operator / (Vector A,double x) {return Vector(A.x/x,A.y/x);}
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
double Distance(Vector A,Vector B){return hypot(A.x-B.x,A.y-B.y);} 
bool cmp(const Point &x,const Point &y) { if(x.x < y.x || x.x == y.x && x.y < y.y) return true;else return false;}
bool check(Point A,Point B,Point C)
{
	Vector u = B-A,v = C-B;
	if(Cross(u,v) < 0) return true;
	else return false;
}
double Area(Point A,Point B,Point C)
{
	return Cross(B-A,C-A)/2;
}
inline void Scan1(int N)
{
	top1 = top1+1;
	stk1[top1] = top1;
	top1 = top1+1;
	stk1[top1] = top1;
	for(int i = 3;i <= N;i++)
	{
		top1 = top1+1;
		stk1[top1] = i;
		while(check(point[stk1[top1-2]],point[stk1[top1-1]],point[stk1[top1]]) == false && top1 > 2) 
		{
			stk1[top1-1] = stk1[top1];
			top1 = top1-1;
	    }
	}
}
 
inline void Scan2(int N)
{
	top2 = top2+1;
	stk2[top2] = N;
	top2 = top2+1;
	stk2[top2] = N-1;
	for(int i = N-2;i >= 1;i--)
	{
		top2 = top2+1;
		stk2[top2] = i;
		while(check(point[stk2[top2-2]],point[stk2[top2-1]],point[stk2[top2]]) == false && top2 > 2) 
		{
			stk2[top2-1] = stk2[top2];
			top2 = top2-1;
	    }
	}
}

double Convex_Hull_Diameter{
	sort(point+1,point+N+1,cmp);
	memset(stk1,0,sizeof(stk1));
	top1 = 0;
    Scan1(N);
	memset(stk2,0,sizeof(stk2));
	top2 = 0;
	Scan2(N);
	for(int i = 1;i <= top1;i++)
	{
		top = top+1;
		stk[top] = stk1[i];
	}
	for(int i = 2;i <= top2;i++)
	{
		top = top+1;
		stk[top] = stk2[i];
	}
	double ans = 0;
	stk[top + 1] = stk[1],num = 3;
	for(int i = 1;i <= top;i++)
	{
		ans = max(ans,dis(point[stk[i]],point[stk[i+1]]));
		while(Area(point[stk[i]],point[stk[i+1]],point[stk[num]]) 
		    < Area(point[stk[i]],point[stk[i+1]],point[stk[num+1]]))
		    {
		    	num++;
		    	if(num == top+1) num = 1;
			}
		ans = max(ans,max(dis(point[stk[i]],point[stk[num]]),dis(point[stk[i+1]],point[stk[num]])));
	}
	return ans;
	}

半平面的表示

struct Line{
	Point p;//直线上的一个点
	Vector V;//方向向量,它的左边是半平面
	double ang;//极角,从x正半轴旋转到v的角度
	Line(){};
	Line(Point p,Vector v):p(p),v(v){ang = atan2(v.y,v.x);}
	bool operator < (Line &L){return ang < L.ang;}//用于排序
};  

半平面交

struct Point(){
	double x,y;
	Point(){};
	Point(double x,double y):x(x),y(y){};
	Point operator + (Point B){return Point(x + B.x,y + B.y);}
	Point operator - (Point B){return Point(x - B.x,y - B.y);}
	Point operator * (double k){return Point(x*k,y*k);}
};
typedef Point Vector;
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
struct Line{
	Point p;
	Vector v;
	double ang;
	Line(){};
	Line(Point p,Vector v):p(p),v(v){ang = atan2(v.y,v.x);}
	bool operator < (Line &L){return ang < L.ang;}
};
bool OnLeft(Line L,Point p){return sgn(Cross(L.v,p-L.p) > 0);}
//点p在线L的左边,即点p在线L的外面
Point Cross_point(Line a,Line b){//两直线交点
	Vector u = a.p-b.p;
	double t = Cross(b.v,u)/Cross(a.v,b.v);
	return a.p+a.v*t;
}
vector<Point> HPI(vector<Line>L){//求半平面交,返回凸多边形
	int n = L.size();
	sort(L.begin(),L.end());
	int first,last;//指向双端队列的第一个元素和最后一个元素
	vector<Point>p(n)//两个相邻的半平面的交点
	vector<Line>q(n);//双端队列
	vector<Point>ans//半平面交形成的凸包
	q[first = last = 0] = L[0];
	for(int i = 1;i < n;i++){
		//删除尾部的半平面
		while(first < last && !OnLeft(L[i],p[last-1]))last--;
		//删除首部的半平面
		while(first < last && !OnLeft(L[i],p[first]))first++;
		q[++last] = L[i];//将当前的半平面加入双端队列尾部
		//极角相同的两个半平面,保留左边
		if(fabs(Cross(q[last].v,q[last-1].v)) < eps){
			last--;
			if(OnLeft(q[last],L[i].p))q[last]=L[i];
		}
		//计算队列尾部半平面交点
		if(first < last)p[last-1] = Cross_point(q[last-1],q[last]);
	}
	//删除队尾无用的半平面
	while(first < last && !OnLeft(q[first],p[last-1]))last--;
	if(last-first <= 1)return ans;//空集
	p[last] = Cross_point(q[last],q[first]);//计算队列首尾部的交点
	for(int i = first;i <= last ;i++)ans.push_back(p[i]);//复制
	return ans;//返回凸多边形
	}

圆的定义

struct Circle{
	Point c;//圆心
	double r//半径
	Circle(){}
	Circle(Point c,double r):c(c),r(r){}
	Circle(double x,double y,double _r){c = Point(x,y);r = _r;}
};

点和圆的位置关系

int Point_circle_relation(Point p,Circle C){
	double dst = Distance(p,C.c);
	if(sgn(dst - C.r) < 0)return 0;//0:点在圆内
	if(sgn(dst - C.r) == 0)return 1;//1:点在圆上
	return 2;//2:点在圆外
}

直线和圆的位置关系

int Line_circle_relation(Line v,Circle C){
	double dst = Dis_point_line(C.c,v);
	if(sgn(dst - C.r) < 0)return 0;//0:直线和圆相交
	if(sgn(dst - C.r) == 0)return 1;//1:直线和圆相切
	return 2;//2:直线在圆外
}

线段和圆的位置关系

int Seg_circle_relation(Segment v,Circle C){
	double dst = Dis_point_seg(C.c,v);
	if(sgn(dst - C.r) < 0)return 0;//0:线段在圆内
	if(sgn(dst - C.r) == 0)return 1;//1:线段与圆相切
	return 2;//2:线段在圆外
}

直线和圆的交点

//pa和pb是交点,返回值是交点个数
int Line_cross_circle(Line v,Circle C,Point &pa,Point &pb){
	if(Line_circle_relation(v,C) == 2)return 0;//无交点
	Point q = Point_line_proj(C.c,v);//圆心在直线上的投影点
	double d = Dis_point_line(C.c,v);//圆心到直线的距离
	double k = sqrt(C.r*C.r - d*d);
	if(sgn(k) == 0){
		pa = q,pb = q;return 1;//一个交点,直线和圆相切
	}
	Point n =(v.p2 - v.p1)/Len(v.p2 - v.p1);//单位向量
	pa = q + n*k;pb = q - n*k;
	return 2;//两个交点
}

最小圆覆盖

struct Point{double x,y;};
double Distance(Point A,Point B){return hyhot(A.x - B.x,A.y - B.y);}
Point circle_center(const Point a,const Point b,const Point c){
	Point center;
	double a1 = b.x - a.x,b1 = b.y - a.y,c1 = (a1*a1 + b1*b1)/2;
	double a2 = c.x - a.x,b2 = c.y - a.y,c2 = (a2*a2 + b2*b2)/2;
	double d = a1*b2 - a2*b1;
	center.x = a.x + (c1*b2 - c2*b1)/d;
	center.y = a.y + (a1*c2 - a2*c1)/d;
	return center;
}
void min_cover_circle(Point *p,int n,Point &c,double &r){
	random_shuffle(p,p + n);//随机函数,打乱所有点
	c = p[0];r = 0;//从第一个点p[0]开始,圆心为p[0],半径为0
	for(int i = 1;i < n;i++){
		if(sgn(Distance(p[i],c) - r) > 0){//点p[i]在圆外部
		c = p[i]; r = 0;//重新设置圆心为p[i],半径为0
		for(int j = 0;j < i;j++){//重新检查前面所有点
			if(sgn(Distance(p[j],c)-r) > 0){//两点定圆
			c.x = (p[i].x + p[j].x)/2;
			c.y = (p[i].y + p[j].y)/2;
			r = Distance(p[j],c);
			for(int k = 0;k < j;k++){
				if(sgn(Distance(p[k],c) - r) > 0){
					c = circle_center(p[i],p[j],p[k]);
					r = Distance(p[i],c);
					}
				}
			}
		}
	}
}

以上是二维计算几何中经常会用到的一些模板,当然计算几何问题一直是算法竞赛中的难点,只有理解背后求解的原理并且勤加练习才能更好地掌握这类题目

标签:return,Point,int,double,sgn,全家,二维,Vector,几何
From: https://www.cnblogs.com/isletfall/p/18340980

相关文章

  • uniapp__微信小程序实现二维码的生成
    uniapp__微信小程序实现生成二维码项目实战中比较常见,方便下次使用文章目录       一、插件地址?使用插件?       二、生成二维码?       三、定制封装二维码?       三、定制封装二维码?一、插件地址?使用......
  • 二维字符型数组和函数
    二维字符型数组chara[5][10]可以存储最大长度为为10的,5个字符串;按行初始化:a[5][10]={“hello”,“world“,“who”,“are”,“you”} chars[3][10]={{"hello"},{"world"},{"english"}};   gets(s[0]);//s[0]就是第0行这个一维字符型数组的数组名    sca......
  • 字符串相关函数、二维数组-
    目录strcpy--字符串复制函数strcat--字符串拼接函数strcmp--字符串对比函数字符串相关函数:二维数组初始化:strcpy--字符串复制函数char*strcpy(char*dest,constchar*src);功能:  将src中字符串拷贝到dest中 用法: strcpy(dest,src);//dest是一个字......
  • 重头开始嵌入式第八天(字符串,二维数组)
    今天继续介绍字符数组以下是一些常见的C语言字符串处理函数的介绍、函数本体、返回值、用法及实现示例: 以下是 puts 和 gets 函数的介绍、函数本体、返回值、用法及实现示例:字符处理函数puts() 函数-函数意思:将字符串输出到标准输出(通常是屏幕)并换行-函数......
  • [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包
    凸包,顾名思义,就是凸多边形包围,具体定义见OI-wiki(既是周长最小也是面积最小)有Graham算法和Andrew算法,后者精度更高常数更小(因为不涉及求角度)Andrew算法:1.将点排序(横坐标为第一关键字,纵坐标为第二关键字)2.从左到右维护上半部分,再从右到左维护下半部分。具体见OI-wiki。最后说的......
  • 请用二维数组输出如下图形 0 0 0 0 0 0 ,0 0 1 0 0 0 , 0 2 0 3 0 0 ,0 0 0 0 0 0
    1publicclassshuzu10{2//编写一个main方法3publicstaticvoidmain(String[]args){4/*5请用二维数组输出如下图形600000070010008020300900000010*/11......
  • JAVA程序设计——二维小游戏制作
    二维小游戏制作一、课题内容和要求1.课题内容:(1)学生需要针对游戏类应用软件(如数独,扫雷,飞机大战,贪食蛇,青蛙过河等,鼓励自己设计开发游戏)的开发,使用互联网信息检索工具,查找和学习游戏类软件开发相关理论,分析和研究开放源代码;选择合适的JAVA开发工具完成软件项目的创建,代码编写......
  • 二维数组下载为excel(导出)
    /*导出*/ consts2ab=function(s){ constbuf=newArrayBuffer(s.length); constview=newUint8Array(buf); for(leti=0;i<s.length;i++)view[i]=s.charCodeAt(i)&0xFF; returnbuf; } constexportClick=asyncfunction(){ //多个组数据......
  • 高效便捷的二维码生成与分享新体验
    在数字化时代,信息的传递与分享变得尤为重要。无论是商务文件、个人文档,还是活动宣传、产品推广,都需要一种高效、便捷的方式来进行信息的展示与分享。易易二维码,作为一款集多WPS、Office文件在线预览、二维码设计、二维码在线报名、网址、图文、文件转二维码以及二维码浏览记录导出......
  • 在绘图破折号地图框中切换几何图层
    我使用下面的帖子在plotlymapbox上绘制maki符号。PlotlyMapbox标记未渲染(圆圈除外)importdashfromdashimportDash,dcc,html,Input,Outputimportdash_bootstrap_componentsasdbcimportplotly.expressaspximportplotly.graph_objsasgoimportnum......