计算几何基础知识
2022/4/30 23:12:54
本文主要是介绍计算几何基础知识,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
计算几何基础知识
向量,极坐标
基础概念高中课本应该讲了吧 贴下 oiwiki 链接:向量,极坐标
平面向量在计算几何中一般用坐标来描述,\((x,y)\) 表示的是起点在 \((0,0)\),而终点在 \((x,y)\) 的平面向量。
所以我们也可以用点来描述向量。
理解下文的式子最好都将向量看成起点在 \((0,0)\),终点在 \((x,y)\) 的一个”箭头“。
基本运算:
设 \(\bold A (x_1,y_1)\),\(\bold B(x_2,y_2)\) 。
那么有:
\(\bold A+\bold B=(x_1+x_2,y_1+y2)\)。
\(\bold A-\bold B=(x_1-x_2,y_1-y_2)\)。
所以点的加减法可以理解成其表示向量的加减法。
而加减法的结果都是向量。
如果\(\bold A,\bold B\) 的夹角为 \(\theta\) 。那么有:
\(\bold A \cdot \bold B=|\bold A||\bold B|\cos\theta\)。
我们称其为 \(\bold A,\bold B\) 的点积。
以上我们的向量的运算都是在二维平面意义下的。
而在三维空间中我们有空间向量。也就是三维空间下的向量,类似平面向量,我们同样可以用一个点的坐标来描述空间向量。
设 \(\bold A(x_1,y_1,z_1),\bold B(x_2,y_2,z_2)\)。而上述二维平面下的运算,我们可以看成是空间向量 \(\bold A,\bold B\) 在 \(z\) 值相等时的运算。
定义向量 \(\bold A,\bold B\) 的向量积为 \(\bold A\times \bold B\)。其结果是一个向量。
这个玩意儿在平面上的应用就是用来判断两个向量的关系位置。
因为 \(\bold A\times \bold B =(y_1z_2-y_2z_1,z_1x_2-z_2x_1,x_1y_2-x_2y_1)\)。
设 \(\bold A,\bold B\) 之间的夹角为 \(\theta(\theta<\pi)\) ,且他们的 \(z\) 均为 \(0\)。
那么 \(\bold A\times \bold B=(0,0,x_1y_2-x_2y_1)\)。
易知向量积的方向由 \(x_1y_2-x_2y_1\) 决定。又根据右手定则(用来看向量积方向的),我们可以得出结论:
如果 \(x_1y_2-x_2y_1>0\)
那么 \(\bold B\) 就由 \(\bold A\) 在 \((x,y,0)(x\in \R,y\in \R)\) 平面内顺时针旋转 \(\theta\) 度得到。
反之,\(\bold B\) 就由 \(\bold A\) 在 \((x,y,0)(x\in \R,y\in \R)\) 平面内逆时针旋转 \(\theta\) 度得到。
\(x_1y_2-x_2y_1=0\) 时他俩重合奥。
就像这样
\(\bold A\times\bold C>0,\bold A\times\bold B<0\)
极角排序
建立极坐标系,以 \(O\) 为极点,\(Ox\) 为极轴 ,正方向定义为逆时针方向。
设 $ (x,y)$ 为一个点 \(A\) (看做一个向量也行),那么这个点的极角是 \(\angle xOA\)。
一种做法是直接利用 \(atan2\) 函数求出极角进行排序,不过运算结果是 double,只能说懂得都懂。
还有一种做法就是先求出极角终边在哪个象限,然后利用叉乘求解。
划成四个象限似乎有些麻烦。
因为叉乘的应用范围是 \([0,\pi)\)。所以我们只要将一个平面划为两部分。如果两个点落在同一部分,那么利用叉乘求解,落在不同部分我们就根据自己定义来直接判断即可。
举个例子,如果我们要让 第四象限的角 \(<\) 第一象限的角 \(<\) 第二 \(<\) 第三。
那么我们将 \([-x,x)\) 划为第一部分,(\(x\) 代表 \(x\) 半轴,\(-x\) 就是负半轴),另一块是第二部分,如果两个点落在第一部分,那么用叉乘计算,如果 \(\bold A\times \bold B>0\) ,那么 \(\bold A\) 的极角小于 \(\bold B\) 的极角。
如果落在不同部分,根据我们的定义,第一部分的就小于第二部分。
凸包
这一块 oiwiki 讲的很详细了,我偷个懒。凸包。
闵可夫斯基和
看我写的这篇:
这篇关于计算几何基础知识的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!