算法设计与分析 第2版 第10章-计算几何.ppt

double ClosestPoints1(vectorPoint a，int leftindex， int rightindex) //求a[leftindex..rightindex]中的最近点对 { int i; vectorPoint b; sort(a.begin()，a.end()，pointxcmp); //按x坐标从小到大排序 for (i=0;ia.size();i++) //将a中点集复制到b中 b.push_back(a[i]); sort(b.begin()，b.end()，pointycmp); //按y坐标从小到大排序 return ClosestPoints11(a，b，0， a.size()-1，minindex1，minindex2); } 　　【算法分析】当求a[0..n-1]中n个点的最近点时，设执行时间为T(n)，求左右部分中最近点对的时间为T(n/2)，求中间部分的时间为O(n)，则: 　　T(n)=O(1) 当n4 　　T(n)=2T(n/2)+O(n) 其他情况 从而推出算法的时间复杂度为O(nlog2n)。 　　在二维空间中求最远点对问题与最近点对问题相似，也具有许多实际应用价值。本节介绍求解最远点对的两种算法。 10.4.1 用蛮力法求最远点对 　　用蛮力法求最远点对的过程是：分别计算每一对点之间的距离，然后找出距离最大的那一对。 double Mostdistp(vectorPoint a,int maxindex1,int maxindex2) //蛮力法求a中的最远点对 { int i,j; double d,maxdist=0.0; for (i=0;ia.size();i++) for (j=i+1;ja.size();j++) { d=Distance(a[i],a[j]); if (dmaxdist) { maxdist=d; maxindex1=i; maxindex2=j; } } return maxdist; } 【算法分析】上述算法的时间复杂度为O(n2)。 10.4.2 用旋转卡壳法求最远点对 　　旋转卡壳法的基本思想是，对于给定的点集，先采用Graham扫描法求出来一个凸包a，然后根据凸包上每条边，找到离他最远的一个点。 　　即卡着外壳转一圈，这便是旋转卡壳法名称的由来。 （a）一个凸包 （b）处理边a0a1 （c）处理边a1a2 （d）处理边a2a3 （e）处理边a3a4 （f）处理边a4a5 （g）处理边a5a0 如何求当前处理的边对应的粗边。以当前处理边为a0a1为例，如下图所示，先从j=1开始，即看a1a2是否为粗边，显然它不是的。　 找粗边的过程 需要解决两个问题 1 　　那么如何判断呢？ 对于边ajaj+1（图中j=2），由向量a1a0和a1aj构成一个平面四边形，其面积为S2，由向量a1a0和a1aj+1构成一个平面四边形，其面积为S1，由于这两个平行四边行的底相同。 找粗边的过程 如果S1S2，说明aj+1离当前处理边越远，表示边ajaj+1不是粗边，需要通过j增1继续判断下一条边，直到这样的平行四边形面积出现S1≤S2为止，此时边ajaj+1才是粗边，图中当前边a0a1找到粗边为a4a5，较大距离的点为a1和a4。 如何求平行四边行的面积。两个向量的叉积为对应平行四边行的有向面积（可能为负），通过求其绝对值得到其面积。 在下图中，S1=fabs(Det(a1，a0，a3))，S2=fabs(Det(a1，a0，a2))，其中Det是求叉积。 2 当前处理的边 粗边 都仅仅转换一圈 执行过程 3 double RotatingCalipers1(Point ch[]，int m，int maxindex1，int maxindex2) {　//由RotatingCalipers调用 　　int i，j; 　　double maxdist=0.0，d1，d2; 　　ch[m]=ch[0]; //添加起点 　　j=1; 　　for (i=0;im;i++) 　　{ while (fabs(Det(ch[i]-ch[i+1]，ch[j+1]-ch[i+1])) 　　　　　　fabs(Det(ch[i]-ch[i+1]，ch[j]-ch[i+1]))) 　　　　　 j=(j+1)%m;　 //以面积来判断，面积大则说明要离平行线远些 d1=Distance(ch[i]，ch[j]); if (d1maxdist