计算几何 学习笔记

发表于 更新于
计算几何的一些小结论

推荐阅读这个，模板可在这里找strangeman的提交记录。

## 向量相关

#### 向量的坐标表示

有点 \(A(x_1,y_1)\) 和点 \(B(x_2,y_2)\)，则 \(\overrightarrow{AB}\) 可表示为 \((x_2-x_1,y_2-y_1)\)

#### 共线向量

共线向量 \(a(x_1,y_1)\) 和 \(b(x_2,y_2)\) 满足 \[ x_1y_2=x_2y_1 \]

由此得到判断三点共线的方法：计算 \(\overrightarrow{AB}\) 和 \(\overrightarrow{BC}\) 进行比较。

#### 向量的点乘

向量 \(a(x_1,y_1)\) 和 \(b(x_2,y_2)\) 的数量积 \[ a \cdot b=x_1x_2+y_1y_2 \]

由此得到向量垂直的条件： \[ a\perp b \Leftrightarrow x_1x_2+y_1y_2=0 \]

#### 向量的叉乘

向量 \(a(x_1,y_1)\) 和 \(b(x_2,y_2)\) 的向量积 \[ a \times b=x_1y_2-y_1x_2 \]

#### 叉乘的意义 + 若两个向量的叉积不为 \(0\)，则他们相交；否则他们重合或平行。

  • 两个向量的叉积是他们围成的平行四边形的面积，由此可以快速计算三角形的面积，从而快速计算多边形的面积。注意：逆时针求得的面积是正的，顺时针求得的是负的。

  • 若两个向量的叉积大于 \(0\),则第二个向量由第一个逆时针选择得到；反之由顺时针旋转得到。由此可以判定多边形的凹凸性、判定点与多边形的位置关系、判定线段相交等等。

多边形相关

#### 三角函数 + \(\pi=\arccos(-1)\)，这样精度比较高。

  • 开平方、反三角函数最容易炸精度。因此不要使用正弦定理求解角度，尽量使用余弦定理或点乘。还有个好处就是余弦值在 \([0,\pi]\) 是唯一的！

#### 凸包与面积 求凸多边形的面积的基本思想是三角剖分后求每个三角形的面积。由此产生了两种子类型：

1.在动态凸包中处理。则每次增加点、删除点的面积与该点和相邻两点组成的三角形的面积相关；

2.以某一点为基准点处理。则面积与基准点和当前边构成的三角形的面积相关，注意三点共线的情况要特判。