计算几何(二)——点与向量
点
二维平面下的点保存横纵坐标即可
struct Point{
double x,y;
Point(double a=0,double b=0):x(a),y(b){}
//运算符重载
};
向量
向量在数学意义上是矢量,即有方向的量,但是计算机并不能存储方向,因此还是要用坐标表示,但是因为一些函数是基于向量计算的,与点没有关系,为了区别开我们重定义向量名Vector
#define Point Vector //typedef Point Vector
常用运算符
加法运算符
加法一般用于向量
Vector operator + (Vector A,Vector B){
return Vector(A.x+B.x,A.y+B.y);
}
减法运算符
两个点作差将得到一个向量。向量之间的减法则是高中那句话“共起点,指被减”,这里的起点在二维坐标系中指原点。向量A-B得到向量BA
Vector operator - (Point A,Point B){
return Vector(A.x-B.x,A.y-B.y);
}
乘法运算符
1.如果是数乘,向量与实数相乘得到等比例缩放的向量
Vector operator * (Vector A,double d){
return Vector(A.x*d,A.y*d);
}
2.如果是向量之间的乘法,那就是向量的数量积
若a=(x1,y1),b=(x2,y2),则a·b=x1·x2 + y1·y2
几何意义:数量积a·b等于 |a| 与b在a的方向上的投影 |b|·cosθ 的乘积,即 a⋅b=∣a∣∣b∣cosθ
那么我们还可以用向量数量积求向量之间的夹角及判断锐角直角钝角,在后面有很大的用处
double operator * (Vector A,Vector B){
return A.x*B.x+A.y*B.y;
}
除法运算符
向量与实数相除得到等比例缩放的向量
Vector operator / (Vector A,double d){
return Vector(A.x/d,A.y/d);
}
^ 运算符——向量积(叉积)
向量积c = a×b = |a|·|b|·sin<a,b>,若a=(x1,y1),b=(x2,y2),则a×b=x1·y2 - x2·y1
a向量与b向量的向量积c的方向与这两个向量所在平面垂直,且遵守右手定则(当右手的四指从a以不超过180度的转角转向b时,竖起的大拇指指向是c的方向)
几何意义:向量积的几何意义是两向量的围成平行四边形的面积
double operator ^ (Vector A,Vector B){
return A.x*B.y-A.y*B.x;
}
< 运算符
用于对点集排序
bool operator < (const Point& a,const Point &b) const {
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
== 运算符
bool operator == (const Point& a, const Point& b) const {
if(dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0)
return true;
return false;
}
常用函数
求模长
double dis(Vector A){
return sqrt(A*A);
}
求模长的平方
double sqrDis(Vector A){
return A*A;
}
计算两向量夹角
由a⋅b=∣a∣∣b∣cosθ,那么cosθ=a⋅b/∣a|·∣b∣,再由反余弦函数即可得到θ,注意是弧度制下的夹角
double angle(Vector A,Vector B){
return acos(A*B/dis(A)/dis(B));
}
计算向量逆时针旋转后的向量
x′ = x·cosα−y·sinα
y′ = x·sinα+y·cosα
Vector rotate(Vector A,double 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=dis(A);
return Vector(-A.y/L, A.x/L);
}
ToLeftTest
判断折线 bc 是不是向 ab 的逆时针方向(左边)转向。凸包构造时将会频繁用到此公式
bool ToLeftTest(Point a, Point b, Point c){
return (b-a)^(c-b) > 0;
}
简单模板
#define Point Vector
const double PI=acos(-1.0);
const double eps=1e-8;
inline int dcmp(double d){ //浮点数和0比较
if(fabs(d)<eps) return 0;
return d>0?1:-1;
}
inline int cmp(double x,double y){ //x>y返回1,x=y返回0,x<y返回-1
return dcmp(x-y);
}
struct Point{
double x,y;
Point(double a=0,double b=0):x(a),y(b){}
Vector operator + (Vector B){
return Vector(x+B.x,y+B.y);
}
Vector operator - (Point B){
return Vector(x-B.x,y-B.y);
}
Vector operator * (double d){ //数乘
return Vector(x*d,y*d);
}
double operator * (Vector B){ //数量积
return x*B.x+y*B.y;
}
Vector operator / (double d){
return Vector(x/d,y/d);
}
double operator ^ (Vector B){ //叉乘
return x*B.y-y*B.x;
}
bool operator < (const Point &b) const {
if(x==b.x) return y<b.y;
return x<b.x;
}
bool operator == (const Point& b) const {
if(dcmp(x-b.x)==0 && dcmp(y-b.y)==0)
return true;
return false;
}
};
double dis(Vector A){ //模长
return sqrt(A*A);
}
double sqrDis(Vector A){ //模长平方
return A*A;
}
double angle(Vector A,Vector B){ //向量夹角
return acos(A*B/dis(A)/dis(B));
}
Vector rotate(Vector A,double rad){ //逆时针旋转
return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
Vector normal(Vector A){ //逆时针90°的法向量
double L=dis(A);
return Vector(-A.y/L, A.x/L);
}
bool ToLeftTest(Point a, Point b, Point c){ //判断折线bc是不是向ab的逆时针方向(左边)转向
return ((b-a)^(c-b)) > 0;
}
推荐阅读
-
Java实现二叉树的建立、计算高度与递归输出操作示例
-
2分钟学会python数据分析与机器学习知识点(二)
-
计算机二级考试MySQL知识点 mysql alter命令
-
计算机二级考试MySQL知识点 常用MYSQL命令
-
php入门学习知识点二 PHP简单的分页过程与原理
-
BZOJ1278: 向量vector(计算几何 随机化乱搞)
-
读书笔记 计算机系统--系统架构与操作系统的高度集成 第二章处理器体系结构
-
51nod 1298 圆与三角形——计算几何
-
计算几何与计算机图形学方面的一些资源及源代码 MatlabFortranC#C++C
-
计算几何与计算机图形学方面的一些资源及源代码 MatlabFortranC#C++C