计算几何入门

PS：Latex加载可能有点慢

首先提一下精度问题

计算几何题目中常常不可避免的需要使用浮点数，而浮点数运算会带来精度误差，因此我们在比较浮点数的时候不能像整数那样直接比较，需要引入一个极小值eps（一般取1e-6）。两个数之间的等价关系就可以由如下所示的方法表示：

a=b：|a-b|<eps

a>b：a-b>eps

a<b：b-a>eps

一、基础概念

1.点

对于平面几何问题，我们一般都是在平面直角坐标系上进行计算的，因此我们一般用(x,y)表示。

2.线段

使用线段的两个端点来表示，也可以用点+向量的形式来表示。

对于线段上的任意点C，满足C=pA+(1-p)B(p∈[0,1])。

证明如下：

在三角形OAB中，我们设AC=kBC，那么$latex \vec{OC}$=$latex \vec{OA}$+$latex \frac{k}{k+1}\vec{AB}$=$latex \vec{OA}$+$latex \frac{k}{k+1}$($latex \vec{OB}$-$latex \vec{OA}$)=$latex \frac{1}{k+1}\vec{OA}$+$latex \frac{k}{k+1}\vec{OB}$，由此就可以得证了。

3.直线

虽然我们可以用直线方程来表示一条直线，但是在计算几何中往往使用几何方法比使用代数方法更为简便。因此直线与线段一样，常使用直线上两个不同点或点+向量来表示。当然，直线方程在某些情况还是有一些用的。

4.多边形

通常按逆时针或顺时针的顺序存储多边形上所有的点，有时也会按顺序存边及起点。

5.园

通常存储圆心坐标及半径。计算时可使用几何方法或圆方程求解。

6.向量

线性空间中有大小与方向的量。

向量的表示

向量可以形象化地表示为带箭头的线段。如果给点了起点A与终点B，则向量可以表示为$latex \vec{AB}$，也可以用字母a，b，u，v等表示（印刷体为加粗，手写体上面要加箭头）。

在直角坐标系上，向量也可以用数对的形式表示。向量(x,y)表示从(0,0)到(x,y)的向量。

向量的长度叫做向量的模长，记作|a|。

向量的运算

加减法

a+b=(x1+x2,y1+y2)

a-b=(x1-x2,y1-y2)

乘除法

ka=(kx,ky)

a/k=(x/k,y/k)

夹角

对于两个非零向量a,b，在空间中取一点O作$latex \vec{OA}$=a，$latex \vec{OB}$=b，则$latex \angle{AOB}$叫做向量a，b的夹角，记作<a,b>。

未完待续