计算几何总结.doc

计算几何一、向量基础知识1、向量的点乘 (Dot Product)与高中数学课本的定义类似，但是略有不同，我们将用代数的语言来定义点乘。两个同维向量和的点乘定义为：其结果是一个实数。在平面上和空间中，它的几何意义是：和的点乘是的模和在上射影的模的乘积，就是：这里是和的夹角，这和高中数学课本是一致的。于是，我们可以求两个向量的夹角：当然，这一条性质仍然保持不变。2、向量的叉乘 (Cross Product)严格的说，两个向量的叉乘是三维向量的二元运算。两个三维向量和的叉乘定义为(这里是空间的三个基底)：其结果仍然是一个三维向量。向量叉乘的几何意义是：(1)它垂直于所在的平面；(2)它的模等于以为邻边构成的平行四边形的面积，即；(3)它的方向根据右手定则判定：将右手四个手指按照到的方向收拢，则大拇指的方向就是积的方向。退一步，在平面上，我们不严谨的定义叉乘，实际上是认为两个向量的为0，并认为所得的结果不是一个向量，而是一个数值，就是说，如果和，那么我们认为，这个数的绝对值是以为临边构成的平行四边形的面积。根据向量叉乘的值正负，我们可以判定两个平面向量的旋转关系(顺时针或逆时针)，实际上是根据右手定则判断的。如果，那么从转到是逆时针；如果，那么从转到是顺时针；如果，顺时针和逆时针旋转是一样的。二、计算几何基础算法1、三角形面积。当然，还有其他的许多方法，包括大家熟知的以及Hero公式。Hero公式是令，则。2、多边形面积计算按逆时针顺序构成的多边形的面积(设)，看成多个三角形的面积和(面积有正负)：写成表达式就是：3、点线距离点到直线的距离：所以要判定一个点是否在一条直线上，可以检查点线距离是否为0。4、点面距离设，点到平面的距离如下计算：所以要判定一个点是否在一个平面上，可以检查点面距离是否为0。5、点在直线的同侧只能考虑二维的情形。检查是否在直线的同侧，只要考察是否同号。6、点在线段上检查是否在线段上，可以检查是否成立。当然也可以先判定是否在直线上，然后检查分的比是否在0到1之间，或者看的坐标是否位于端点坐标之间。7、点在凸多边形内部要检查是否在一个凸多边形内部，找一个肯定在凸多边形内部的点(比如所有顶点的平均点)。然后检查是否在每条边所在的直线的同侧。8、两条直线相交在平面上，就是检查是否不平行。在空间中，两条直线相交当且仅当共面且不平行。 9、两条线段相交在平面上，两条线段相交当且仅当在异侧且在异侧。三维的情形，解方程(是未知的)，如果有解，且满足，则两个线段相交于满足。10、两条直线的交点解方程，实际上是把两条直线写成方向向量的参数方程求解。11、检查多边形的凸性按照顺时针的方向检查每个三元对，如果所有的这样的三元对都满足是正数，则多边形是凸的。12、点在非凸多边形内部判定一个点是否在一个多边形内部，从该点引出一条射线，满足射线与多边形的交点非多边形的顶点，考察射线与多边形的公共点个数，点在一个多边形内部当且仅当公共点个数为奇数。这个方法在高维的情形下也是适用的。 三、凸包给出一些平面上的点，找一个面积最小的凸多边形，使得所给的点都不在这个凸多边形的外部。这个凸多边形叫做这些点的凸包。下图是凸包的一个例子。求二维凸包有许多方法。这里，我们先介绍一种“卷包裹法”(Gift-wrapping)，是最简单的方法。将一个肯定在凸包上的点(例如，纵坐标最小者，当不止一个时，取横坐标最大者)记为，从出发，向右做一条水平射线，以为中心将该射线逆时针旋转，直到接触到某个点(如果碰到多个点，选个最远的)，则也为凸包的一个顶点，再以为中心，这样下去直到该射线又接触到。这样得到的即为凸包的n个顶点。这样的过程类似于卷包裹直到把点集中的点都卷入为止。射线的倾斜角可以通过反正切求得。对于每个旋转中心，我们都要判断对于哪一个点，倾斜角最小的，这需要的时间。由于可能有n个点都要这样进行，所以这样算法的复杂度是，虽然复杂度比较高，但是有很好的推广性，高维的凸包也可以这样做。下面介绍复杂度低一些的Graham扫描法，也是容易编程和容易记忆的。这个算法的基本思想是按着顺时针或者逆时针的方向加点，检查是否存在大于的角被建立，这将使得多边形变成凹的。如果有三个点形成超过的角，则删去中间的那个点。检查角度可以通过计算相邻两边的叉乘完成。寻找凸包： 计算每个点的角度(与中心和x轴形成的角)排序(0到) 加入头两个点 对于每个其它点(不是最后一个点) 使它是凸包的下一个点 检查它与前面两个点是否形成超过的角o 不断删去前一个点，直到不出现超过的角 加入最后一个点o 执行上述的删除操作o 检查最后一个点和倒数第2个点以及前一个点是否形成超过的角；检查头两个点和最后一个点是否形成超过的角o 如果第一种情况为真，删去最后一个点，继续检查o 如果第二种情况为真，删去第一个点，继续检查o 如果两种情况都不真，停止加入点是线型的时间，所以运行时间基于排序的复杂度。所以这个方法的复杂度是。 下面是伪代码：#x(i),y(i)是第i个点的坐标#zcrossprod(v1, v2)是向量v1,v2的叉乘1(midx,midy)=(0,0)2Forallpointsi3(midx,midy)=(midx,midy)+ (x(i)/npoints,y(i)/npoints)4Forallpointsi5angle(i)=atan2(y(i)-midy, x(i)-midx)6perm(i)=i7sortpermbasedontheangle()values#i.e.,angle(perm(0)1andzcrossprod(hull(hullpos-2)- hull(hullpos-1), hull(hullpos-1)-p)1andzcrossprod(hull(hullpos-2)- hull(hullpos-1), hull(hullpos-1)-p)=2and zcrossprod(p- hull(hullpos-1), hull(hullstart)-p)=2and zcrossprod(hull(hullstart)-p, hull(hullstart-1) - hull(hullstart)= 0 # Let R = ax + by + c = 0 and R” = ax + by + c 0, L : ax + by + c = 0 # P stores the vertices of Q. 1 if head = 0 then return nil 2 x = nexthead 3 while (x head) and (px in R) do 4 x = nextx 5 if (px in R) then 6head = 0 7return 8 head = aa = x 9 aa = x10 bb = nextx11 while (aa bb) and (pbb in R)12x = bb;13bb = nextbb;14 if aa = bb then exit;15 get the intersection I(ix, iy) of L and the segment pbb-px16 if (point I is not px) then17last = last + 118nextx = last19x = last20px = I21nextx = bb22 xx = qq = x23 while (pbb in R”) do24qq = bb25bb = nextbb26 get the intersection I(ix, iy) of L and the segment pbb-pqq27 if (point I is not px) then28last = last + 129px = I30nextlast = bb31nextxx = last32 if nextnexthead = head33head = 0利用分治法也可以解决这个问题。因为：两个括号表示个半平面的交，它们至多是条边的凸多边形区域，我们合并这样的两个多边形区域需要时间，所以我们的分治算法的时间复杂度是。分治算法：输入n个半平面S1,Sn输出它们的交将n个半平面分成两个大小近似相等的集合递归的构造凸多边形区域A和A合并A和A六、应用举例例1、Hotter and Colder (Waterloo local contest)A和B在的棋盘上进行一个游戏。A确定一个点P，B每回合移动一次。每次A都会告诉B，他当前所处的位置是离P更近了(Hot)还是更远了(Cold)，或者是距离不变(Same)。请在A每次回答后，确定P点可能存在的区域的面积。解：假设B从移动到了，A回答Hot。则点所处的位置满足，即：类似地，回答Cold对应于另一个不等式。回答Same对应于一个等式，这将导致P点可能存在的区域的面积为0。初始时可能的区域是。每回合后都用相应的不等式对应的半平面与当前区域求交，并输出交的面积。例2、Triathlon (NEERC 2000)n名选手参加铁人三项赛，比赛按照选手在三个赛段中所用的总时间排定名次。已知每名选手在三个项目中的速度。问对于选手i，能否通过适当的安排三个赛段的长度(但每个赛段的长度都不能为0)，来保证他获胜。解：假设三个赛段的长度分别为，则选手i获胜的充要条件就是：对于都成立。移项，两边同除以z，令。我们把上式改写为：本题就转化为求这个不等式对应的半平面的交，并判断其面积是否大于0。七、最小包含球问题给出n个在平面上的点构成的集合P，设为覆盖这些点得半径最小圆及其内部。我们允许，此时，当时也是如此。容易看出，这样一个圆是唯一的：假设和是两个最小圆，具有相同的半径r，圆心分别是。如果且则，被包含在D中，D具有圆心和半径，这里a是距离的一半。必须有否则就有一个更小半径的圆D包含了这些点。这就说明了重合。我们也知道用P中的至多三个在边上的点就可以确定。就是，存在P的子集S在的边界上满足和；所以如果则，或等价地，如果则，p在的边上。对于n个点构成的集合P，我们用这种称之为增加法的方法计算。从空集开始，然后不断添加P中的点，同时维护最小圆。设且假设我们已经计算了。如果则D是前点的最小圆，否则根据在的边界上，调用过程b_minidisk(A, p)，它是计算包含且在边界上的最小圆。我们有如下的伪代码：function procedure minidisk(P); comment; returns md(P) if P = thenD = elsechoose pPD = minidisk(P-p)if pD then D = b_minidisk(P-p,p) return D在我们描述b_minidisk(A,p)之前，先假设它需要来结束计算。那么，时间复杂度是什么? 我们随机的选择，则每个p被选中的概率是。设是对于执行minidisk(P)的步数。则t满足：因为至多有3个点属于P满足，而对于其他点都有，所以。于是，。过程b_minidisk和上面的差不多，但是在给出它的具体伪代码之前，我们引入一些记号，再证明一些引理。对于平面上的有限点集P和R，设是使包含P且R在边界上的最小半径圆。显然，。引理：设P和R是平面上的有限点集，P非空，且(i) 如果存在一个圆满足P属于它且R在它边界上，则是唯一的。(ii) 如果则p在的边界上，也就是：。(iii) 如果存在，则存在一个至多个点的集合S属于P满足。证明在此全部略去。注意到一般情况下，(iii)所说的集合S不是唯一的。(iii)的重要意义在于，P中有至多个点满足。(ii)告诉我们如何计算。如果，问题很简单，我们直接计算。否则，我们随即选取，计算。function procedure b_minidisk(P,R); comment; returns b_md(P,R) if P = thenD = b_md(,R) elsechoose random pPD = b_minidisk(P-p,R)if D exists and pD then D = b_minidisk(P-p,Rp) return D前面计算的过程可以被描述为：function procedure minidisk(P); comment; returns md(P) return B_MINIDISK(P,)下面我们向高维拓展。为了得到更为高效的算法，我们把P看作一个序列。先修改b_minidisk中的else部分，如下：choose last p in PD = b_mindisk(P-p,R)If pD then choose a random permutation p of 1(|P|-1) D = b_mindisk(p(P-p),Rp)操作只将p从P中移去，不影响其他元素的顺序。我们让mindisk(P)在调用b_minidisk之前选择一个P的随机排列。function procedure mindisk(P); comment; returns md(P) choose a random permutation p of 1|P| return b_mindisk(p(P), )在上面的程序中，我们要选取排列。什么样的排列是一个较好的排列呢? 当然，就是这个排列的前面几个点确定了问题的解，这样，我们可以省去很多的递归。这是理想情况，但是我们要尽量使确定解的点靠近序列的前部。于是，我们在计算的过程中，将我们认为的重要的点移动到序列的最前部。这是一个启发式的做法。function procedure MTFDISK(