文档介绍：第八章数论算法及计算几何算法
凸包问题
1、问题提出
给定一个点集S={P0,P1,…,Pn-1},它的凸包是一个最小的凸多边形P,且满足S中的每个点或者在P的边界上或者在P的内部。
如果点集S是两个点的集合,显然它的凸包是连接这两个点的线段;
如果S是由三个不共线的点组成的集合,那么凸包是以这三个点为顶点的三角形;
如果三点共线,则凸包是以距离最远的两个点为端点的线段。
对于更大的集合,在直观上,可以把S中的每个点看作订在地上的木桩,那么凸包就是将所有木桩围起来的一个拉紧的橡皮绳的形状,如图8-1所示。
解决方法: 1、穷举搜索法 2、分治法
1、算法思想:
根据凸多边形的定义,对于一个由n个点组成的集合S中的任意两个点Pi和Pj,当且仅当该集合中的其它点要么位于穿过Pi和Pj直线的同侧,要么位于线段PiPj上。则线段PiPj是该集合凸多边形边界的一部分。对每一个点都做一遍检验之后,满足条件的线段就构成了该凸包的边界。
2、算法求解步骤:
步骤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)
1、算法思想
将点集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、算法程序语言描述
详见课本