算法合集之《计算几何学》
更新时间:2023-10-06 10:32:01 阅读量: 综合文库 文档下载
- 计算几何算法与应用推荐度:
- 相关推荐
For personal use only in study and research; not for commercial use
发言稿
芇
莅 计算几何学是研究几何问题的算法,在现代工程学与数学,诸
如计算机图形学、计算机辅助设计、机器人学都要应用计算几何学,在信息学竞赛中几何题也开始出现了,但是在实际的竞赛中,几何题得分率往往是最低的,所以我对几何题的算法进行了一下探索
肁任何复杂的算法都是由许多简单的算法组合而成的,计算几何
题也同样如此,先来看最基本的算法: 1、
2、蝿求直线的斜率 3、
4、肆求2条直线的交点 5、
6、蒅判断2条线段是否相交 7、
8、蒂求叉积等等。
芇这些都是最基本的算法,是解几何题的基础,任何对基本算法
的不熟悉,都可能导致解题的失败,所以熟悉几何题中的基本算法是非常重要的。
袅但是有了基本算法是远远不够的,因为光靠竞赛时的临时思考,
组合算法从时间上来说是来不及的,这就需要熟悉一些经典算法,在竞赛中直接使用,比如: 1、 2、薅求凸包 3、
4、袃求最近点对 5、
6、罿判断点是否在多边形内等等
袈 基本算法和经典算法都是比较简单的,最后我们再来说一下几
何题的题型及解几何题的一些技巧,
蚄几何题的几种类型
1、 2、
蚁羀纯粹的计算求解题
解这一类题除了需要有扎实的解析几何的基础,还要全面地看
待问题,仔细地分析题目中的特殊情况,比如求直线的斜率时,直线的斜率为无穷大,求2条直线的交点时,2直线平行,等等。这些都是要靠平时学习时的积累。 3、 4、
螄蚇存在性问题
这一类问题可以用计算的方法来直接求解,如果求得了可行解,
则说明是存在的,否则就是不存在的,但是模型的效率同模型的抽象化程度有关,模型的抽象化程度越高,它的效率也就越高,几何模型的的抽象化程度是非常低的,而且存在性问题一般在一个测试点上有好几组测试数据,几何模型的效率显然是远远不能满足要求的,这就需要对几何模型进行一定的变换,转换成高效率的模型,下面就通过一个例子来对这种方法进行一下阐述。 5、 6、
腿莁求几何中的最佳值问题
这类问题是几何题中比较难的问题,一般没有什么非常有效的
算法能够求得最佳解,最常用的是用近似算法去逼近最佳解,近似算法的优劣也完全取决于得出的解与最优解的近似程度。
莆[例1]游戏者B在一张100*100纸上确定了一个目标点,游戏者A
一开始在点(0,0)上,每次游戏者A从一个点到另一个点,如果新的点
离目标点近了,那么游戏者B说“Hotter”,如果新的点离目标远了,那么游戏者B说“Colder”,如果距离不变,那么游戏者B说“Same”。
袄 输入文件包括很多行,每行包含游戏者A这一步到达的点(x,y)
和游戏者B说的话,对每次游戏者B说话,判断目标点可能的位置的面积,精确到小数点后2位。
螂这是一道纯粹的计算求解题,首先证明可能的位置的图形一定
是个凸多边形。
袁因为每次对游戏者B的回答,就可以确定可能的位置在出发点
和到达点中垂线的哪一边或就是中垂线,每次的可能图形都是凸多边形。所以这个图形是许多个凸多边形的交集,所以这个图形是凸多边形。
膅接下来就是解题了,先令多边形为一个四边形,(0,0),(0,100),
(100,100),(100,0),然后对每次游戏者B的回答,用这条中垂线将多边形分成2部分,取可能的那部分,即可。
羄不过这样并不是完全正确的,必须考虑到特殊情况,比如游戏
者A到达的点和这步前的点完全相同,这时就不存在中垂线了,这些都是解题中要注意的重点。
膃在这道题中就用到了很多解析集合的知识,包括求线段之间的
交点,判断点是否在线段的两边,证明最终图形是凸多边形等等。
芈[例2]在一个无限长的条形路上,
膈有n(n<=200)个柱子,体积不计,
羄有一个人想从左边走到右边,人
艿近似看成一个半径为R的圆(如右图),
肀问能否实现。
羆拿到这道题最基本的做法是对从最左边的柱子到最右边的柱子
中,每一个竖列进行扫描,计算可走到的范围,如果到最右边的柱子所在的列都有可走到的范围,则有解,否则无解。可是如果最左和最右的2个柱子相距非常远,那么这样计算的时间复杂度无疑是非常高的,所以我们应该对这个几何模型进行转化。
肄首先在这个图形中,不动的是柱子(近似看成点),动的是人(近
似看成一个圆),这样处理比较麻烦,所以我们应该先把动的转换成
正在阅读:
算法合集之《计算几何学》10-06
《领带》小班美术教案05-02
基于内容的图像检索05-18
校园舞会主持词12-31
中国传媒大学学生对马哲课态度调查报告05-31
如何编制2013版知识产权布局研究项目商业计划书(符合VC风投+甲级资质)及融资方案实施指导 - 图文01-13
二十八星宿吉凶释义05-15
区建设局2021年建设领域安全生产百日会战实施方案08-17
SG186营销业务应用系统简介04-12
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 合集
- 几何学
- 算法
- 计算
- 朱刚强课程设计: 无线电发送与接收实验研究 - 图文
- 2013年PEP五年级专题训练句型转换(肯定句,否定句,一般疑问句,特殊疑问句)
- 住宅栏杆计算书
- 王凯辰- 杭州第七中学-首页
- 1.1化学真奇妙第二课时(种道明)
- 2014管理评审报告1 - 图文
- 二级C语言上机题库及答案
- 2011年秋地理周练5
- 中学生百科知识竞赛题及答案(第一套)
- 2018年第一督学责任区上半年督导工作总结
- 2019年整理--网站网络营销初期推广方案
- 中考物理总复习专题功和功率
- 古诗词中的哲理
- 基本均衡盒内目录
- 青海某改造装饰工程施工组织设计方案
- 福建省四地六校2013届高三上学期第三次月考数学理试题 Word版含答案
- 小学安全知识点
- 物权行为理论评析(上)
- 浅谈原始凭证失真及解决办法
- 《模拟电子技术基础》练习题