计算几何和矢量操作.docVIP

计算几何与矢量运算 讲义 邵铮 2000/7/5 计算几何简介 什么是计算几何？ 与一般几何学的区别 不可能用可视化的方法如作图法（与解析几何类似） 利用计算机强大的运算能力，与数据结构的结合 矢量方法的重点：用非可视化的方法研究几何问题 例 矢量 什么是矢量？ 矢量的维数： 矢量方法在计算几何中的重要地位 例 1．1矢量的表示 矢量的表示-点的表示 基与坐标 平面上的点：直角坐标系与极坐标系 空间中的点：直角坐标系、柱坐标系与球坐标系 约定：以下的分析以三维矢量为主，并且都采用直角坐标系 1．2矢量的运算 模 加法与减法 点乘（点积、标量积） 叉乘（叉积、矢量积） 点乘与叉乘的线性性 1．3矢量的加法 1．4矢量的减法 1．5矢量的点乘， 点乘的物理意义：作功 1．6三维矢量的叉乘 叉乘的几何意义：平行四边形的面积 1．7二维矢量的叉乘 标量结果 正负号的意义 1．8点乘与叉乘的一个关系式 (a.b)^2+(axb)^2=abcos(a,b) 矢量的简单应用 基本的几何问题 与几何课上研究问题的区别：结论要便于用计算机实现 2．0基本几何元素的表示 直线、射线与线段 平面 2．1平面中的几何问题一 三个有序点的位置关系 同一直线、逆时针三角形、顺时针三角形 2．2平面中的几何问题二 三角形的内角 锐角三角形、直角三角形、钝角三角形 2．3平面中的几何问题三 顺次给出一个多边形的顶点，判定它是否是凸多边形 点是否在三角形内？点是否在多边形内？ 2．4平面中的几何问题四 两条线段是否相交 点到直线的距离 点在直线上的投影 点到线段的距离 2．5平面中的几何问题五 直线与直线的交点 2．6空间中的几何问题一 平行六面体的体积 点到直线的投影 点到直线的距离 2．7空间中的几何问题二 轴矢量的对称 旋矢量的对称 2．8空间中的几何问题三 v向vs旋转angle v绕vs旋转angle（右手方向） 2．9空间中的几何问题四 四点共面 直线与平面是否平行 直线与直线之间的距离 线段与线段之间的距离 2．10空间中的几何问题五 直线与平面的交点 平面与平面的交线 例题 3．1平面凸包问题 3．2监视器问题Video(CTSC’98) 3．3线段相交问题 平面内有n条线段，求一直线使其与线段的交点最多。 3．4矩形的可视问题 平面内有n个矩形，求一点使其能够“看”到尽可能多的矩形。（注：只要看到一个矩形上的一个点，就算看到了这个矩形。） 3．5 空间凸包问题 演示：几何模块OpenGL演示(章准平) 附录：几何模块 Geometry 3D 2.0 (章准平)Geometry Hurricane 1.0(邵铮)