tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 其它 >>

第8章 数论算法及计算几何算法


第八章 数论算法及计算几何算法

8.5 凸包问题
1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点或者在P 的边界上或者在P的内部。 ? 如果点集S是两个点的集合,显然它的凸包是连接这 两个点的线段; ? 如果S是由三个不共线的点组成的集合,那么凸包是 以这三个点为顶点的三角形; ? 如果三点共线,则凸包是以距离最远的两个点为端 点的线段。 ? 对于更大的集合,在直观上,可以把S中的每个点看 作订在地上的木桩,那么凸包就是将所有木桩围起 来的一个拉紧的橡皮绳的形状,如图8-1所示。

图8-1 凸包示例

解决方法: 1、穷举搜索法 2、分治法

8.5.1凸包问题的穷举搜索法
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)

8.5.2凸包问题的分治法
1、算法思想 将点集S中的点按照x坐标升序排序,x坐标相同的 按照y坐标升序排序,排好序的序列存放在点结构 数组P中。 那么最左边的点P0、最右边的点Pn-1肯定是凸包上 的点。 线段P0Pn-1将集合S中的点分成两个集合S1和S2。

? 子集S1的凸包由线段P0Pn-1作为下边界、多节链条作 为上边界组成。这条上边界称为上包。 ? 子集S2的凸包由线段P0Pn-1作为上边界、多节链条作 为下边界组成。这条下边界称为下包。 ? 整个集合的凸包由上包和下包构成。如图8-2所示。
上包

Pn-1 P0

下包 图8-2 凸包的上包和下包

2、算法求解步骤
构造上包步骤: ? 找到子集S1中的点Pmax,它是距离线段P0Pn-1最远的点 ? 连接 P0 Pmax Pmax Pn ?1 ,找出S1中位于直线 P0 Pmax 左边的点, Pmax Pn ?1 这些点构成集合S11;找出S1中位于直线 左边的 点,这些点构成集合S12;△P0PmaxPn-1内部的点不予考 虑。 ? 递归构造S11和S12的上包,然后简单地将它们连接起来, 得到S1的上包。 构造下包步骤: ? 找到子集S2中的点Pmin,它是距离线段P0Pn-1最远的点 ? 连接 P0 Pmin Pmin Pn ?1 ,找出S2中位于直线 P0 Pmin 右边的点, Pmin Pn ?1 这些点构成集合S21;找出S2中位于直线 右边的 点,这些点构成集合S22;△P0PminPn-1内部的点不予考 虑 ? 递归构造S21和S22的下包,然后简单地将它们连接起来, 得到S2的下包 。

3、 算法程序语言描述 ? 详见课本

8.6最接近点对问题
1、问题提出 ? 最接近点对问题要求给定平面上n个点组成的集 合S,找出其中n个点组成的点对中距离最近的一 对点 。 ? 该问题具有很大的实际应用价值,例如,一个控 制空中或者海上交通的系统就需要了解2个最近的 交通工具,以预测可能产生的相撞事故。 2、解决问题方法 ? 穷举搜索、分治法(略)

8.6.1最接近点对问题的穷举搜索法
1、算法思想 分别计算点集中每一对点的距离Dij,从中找出值最小的那 对点。 为了避免点对的重复计算,算法只考虑i<j的情况. 2、算法描述
Double shortdis( ) {double temp=∞,d=0; for(int i=0; i<n-1;i++ ) for(int j=i+1; j<n,j++ ) d=sqrt( (pow( p[i].x-p[j].x)) , 2)+pow((p[i].y-p[j].y),2 ); if(d<tempt) {tempt=d; p1=p[i]; p2=p[j]; } }

3、算法分析
从算法描述可知循环体内的时间是常数时间,循环 次数 n(n ? 1) ,
2

因此算法的时间复杂性为O(n2) 。

8.6.2最接近点对问题的分治法
1、算法思想 将所给平面上的n个点的集合S分成规模大致相等 的两个子集S1和S2。递归求解S1和S2中的最接 近点对; 集合S中的最接近点对: 或者是子问题S1的解; 或者是子问题S2的解, 或者是一个点在S1中,一个点在S2中的情况组成 的最接近点对。

? 一维情形下最小点对: ? 算法描述:
Step1:用xm将x1,x2,…,xn分成两部分S1和S2 Step2:递归求S1中最接近点对,其距离为d1; Step3:递归求S2中最接近点对,其距离为d2; Step4:求S1中的最大值p,S2中的最小值q; Step5:计算d3=|p-q|; Step6:比较d1,d2,d3确定哪个是最接近点对。

? 算法分析
O(1) ? T ( n) ? ? ?2T ( n / 2) ? O( n)
解此递归方程可得T(n)=O(nlogn)。

n?3 n?3

? 二维情形 ? 算法描述:
Step1:选取一垂直线l:x=xm作为分割线。其中xm为S中 各点x坐标的中位数。由此将S分割为S1和S2 Step2:递归求S1中最接近点对,其距离为d1 Step3:递归求S2中最接近点对,其距离为d2 Step4:令d=min(d1,d2) Step5:找出S1中的某个点p和S2中的某个点q组成的点对 (p,q) (难点) Step6:比较|p-q|,d1,d2确定哪个是最接近点对

? 思考:如何找出点对(p,q) ?
– 如果|p-q|小于d,则p点分布在P1带形区域内(左虚线和 分割线l所夹的区域),q点分布在P2带形区域内(右虚线和 分割线l所夹的区域)。如图8-5所示

d

l

d

d

l

d P2

P1
P2
p

2d

P1

x=xm
图8-5 距离直线l的距离小于d的所有点

x=xm
图8-6 包含点q的d× 2d矩形区R

? 对于P1中任意一点p,与它距离小于d的点 分布在以p点为圆心,以d为半径的圆内。 因此,与点p构成最接近点对的P2中的点一 定落在一个d×2d的矩形R中。如图8-6所示。

? 由d的意义可知,矩形R中任何 两个S中的点的距离都大于等于 d。由此可知,至少可以将 d×2d的矩形R分割成如图8-7 所示的六部分,其中任何一部 分包含P2中的点最多有一个 ? 因此,在矩形R中最多只有6个 P2中的点与p构成最接近点对

d/2

d/2

图8-7 矩形R中点的稀疏性

2d/3

2d/3

2d/3

? 思考:针对P1中的任意一点p,检查P2中的 哪6个点,从而可以找出最接近点对呢 ? 可以将p和P2中所有点到垂直线l上。由于能与 p点一起构成最接近点对候选者的P2中的点 一定在矩形R中,所以它们在直线l上的投影 点与p在l上的投影点的距离小于d ? 算法分析(nlogn)
O(1) ? T ( n) ? ? ?2T (n / 2) ? O(n) n?3 n?3



推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com