计算几何总结

《计算几何总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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如果两