• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

计算几何基础知识

向量,极坐标

基础高中课本要讲一下。oiwiki链接:矢量,极坐标。

平面向量在计算几何中一般用坐标来描述。\((x,y)\)是指起点为\((0,0)\),终点为\((x,y)\)的平面向量。

所以我们也可以用点来描述向量。

以下公式最好理解为起点为\((0,0)\)终点为\((x,y)\)的“箭头”。

基本操作:

Set \(\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\)的点积。

以上矢量运算都是二维平面意义上的。

在三维空间中,我们有空间向量。即三维空间中的向量,类似于平面向量。我们也可以用一个点的坐标来描述一个空间矢量。

Set \ (\ bold a (x _ 1,y _ 1,z _ 1),\ bold b (x _ 2,y _ 2,z _ 2) \)。当\(z\)的值相等时,上述二维运算可视为空间向量\(\bold A,\bold B\)的运算。

向量\(\bold A,\bold B\)的叉积定义为\(\ bold A \乘以\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\)决定。根据右手定则(用来看叉积的方向),我们可以得出结论:

If \(x_1y_2-x_2y_10\)

然后在\((x,y,0)(x\in \R,y\in \R)\)平面内顺时针\(\bold A\)旋转\(\theta\)度得到\(\bold B\)。

相反,\(\bold B\)是在\((x,y,0)(x\in \R,y\in \R)\)平面内逆时针旋转\(\theta\)度得到的。

\(x_1y_2-x_2y_1=0\),它们重合。

像这样

OpJbGR.png

\(\bold A\times\bold C0,\bold A\times\bold B0\)

极角排序

建立以\(O\)为极点,以\(Ox\)为极轴的极坐标系统,正方向定义为逆时针方向。

设$ (x,y)$是一个点\(A\)(可以看作一个向量),那么这个点的极角是\(\angle xOA\)。

一种方法是直接用\(atan2\)函数求极角进行排序,但是运算的结果是double,只能说什么都知道了。

另一种方法是先找出极角的终端边缘在哪个象限,然后用十字乘法求解。

画四个象限好像很麻烦。

因为十字乘法的应用范围是\([0,\pi)\)。所以我们只需要把一个平面分成两部分。如果两个点落在同一个部分,那么我们可以用十字乘法来求解,如果落在不同的部分,我们可以根据自己的定义直接判断。

比如我们想让第四象限的角\ (\),第一象限的角\ (\)和第二象限的角\ (\)为第三。

那么我们把\([-x,x)\)分成第一部分,(\(x\)代表\(x\)半轴,\(-x\)是负半轴),另一部分是第二部分。如果两个点落在第一部分,则通过交叉乘法计算,if \ (\)

如果它落在不同的部分,根据我们的定义,第一部分比第二部分小。

凸包

这个oiwiki很详细,所以我很懒。凸包

闵可夫斯基和

看我写的这个:

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now