计算几何入门
PS:Latex加载可能有点慢
首先提一下精度问题
计算几何题目中常常不可避免的需要使用浮点数,而浮点数运算会带来精度误差,因此我们在比较浮点数的时候不能像整数那样直接比较,需要引入一个极小值eps(一般取1e-6)。两个数之间的等价关系就可以由如下所示的方法表示:
a=b:|a-b|<eps
a>b:a-b>eps
a<b:b-a>eps
对于平面几何问题,我们一般都是在平面直角坐标系上进行计算的,因此我们一般用(x,y)表示。
使用线段的两个端点来表示,也可以用点+向量的形式来表示。
对于线段上的任意点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}$,由此就可以得证了。
虽然我们可以用直线方程来表示一条直线,但是在计算几何中往往使用几何方法比使用代数方法更为简便。因此直线与线段一样,常使用直线上两个不同点或点+向量来表示。当然,直线方程在某些情况还是有一些用的。
通常按逆时针或顺时针的顺序存储多边形上所有的点,有时也会按顺序存边及起点。
通常存储圆心坐标及半径。计算时可使用几何方法或圆方程求解。
线性空间中有大小与方向的量。
向量可以形象化地表示为带箭头的线段。如果给点了起点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>。
未完待续
首先提一下精度问题
计算几何题目中常常不可避免的需要使用浮点数,而浮点数运算会带来精度误差,因此我们在比较浮点数的时候不能像整数那样直接比较,需要引入一个极小值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>。
未完待续
评论
发表评论