[数据结构与算法] 计算几何(4.17)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 计算几何(4.17) -> 正文阅读

[数据结构与算法]计算几何(4.17)

计算几何

前置知识：
1. ```
pi = acos(-1)
```
2. 余弦定理： $c^2 = a^2+b^2-2abcos(t)$

浮点数的比较。

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. 内积（点积） $\cdot B=|A||B|cos(C)$
  
  几何意思：向量A在向量B上的投影乘向量B的长度。
```
double dot(Point a,Point b){
    return a.x*b.x+a.y*b.y;
}
```
3. 外积（叉积） $\times B = |A||B|sin(C)$ （行列式推的）
  
  几何意义：向量A和B张成的平行四边形的面积(有向面积)的一半。方向遵循定则。
```
double cross(Point a,Point b){
    return a.x*b.y-a.y*b.x
}
```
由点积和叉积延伸出来的常用函数。
1. 求向量的长度。
```
double get_length(Point a){
    return sqrt(dot(a,a));
}
```
2. 计算向量的夹角
```
double get_angle(Point a,Point b){
    return acos(dot(a,b)/get_length(a)/get_length(b));
}
```
3. 计算平行四边形面积
```
double get_area(Point a,Point b,Point c){
	return cross(a-b,c-b);
}
```
4. 将一个向量旋转一个角度。
  
  将 $(x, y)$ 顺时针旋转一个 $\theta$ 角。
  $\begin{bmatrix} x , y \end{bmatrix} \begin{bmatrix} cos(\theta) & -sin(\theta)\\ sin(\theta) &cos(\theta) \end{bmatrix}=[{xcos(\theta)+ysin(\theta)},{-xsin(\theta)+ycos(\theta)}]$
点与线
1. 直线定理。
  1. 一般式 $a x + b y + c = 0$
  2. 点向式(用的最多) $p_0(任意一个点)+\overline v(过p_0的非0向量) *t$
  3. 斜截式 $y = kx+b
2. 判断点在不在直线上。
  
  $\times B = 0$ 表示 $a 点和向量 B 上的某个点组成的向量 A 和 B 所围成的三角形的面积是 0$ ，表示点在直线上。
3. 两直线相交，求交点。
  
  $c r o s s (v, w) = = 0$ 特判两直线平行或者重合的情况。(用了相似来证明)
```
Point get_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 a,Point b,Point c){
    Vector v1 = b-a;
    Vector v2 = c-a;
    return fabs(cross(v1,v2))/getlength(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. 点到直线的投影。
```
Point 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){
    // 线段是a->b,判断p是否在线段上。满足p在线段上，且p在[a,b]中间。
    return sign(cross(p-a),cross(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);
    double c2 = cross(a2-a1,b2-a1);
    double c3 = cross(b2-b1,a2-b1);
    double c4 = cross(b2-b1,a1-b1);
    return sign(c1)*sign(c2)<=0 && sign(c3)*sign(c4)<=0;
}
```
多边形。
1. 三角形的四心。
  1. 外心：三角形外接圆的圆心，三边的中垂线的交点，到三角形的三个顶点的距离相等。
  2. 内心：内切圆的圆心，角平分线的交点，到三边的距离相等。
  3. 垂心：三个垂足的交点。
  4. 重心：三条中线的交点。（到三角形三顶点距离的平方和最小的点，三角形内到三边距离的乘积最大的点）。
2. 定义：在同一平面，不在同一直线上，多条线段首尾顺次连接且不相交的图形。
3. 简单多边形：除相邻边外，其他边不相交。
4. 凸多边形：
  
  过多边形的任意一条边做一条直线，如果其他各个顶点都在这条边的一侧，就是凸多边形。
  1. 任意凸多边形的外角和都是360度。
  2. 任意凸多边形的内角和都是 $(n ? 2) ? 180$ 度。
5. 常用函数：
  1. 求任意多边形的面积。
    
    可以将多边形进行三角剖分，分成 $n ? 2$ 个三角形，将所有的边按照逆序，或者顺序进行排序。
  2. 可以在平面上任意选一点，按照边的顺序，遍历每一条边，通过求两个向量的叉积的方法，得到多边形的面积和。（利用了叉积面积有正负的性质，非常的巧妙）
```
double polygon_area(Point p[],int n){
    // 取任意点的时候，一般取多边形的第一个点p[0]
    double s=0;
    for(int i=1;i<n-1;i++){
        s += cross(p[i]-p[0],p[i+1]-p[i]);
    }
    return s/2;
}
```
  3. 判断一个点是否在多边形内（可以是任意多边形）
    
    射线法 or 转角法
    
    射线法：从该点任意做一条和所有边都不平行的射线，交点个数为偶数，该点在多边形外，否则在多边形内。
  4. 判断一个点是否在凸多边形内（凸多边形按照逆时针存储）
    
    判断点是否在凸多边形的左侧。（叉积）
6. 皮克定理
  
  ? 要求：多边形的所有点必须在格点上。
  
  ? ${b\over 2}-1$ 。
  
  ? $a ：$ 多边形内部的整点个数。
  
  ? $b :$ 多边形边上的整点个数。