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


推荐相关:

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

第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? 理...


第8章 数论算法及计算几何算法_图文.ppt

第8章 数论算法及计算几何算法 - 第八章 数论算法及计算几何算法 教学目标 ?


第8章 数论算法.ppt

第8章 数论算法_数学_自然科学_专业资料。算法设计 教学目标 ? 理解求最大...几何意义 ?以 P1 和P 2 为边的平行四边形的面积 ? 叉积定义为一个矩阵...


第8章+数论入门_图文.ppt

第8章 数论入门 本章内容素数 模运算 Euclid算法 ...之剩二,五五数之剩三, 七七数之剩二,问物几何?...离散对数离散对数的计算: Y?g mod p X 已知...


数论和计算几何.ppt

数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 数论...第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与数...


第9章 数论算法_图文.ppt

第9章 数论算法_计算机软件及应用_IT/计算机_专业资料。第九章 数论算法 内容...第三章 数论算法-2 30页 免费 第8章 数论算法及计算几... 暂无评价 32...


简单数论、计算几何及其应用_图文.ppt

简单数论、计算几何及其应用_学科竞赛_高中教育_教育专区。2012福建省信息学奥林...第8章 数论算法及计算几... 19页 1下载券 小学奥数可以分为计算计... ...


第一讲算法基础.ppt

基础知识 第2章 贪心法 第3章 分治法 第4章 动态规划 第5章 搜索法 第6章 随机化算法 第7章 线性规划问题 第8章 数论算法及计算几何算法 第9章 NP完全...


计算几何算法设计与分析实验课改革.doc

计算几何算法设计与分析实验课改革_理学_高等教育_教育专区。计算几何算法设计与分析实验课改革 摘要:计算几何算法设计与分析是一门面向设计,处于计算机 科学与...


北京大学ACM暑期课讲义-计算几何教程_图文.ppt

北京大学ACM暑期课讲义-计算几何教程_理学_高等教育_教育专区。北京大学ACM/ICPC...? 否则?? 算法流程 ? 算法演示建立初始凸包,并试图添加第一个点。 算法演示...


计算几何常用算法.txt

相交及求直线交点 13.判断线段是否相交,如果相交返回交点㈢ 多边形常用算法模块 ...第八章 数论算法及计算几... 28页 免费 计算几何算法简介(理论指... 13页...


第三章 数论算法.ppt

第三章 数论算法_工学_高等教育_教育专区。III数论算法 §3.1基本概念 最大公...4~(1,4),9~(0,4), 14~(2,4) 计算:对各分量进行: 8?14 ~ (2,3...


计算几何算法与应用大作业.doc

计算几何算法与应用大作业_天文/地理_自然科学_专业资料。作业名称: 计算凸包的分治式算法 基本策略及其原理(30 分): 应用分治法思想,把一个大凸包分成几个结构...


计算几何与图形学有关的几种常用算法.doc

算法系列”接下来的几 篇文章就会介绍一些图形学中常见的计算几何算法(顺便晒晒我的旧代码),都 是一些图形学中的基础算法,需要一些图形学的知识和数学知识,但是...


计算几何常用算法.doc

计算几何常用算法一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,


计算几何_算法与应用.pdf

计算几何_算法与应用_数学_自然科学_专业资料。计算...为了实现一个几何算法,若干基本的数据类型??点、...(s'', sr, p) 请注意,在第 8~16 行中假定...


计算几何算法概览.doc

计算几何算法概览 一、引言 计算机的出现使得很多原本十分繁琐的工作得以大幅度简化


计算几何--算法与应用(第2版)(中文版)111.pdf

计算几何--算法与应用(第2版)(中文版)111_自然科学_专业资料。计算几何 ?? ...为了构造Voronoi图之类的几何结构,需要一些几何算法(geometric algorithm)。这些 ...


免费-ACM常用算法计算几何吴翼_图文.ppt

免费-ACM常用算法计算几何吴翼_学科竞赛_高中教育_教育专区。本文档介绍了ACM/OI竞赛中常用的算法计算几何,讲得很精典,推荐下载 ...


计算机图形学中计算几何算法.txt

计算机图形学中计算几何算法_计算机硬件及网络_IT/计算机_专业资料。计算机图形学...已知矩形三点坐标,求第4点坐标 22 ㈥ 常用算法的描述 22 ㈦ 补充 1.两圆...

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