计算几何基础整合(Point类) | Bill Yang's Blog

计算几何基础整合(Point类)

本篇专讲计算几何基础,然后贴板子。
本文中用 $\vec v$ 表示向量 $v$,用$\times$表示叉积,$\cdot$ 表示点积。

首先定义Point类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const double eps=1e-8;
int dcmp(double x) {return fabs(x)<=eps?0:x>eps?1:-1;}
struct Point {
double x,y;
Point(double x=0,double y=0):x(x),y(y) {}
Point operator + (const Point &a) {return Point(x+a.x,y+a.y);}
Point operator - (const Point &a) {return Point(a.x-x,a.y-y);} //注意翻转!!
Point operator * (double a) {return Point(x*a,y*a);}
Point operator / (double a) {return Point(x/a,y/a);}
bool operator < (const Point &b) const {return x<b.x||(x==b.x&&y<b.y);}
bool operator == (Point b) {return dcmp(x-b.x)==0&&dcmp(y-b.y)==0;}
double length() {return sqrt(x*x+y*y);}
Point rotate(double rad) {return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));} //逆时针
Point normal(Point a) {return Point(-a.y/a.length(),a.x/a.length());} //长度归一
};
typedef Point Vector; //仅为了写法方便,但意义不同

值得注意的是,在重载减法的时候,为了代码方便将其反过来定义了,这样$a-b$就表示$a\rightarrow b$这个向量。但如果要用到减法时请将它翻转回去。

类中定义了两个操作:

  • 向量旋转
    根据仿射变换,逆时针旋转$\alpha$度时需要执行:
  • 长度归一
    这是方向向量的一种定义方法,向量只有方向没有长度。

然后是叉积点积,夹角以及三角形面积

1
2
3
4
double Cross(const Vector& a,const Vector& b) {return a.x*b.y-b.x*a.y;}
double Dot(Vector a,Vector b) {return a.x*b.x+a.y*b.y;}
double Angle(Vector a,Vector b) {return acos(Dot(a,b)/a.length()/b.length());}
double Area(Point a,Point b,Point c) {return Cross(b-a,c-a);}

判断$p$是否在线段上
通过叉积判断面积是否为$0$,也就是判断是否在直线上。
通过点积判断投影是否小于$0$,也就是判断$p$到线段端点是否同向。

1
bool OnSegment(Point st,Point ed,Point p) {return dcmp(Cross(st-p,ed-p))==0&&dcmp(Dot(st-p,ed-p))<0;}

判断线段是否相交
有两种线段相交的方式。

一种是规范相交,任意三点不共线,如上图的第一、二种情况。
判断这种情况的方法是:
判断A、B点是否在线段$CD$两侧,即计算叉积时异号,同理也需要判断C、D点是否在线段$AB$两侧。

1
bool Segment_Intersection(Point a1,Point a2,Point b1,Point b2) {return dcmp(Cross(a2-a1,b1-a1))*dcmp(Cross(a2-a1,b2-a1))<0&&dcmp(Cross(b2-b1,a1-b1))*dcmp(Cross(b2-b1,a2-b1))<0;}

然后考虑第三种情况,也就是非规范相交,有至少三点共线。
这情况发生时有一个点在其它线段上,判断一下即可。

1
bool _Segment_Intersection(Point a1,Point a2,Point b1,Point b2) {return Segment_Intersection(a1,a2,b1,b2)||OnSegment(a1,a2,b1)||OnSegment(a1,a2,b2)||OnSegment(a1,b1,b2)||OnSegment(a2,b1,b2);}

计算直线交点
需要保证相交,否则会GG。
设直线的参数方程为:$P+t\vec v,Q+t\vec w$。
设交点为$P+t_1\vec v=Q+t_2\vec w$。
列出方程组:

解得:

1
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w) {return P+v*(Cross(P-Q,w)/Cross(v,w));}

点到直线距离
叉积除以长度即可得到高度。

1
double DistanceToLine(Point p,Point a,Point b) {Vector v1=b-a,v2=p-a;return fabs(Cross(v1,v2))/v1.length();}

点到线段距离
判断一下是到两个端点更近,还是到直线更近。

1
2
3
4
5
6
7
double DistanceToSegment(Point p,Point a,Point b) {
if(a==b)return (p-a).length();
Vector v1=b-a,v2=p-a,v3=p-b;
if(dcmp(Dot(v1,v2))<0)return v2.length();
else if(dcmp(Dot(v1,v3))>0)return v3.length();
else return DistanceToLine(p,a,b);
}

多边形面积
三角剖分求面积。

1
2
3
4
5
double Area(int n,Point* P) {
double ans=0;
for(int i=2; i<n; i++)ans+=Area(P[1],P[i],P[i+1]);
return ans/2;
}

本篇文章有用吗?有用还不快点击!
0%