《算法从入门到入土系列》第三集＜上＞ 计算几何专题（基础知识）

---

基础知识

计算几何是一个偏模拟的专题。几何大家都学过，应该都觉得挺简单的吧，从二维到三维思维的快乐跳跃，需要一些空间想想能力，让我们一起畅游几何学吧！

计算几何题目特点及要领

大体不难，少量题目需要灵光一现。

1. 做计算几何题目，打造一个自己熟悉的模板很重要，因为稍微难一点的题目，代码量会很大（但是大部分都是模板），如果常用的模板出问题，现场debug真的是个要命的操作。
2. 注意精度控制
3. 可以用扩大数据的方法，来减少计算量，例如扩大10倍去掉小数，计算完之后再进行变换成小数，有根的时候，可以取平方，以达到减少计算量的目的。

计算几何需要具备很多的基础知识，现在梳理一下基础知识。

常用的一些公式

1. π的表示方法：PI = acos(-1); #define PI acos(-1)
2. 余弦定理：$c^2=a^2+b^2-2abcos\theta$

(一) 前置知识

浮点数的比较

因为在计算几何中，一般情况下结果都是浮点数，由于浮点数的精度问题，需要重新定义一些变量的边界。
(1) 将小于 1e-8 的数 且 大于0 的数，定义为0
(2) 如果两个数差值的绝对值小于 1e-8，那么认为这两个数相等

const double eps = 1e-8;
//符号函数
int sign(double x) {
   
	if (fabs(x) < eps) return 0;
	if (x < 0) return -1;
	return 1;
}
//比较函数
int cmp(double x, double y) {
   
	if (fabs(x - y) < eps) return 0;
	if (x < y) return -1;
	return 1;
}

(二) 向量的基础知识

1. 向量的加减法和数乘运算

直接对点的坐标进行加减和数乘的运算即可

---

2. 内积（点积）$\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}=(x_1,y_1)，\vec{b}=(x_2,y_2)$ 。则$\vec{a}\cdot \vec{b}=x_1\times x_2+y_1\times y_2$
。内积得到的答案是一个数值。
**内积的几何意义：**向量A在向量B上的投影与B的长度的乘积
代码实现：

double dot(Point a, Point b) {
   
		return a.x * b.x + a.y + b.x;
}

---

3. 外积（叉积） $\vec{A}\times \vec{B}=|\vec{A}||\vec{B}|sin\theta$

**外积的几何意义：**由$\vec{A}$ 与 $\vec{B}$ 形成的三角形面积的两倍

---

4. 取模 $|\vec{A}|=\sqrt{\vec{A}\cdot \vec{A}}$

double getLen(Point a) {
   
	return sqrt(dot(a, a));
}

---

5. 两向量夹角：

$\vec{A}\cdot \vec{B}=|\vec{A}||\vec{B}|cos\theta$
$cos\theta =\frac{\vec{A}\cdot \vec{B}}{|\vec{A}||\vec{B}|}$ → $\theta =arcos(\frac{\vec{A}\cdot \vec{B}}{|\vec{A}||\vec{B}|})$

double getAngle(Point a, Point b) {
   
	return acos(dot(a, b) / getLen(a) / getLen(b));
}

---

6. 计算两向量构成的平行四边形有向面积

double area(Point a, Point b, Point c) {
   
	return cross(b - a, c - a);
}

7. 将向量a顺时针旋转θ

( x , y ) → ( x 1 , y 1 ) = ( x , y ) ( c o s θ − s i n θ s i n θ c o s θ ) = ( x c o s θ + y s i n θ , − x s i n θ + y s i n θ ) (x, y) → (x_1, y_1) = (x, y) \bigl(

$$\begin{matrix} cosθ & -sinθ \\ sinθ & cosθ \end{matrix}$$ \bigr) = (xcosθ+ysinθ, -xsinθ + ysinθ) (x,y)→(x1​,y1​)=(x,y)(cosθsinθ​−sinθcosθ​)=(xcosθ+ysinθ,−xsinθ+ysinθ)

double rotate(Point a, double angle) {
   
      return Point(a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) + a.y * cos(angle));
}  

(三) 点与直线的基础知识

1. 直线有三种表示方式

(1) $ax+by+c=0$（一般式，可以表示所有直线）
(2) $y=kx+b$ （斜截式，不能表示与x轴垂直的直线）
(3) $a+k\vec{v}$(常用) （t为模长，其实这就是直线的参数方程）

2. 判断一个点是否在直线上

这个点与直线上任意两个不同的点形成的向量，做叉乘，如果为0，则该点一定在直线上，反之则不在。几何意义：这个点与直线上任意两个不同的点形成的面积为0，则该点一定在直线上
$$A\times B==0$$

3. 两直线是否平行或者在同一条直线上

(1) 先判断叉积是否为0
(2)

// cross(v, w) == 0则两直线平行或者重合
Point get_line_intersection(Point p, Vector v, Point q, vector w) {
   
    vector u = p - q;
    double t = cross(w, u) / cross(v, w);
    return p + v * t;
}

4. 点到直线的距离

double distance_to_line(Point p, Point a, Point b) {
   
    vector v1 = b - a, v2 = p - a;
    return fabs(cross(v1, v2) / get_length(v1));
}

5. 点到线段的距离

double distance_to_segment(Point p, Point a, Point b)
{
   
    if (a == b) return get_length(p - a);
    Vector v1 = b - a, v2 = p - a, v3 = p - b;
    if (sign(dot(v1, v2)) < 0) return get_length(v2);
    if (sign(dot(v1, v3)) > 0) return get_length(v3);
    return distance_to_line(p, a, b);
}

6. 点到直线上的投影（是一个向量）

double get_line_projection(Point p, Point a, Point b) {
   
    Vector v = b - a;
    return a + v * (dot(v, p - a) / dot(v, v));
}

7. 判断点是否在线段上

bool on_segment(Point p, Point a, Point b) {
   
    return sign(cross(p - a, p - b)) == 0 && sign(dot(p - a, p - b)) <= 0;
}

8. 判断两线段是否相交

bool segment_intersection(Point a1, Point a2, Point b1, Point b2) {
   
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
    return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
}

(四) 多边形

1. 三角形

Ⅰ. 面积

(1) 两个向量的叉积 / 2
(2) 海伦公式
$$p=(a+b+c)/2$$
$$S=\sqrt{p(p-a)(p-b)(p-c)}$$

Ⅱ. 三角形的四心

① 外心，外接圆圆心
三边中垂线交点。到三角形三个顶点的距离相等
② 内心，内切圆圆心
角平分线交点，到三边距离相等
③ 垂心
三条垂线交点
④ 重心
三条中线交点（到三角形三顶点距离的平方和最小的点，三角形内到三边距离之积最大的点）

2. 普通多边形

通常默认按照逆时针存储所有点

Ⅰ. 简单多边形定义

由在同一平面且不再同一直线上的多条线段首尾顺次连接且不相交所组成的图形叫多边形。

Ⅱ. 凸多边形定义

过多边形的任意一边做一条直线，如果其他各个顶点都在这条直线的同侧，则把这个多边形叫做凸多边形

Ⅲ. 凸多边形的性质

        1. 任意凸多边形外角和均为360°
        2. 任意凸多边形内角和为(n−2)180°

常用的函数：

Ⅳ. 求多边形面积（任意多边形）

我们可以从第一个顶点除法把凸多边形分成n − 2个三角形，然后把面积加起来。

double polygon_area(Point p[], int n)
{
   
    double s = 0;
    for (int i = 1; i + 1 < n; i ++ )
        s += cross(p[i] - p[0], p[i + 1] - p[i]);
    return s / 2;
}

Ⅴ. 判断点是否在多边形内（任意多边形）

Ⅰ. 射线法：从该点任意做一条和所有边都不平行的射线。交点个数为偶数，则在多边形外，为奇数，则在多边形内。
Ⅱ. （特殊的）如果该多边形是凸多边形，只需要判断点是否在所有便的做i便（逆时针存储多边形）

转载：https://blog.csdn.net/m0_46272108/article/details/115432431