[计算几何PPT.ppt

计算几何 钟思思 / 目录 前言 计算几何是计算机理论科学的一个重要分支。 自20世纪70年代末从算法设计与分析中独立出来起，不到30年，该学科已经有了巨大的发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应用。 常见应用领域：计算机图形学，机器人学，地理信息系统（GIS），CAD/CAM……….. 前言 在ICPC竞赛中，计算几何相比于其它部分来说是比较独立的。 除近年来出现与图论和动态规划相结合的题目，计算几何与其它的知识点很少有过多的结合。 计算几何的题目难度不会很大，但也永远不会成为最弱的题。 计算几何题目具有代码量大、特殊情况多、精度问题难以控制等特点。 准备知识 头文件#include cmath 浮点数double 常量 const double PI = acos(-1.00); #define PI 3.1415926535897932384626433832795 const double INF = 1e100; const double EPS = 1e-6; 准备知识 符号函数 int sign(double d) { if(fabs(d) EPS) return 0; return (d 0) ? 1 : -1; } 准备知识 浮点数转化成整数 地板函数floor(x) 天花板函数ceil(x) 四舍五入(int) (x + 0.5) 下取整(int) (x + ERROR) 尽量少用三角函数、除法、开方、求幂、取对数 浮点误差 请不要直接用等号判断浮点数是否相等！ 解决方法一,误差判断法： const double EPS=1e-9; 浮点数判断相等，fabs(x-y)EPS; 浮点数判断为零，fabs(x)EPS。 解决方法二，化浮为整法： 在不溢出整数范围的情况下，可以通过乘上10的k次方，转化为整数运算，最后在将结果转化为整数。 浮点误差 在求解过程中，如果使用了除法，将带来更大的浮点误差，在许多情况下我们要考虑将除法转化为乘法。 尽可能让算法简洁，将公式化到最简，仅限于加、减、乘和比较运算。在使用除法、开根号、和三角函数的时候，我们要考虑由浮点误差运算产生的代价。 基本定义 向量 既有大小又有方向的量叫做向量。 用坐标表示和用有向线段表示。 向量的运算 加法 α + β = { x1 + x2 , y1 + y2 } 减法 α – β = { x1 – x2 , y1 – y2 } 向量的运算 向量的旋转 坐标或向量向量(x, y)关于原点的逆时针旋转θ后的坐标为(x’, y’), 向量的运算的应用 求两个向量的夹角(acos, asin) 判断向量的位置和方向 求三角形面积 判断三点共线 判断点与线段关系 点在线段上(叉乘 = 0) 点在线段延长线上(叉乘 = 0) 点在线段顺时针方向(叉乘 0) 点在线段逆时针方向(叉乘 0) 判断线段和直线是否相交 取直线上一点，连接线段的两点，如果所得的两系线段都在直线的同一侧，则不相交。 判断两线段是否相交 两条线段恰有惟一一个不是端点的公共点，称之为“规范相交”。 否则称为非规范相交。 判断两线段是否相交 我们分两步确定两条线段是否相交: (1)快速排斥试验　设以线段 P1P2 为对角线的矩形为R，设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。 判断两线段是否相交 (2)跨立试验 如果两线段相交，则两线段必然相互跨立对方。 若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧。 同理判断Q1Q2跨立P1P2。 向量的运算的应用 计算点到线段、直线的最近点 求点到直线的距离 求点关于直线的对称点 构造两点中垂线 …… 三角形面积 S = a * h / 2 = a * b * sin(c)/2 = a * b * c / (4R) = a * b * c * r / 2 = sqrt(p * (p – a) * (p – b) * (p – c)) 海伦公式 R为外接圆半径 r为内切圆半径 p =(a+b+c)/2 三角形五心 外心：三边中垂线交点，到三角形三个顶点的距离相等 内心：角平分线的交点，到三角形三边的距离相等 垂心：三条高线的交点 重心：三条中线的交点，到三角形三顶点距离的平方和最小的点,三角形内到三边距离之积最大的点. 旁心:三角形的一条内角平分线与其他两个角的外角平分线的交点，旁心到三角形一边及其他两边延