二维计算几何基础

2023-12-06 10:32:16

点

表示方法

用两个变量$(x,y)$表示

struct pt{
	db x,y;
	pt(db _x=0,db _y=0){x=_x,y=_y;}
	inline void read(){scanf("%lf %lf",&x,&y);}
	inline void print(){printf("%.3lf %.3lf\n",x,y);}
};

用点也可以表示向量，即$(0,0)\to (x,y)$的向量

欧几里得距离

$\sqrt{x^2+y^2}$

inline db len2(pt a){return a.x*a.x+a.y*a.y;}
inline db len(pt a){return sqrt(a.x*a.x+a.y*a.y);}//距离

向量的坐标表示

$A(a,b),B(c,d)$，那么$\overrightarrow{AB}=(a-c,b-d)$

向量

前置芝士：高中数学必修四第二章平面向量

一个点在一个向量的左边指：该点在向量的逆时针方向

向量运算

加减与数乘

inline pt operator +(pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
inline pt operator -(pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
inline pt operator *(pt a,db b){return pt(a.x*b,a.y*b);}//数乘

点积

设向量 $a,b$ 夹角为 $\theta$

\[a\cdot b=|a||b|\cos \theta \]

几何意义：$a$的模与$b$在$a$方向上的投影的乘积

坐标运算：

若$a=(m,n),b=(p,q)$，则 $a\cdot b=mp+nq$

inline db operator *(pt a,pt b){return a.x*b.x+a.y*b.y;}//点积

应用：

根据正负号判断夹角：$>0\to $锐角，$=0\to $直角，$<0\to $钝角
计算夹角：$\cos \theta = \dfrac{|a||b|}{a\cdot b}$

叉积

这部分是高中教材没有的

叉积也叫向量积

向量$a,b$的叉积$a\times b$是一个向量，其模长$|a\times b|=|a||b|\sin\langle a,b\rangle$，方向遵循右手定则（右手定则：右手除姆指外的四指合并,姆指与其他四指垂直,四指由$a$向量的方向握向$b$向量的方向，这时姆指的指向就是$a,b$叉积的方向）

关于叉积的方向，在OI中应用较少，我们只需要记住

\[|a\times b|=|a||b|\sin\langle a,b\rangle \]

坐标运算：

若$a=(m,n),b=(p,q)$，则 $|a\times b|=mq-np$

inline db operator ^(pt a,pt b){return a.x*b.y-a.y*b.x;}

应用：

计算面积：三角形面积公式为$S=\dfrac{1}{2}ab\sin C$，$|a\times b|$就是$a,b$为领边的平行四边形面积（有向面积），除以$2$即可计算三角形面积

inline db S_tri(pt a,pt b,pt c){return fabs((a-c)^(b-c))/2.0;

判断方向：顺负逆正

inline bool Left(Line a,pt b){return sgn((a.y-a.x)^(b-a.x))>=0;}//是否在左边(逆时针)

向量旋转

设$a=(x,y)$，逆时针旋转$\theta$（角度制），旋转之后的向量为

\[a=(x\cos \theta-y\sin \theta,x\sin\theta+y\cos\theta) \]

证明：

设$|a|=l$，夹角为$\alpha$，$l\cos \alpha=x,l\sin\alpha=y$，那么新的夹角为$\theta+\alpha$

根据和角公式，横坐标：$l\cos(\theta+\alpha)=l(cos\theta\cos\alpha-\sin\theta\sin\alpha)=x\cos \theta-y\sin \theta$

纵坐标同理

三角恒等变形

和差角公式

\[\sin(\alpha\pm\beta)=\sin\alpha\cos\beta\pm\cos\alpha\sin\beta\\ \cos(\alpha\pm\beta)=\cos\alpha\cos\beta\mp\sin\alpha\sin\beta\\ \tan(\alpha\pm\beta)=\dfrac{\tan\alpha\pm\tan\beta}{1\mp\tan\alpha\tan\beta} \]

直线

一般使用两点或者一个点一个向量的表示方法，我是用的是两点式，因为这样可以方便地表示线段和进行点与直线的转化

点到直线距离

平行四边形面积（叉积）除以底边长

inline db dis(Line a,pt b){return (fabs((a.y-a.x)^(b-a.x))/2.0)/len(a.x-a.y);}//点到直线距离

垂足

点击求出映射的长度，比上向量模长，得到变化的比例

inline pt footpoint(Line a,pt b){//垂足 
	pt x=b-a.x,y=a.y-a.x;
	db s=x*y/len(y);
	return a.x+(a.y-a.x)*(s/len(y));
}

对称点

求出垂足之后中心对称即可

inline pt symmetry(Line a,pt b){pt ft=footpoint(a,b);return ft+ft-b;}//对称点

点与线的位置关系

点与直线

叉积判

点与射线

在直线上+点积判角度

点与线段

同时在两条射线上

inline bool on_line(Line a,pt b){return !sgn((b-a.x)^(a.y-a.x));}//在直线上 
inline bool on_ray(Line a,pt b){return (!sgn((b-a.x)^(a.y-a.x)))&&(sgn((b-a.x)*(a.y-a.x))>=0);}//在射线上 
inline bool on_segment(Line a,pt b){return (!sgn((b-a.x)^(a.y-a.x)))&&(sgn((b-a.x)*(b-a.y))<=0);}//在线段上

交点

线段有无交点

快速排斥实验

一目了然

跨立实验

即一个线段的两个点在另一个线段的两侧，叉积判一判

inline bool check_intersec(Line a,Line b){
	if(max(a.x.x,a.y.x)+eps<min(b.x.x,b.y.x)||min(a.x.x,a.y.x)>max(b.x.x,b.y.x)+eps
		|| max(a.x.y,a.y.y)+eps<min(b.x.y,b.y.y)||min(a.x.y,a.y.y)>max(b.x.y,b.y.y)+eps)return 0;//快速排斥实验 
	return sgn((b.x-a.x)^(a.y-a.x))*sgn((b.y-a.x)^(a.y-a.x))<=0&&sgn((a.x-b.x)^(b.y-b.x))*sgn((a.y-b.x)^(b.y-b.x))<=0;//跨立实验 
}

求交点

面积比得到长度比

inline pt intersec(Line a,Line b){//两直线交点（需要保证不平行/重合） 
	pt x=a.y-a.x,y=b.y-b.x,z=a.x-b.x;
	return a.x+x*((y^z)/(x^y));
}

码农公寓

点