计算几何的基础运算(笔记)

余弦

余弦定理：三角形任一边的平方等于其他两边平方和减去这两边与它们夹角的余弦的积的两倍

\(a^2=b^2+c^2-2bc\cdot cosA\)

点积

两个向量\(v\)和\(w\)的点积等于二者模积乘上它们夹角的余弦，因此当夹角大于\(90^o\)时点积为负

两个向量OA和OB的点积等于\(x_Ax_B+y_Ay_B\)，即\(\overrightarrow{OA}\cdot\overrightarrow{OB}=\overrightarrow{|OA|}\cdot\overrightarrow{|OB|}cos\theta=x_Ax_B+y_Ay_B\)

证明略

叉积

两个向量\(v\)和\(w\)的叉积等于\(v\)和\(w\)所组成的三角形的有向面积的两倍

从向量\(v\)来看，如果\(w\)在左边(逆时针)，则\(v\)和\(w\)的叉积大于\(0\)，否则小于\(0\)。特殊地，如果两个向量共线(方向相同)，那么叉积等于\(0\)(三角形退化成线段)

可以发现，叉积不满足交换律：\(cross(v,w)=-cross(w,v)\)，两个向量\(OA\)和\(OB\)的叉积等于\(x_Ay_B-x_By_A\)

直线的参数表示

直线可以用直线上一点\(P_0\)和方向向量\(v\)表示(这个向量的大小在表示中无用)，借此直线上所以点\(P\)可以满足\(P=P_0+tv\)，其中t为参数

如：一直直线上不同两点\(A和B\)，则方向向量为\(B-A\)，所以参数方程为\(A+(B-A)t\)

直线交点

设直线分别为\(P+tv\)和\(Q+tw\)，设向量\(u=P-Q\)，设交点在第一条直线参数为\(t_1\)，在第二条直线参数为\(t_2\)，则：

\[t_1=\frac{cross(w,u)}{cross(v,w)},t2=\frac{cross(v,u)}{cross(v,w)}\]

点到线段的距离

距离有两种可能

一种是点\(P\)在直线\(AB\)的投影点\(Q\)在线段\(AB\)上，其距离为线段\(PQ\)的长度；另一种，则距离为点\(P\)到线段\(AB\)两端点的最小值

可以利用点积判断位置关系分类处理

inline double Getlength(Point P,Point A,Point B){
    if(A==B) return Length(P-A);
    if(dcmp(Dot(v1, v2)) < 0) return Length(v2);
    else if(dcmp(Dot(v1, v2))< 0) return Length(v3);
    else return fabs(Cross(v1, v2)) / Length(v1);
}

多边形面积

凸包的面积求法很显然：找到左下角一点然后顺时针求相邻两点分割成三角形即可

那非凸(不规则)多边形呢？其实方法是相同的，因为三角形面积是有向的，在外面的部分可以抵消掉(好神奇啊！！！(*￣︶￣))

计算几何的基础运算(笔记)

原文：https://www.cnblogs.com/y2823774827y/p/10344817.html