记录一些计算几何相关的知识。
推荐学习资料：wjyyy 的博客 。
向量
模
向量的长度，\(\vec{a}=(x,y),|\vec{a}|=\sqrt{x^2+y^2}\)。
加减
几何意义为两个向量 \(\vec{a},\vec{b}\) （线段）首尾相接，\(\vec{a}\) 的头指向 \(\vec{b}\) 的尾即 \(\vec{a}+\vec{b}\)。
对于 \(\vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2)\)，\(\vec{a}+\vec{b}=(x_1+y_1,x_2+y_2)\)。
数乘
对向量缩放。对于 \(\vec{a}=(x,y)\)，\(\lambda\vec{a}=(\lambda x,\lambda y)\)。
点积（数量积、内积）
几何意义为向量 \(\vec{a}\) 在向量 \(\vec{b}\) 上的投影再乘上向量 \(\vec{b}\) 的模长。
点积是一个数量，设 \(\theta\) 为 \(\vec{a},\vec{b}\) 的夹角，\(\vec{a}\cdot \vec{b}=|\vec{a}||\vec{b}|\cos\theta\)。
对于 \(\vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2)\)，\(\vec{a}\cdot\vec{b}=x_1x_2+x_2y_2\)。
点积满足交换律。
叉积（外积）
几何意义为两个向量平行四边形法围成的有向面积。
叉积是一个数量，设 \(\theta\) 为 \(\vec{a},\vec{b}\) 的夹角，\(\vec{a}\cdot \vec{b}=|\vec{a}||\vec{b}|\sin\theta\)。
对于 \(\vec{a}=(x_1,y_1),\vec{b}=(x_2,y_2)\)，\(\vec{a}\cdot\vec{b}=x_1y_2-x_2y_1\)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| struct Vector {
double x, y;
Vector(const double &_x = 0, const double &_y = 0): x(_x), y(_y) {}
friend const Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
friend const Vector operator -(const Vector &a, const Vector &b) {
return Vector(a.x - b.x, a.y - b.y);
}
friend const Vector operator *(const Vector &a, const double &k) {
return Vector(a.x * k, a.y * k);
}
friend const Vector operator /(const Vector &a, const double &k) {
return Vector(a.x / k, a.y / k);
}
friend const double cross(const Vector &a, const Vector &b) {
return a.x * b.y - a.y * b.x;
}
friend const double dot(const Vector &a, const Vector &b) {
return a.x * b.x + a.y * b.y;
}
double len2() const {
return x * x + y * y;
}
double len() const {
return sqrt(len2());
}
Vector norm() const {
return *this / len();
}
Vector rotate() const {
return Vector(y, -x);
}
};
|