首页 > 代码库 > [学习笔记]计算几何基础
[学习笔记]计算几何基础
三角函数
向量
线性空间中有大小和方向的量.
坐标表示:$P(x_1,y_1),Q(x_2,y_2)$.
$\overrightarrow{PQ}=(x_2-x_1,y_2-y_1)$.
$|PQ|=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$.
向量运算
$a=(x_1,y_1),b=(x_2,y_2)$.
- 加法
$a+b=(x_1+x_2,y_1+y_2)$.
- 减法
$a-b=(x_1-x_2,y_1-y_2)$.
- 点乘
$a\;\cdot\;b=x_1x_2+y_1y_2$.
$a\;\cdot\;b=|a||b|cos<a,b>$
应用:求两向量夹角,判断是否垂直($cos90$°$=0$).
- 叉乘
$a\;\times\;b=x_1y_2-x_2y_1$.
$|a\;\times\;b|=|a||b|sin<a,b>$.
$a\;\times\;b=0$,共线.
判断线段交
$(AC\;\times\;AD)(BC\;\times\;BD)\;\leq\;0$且$(CA\;\times\;CB)(DA\;\times\;DB)\;\leq\;0$.
向量旋转
将$a(x_1,y_1)$逆时针旋转$\theta$(弧度)得到$b(x_1cos\theta-y_1sin\theta,x_1sin\theta+y_1cos\theta)$.
$P.S.$只改变方向(长度不变).记忆方法:旋转$\pi/2$得到的结果$(-y_1,x_1)$.
三点共线
夹角为$0$且$a\;\times\;b=0$.
点是否在射线上
夹角为$0$且点乘$\geq\;0$.
$<0$?反向!
多边形面积
设多边形顶点依次为$P_1,P_2,...,P_n$.
$\large{S=|\frac{\sum_{i=1}^{n-1}\overrightarrow{OP_i}\times\overrightarrow{OP_{i+1}}+\overrightarrow{OP_n}\times\overrightarrow{OP_{1}}}{2}}|$.
点到直线垂足
点到直线垂足$D,ED\;\perp\;AB$.
旋转$\overrightarrow{AB}\pi/2$.
直线求交.
圆的位置关系
$d$为两圆圆心距,$R,r$分别为两圆半径.
$d>R+r$ 外离;
$d=R+r$ 外切;
$|R – r|<d<R+r$ 相交;
$d=|R–r|$ 内切;
$d<|R–r|$内含.
点是否在凸多边形内
随机射线
推荐
http://dev.gameres.com/Program/Abstract/Geometry.htm#判断点是否在多边形中
[学习笔记]计算几何基础