计算几何入门

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}$,也可以用字母abuv等表示(印刷体为加粗,手写体上面要加箭头)。

在直角坐标系上,向量也可以用数对的形式表示。向量(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>。

未完待续

评论

此博客中的热门博文