二维几何基础

在几何中,向量是一个炒鸡重要的东西,像空气对于人,水对于鱼……QAQ
在这里就不详细介绍向量了,大家在高中数学中会学到,数学毒瘤,貌似信息也是哈哈哈


下面是他们的常用定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct point
{
double x,y;
point(double x=0,double y=0) :x(x),y(y){}//构造函数,方便代码编写
};

typedef point vector; //从程序实现上,vector只是point的别名
//向量+向量=向量, 点+向量=点
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 p){return vector(a.x*p,a.y*p);}
//向量/数=向量
vector operator / (vector a,double p){return vector(a.x/p,a.y/p);}

bool operator < (const point& a,const point& b)
{
return a.x<b.x||(a.x==b.x && a.y<b.y);
}

const double eps=1e-10;
int dcmp(double x)
{
if(fabs(x)<eps) return 0;else return x<0 ? -1:1;
}

bool operator == (const point& a,const point& b)
{
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y) == 0;
}

注意上面的“相等”函数用到了“三态函数”dcmp,减少了精度问题。另外,向量有一个所谓的极角,即从x轴正半轴旋转到该方向所需要的角度。C标准库里的atan2函数就是用来求极角的,如向量(x,y)的极角就是atan2(y,x)(单位:弧度)。

#基本运算


点积:两个向量v和w的点积等于二者长度的乘积再乘上他们夹角的余弦,即$ab=|a||b|*cos\theta$
余弦是偶函数,因此点积满足交换律。如果两向量垂直,点积等于0。不难推导出:在平面坐标系下,两个向量OA和OB的点积等于$x_Ax_B+y_Ay_B$。
下面是点积计算方法,以及利用点积计算向量长度和夹角的函数。

1
2
3
double Dot(vector A, vector B){return A.x*B.x+A.y*B.y}
double Lenth(vector A){return sqrt(Dot(A,A));}
double Angle(vector A, vector B) {return acos(Dot(A,B)/Lenth(A)/Lenth(B));}

叉积。简单的说,两个向量v和w的叉积等于v和w组成的三角形的有向面积的两倍。什么叫“有向面积”呢?

这里写图片描述
顺着第一个向量v看,如果w在左边,那么v和w的叉积大于0,否则小于0。如果两个向量共线(方向相同),那么叉积等于0(三角形退化成线段)。不难发现,叉积不满足交换律。事实上,cross(v,w)=-cross(w,v),两个向量OA和OB的叉积等于$x_Ay_B-x_By_A$。代码如下:

1
2
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);}

两个向量的位置关系。把叉积和点积组合到一起,我们可以更细致地判断两个向量的位置关系。
向量旋转。向量可以绕起点旋转,公式为$x’=xcosa-ysina,y’=xsina+ycosa$其中a为逆时针旋转的角。代码如下:

1
2
3
4
5
//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°以后把长度归一化。

1
2
3
4
5
6
//调用前请确保A不是零向量
vector Normal(vector A)
{
double L=Lenth(A);
return vector(-A.y/L,A.x/L);
}