欢迎来到天天文库
浏览记录
ID:37321370
大小:613.50 KB
页数:12页
时间:2019-05-21
《计算几何总结》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、计算几何一、向量基础知识1、向量的点乘(DotProduct)与高中数学课本的定义类似,但是略有不同,我们将用代数的语言来定义点乘。两个同维向量和的点乘定义为:其结果是一个实数。在平面上和空间中,它的几何意义是:和的点乘是的模和在上射影的模的乘积,就是:这里是和的夹角,这和高中数学课本是一致的。于是,我们可以求两个向量的夹角:当然,这一条性质仍然保持不变。2、向量的叉乘(CrossProduct)严格的说,两个向量的叉乘是三维向量的二元运算。两个三维向量和的叉乘定义为(这里是空间的三个基底):其结果仍然是一个三维向量。向量叉乘的几何意义是:(1)它垂直于所在
2、的平面;(2)它的模等于以为邻边构成的平行四边形的面积,即;(3)它的方向根据右手定则判定:将右手四个手指按照到的方向收拢,则大拇指的方向就是积的方向。。退一步,在平面上,我们不严谨的定义叉乘,实际上是认为两个向量的为0,并认为所得的结果不是一个向量,而是一个数值,就是说,如果和,那么我们认为,这个数的绝对值是以为临边构成的平行四边形的面积。根据向量叉乘的值正负,我们可以判定两个平面向量的旋转关系(顺时针或逆时针),实际上是根据右手定则判断的。如果,那么从转到是逆时针;如果,那么从转到是顺时针;如果,顺时针和逆时针旋转是一样的。二、计算几何基础算法1、三角形
3、面积。当然,还有其他的许多方法,包括大家熟知的以及Hero公式。Hero公式是令,则。2、多边形面积计算按逆时针顺序构成的多边形的面积(设),看成多个三角形的面积和(面积有正负):写成表达式就是:3、点线距离点到直线的距离:所以要判定一个点是否在一条直线上,可以检查点线距离是否为0。4、点面距离设,点到平面的距离如下计算:所以要判定一个点是否在一个平面上,可以检查点面距离是否为0。5、点在直线的同侧只能考虑二维的情形。检查是否在直线的同侧,只要考察是否同号。6、点在线段上检查是否在线段上,可以检查是否成立。当然也可以先判定是否在直线上,然后检查分的比是否在0
4、到1之间,或者看的坐标是否位于端点坐标之间。7、点在凸多边形内部要检查是否在一个凸多边形内部,找一个肯定在凸多边形内部的点(比如所有顶点的平均点)。然后检查是否在每条边所在的直线的同侧。8、两条直线相交在平面上,就是检查是否不平行。在空间中,两条直线相交当且仅当共面且不平行。9、两条线段相交在平面上,两条线段相交当且仅当在异侧且在异侧。三维的情形,解方程(是未知的),如果有解,且满足,则两个线段相交于满足。10、两条直线的交点解方程,实际上是把两条直线写成方向向量的参数方程求解。11、检查多边形的凸性按照顺时针的方向检查每个三元对,如果所有的这样的三元对都满
5、足是正数,则多边形是凸的。12、点在非凸多边形内部判定一个点是否在一个多边形内部,从该点引出一条射线,满足射线与多边形的交点非多边形的顶点,考察射线与多边形的公共点个数,点在一个多边形内部当且仅当公共点个数为奇数。这个方法在高维的情形下也是适用的。三、凸包给出一些平面上的点,找一个面积最小的凸多边形,使得所给的点都不在这个凸多边形的外部。这个凸多边形叫做这些点的凸包。下图是凸包的一个例子。求二维凸包有许多方法。这里,我们先介绍一种“卷包裹法”(Gift-wrapping),是最简单的方法。将一个肯定在凸包上的点(例如,纵坐标最小者,当不止一个时,取横坐标最大
6、者)记为,从出发,向右做一条水平射线,以为中心将该射线逆时针旋转,直到接触到某个点(如果碰到多个点,选个最远的),则也为凸包的一个顶点,再以为中心,…,这样下去直到该射线又接触到。这样得到的即为凸包的n个顶点。这样的过程类似于卷包裹直到把点集中的点都卷入为止。射线的倾斜角可以通过反正切求得。对于每个旋转中心,我们都要判断对于哪一个点,倾斜角最小的,这需要的时间。由于可能有n个点都要这样进行,所以这样算法的复杂度是,虽然复杂度比较高,但是有很好的推广性,高维的凸包也可以这样做。下面介绍复杂度低一些的Graham扫描法,也是容易编程和容易记忆的。这个算法的基本思
7、想是按着顺时针或者逆时针的方向加点,检查是否存在大于的角被建立,这将使得多边形变成凹的。如果有三个点形成超过的角,则删去中间的那个点。检查角度可以通过计算相邻两边的叉乘完成。寻找凸包:·计算每个点的角度(与中心和x轴形成的角)排序(0到)·加入头两个点·对于每个其它点(不是最后一个点)·使它是凸包的下一个点·检查它与前面两个点是否形成超过的角o不断删去前一个点,直到不出现超过的角·加入最后一个点o执行上述的删除操作o检查最后一个点和倒数第2个点以及前一个点是否形成超过的角;检查头两个点和最后一个点是否形成超过的角o如果第一种情况为真,删去最后一个点,继续检查
8、o如果第二种情况为真,删去第一个点,继续检查o如果两
此文档下载收益归作者所有