计算几何常用函数

const double eps=1e-9;//精度
const int INF=1<<29;
const double PI=acos(-1.0);
int dcmp(double x){//判断double等于0或。。。if(fabs(x)0) return tempa-tempb;else return tempa-tempb+2*PI;
}
Vector Rotate(Vector a,double rad){//向量旋转rad弧度return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}
Vector Normal(Vector a){//计算单位法线double L=Length(a);return Vector(-a.y/L,a.x/L);
}
Point GetLineProjection(Point p,Point a,Point b){//点在直线上的投影Vector v=b-a;return a+v*(Dot(v,p-a)/Dot(v,v));
}
Point GetLineIntersection(Point p,Vector v,Point q,Vector w){//求直线交点 有唯一交点时可用Vector u=p-q;double t=Cross(w,u)/Cross(v,w);return p+v*t;
}
int ConvexHull(Point* p,int n,Point* ch){//计算凸包sort(p,p+n);int m=0;for(int i=0;i1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;ch[m++]=p[i];}int k=m;for(int i=n-2;i>=0;i--){while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;ch[m++]=p[i];}if(n>0) m--;return m;
}
double Heron(double a,double b,double c){//海伦公式double p=(a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));
}
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){//线段规范相交判定double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1);double c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
double CutConvex(const int n,Point* poly, const Point a,const Point b, vector result[3]){//有向直线a b 切割凸多边形vector points;Point p;Point p1=a,p2=b;int cur,pre;result[0].clear();result[1].clear();result[2].clear();if(n==0) return 0;double tempcross;tempcross=Cross(p2-p1,poly[0]-p1);if(dcmp(tempcross)==0) pre=cur=2;else if(tempcross>0) pre=cur=0;else pre=cur=1;for(int i=0;i0) cur=0;else cur=1;if(cur==pre){result[cur].push_back(poly[(i+1)%n]);}else{p1=poly[i];p2=poly[(i+1)%n];p=GetLineIntersection(p1,p2-p1,a,b-a);points.push_back(p);result[pre].push_back(p);result[cur].push_back(p);result[cur].push_back(poly[(i+1)%n]);pre=cur;}}sort(points.begin(),points.end());if(points.size()<2){return 0;}else{return Length(points.front()-points.back());}
}
double DistanceToSegment(Point p,Segment s){//点到线段的距离if(s.a==s.b) return Length(p-s.a);Vector v1=s.b-s.a,v2=p-s.a,v3=p-s.b;if(dcmp(Dot(v1,v2))<0) return Length(v2);else if(dcmp(Dot(v1,v3))>0) return Length(v3);else return fabs(Cross(v1,v2))/Length(v1);
}
bool isPointOnSegment(Point p,Segment s){//点在线段上return dcmp(DistanceToSegment(p,s))==0;
}
int isPointInPolygon(Point p, Point* poly,int n){//点与多边形的位置关系int wn=0;for(int i=0;i0&&d1<=0&&d2>0)wn++;if(k<0&&d2<=0&&d1>0)wn--;}if(wn) return 1;//点在内部else return 0;//点在外部
}
double PolygonArea(vector p){//多边形有向面积double area=0;int n=p.size();for(int i=1;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！