计算几何入门

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,那么\(\vec{OC}\)=\(\vec{OA}\)+\(\frac{k}{k+1}\vec{AB}\)=\(\vec{OA}\)+\(\frac{k}{k+1}\)(\(\vec{OB}\)-\(\vec{OA}\))=\(\frac{1}{k+1}\vec{OA}\)+\(\frac{k}{k+1}\vec{OB}\),由此就可以得证了。

3.直线

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

4.多边形

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

5.园

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

6.向量

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

向量的表示

向量可以形象化地表示为带箭头的线段。如果给点了起点A与终点B,则向量可以表示为\(\vec{AB}\),也可以用字母abuv等表示(印刷体为加粗,手写体上面要加箭头)。

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

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

向量的运算

加减法

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

ab=(x1-x2,y1-y2)

乘除法

ka=(kx,ky)

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

夹角

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

未完待续

发表评论

电子邮件地址不会被公开。 必填项已用*标注