第一讲计算几何7月8日_第1页
第一讲计算几何7月8日_第2页
第一讲计算几何7月8日_第3页
第一讲计算几何7月8日_第4页
第一讲计算几何7月8日_第5页
已阅读5页，还剩23页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、计算几何ComputationalGeometryMDZfirstofTianjinUniversity2008 - 2 - 20计算几何是计算机理论科学的一个重要分支。自20世纪70年代末从算法设计与分析中出来起，不到30年，该学科已经有了巨大的发展，不仅产生 了一系列重要的理论成果， 也在众多实际领域中得到了广泛的应用。准备知识头文件#include <cmath>浮点数double常量constconst constdoubledouble doublePI = 2 * acos(0.0);INF = 1e100; ERROR = 1e-6;符号函数int sign(doub

2、le x)if (fabs(x) < ERROR) return (0);elsereturn (x > 0 ? 1 : -1);浮点数转化成整数地板函数天花板函数四舍五入下取整floor(x)ceil(x)(int) (x + 0.5) (int) (x + ERROR)尽量少用三角函数、除法、开方、求幂、取对数。重要工具向量向量的定义既有大小又有方向的量叫做向量。yB向量的表示用坐标表示A和用有向线段表示。COx向量的运算加法 + = x1 + x2 , y1 + y2 减法 = x1 x2 , y1 y2 + 向量的运算点积· = x1×x2 + y1&#

3、215;y2 = |·|·cos叉积× = x1×y2 x2×y1 = |·|·sin向量乘积的应用夹角的范围求两个向量的夹角求三角形面积位置和方向线段相交两条线段恰有惟一一个不是端点的公共点，称之为“规范相交”。两条线段规范相交时，每条线段两个端点都在另一条线段的异侧。其它应用多边形由在同一平面且不在同一直线上的多条线段首尾顺次连结且不相交所组成的图形叫做多边形。凸多边形过多边形任意一边做一条直线，如果其他各顶点都在这条直线的同侧，则把这个多边形叫做凸多边形。求凸多边形的面积求一般多边形的面积多边形的重心一个物体的各部分都

4、要受到重力的作用。从效果上看， 我们可以认为各部分受到的重力作用集中于一点，这一点叫做物体的重心。质量均匀分布的物体，重心的位置只跟物体的形状有关，它的重心就在几何重心上。三角形的重心AOCMB一般多边形的重心· ·········点与多边形的位置关系几种特殊情况点是否在多边形边上。1.2. 不考虑水平边。3. 若边与射线正规相交，则计数。4. 只考虑纵坐标较大的顶点。线段是否在多边形内凸包的应用········&#

5、183;·············卷包裹法········Graham-Scan算法········Graham-Scan算法push(p1);push(p2); i = 3;while i <= n doif p1在栈顶边的左手方向thenpush(pi); 并且i+elsepop();最小包围圆Smalle

人人文库> 全部分类> 应用文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论