1.什么是计算几何#

维基百科计算几何

计算几何是一门兴起于二十世纪七十年代末的计算机科学的一个分支，主要研究解决几何问题的算法。

简单来说就是用计算机算解析几何

2.计算几何的恶心之处#

• 有精度误差¹

• 需要讨论各种边界情况

• 代码长（看一看NOI2017D2T3的标称就知道了）

  解决精度问题
  设$\epsilon$为非常小的量

  • $a=b \Leftrightarrow |a-b|< \epsilon$
  • $a< b \Leftrightarrow a-b < -\epsilon$
  • $a\leq b \Leftrightarrow a - b < \epsilon$

3.二维矢量#

矢量#

• 既有大小又有方向的量
• 又称为向量

矢量的表示#

• 在n维空间下，矢量经常被表示为 $\vec{a}=(a_1,a_2,\ldots,a_n)$
• 在二维空间中则以$(x,y)$来表述

点积#

$(a_1,a_2,\ldots,a_n)\cdot(b_1,b_2,\ldots,b_n) = a_1 b_1 + a_2 b_2+\cdots+ a_n b_n$

矢量的模#

矢量的长度

! 二维叉积#

$(x_1,y_1)\times(x_2,y_2) = x_1 y_2 - x_2 y_1$

二维叉积满足逆交换律: $\vec{a}\times\vec{b} = - \vec{b}\times\vec{a}$

有向面积#

• 由$\vec{a}$和$\vec{b}$所成的平行四边形的面积为$|\vec{a}\times\vec{b}|$ 的值
• 去掉绝对值二维叉积定义为有向面积

有向面积的符号#

伸出右手将四指由$\vec{a}$沿小于平角转到$\vec{b}$若拇指指向纸面上方则$\vec{a}\times\vec{b}$为正否则为负

二维矢量的旋转#

将矢量$\vec{a}$逆时针旋转$\theta$后为$\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \\ \end{pmatrix} \vec{a}$

二维矢量的极角#

极角指示矢量的方向，以x轴正半轴逆时针转过的角度来指示 矢量$(x,y)$的极角为$atan2(y,x)$

直线#

用两个相异点来表示 $\forall\lambda \in R,\lambda A +(1-\lambda)B$ 表示直线上任意一点

点到直线的距离#

点$P$到直线$AB$的距离 即$|\vec{AP}-\vec{AB}\frac{\vec{AB}\cdot\vec{AP}}{\vec{AB}^2}|$

分点#

若A,B,C共线，且$\frac{|\vec{AC}|}{\vec{CB}} =\frac{\lambda_1}{\lambda_2}$ 则$C=\frac{\lambda_2 A + \lambda_1 B}{\lambda_1 + \lambda_2}$

三角形的面积#

$S(\Delta ABC) = \frac{|\vec{AB}\times\vec{AC}|}{2}$

两直线交点#

$\frac{|\vec{AO}|}{|\vec{OB}|} = \frac{S(\Delta ADC)}{S(\Delta BCD)} = \frac {\vec{AD}\times\vec{AC}}{\vec{BC}\times\vec{BD}}$

为完待续…(2017-8-6)#