【学习笔记】【数学】计算几何基础

向量，就是带有方向和大小两个属性的边，通常形式为\(\overrightarrow{AB}=(a_1，a_2)=A\)。

运算与性质：

• 判等：两点坐标重合。

il int dcmp(double a){
    if(a<-eps)	return -1;
    if(a>eps)	return 1;
    return 0;
}
il bool operator==(node a,node b)<% return !dcmp(a.x-b.x) && !dcmp(a.y-b.y); %>

• 加减：\(A+B=(a_1,a_2)+(b_1,b_2)=(a_1+b_1,a_2+b_2)\)。

il node operator+(node a,node b)<% return node(a.x+b.x,a.y+b.y); %>
il node operator-(node a,node b)<% return node(a.x-b.x,a.y-b.y); %>

• 模长：\(|A|=\sqrt{a_1^2+a_2^2}\)。

il double len(node a)<% return sqrt(dot(a,a)); %>
//dot是点乘函数

• 角度：\(\tan \theta =\frac{a_2}{a_1},\theta =arctan \frac{a_2}{a_1}\)

• 数乘：\(k\times A=k\times (a_1,a_2)=(ka_1,ka_2)\)。

il node operator*(node a,double k)<% return node(a.x*k,a.y*k); %>

• 点乘：\(A\cdot B=(a_1,a_2)\cdot (b_1,b_2)=a_1b_1+a_2b_2\)。

（几何意义：\(A\) 乘上 \(B\) 在 \(A\) 上的投影，即\(|A|\times |B|\times cos \Theta\))

il double dot(node a,node b)<% return a.x*b.x+a.y*b.y; %>

• 夹角：\(\cos \theta=\frac{A\cdot B}{|A|\times |B|}\)。

il double angle(node a,node b)<% return acos(dot(a,b)/len(a)/len(b)); %>

• 若 \(A\cdot B=0\)，（\(A,B\) 不为0）则 \(A\) 与 \(B\) 垂直，\(>0\) 为锐角，\(<0\) 为钝角。

• 叉积：\(A\times B=\begin{vmatrix} a_1&b_1\\a_2&b_2 \end{vmatrix}=a_1b_2-b_1a_2=-B\times A\)。

（几何意义：叉积的绝对值=面积）

il double cro(node a,node b)<% return a.x*b.y-a.y*b.x; %>

• 面积：\(|A\times B|=|A||B|\sin \theta\)。

• 旋转：将 \(A\) 旋转 \(\alpha\) 弧度得到 \(A'\)：

\(A=(a_1,a_2)=r(\cos\theta,\sin\theta);\)

\(A'=r(\cos(\theta+\alpha),\sin(\theta+\alpha)=r(\cos\theta \cos\alpha-\sin\theta \sin\alpha,\cos\theta \sin\alpha+sin\theta \cos\alpha)\)

\(=(a_1 \cos\alpha-a_2 \sin\alpha,a_1 \sin\alpha+a_2 \cos\alpha)\)

直线一般形式有四：

其中，\(k\) 是直线的斜率，\(k=\frac{y_2-y_1}{x_2-x_1}=tan \alpha\)，\(b\) 是直线的截距。

特别地，当两条直线垂直时有 \(k1\times k2=-1\)。

而线段，在代码中往往可以这样表示：

struct Node{double x,y;};
struct line{node p1,p2;};

有以下运算：

• 判断点 \(P\) 是否在直线 \(AB\) 上。

il int judge_LINE(Node p,Node a,Node b)<% return !mystd::dcmp(Vector::cro(p-a,b-a)); %>

• 判断点 \(P\) 是否在线段 \(AB\) 上。

il int judge_line(Node p,Node a,Node b)<% return !mystd::dcmp(Vector::cro(p-a,b-a)) && mystd::dcmp(mystd::fMin(a.x,b.x)-p.x)<=0 && mystd::dcmp(mystd::fMax(a.y,b.y)-p.y)<=0; %>

• 求点 \(P\) 到直线 \(AB\) 的垂足。

il Node footnode(Node p,Node a,Node b){
		Node x=p-a,y=p-b,z=b-a;
		double len1=Vector::dot(x,z)/Vector::len(z),len2=-1.0*Vector::dot(y,z)/Vector::len(z);
		return a+z*(len1/(len1+len2));
	}

证明：见图。

• 求点 \(P\) 到直线 \(AB\) 的对称点：

il Node symmetry(Node p,Node a,Node b)<% return p+(footnode(p,a,b)-p)*2; %>

double multi(node p1, node p2, node p0) {
    double x1, y1, x2, y2;
    x1 = p1.x - p0.x;
    y1 = p1.y - p0.y;
    x2 = p2.x - p0.x;
    y2 = p2.y - p0.y;
    return x1 * y2 - x2 * y1;
}