第8章 数论算法及计算几何算法ppt课件.ppt

、问题提出给定一个点集S={P0,P1,…,Pn-1},它的凸包是一个最小的凸多边形P,且满足S中的每个点或者在P的边界上或者在P的内部。如果点集S是两个点的集合,显然它的凸包是连接这两个点的线段;如果S是由三个不共线的点组成的集合,那么凸包是以这三个点为顶点的三角形;如果三点共线,则凸包是以距离最远的两个点为端点的线段。对于更大的集合,在直观上,可以把S中的每个点看作订在地上的木桩,那么凸包就是将所有木桩围起来的一个拉紧的橡皮绳的形状,如图8-1所示。.解决方法:1、穷举搜索法2、、算法思想:根据凸多边形的定义,对于一个由n个点组成的集合S中的任意两个点Pi和Pj,当且仅当该集合中的其它点要么位于穿过Pi和Pj直线的同侧,要么位于线段PiPj上。则线段PiPj是该集合凸多边形边界的一部分。对每一个点都做一遍检验之后,满足条件的线段就构成了该凸包的边界。、算法求解步骤:步骤1:对于集合中的任意两点Pi和Pj,定义穿过两点Pi和Pj的直线方程。(x-xi)/(xj-xi)=(y-yi)/(yj-yi)步骤2:将点集S中的其余点代入直线方程,然后检查是否位于线段同侧,如果不是,说明线段PiPj不是点集S的凸多边形的边界。否则,PiPj是凸多边形的边界。步骤3:对点集中的每个点,重复上述步骤1和步骤2,直到找出全部多边形的边界。.3、算法程序语言描述详见课本4、算法分析点集中的点构成的线段数目最多为n(n-1)/2,对每一条线段,最坏情况要检查点集中其余n-2个点属于哪个半平面,故算法的时间复杂性为O(n3).、算法思想将点集S中的点按照x坐标升序排序,x坐标相同的按照y坐标升序排序,排好序的序列存放在点结构数组P中。那么最左边的点P0、最右边的点Pn-1肯定是凸包上的点。线段P0Pn-1将集合S中的点分成两个集合S1和S2。.子集S1的凸包由线段P0Pn-1作为下边界、多节链条作为上边界组成。这条上边界称为上包。子集S2的凸包由线段P0Pn-1作为上边界、多节链条作为下边界组成。这条下边界称为下包。整个集合的凸包由上包和下包构成。如图8-2所示。.2、算法求解步骤构造上包步骤:找到子集S1中的点Pmax,它是距离线段P0Pn-1最远的点连接,找出S1中位于直线左边的点,这些点构成集合S11;找出S1中位于直线左边的点,这些点构成集合S12;△P0PmaxPn-1内部的点不予考虑。递归构造S11和S12的上包,然后简单地将它们连接起来,得到S1的上包。构造下包步骤:找到子集S2中的点Pmin,它是距离线段P0Pn-1最远的点连接,找出S2中位于直线右边的点,这些点构成集合S21;找出S2中位于直线右边的点,这些点构成集合S22;△P0PminPn-1内部的点不予考虑递归构造S21和S22的下包,然后简单地将它们连接起来,得到S2的下包。.3、算法程序语言描述详见课本.