计算几何学习笔记

引入

计算几何和解析几何不同,计算几何算法非常简介,仅限于加、减、乘以及比较运算,还非常容易推广到高维的情况。

只有加、减、乘以及比较运算可以有效的减少计算机浮点数运算所带来的误差。

两个概念

叉积

定义

用于判断有公共端点\(P_0\)的两个向量\(\vec{a}\)和\(\vec{b}\)的螺旋方向。

设两个向量\(\vec{a}=(x_a,y_a)\),\(\vec{b}=(x_b,y_b)\)。

如果两个向量都在第一象限内,我们可以直接通过斜率来判断:\(\frac{y_b}{x_b}>\frac{y_a}{x_a}\)

    但是这个式子有除法,有很多问题需要处理。于是我们考虑通分上面的式子,并定义这样的运算为叉积:\(\vec{a}\times \vec{b}=x_ay_b-x_by_a=-\vec{b}\times \vec{a}\)。

    显然,如果\(\vec{a}\times \vec{b}>0\)说明\(\vec{a}\)到\(\vec{b}\)是逆时针旋转。

    几何意义

    很显然的\(|\vec{a}\times \vec{b}|=|\vec{a}||\vec{b}|sin\theta (0\le \theta <\pi)\)

    这样就能看出来,叉积的几何意义就是两个向量作为两条邻边的平行四边形面积。

    点积

    定义

    向量\(\vec{A}(x_1,x_2,\cdots ,x_n)\),\(\vec{B}(x‘_1,x’_2,\cdots ,x‘_n)\)

    点积\(\vec{A}\cdot \vec{B}=\sum_{i=1}^{n}x_ix’_i\)(点积的结果是标量)

    几何意义

    \(|\vec{A}\cdot \vec{B}|=|\vec{a}||\vec{b}|cos\theta (0\le \theta <\pi)\)

    这样以来就可以利用反函数来计算\(\theta\)。

    多边形类

    误差修正eps

    • cmp(x)函数用于\(x\)的符号。

    点类

    • sqr(x)计算\(x\)的平方
    • det 计算两个向量的叉积
    • dot 计算两个向量的点积
    • dist 计算两个点的距离
    • rotate_point(p,A) 计算向量\(\vec{op}\)绕原点逆时针旋转弧度A

     

     

     


    发表评论

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