计算几何系列知识

我对计算几何一无所知

基础知识

向量

定义:在一个\(n\)维空间中的一条有方向和长度(没有位置)的线段,记作:\[\vec{a}=\begin{bmatrix}a_1,\cdots,a_n\end{bmatrix}\]一般在计算几何中常用的是二维向量。一个n维向量的模长:\[|\vec{a}|=\sqrt{a_1^2+a_2^2+\cdots+a_n^2}\]表示这条有向线段在空间中的实际长度

向量的数量积(点积)

对于两个同维向量 \(\vec{a}=\begin{bmatrix}a_1,\cdots,a_n\end{bmatrix}\) 和 \(\vec{b}=\begin{bmatrix}b_1,\cdots,b_n\end{bmatrix}\),定义向量数量积:\[\vec{a}\cdot\vec{b}=a_1 b_1+a_2 b_2+\cdots+a_n b_n\]对于二维向量,数量积也可以使用模长和夹角计算:\[\vec{a}\cdot\vec{b}=|\vec{a}|\times|\vec{b}|\times\cos{\theta}\]其表示一个向量在另一个向量上的投影长度乘上投影向量的长度

使用数量积,我们可以计算两个向量的最小夹角(\(\theta\in[0,\pi]\)):\[\theta=\arccos\frac{\vec{a}\cdot\vec{b}}{|\vec{a}||\vec{b}|}\]进而我们可以按照\(\arccos\)的性质来推断两个向量的方向关系:

  • \(\vec{a}\cdot\vec{b}>0\):方向基本相同,\(\theta\in[0,\frac{\pi}{2})\)
  • \(\vec{a}\cdot\vec{b}=0\):正交(垂直),\(\theta=\frac{\pi}{2}\)
  • \(\vec{a}\cdot\vec{b}<0\):方向基本相反,\(\theta\in(\frac{\pi}{2},\pi]\)

向量的向量积(叉积)

对于两个二维向量\(\vec{a}\)和\(\vec{b}\),她们的向量积\(\vec{a}\times\vec{b}\)方向在右手系中按照右手定则确定(伸出右手,将四指从a向b转动,大拇指方向即为叉积方向),模长即等于:\[|\vec{a}\times\vec{b}|=|\vec{a}|\times|\vec{b}|\times\sin{\theta}\]她在数值上即等于两个向量围成的平行四边形面积。

同时,向量叉乘满足以下性质:

  1. \(\vec{a}\times\vec{a}=\vec{0}\)(夹角为零,\(\sin\theta\)即为零)
  2. \(\vec{a}\times\vec{b}=-(\vec{b}\times\vec{a})\)(伸出右手,转动方向相反,结果方向就相反)(反交换律)
  3. \(\lambda\vec{a}\times\vec{b}=\lambda(\vec{a}\times\vec{b})\)(长度缩放\(\lambda\)倍,平四面积也缩放\(\lambda\)倍)
  4. \(\vec{a}\times(\vec{b}\times\vec{c})=\vec{a}\times\vec{b}+\vec{a}\times\vec{c}\)(证明很复杂的谜之分配律)

未完成:

凸包的求法和性质
求点线圆的交点
半平面交的求法与性质

学习难点:
旋转卡壳
Simpson 积分
求面积并、面积

发表评论

电子邮件地址不会被公开。 必填项已用*标注