首页 > 代码库 > [学习笔记]计算几何基础

[学习笔记]计算几何基础

三角函数

技术分享

向量

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

坐标表示:$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#判断点是否在多边形中

[学习笔记]计算几何基础