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