计算几何及算法.docVIP

计算几何 计算几何学是研究几何问题的算法，在现代工程学与数学，诸如计算机图形学、计算机辅助设计、机器人学都要应用计算几何学，在信息学竞赛中几何题也开始出现了，但是在实际的竞赛中，几何题得分率往往是最低的，所以我对几何题的算法进行了一下探索。 任何复杂的算法都是由许多简单的算法组合而成的，计算几何题也同样如此，先来看最基本的算法： 求直线的斜率 求2条直线的交点 判断2条线段是否相交 求叉积等等。 这些都是最基本的算法，是解几何题的基础，任何对基本算法的不熟悉，都可能导致解题的失败，所以熟悉几何题中的基本算法是非常重要的。 但是有了基本算法是远远不够的，因为光靠竞赛时的临时思考，组合算法从时间上来说是来不及的，这就需要熟悉一些经典算法，在竞赛中直接使用，比如： 求凸包 求最近点对 判断点是否在多边形内等等 基本算法和经典算法都是比较简单的，最后我们再来说一下几何题的题型及解几何题的一些技巧， 几何题的几种类型 纯粹的计算求解题 解这一类题除了需要有扎实的解析几何的基础，还要全面地看待问题，仔细地分析题目中的特殊情况，比如求直线的斜率时，直线的斜率为无穷大，求2条直线的交点时，2直线平行，等等。这些都是要靠平时学习时的积累。 存在性问题 这一类问题可以用计算的方法来直接求解，如果求得了可行解，则说明是存在的，否则就是不存在的，但是模型的效率同模型的抽象化程度有关，模型的抽象化程度越高，它的效率也就越高，几何模型的的抽象化程度是非常低的，而且存在性问题一般在一个测试点上有好几组测试数据，几何模型的效率显然是远远不能满足要求的，这就需要对几何模型进行一定的变换，转换成高效率的模型，下面就通过一个例子来对这种方法进行一下阐述。 求几何中的最佳值问题 这类问题是几何题中比较难的问题，一般没有什么非常有效的算法能够求得最佳解，最常用的是用近似算法去逼近最佳解，近似算法的优劣也完全取决于得出的解与最优解的近似程度。 [例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个柱子相距非常远，那么这样计算的时间复杂度无疑是非常高的，所以我们应该对这个几何模型进行转化。 首先在这个图形中，不动的是柱子（近似看成点），动的是人（近似看成一个圆），这样处理比较麻烦，所以我们应该先把动的转换成点，圆转换成圆心是最容易想到的，对圆心来说，和柱子的距离不能R，所以可以把每个柱子转换为以其为圆心，半径为R的圆，人转换成他的圆心，这样就使得计算可走到范围容易多了。 不过转换成这个模型后，问题还没有得到根本的解决，必须进一步的转换。 前2个算法有一个公共的特点，就是计算的都是圆外的部分，而计算圆内的部分的连通性显然比计算圆外部分来得简单，所以我们现在的目标就是把圆外部分换成圆内部分。 因为左右方向上是无穷长的，所以如果左右部分在圆外相通的话，那么上下两条直线在圆内部分就是不相通的，反之如果左右部分在圆外不相通的话，那么上下两条直线在圆内部分就是相通的， 所以我们可以将对每一个竖列的扫描转换成对每一个横行的扫描，而且又是在圆内操