“最近”是指通常意义上的欧几里德距离。《算法导论》中对这个问题进行了介绍。[i]问对于经典的分治法求最近点对有深入的介绍和详尽的伪代码。
29.1.1实例
PKU JudgeOnline, 3714, Raid.
29.1.2问题描述
给定n个岗位和n个战士的坐标(0 ≤ X ≤1000000000, 0 ≤ Y ≤ 1000000000)。问这些战士当中,离某个岗位最近的距离是多少?
29.1.3输入
2
4
00
01
10
11
22
23
32
33
4
00
00
00
00
00
00
00
0 0
29.1.4输出
1.414
0.000
29.1.5分析
这也是一个最近距离的问题,只不过是两个集合中的元素的最近距离的问题。采用的方法不同于经典的最近距离点对的分治算法,但是思想上也有类似的地方。
对于每个战士(x0, y0),首先找到一个点,这个点是x最接近x0的所有点中y最接近y0的点,求出(x, y)、(x0, y0)两点距离dis。若minDis > dis,令minDis = dis。在[x - minDis, x + minDis]的横坐标范围内移动x,并对每个x,寻找y最接近y0的点(x, y),若minDis > dis,令minDis = dis。
上述描述中,“最接近x0的x”或者“最接近y0的y”都通过对有序数组的二分查找法来找出。
29.1.6程序
29.2 线段相交
关于线段相交,《算法艺术与信息学竞赛》介绍得比较细致。
29.2.1实例
PKU JudgeOnline, 1039, Pipe.
29.2.2问题描述
如上图所示,有一条管子,拐角处的两点坐标为(x, y)和(x, y + 1)。有一束光从入口射入,遇到管壁则被阻挡。求光所能达到的最大的x。
29.2.3输入
4
01
22
41
64
6
01
2-0.6
5-4.45
7-5.57
12-10.8
17-16.55
0
29.2.4输出
4.67
Through all the pipe.
29.2.5分析
《算法艺术与信息学竞赛》对这个题有结题报告。
29.2.6程序
29.3 Melkman在线凸包算法
《算法艺术与信息学竞赛》比较全面、生动地介绍了凸包算法及其应用。
Melkman凸包算法继承Graham-Scan算法的主要思想,并更近一步地采用双端队列,动态地在队列两头进行增删操作,维护“凸性”。
一个Melkman凸包算法的实例如下:
[ii]中描述的Melkman凸包算法如下所示:
1. t ← 1; b ← 0;//这里似乎Melkman弄反了,应该改成:t ← 0;b ←1;
vl← input; v2 ← input; v3 ← input;
if (Vl, v2, v3) > 0
then begin push vl; push v2; end;
else begin push v2; push v1; end;
pushv3 ; insert v3;
2. v ← input;
until (v, db, db+l) < 0 or (dt-1, dt, v) < 0
do v ← inputend;
3. until (dt-l,dt, v) > 0 do pop dt end;
pushv;
4. until(v, db, db+l) > 0 do remove db end;
insertv;
goto 2.
其中定义:
(x, y, z)为根据z在x到y的向量右边、同一条直线上、或左边,而返回1, 0, -1的函数。
push操作就是使得t = t + 1; dt = v。
pop操作就是使得 t = t - 1。
insert操作就是使得b = b - 1; db = v。
remove操作就是使得b = b + 1。
29.3.1实例
PKU JudgeOnline, 1113, Wall.
29.3.2问题描述
已知N个点的坐标,要将这些点用围墙围起来,并使得围墙距离点的距离不超过L。求围墙的周长。输出四舍五入。
先输入N和L,然后是N个点的坐标。
1.3.3输入
9100
200400
300400
300300
400300
400400
500400
500200
350200
200 200
29.3.4输出
1628
29.3.5分析
先求这些点的凸包。
可以很容易地证明:周长最短的围墙是由由于凸包的每条边,垂直向外平移L的距离,再将这些线段用半径为L的圆弧连接起来而构成的。
同时又很容易证明:这些圆弧的角度之和为360度。
故此这个问题直接转化为求凸包的周长问题。
凸包的求法中三点共线是十分需要注意的。Melkman算法描述中略去了对三点共线的许多细节的处理。
29.3.6程序
29.4 实例
29.4.1线段相交的实例
PKU JudgeOnline, 1039, Pipe.
29.4.2凸包的实例
PKU JudgeOnline, 1113, Wall.
本文章欢迎转载,请保留原始博客链接http://blog.csdn.net/fsdev/article
[i] Discrete Mathematics, Sixth Edition. Richard Johnsonbaugh.
[ii] On-line Construction of the Convex Hull of a Simple Polygon. MelkmanA. Information Processing Letters
25, p11-12 , (1987).
分享到:
相关推荐
计算机图形学几何工具算法详解,含图形学的经典实用算法的原理与实现。1/2个parts。
实用算法的分析和程序设计。讲思路,基础算法,顺序统计算法和中位数,有关数论的算法,计算几何学,显示图的基本算法。。。。。。
简介:本书是一部程序设计竞赛教程。书中首先讲述了算法的基本概念、各种排序与解题的方法及策略·然后论述了初等数论、计算几何学、搜索和图论的有关算法,最后讨论了动态规划。...
复杂几何形状面积的计算,属于计算几何方面的问题。在实际应用中, 不但经常需要计算一般多边形的面积,而且有时还需要计算有曲线边多边 形的面积。为简便和考虑实用需要,可以假定曲线边是圆锥曲线边或三次 Bezier...
计算机图形学几何工具算法详解,含图形学的经典实用算法的原理与实现。2/2个parts。
C#,计算几何,计算机图形学(Computer Graphics)洪水填充算法(Flood Fill Algorithm)与源代码 泛洪填充算法(Flood Fill Algorithm) ,又称洪水填充算法,是在很多图形绘制软件中常用的填充算法,最熟悉不过就是 ...
C#,计算几何,随机点集之三角剖分的德劳内(Delaunay)算法的源代码。点集的三角剖分(Triangulation),对数值分析(比如有限元分析)以及图形学来说,都是极为重要的一项预处理技术。尤其是Delaunay三角剖分,...
·第1章讨论了算法在计算中的作用。 ·第5章介绍了概率分析和随机算法。如第1版中一样,这些主题贯穿了整本书。 ·第29章专门讨论了线性规划。 ·在从第1版保留下来的各章中,增加了关于以下主题的新节: ·完全...
计算教程2010报告的这篇附录定义了计算机科学本科教学计划中可能讲授的知识领域。该分类方案的依据及其历史、结构和应用的其它细节包含在完整的任务组报告中。由于我们希望附录比完整的报告有更多的读者,所以任务组...
+ [计算几何思想](#计算几何思想) + [圆](#圆) + [半平面交](#半平面交) * [矩阵](#矩阵) + [矩阵](#矩阵-1) + [高斯消元](#高斯消元) * [数学方法](#数学方法) + [数学思想](#数学思想) + [数学归纳法](#...
本书即为信息学界著名的两本“黑书”之一(另一本为吴文虎、王建德编著的实用算法的分析与程序设计,这本书现在已经在市场是接近绝版,但是在网上能找到电子书.如果想找到替代品的话可以找另外一本由吴文虎教授以及...
本书即为信息学界著名的两本“黑书”之一(另一本为吴文虎、王建德编著的实用算法的分析与程序设计,这本书现在已经在市场是接近绝版,但是在网上能找到电子书.如果想找到替代品的话可以找另外一本由吴文虎教授以及...
·第1章讨论了算法在计算中的作用。 ·第5章介绍了概率分析和随机算法。如第1版中一样,这些主题贯穿了整本书。 ·第29章专门讨论了线性规划。 ·在从第1版保留下来的各章中,增加了关于以下主题的新节: ·完全...
本书的特色和优势是:注重算法与程序实现,强调理论知识与程序设计的紧密结合,既有理论性,也有实用性,对每个常用方法配有一个N-S图算法和一个独立完整的C程序,并且所有程序都已调试通过;重点突出,解释详尽;...
计算几何和计算机图形学领域的经典著作,书中介绍了很多非常实用的算法,并附有C++实现代码
计算机图形学作业题 1. 计算机中由图形的形状参数(方程或分析表达式的系数,线段的端点坐标等)加属性参数 (颜色、线型等)来表示图形称图形的参数表示;枚举出图形中所有的点称图形的点阵 表示,简称为图像(数字图像...
本书对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用...
第二部分以标准的三维图形程序设计为主题,内容包括基元、次物体、几何拓扑、图形学变换、可见性测试、颜色缓冲、深度缓冲、光源、材质、光照明计算、着色等图形学基本技术。第二部分重点说明图形开发的基本过程。...
第二部分以标准的三维图形程序设计为主题,内容包括基元、次物体、几何拓扑、图形学变换、可见性测试、颜色缓冲、深度缓冲、光源、材质、光照明计算、着色等图形学基本技术。第二部分重点说明图形开发的基本过程。...
另外有一个约80篇参考文献的目录,以及可进行索引的近400个术语。全书译成中文约合100万字(也包括图片、绘图、表格、公式等)。本书可作为已具有初步图像技术知识的相关专业高年级本科生和低年级研究生的专业基础课...