计算几何技巧整理(更新中)

平面向量基本操作

设向量$a=(a.x,a.y)$
$cp(a,b)=a.xb.y-b.xa.y$
$mul(a,b)=(a.xb.x-a.yb.y,a.xb.y+a.yb.x)$
$dis(a)=\sqrt{a.x^2+a.y^2}$

向量旋转

向量$a$旋转角度$\beta$后的向量为$mul(a, (\cos(\beta),\sin(\beta)))$
相当于复平面上的旋转,$e^x=\cos x+\sin x$

向量角度

使用C++库函数atan2可提高精度。
向量$a$的角度为$atan2(a.y,a.x)$
向量$(x1,y1)$和$(x2,y2)$之间的夹角等于$(x1x2+y1y2,-x1y2+y1x2)$与$(1,0)$之间的夹角
可类比$e^x/e^y=e^{x-y}$

求相对位置

如果$cp(a,b)>0$则说明B在A的逆时针方向且夹角小于180度。
如果$cp(a,b)<0$则说明B在A的顺时针方向且夹角小于180度。
如果$cp(a,b)=0$说明两者平行。

求三角形面积

如果已知三点坐标$A,B,C$,可使用cp计算,面积为$\frac{|cp(\overrightarrow{AB},\overrightarrow{AC})|}{2}$
如果已知三边长度$a,b,c$,则可用海伦公式计算面积为$\frac{\sqrt{(a+b+c)(a+b-c)(a-b+c)(-a+b+c)}}{4}$
能用第一种的尽量用第一种

直线包含

直线$AB$包含点$X$当且仅当$|\overrightarrow{AX}\times \overrightarrow{AB}|=0$

线段/射线包含

先判直线包含,然后再判横坐标的区间

半平面包含

对于$\overrightarrow{AB}$的逆时针方向的半平面对于点$X$。
如果$cp(\overrightarrow{AB},\overrightarrow{AX})>0$则说明严格包含。
如果$cp(\overrightarrow{AB},\overrightarrow{AX})=0$则说明在线上。
如果$cp(\overrightarrow{AB},\overrightarrow{AX})<0$则说明没有包含。

凸多边形包含

把凸多边形拆分成若干个半平面然后依次判断。

直线求交

对于相交的两条直线$AB$和$CD$,设它们交点为$P$,则
$\overrightarrow{OP}=\frac{\overrightarrow{OB}cp(\overrightarrow{CD},\overrightarrow{CA})+\overrightarrow{OA}cp(\overrightarrow{CB},\overrightarrow{CD})}{cp(\overrightarrow{CD},\overrightarrow{CA})+cp(\overrightarrow{CB},\overrightarrow{CA})}$
可以用分类讨论+面积法证明

点到线的投影

求点$X$到点$A$和点$B$组成直线的投影
$\overrightarrow{OX}=\overrightarrow{OA}+\overrightarrow{AB} (\frac{\overrightarrow{AB} \cdot \overrightarrow{AX}}{|\overrightarrow{AB}|^2})$
设$proj(X,L)$为点X到直线L的投影点。

点到线的距离

设$dis(X,L)$为点X到直线L的距离。
$dis(X,L)=dis\big(\overrightarrow{X proj(X,L)}\big)$

空间向量基本操作

设空间向量$A=(A.x,A.y,A.z)$
$dis(A)=(A.x^2+A.y^2+A.z^2)$

点到直线的投影

和平面向量类似

点到直线的距离

和平面向量类似

两个向量的夹角

设夹角为$\theta$,两个向量分别为$a,b$
$\cos \theta=\frac{a\cdot b}{|a||b|}$

Tagged with:

发表评论