[数学基础] 9 计算几何初步(1)

本文主要是介绍[数学基础] 9 计算几何初步(1)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

今天复习到了高数的向量代数，那就顺手把一部分计算几何的基础知识总结下贴上来QWQ
感觉……计算几何的板子，很容易出错（我下载到的板子也在一些小地方和特殊情况存在问题），所以这些都是我尽量验证过的，但是，也不能保证考虑到了100%的情况，因此推荐在应用之前，也尝试着进行一些验证（比如自己代入特殊点，或者找几个模板题试一下，不推荐在AcWing上测试，数据一般都比较水）
计算几何这一部分我自己也没有学的很好，而且是比赛前赶鸭子上架学的，笔记很散乱而且不全，后续如果更新的话速度也会较慢QAQ

常用定理

余弦定理

\(c^2=a^2+b^2-2\times a \times b\times \cos (C)\)

海伦公式

\(p=\frac{(a+b+c)}2\)

\(S_{\triangle ABC}=\sqrt{p(p-a)\times (p-b)\times (p-c)}\)

向量

常用运算

内积（点积） \(\overrightarrow A·\overrightarrow B = |\overrightarrow A||\overrightarrow B|\cos(\theta)\)

(1) 几何意义：向量\(\overrightarrow A\)在向量\(\overrightarrow B\)上的投影与\(\overrightarrow B\)的长度的乘积。

(2) 公式推导

定义向量\(\overrightarrow c=\overrightarrow a-\overrightarrow b\)

\(c^2=a^2+b^2-2\times |\overrightarrow a||\overrightarrow b|\cos \theta\)

即\((\overrightarrow a -\overrightarrow b)·(\overrightarrow a - \overrightarrow b)=a^2+b^2-2\overrightarrow a·\overrightarrow b=a^2+b^2-2\times |\overrightarrow a||\overrightarrow b|\cos \theta\)

则\(\overrightarrow a ·\overrightarrow b=|\overrightarrow a||\overrightarrow b|\cos \theta\)

(3) 代码实现

// 计算A·B(点积)
double dot(Point A, Point B){
    return A.x * B.x + A.y * B.y;
}

外积（叉积） \(\overrightarrow A\times\overrightarrow B = |\overrightarrow A||\overrightarrow B|\sin(\theta)\)

(1) 几何意义：

向量\(\overrightarrow A\)与\(\overrightarrow B\)张成的平行四边形的有向面积。\(\overrightarrow B\)在\(\overrightarrow A\)的逆时针方向为正。

(2) 公式推导

$S= |\alpha|\times|\beta|\times \sin(b-a)= |\alpha|\times |\beta|\times (\sin b\times \cos a-\cos b \times \sin a)\=(|\alpha|\cos a)(|\beta|\sin b)-(|\alpha|\sin a)(|\beta| \cos b)=A.x\times B.y - A.y\times B.x $

(3) 代码实现

// 计算AxB(叉积)
double Cross(Vector A, Vector B){
    return A.x * B.y - A.y * B.x;
}

常用函数

1. 取模

// 计算|A|
double get_length(Point A){
    return sqrt(dot(A, A));
}

2. 计算向量夹角

\(\theta=\arccos(\frac{\overrightarrow a·\overrightarrow b}{|\overrightarrow a||\overrightarrow b|})\)

余弦公式没啥好说的0.0

// 计算A,B之间夹角, AB可以交换顺序
double get_angle(Point A, Point B){
    return acos(dot(A, B) / get_length(A) / get_length(B));
}

3. 向量\(\overrightarrow A\)顺时针旋转\(\theta\)的角度

\(x_2=OA\times \cos(\alpha -\theta)=OA\times(\cos \alpha \cos \theta+\sin\alpha \sin \theta)=x_1\times \cos \theta+y_1\times \sin \theta\)

\(y_2=OA\times \sin(\alpha -\theta)=OA\times(\sin \alpha \cos \theta-\cos\alpha \sin \theta)=-x_1\times \sin \theta+y_1\times \cos \theta\)

// 向量A顺时针旋转theta度，theta是PI/6之类的, 不是90°,45°这样的
Point rotate(Point A, double theta){
    return Point(A.x * cos(theta) + A.y * sin(theta), -A.x * sin(theta) + A.y * cos(theta));
}

点、直线

直线公式

一般式：\(ax+by+c=0\)

点向式：\(\begin{cases} x=x_0+mt \\ y=y_0+nt \end{cases}\)

设直线\(L\)过点\(M_0(x_0,y_0)\)，\(\overrightarrow s=\{m,n\}\)是直线\(L\)的向量。设\(M\)为直线\(L\)上任意一点，则\(\overrightarrow {M_0M}=\{x-x_0,y-y_0\}\)，且\(\overrightarrow {M_0M} ~//~~ \overrightarrow s\)。由两向量平行的充要条件可知：

\(t=\frac{x-x_0}m =\frac{y-y_0}n\)，即直线的点向式方程为：

\(\frac{x-x_0}m =\frac{y-y_0}n\)（当\(m,n\)中有一个为0时，就理解为相应的分子为0）

则方程组\(\begin{cases} x=x_0+mt \\ y=y_0+nt \end{cases},t\in\R\)

称为直线的参数方程

斜截式 \(y=kx+b\)

两点式 \(\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}\)

常用操作与函数

点与直线

判断一个线段上有多少个整数点

int getPoint(Point A){
    return abs(gcd(A.x, A.y)) + 1;
}

判断点和直线的关系

判断点\(C\)和直线\(AB\)的关系时，可以转为判断\(x=\overrightarrow {AC}\times \overrightarrow {AB}\)的值。

// 点C和直线AB的关系: 判断AC和AB的叉积
// -1: C在AB左边 0: C在AB上 1: C在AB右边
int relation(Point A, Point B, Point C){
    ll c = Cross(C - A, B - A);
    return sgn(c);
}

点C是否在线段AB上

首先应满足点\(C\)在直线\(AB\)上，其次满足点\(C\)在线段\(AB\)间。

即：\(\overrightarrow {AC}\times \overrightarrow {AB}=0,\overrightarrow{AC}·\overrightarrow {BC}\leq 0\)。

// 判断点C是否在线段AB上
// 0: 点C不在线段AB上; 1: 点C在线段AB上
bool onSegment(Point A, Point B, Point C){
    return relation(A, B, C) == 0 && sgn(dot(C - A, C - B)) <= 0;
}

点到直线的距离

\(S_{ABCD}=\overrightarrow {v_1}\times \overrightarrow {v_2}=d\times |\overrightarrow {v_2}|\)，\(\therefore d=\frac{\overrightarrow {v_1}\times \overrightarrow {v_2}}{|\overrightarrow {v_1}|}\)

// 返回点C到直线AB的距离
double dis2Line(Point A, Point B, Point C){
    Vector v1 = B - A, v2 = C - A;
    return fabs(Cross(v1, v2) / get_length(v1));
}

点\(C\)到线段\(AB\)的距离

注意：A点必须在B点的左边，否则会计算错误

当\(AB\)为一个点时，返回\(get\_dis(A,C)\)；当\(C\)在线段\(AB\)间时，返回\(dis2Line(C,A,B)\)；

当\(C\)在线段的左边，返回\(|\overrightarrow v_2|\)；当\(C\)在线段的右边，返回\(|\overrightarrow v_1|\)。

// 点C到线段AB的距离, 必须保证A在B点左边或者与B重合
double dis2Segment(Point A, Point B, Point C){
    if (A == B) return get_length(C - A);
    Vector v1 = B - A, v2 = C - A, v3 = C - B;
    if (sgn(dot(v1, v2)) < 0) return get_length(v2);
    if (sgn(dot(v1, v3)) < 0) return get_length(v3);
    return dis2Line(A, B, C);
}

点在直线上的投影

如图点\(D\)的坐标就为\(\overrightarrow {OA} +\overrightarrow {AD}\)，因此，求出\(\overrightarrow {AD}\)即可求出投影点坐标。

\(|\overrightarrow {AD}|=|\overrightarrow {AC}|\times \cos \theta\)，$\overrightarrow {AB}·\overrightarrow {AC}=|\overrightarrow {AC}|\times\cos \theta\times | \overrightarrow {AB}| $

\(\therefore t=\frac{|\overrightarrow {AD}|}{|\overrightarrow {AB}|}=\frac{\overrightarrow {AB}·\overrightarrow {AC}}{|\overrightarrow {AB}|^2}=\frac{\overrightarrow {AB}·\overrightarrow {AC}}{\overrightarrow {AB}·\overrightarrow {AB}}\)

\(\overrightarrow {AD}=\overrightarrow {OA}+\overrightarrow {AB}\times t\)

// 计算点C到直线AB的投影
Point projection2Line(Point A, Point B, Point C){
    Point v = B - A;
    v = v * (dot(v, C - A) / dot(v, v)); // 咳咳, 直接写到一行会报错0.0
    return A + v;
}

这篇关于[数学基础] 9 计算几何初步(1)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！