计算几何.pptxVIP

林舒 2012年7月20日 于 北京大学;概述 基础——点、线、面 进阶——多边形、半平面;概述;计算几何 Computational Geometry 研究几何形体的计算机表示、分析与综合 “计算几何”——以计算为主的几何;计算几何有何用;题目比较长 图形抽象，需要良好的数学基础和空间想象能力 有许多容易忽视的特殊情况，而且往往需要单独处理，代码量大 需要考虑浮点运算时产生的精度误差 可以与其他类型的题目结合，从而更加复杂 常作为压轴题目出现在程序设计竞赛中 ;基础——点、线、面;几何图形的表示;沿用解析几何中的表示方法？ 点 P(x,y,z) 线 x=axt+bx,y=ayt+by,z=azt+bz 面 ax+by+cz+d=0 ;有没有更好的办法？;表示简单 功能强大 特殊情况少，思维难度较低 函数可重复利用（即所谓的“模版”） 尽可能避免除法和三角函数，精度高，效率高;矢量表示;矢量的基本运算;性质：p·q=|p||q|cosp,q 功能：求距离；求同向还是异向；求投影；判断是否在半空间上;性质：在二维情况中，|p×q|=|p||q|sinp,q 功能：求面积（体积）；求顺时针方向还是逆时针方向；判断是否在半平面上;矢量与自身点积;矢量除以自身的长度;矢量与该方向单位矢量的点积 注意：负数表示反方向;两个矢量的叉积的模长的一半 注意：得到的面积为有向面积，可能为负;点、线、面的表示;常用常数与函数;从A点指向B点的矢量AB可用B-A来表示 将A点沿矢量p移动到B可以用A+p来表示;任取平面上两条不平行的矢量求叉积，即可得到一个法向量;求距离 求位置关系 求垂足 求交点、交线 求夹角;求距离 求位置关系 求垂足 求交点、交线 求夹角;利用两点间矢量的模长 应用：圆与点的位置关系;利用叉积求面积，然后除以底即为高 应用：求直线与球的交点 拓展：点与线段距离（需考虑顶点位置）;利用面的法向量 拓展：线段与面的距离（需考虑顶点位置）;先求公垂线，然后在两直线上各找一点，求这两点间的矢量在公垂线上的投影 注：若两直线平行，则可将问题转变为点与线的距离 ;求距离 求位置关系 求垂足 求交点、交线 求夹角;旋转矢量AB到AC 注：在xy平面上逆时针旋转α角（弧度制）;应用：过点作面的垂线（即法向量的平行线） ;拓展：过点作与线成α角的线（二维）;求距离 求位置关系 求垂足 求交点、交线 求夹角;利用点积求投影，进而求出垂足 应用：求对称点 注：在平面上也可作垂线，利用线与线交点(后面会提到)来求 ;利用点积求投影，进而求出垂足 应用：求对称点;求距离 求位置关系 求垂足 求交点、交线 求夹角;先判断是否有唯一解（不平行），再利用叉积求解;先判断是否有唯一解（不平行不共面），再利用投影和垂足求解;先判断是否有唯一解（不平行），再取面上不与另一面平行的两条线，与另一面交于两点，确定交线 注：若两条线恰好交于同一点，需要特殊处理;求距离 求位置关系 求垂足 求交点、交线 求夹角;利用投影（也可以利用叉积或余弦定理） 应用：两直线的位置关系，射线夹角（注意方向即可）;先判断是否平行。若不平行，取一平面上一点（不在另一平面上），利用该点到另一平面的距离与到二面交线的距离来计算夹角 拓展：求二面角时，可通过判断垂足是否在另一个半平面上来确定二面角是锐角还是钝角;以上是有关点线面的一些基本问题 这些问题若单独考虑都比较简单,但若组合起来,却能构成十分复杂的问题 同样,再复杂的点线面问题,几乎都能分解成上述问题进行求解 下面是几道相关的例题;POJ 2624 已知平行四边形的两条邻边，求第四个点的坐标 矢量和;POJ 2007 乱序给出凸多边形的顶点坐标，要求按逆时针顺序输出各顶点 利用叉积排序;POJ 3462 已知望远镜的方向和最大视角范围，求空间中指定点是否可以被看到 点积求夹角 ;POJ 1569 平面上有一些点（很少），求以这些点为顶点的三角形中，内部无其他点的面积最大的三角形是哪个 枚举三角形三个顶点，用叉积判断其他点是否在三角形内 ;POJ 1292 平面上有一些墙，人可以在墙上走，也可以在两堵墙间架木板走到另一堵墙上，求从起点到终点至少要带多长的木板 主要问题在于求两条线段的距离：若相交则为0，否则可转化为点到线段的距离 ;POJ 3944 空间内有一些可反射光线的球，现从某一点向某一方向射出一束光，求光线与球的最后一次碰撞点 本题重点在于如何求反射后的直线，具体做法是：利用点与线的距离求线与球的交点，再求起点关于法线的对称点（利用点到线的垂足） ;POJ 1039 在平面上有一根由线段（至多20根）组成的折线管道，管道任意处上边界比下边界高1，求是否存在一束光能穿过管道 枚举一个上边界的顶点和一个下边界的顶点，组成一束光，利用线与