文档介绍：计算几何及其应用
计算几何
计算几何是几何学的一个重要分支,也是计算机科学的一个分支,研究解决几何问题的算法。在现代工程与数学、计算机图形学、机器人学、VLSI设计、计算机辅助设计等学科领域中都有重要应用。
计算几何问题的输入一般是关于一组几何物体(如点、线)的描述;输出常常是有关这些物体的问题的回答,如直线是否相交,点围成的面积等问题。
最有名的例子就是“凸包”问题。即:
计算几何
计算几何很难,究其原因是:一是这类题目要求学生有深厚的计算几何知识,而这些知识平时应用很少,学生研究的少;二是要求学生有很强的数学功底(如高等数学)和良好的空间思维能力,对计算几何中一些经典的算法熟练掌握,综合应用,精度要求也很高,编程量往往也很大;三是这类题目的每个测试点往往包含多组测试数据,造成时间不够。
熟练掌握了计算几何中的一些基本问题和经典算法,问题解决起来往往是很高效的。因为一般而言,数学工具越高级,解决问题就越高效。计算几何题不同于一般几何题,没有证明题,计算机擅长的是高速运算,所以这类题目中一般都有一个(或多个)解析几何中的坐标系,需要大量繁琐的、人力难以胜任的计算工作,这也许正是它们被称为计算几何的原因吧!
计算几何题的常见问题类型:
* 计算求解题
解这一类题除了需要有扎实的解析几何基础,还要注意全面地看问题,仔细分析题目中的特殊情况,比如求直线的斜率时,直线的斜率为无穷大;求两条直线的交点时,这两条直线平行等等;
* 存在性问题
这一类问题可以用计算的方法来直接求解,如果求得了可行解,则说明是存在的,否则就是不存在的。但是模型的效率同模型的抽象化程度有关,模型的抽象化程度越高,它的效率也就越高。几何模型的的抽象化程度是非常低的,而且存在性问题一般在一个测试点上有好几组测试数据,几何模型的效率显然是远远不能满足要求的,这就需要对几何模型进行一定的变换,转换成其它高效率的模型。
计算几何
* 最佳值问题
这类问题是计算几何题中比较难的问题,一般没有什么非常有效的算法能够求得最佳解,最常用的是用近似算法去逼近最佳解,近似算法的优劣也完全取决于得出的解与最优解的近似程度。
主要内容:
一、计算几何的基础
二、计算几何的基本算法
三、经典算法求平面凸包
四、多边形的相关问题
五、常用的特殊算法
六、平面Voronoi图的构造及应用
计算几何基础
计算几何
一、计算几何的基础——矢量
矢量分析是高等数学的一个分支,主要应用于物理学(如力学分析)。在一些计算几何问题中,矢量和矢量运算的一些独特的性质往往能发挥出十分突出的作用,使问题的求解过程变得简洁而高效。熟练掌握一些矢量分析的方法,并灵活地加以运用,就能轻松地解决许多看似复杂的计算几何题,或者会对我们解这类题目有很大帮助,甚至还有一些计算几何题是非用矢量方法不能解决的。
计算几何
1、平面坐标系和平面坐标系上的点
点一般表示成P(x,y),其中x,y为点的坐标。如左图4个点的坐标分别为:P1(3,2) P2(-2,-2) P3(2,4) P4(4,0)。
坐标系的性质,各个象限的点的坐标有下列关系:
第 I 象限 x>0 且y>0
第 II 象限 x<0 且y>0
第Ⅲ象限 x<0 且y<0
第Ⅳ象限 x>0 且y<0
I
II
Ⅲ
Ⅳ
c++中定义几何元素
/* 定义常用变量*/
typedef double type;
const double pi = acos(-);
const double eps = 1e-10;
const double inf = 1e20;
/* 定义点*/
struct point
{
type x, y;
};