计算几何基础，点、线、面位置关系，模板

😎直线相交：

int lineInter(Line l1,Line l2){//两个直线是否相交 
	if(sgn((l1.s-l1.e)^(l2.s-l2.e))==0){//两直线方向平行
			if(sgn((l1.s-l2.e)^(l1.s-l1.e))==0) return 1; //l2的s点在直线l1上，两直线重合 
			else return 0; //两直线平行 
	}else return 2
}//平行为0，重合为1，相交为2

😎两个线段是否相交：1.x，y轴上两线段投影有重合

2.l2两个端点在l1两侧&&l1两个端点在l2两侧

bool segInter(Seg l1,Seg l2){//两个线段是否相交 
	return
	max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x) &&//x轴上l1的最大的大于l2最小的 
	max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x) &&//x轴上l2最大的大于 l1最小的 //x轴上投影l1和l2有重合 
	max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y) &&//y轴 
	max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y) &&
	sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0 &&//l2两个端点在直线l1的两侧 图1
	sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e))<=0;//图2
}

图1：

图2：

😎直线与线段相交

int lineInterSeg(Line l1,Seg l2){//直线与线段相交 
	if(sgn((l1.s-l1.e)^(l2.s-l2.e))==0){//两直线方向平行
			if(sgn((l1.s-l2.e)^(l1.s-l1.e))==0) return 1; //l1的s点在直线l2上，两直线重合 
			else return 0; //直线与线段平行 ,不相交 
	}else{
		if(sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e))<=0) return 2;//l2两个端点在直线l1的两侧 ,若严格相交去= 
		else return 0;//否则不相交，线段在直线的一侧 
	} 
	 
}//不相交为0，重合为1，相交为2

😎两直线（线段）的交点，必须事先确定两线相交

Point cross(Line a,Line b){//必须确定两个直线是相交的，或者线段 ，本函数不判断相交性 
	Point res=a.s;
	double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));
	res.x+=(e.x-s.x)*t;
	res.y+=(e.y-s.y)*t;
	return res;
}

点是否在线段上

bool OnSeg(Point P,Line L){//点p是否在线l上 
	return
	sgn((L.s-P)^(L.e-P))==0 &&//叉积为0 ，代表的面积为0 
	sgn((P.x-L.s.x)*(P.x-L.e.x))<=0 &&//p的x比一个端点x大，比另一个端点小 
	sgn((P.y-L.s.y)*(P.y-L.e.y))<=0; //P点的x与y应当介于s和e的x与y之间,因为它是线段不是直线 
}

点是否在凸多边形内

//点是否在凸多边形内
//凸n多边形的点按逆时针给出， 
int inConvexPoly(Point a,Point p[],int n){
	for(int i=0;i<n;i++){
		if(sgn((p[i]-a)^(p[(i+1)%n]-a))<0) return -1; //<0,前向量顺时针到后向量，由于点按逆时针给，所以在凸多边形外 
		else if(OnSeg(a,Line(p[i],p[(i+1)%n]))) return 0; //在凸多边形边界上 
	}
	return 1; //在凸多边形内 
}

点是否在多边形内（任意的）：

int inPoly(Point p,Point poly[],int n){//测试点，n边形的点集，n边形 
	int cnt;
	Line ray,side;//ray射线 
	cnt=0; ray.s=p;
	ray.e.y=p.y; 
	ray.e.x=-100000000000.0; //构造一条一点p为起始点的射线 ，射线方向为x负方向 
	for(int i=0;i<n;i++){ //枚举边 
		side.s=poly[i];
		side.e=poly[(i+1)%n];
		if(OnSeg(p,side)) return 0; //在边界上 
		//如果平行轴则不用考虑 
		if(sgn(side.s.y-side.e.y)==0) continue;//测试点在边的端点上 
		if(OnSeg(side.s,ray)){//射线穿过边的逆时针先端点 
			if(sgn(side.s.y-side.e.y)>0) cnt++;//边的先端点在后端点上不相同，即边不与射线平行，因为每次出现这样情况只记入一次，所以>0而不是！=0 
		}
		else if(OnSeg(side.e,ray)){//射线穿过边逆时针的后端点 
			if(sgn(side.e.y-side.s.y)>0) cnt++;//边的后端点在先端点的上 
		}
		else if(inter(ray,side)) cnt++;
	}
	if(cnt%2==1) return 1; //在多边形内 
	return -1; //在多边形外 
}