网上找的一些算法讲义计算几何.pptx

JSOI2007冬令营计算几何及其应用林厚从 于南京航空航天大学常州市第一中学 林厚从计算几何在信息学奥赛中的应用 计算几何是几何学的一个重要分支，也是计算机科学的一个分支，研究解决几何问题的算法。在现代工程与数学、计算机图形学、机器人学、VLSI设计、计算机辅助设计等学科领域中都有重要应用。 计算几何问题的输入一般是关于一组几何物体（如点、线）的描述；输出常常是有关这些物体的问题的回答，如直线是否相交，点围成的面积等问题。 最有名的例子就是“凸包”问题。即： 常州市第一中学 林厚从计算几何在信息学奥赛中的应用 问题：求平面凸包 即求覆盖平面上n个点的最小的凸多边形。也可以这样描述： 给定一个连接的多边形，可能是凸多边形，也有可能是凹多边形。现在，你的任务就是编程求这个多边形的最小凸包。如果它本身是凸多边形，那么最小凸包就是它本身。 常州市第一中学 林厚从计算几何在信息学奥赛中的应用 在近几年的各项信息学竞赛中也出现了一些计算几何题，让人觉得耳目一新，但实际情况表明，信息学竞赛中的计算几何题得分率往往是很低的。究其原因是多样的，一是这类题目要求学生有深厚的计算几何知识，而这些知识平时应用很少，不仅中学生很少接触到，甚至普通的大学计算机专业学生也不会去研究；二是要求学生有很强的数学功底（如高等数学）和良好的空间思维能力，对计算几何中一些经典的算法熟练掌握，综合应用，精度要求也很高，编程量往往也很大；三是这类题目的每个测试点往往包含多组测试数据，造成时间不够；再者，选手遇到这类题目，有时会因为理解和思维上的困难而无法下手，导致得零分；有时又会因为考虑问题不够全面导致一些致命的错误。 常州市第一中学 林厚从计算几何在信息学奥赛中的应用 但是，一旦你熟练掌握了计算几何中的一些基本问题和经典算法，那么，问题解决起来往往是很高效的。因为：一般而言，数学工具越高级，解决问题就越高效。 信息学竞赛中的计算几何题有一些不同于一般几何题的、很明显的特点。它们不会是证明题，依靠计算机进行的证明是极为罕见的。计算机擅长的是高速运算，所以这类题目中一般都有一个（或多个）解析几何中的坐标系，需要大量繁琐的、人力难以胜任的计算工作，这也许正是它们被称为计算几何的原因吧！计算几何题的几种常见问题类型有： 常州市第一中学 林厚从计算几何在信息学奥赛中的应用 * 计算求解题 解这一类题除了需要有扎实的解析几何基础，还要注意全面地看问题，仔细分析题目中的特殊情况，比如求直线的斜率时，直线的斜率为无穷大；求两条直线的交点时，这两条直线平行等等；这些都要靠平时学习时的积累。 * 存在性问题 这一类问题可以用计算的方法来直接求解，如果求得了可行解，则说明是存在的，否则就是不存在的。但是模型的效率同模型的抽象化程度有关，模型的抽象化程度越高，它的效率也就越高。几何模型的的抽象化程度是非常低的，而且存在性问题一般在一个测试点上有好几组测试数据，几何模型的效率显然是远远不能满足要求的，这就需要对几何模型进行一定的变换，转换成其它高效率的模型。 常州市第一中学 林厚从计算几何在信息学奥赛中的应用 * 最佳值问题 这类问题是计算几何题中比较难的问题，一般没有什么非常有效的算法能够求得最佳解，最常用的是用近似算法去逼近最佳解，近似算法的优劣也完全取决于得出的解与最优解的近似程度。 常州市第一中学 林厚从计算几何在信息学奥赛中的应用 一、计算几何的基础——矢量 矢量分析是高等数学的一个分支，主要应用于物理学（如力学分析）。在一些计算几何问题中，矢量和矢量运算的一些独特的性质往往能发挥出十分突出的作用，使问题的求解过程变得简洁而高效。熟练掌握一些矢量分析的方法，并灵活地加以运用，就能轻松地解决许多看似复杂的计算几何题，或者会对我们解这类题目有很大帮助，甚至还有一些计算几何题是非用矢量方法不能解决的。 常州市第一中学 林厚从计算几何在信息学奥赛中的应用 1、平面坐标系和平面坐标系上的点 点一般表示成P(x,y)，其中x,y为点的坐标。如左图4个点的坐标分别为：P1(3,2) P2(-2,-2) P3(2,4) P4(4,0)。III坐标系的性质,各个象限的点的坐标有下列关系： 第 I 象限x0 且y0 第 II 象限x0 且y0 第 Ⅲ 象限x0 且y0 第 Ⅳ 象限x0 且y0 ⅣⅢ常州市第一中学 林厚从计算几何在信息学奥赛中的应用 过两点（P1，P2）可连成一线段，两点之间的距离记为|P1P2|假设点的坐标为： 由勾股定理可知： 常州市第一中学 林厚从计算几何在信息学奥赛中的应用 2、直线①　直线的方程： 一般形式为：ax+by+c=0，或y=kx+b。 k称为直线的斜率，b称为截矩。如上图，直线L