计算几何课件

计算几何ppt课件计算几何ppt课件1概述基础点、线、面进阶多边形、半平面内容内容概述内容2计算几何课件3计算几何课件4图形学辅助设计数字可视化机器人技术地理信息集成电路辅助工程计算机视觉计计算几何有何用算几何有何用图形学辅助设计数字可视化机器人技术地理信息集成电路5题目比较长图形抽象，需要良好的数学基础和空间想象能力有许多容易忽视的特殊情况，而且往往需要单独处理，代码量大需要考虑浮点运算时产生的精度误差可以与其他类型的题目结合，从而更加复杂常作为压轴题目出现在程序设计竞赛中计计算几何算几何题题的特点的特点题目比较长计算几何题的特点6基基础础点、点、线线、面、面用矢量描述计算几何中的基本元素基础点、线、面用矢量描述计算几何中的基本元素7几何几何图图形的表示形的表示计计算算机机如如何何理理解解几何图形的表示计算机如何理解8沿用解析几何中的表示方法？点 P(x,y,z)线 x=axt+bx,y=ayt+by,z=azt+bz面 ax+by+cz+d=0几何几何图图形的表示形的表示特特殊殊情情况况太太多多沿用解析几何中的表示方法？几何图形的表示特殊情况太多9有没有更好的办法？10表示简单功能强大特殊情况少，思维难度较低函数可重复利用（即所谓的“模版”）尽可能避免除法和三角函数，精度高，效率高矢量法矢量法表示简单矢量法11矢量表示矢量表示class CVector double x,y,z;矢量表示class CVector 12矢量的基本运算矢量的基本运算CVector operator+(CVector p,CVector q)return CVector(p.x+q.x,p.y+q.y,p.z+q.z);CVector operator-(CVector p,CVector q)return CVector(p.x-q.x,p.y-q.y,p.z-q.z);CVector operator*(double k,CVector p)return CVector(k*p.x,k*p.y,k*p.z);矢量的基本运算CVector operator+(CVec13性质：pq=|p|q|cos功能：求距离；求同向还是异向；求投影；判断是否在半空间上矢量的点矢量的点积积double operator*(CVector p,CVector q)return p.x*q.x+p.y*q.y+p.z*q.z;性质：pq=|p|q|cos 矢量的点积doub14性质：在二维情况中，|pq|=|p|q|sin功能：求面积（体积）；求顺时针方向还是逆时针方向；判断是否在半平面上矢量的矢量的叉叉积积CVector operator(CVector p,CVector q)return CVector(p.y*q.z q.y*p.z,p.z*q.x q.z*p.x,p.x*q.y q.x*p.y);性质：在二维情况中，|pq|=|p|q|sin15矢量与自身点积矢量模矢量模长长double length(CVector p)return sqrt(p*p);矢量与自身点积矢量模长double length(CVect16矢量除以自身的长度矢量矢量单单位化位化CVector unit(CVector p)return 1/length(p)*p;矢量除以自身的长度矢量单位化CVector unit(CVe17矢量与该方向单位矢量的点积注意：负数表示反方向矢量的投影矢量的投影长长度度double project(CVector p,CVector n)return dot(p,unit(n);npp矢量与该方向单位矢量的点积矢量的投影长度double pro18两个矢量的叉积的模长的一半注意：得到的面积为有向面积，可能为负double area(CVector p,CVector q)return length(vector(p,q)/2;两两个矢量所个矢量所围围成的三角形面成的三角形面积积pq两个矢量的叉积的模长的一半double area(CVect19点、点、线线、面的表示、面的表示class CPoint double x,y,z;class CLine CPoint a,b;class CSurface CPoint a,b,c;点、线、面的表示class CPoint class CL20常用常数与函数常用常数与函数double PI=acos(-1);double INF=1e20;double EPS=1e-6;CPoint O(0,0,0);bool isZero(double x)return EPS x&x EPS;常用常数与函数double PI=acos(-1);bo21从A点指向B点的矢量AB可用B-A来表示将A点沿矢量p移动到B可以用A+p来表示点与矢量点与矢量CVector operator-(CPoint b,CPoint a)return CVector(b.x a.x,b.y a.y,b.z a.z);CPoint operator+(CPoint a,CVector p)return CPoint(a.x+p.x,a.y+p.y,a.z+p.z);从A点指向B点的矢量AB可用B-A来表示点与矢量CVecto22任取平面上两条不平行的矢量求叉积，即可得到一个法向量面的法向量面的法向量double normal(CSurface s)return(s.b s.a)(s.c s.a);BACS任取平面上两条不平行的矢量求叉积，即可得到一个法向量面的法向23求距离求位置关系求垂足求交点、交线求夹角点点线线面面问题问题分分类类求距离点线面问题分类24求距离求位置关系求垂足求交点、交线求夹角点点线线面面问题问题分分类类求距离点线面问题分类25利用两点间矢量的模长应用：圆与点的位置关系点与点距离点与点距离double dist(CPoint p,CPoint q)return length(p q);利用两点间矢量的模长点与点距离double dist(CPo26利用叉积求面积，然后除以底即为高应用：求直线与球的交点拓展：点与线段距离（需考虑顶点位置）点与点与线线距离距离double dist(CPoint p,CLine l)return fabs(p l.a)(l.b l.a)/length(l.b l.a);PABl利用叉积求面积，然后除以底即为高点与线距离double di27利用面的法向量拓展：线段与面的距离（需考虑顶点位置）点与面距离点与面距离double dist(CPoint p,CSurface s)return fabs(project(p s.a,normal(s);ASPn利用面的法向量点与面距离double dist(CPoint28先求公垂线，然后在两直线上各找一点，求这两点间的矢量在公垂线上的投影注：若两直线平行，则可将问题转变为点与线的距离线线与与线线距离距离double dist(CLine l,CLine m)CVector n=(l.b l.a)(m.b m.a);if(isZero(length(n)return dist(l.a,m);return fabs(project(l.a m.a,n);n先求公垂线，然后在两直线上各找一点，求这两点间的矢量在公垂线29求距离求位置关系求垂足求交点、交线求夹角点点线线面面问题问题分分类类求距离点线面问题分类30旋转矢量AB到AC注：在xy平面上逆时针旋转角（弧度制）点点绕绕点点旋旋转转(二二维维)CPoint rotate(CPoint b,CPoint a,double alpha)CVector p=b a;return CPoint(a.x+(p.x*cos(alpha)-p.y*sin(alpha);a.y+(p.x*sin(alpha)+p.y*cos(alpha);ABC旋转矢量AB到AC点绕点旋转(二维)CPoint rotat31应用：过点作面的垂线（即法向量的平行线）过过点作点作线线的平行的平行线线CLine parrllel(CPoint p,CLine l)return CLine(p,p+(l.b l.a);lP应用：过点作面的垂线（即法向量的平行线）过点作线的平行线CL32拓展：过点作与线成角的线（二维）过过点作点作线线的的垂垂线线（二（二维维）CLine Vertical(CPoint p,CLine l)return CLine(p,p+(rotate(l.b,l.a,PI/2)l.a);lP拓展：过点作与线成角的线（二维）过点作线的垂线（二维）CL33求距离求位置关系求垂足求交点、交线求夹角点点线线面面问题问题分分类类求距离点线面问题分类34利用点积求投影，进而求出垂足应用：求对称点注：在平面上也可作垂线，利用线与线交点(后面会提到)来求点到点到线线的垂足的垂足CPoint foot(CPoint p,CLine l)return l.a+project(p l.a,l.b l.a)*unit(l.b l.a);PHlBA利用点积求投影，进而求出垂足点到线的垂足CPoint foo35利用点积求投影，进而求出垂足应用：求对称点点到面的垂足点到面的垂足CPoint foot(CPoint p,CSurface s)return p+project(s.a-p,normal(s)*unit(normal(s);ASPnH利用点积求投影，进而求出垂足点到面的垂足CPoint foo36求距离求位置关系求垂足求交点、交线求夹角点点线线面面问题问题分分类类求距离点线面问题分类37先判断是否有唯一解（不平行），再利用叉积求解线线与与线线交点（二交点（二维维）CPoint intersect(CLine l,CLine m,string msg)double x=area(m.a l.a,l.b l.a);double y=area(l.b l.a,m.b l.a);if(isZero(x+y)if(isZero(dist(l,m)msg=“重合”;else msg=“平行”;return null;return m.a+x/(x+y)*(m.b m.a);lmPyx先判断是否有唯一解（不平行），再利用叉积求解线与线交点（二维38先判断是否有唯一解（不平行不共面），再利用投影和垂足求解线线与面交点与面交点CPoint intersect(CLine l,CSurface s,string msg)CVector n=normal(s);double x=project(l.b l.a,n);if(isZero(x)if(isZero(dist(l.a,s)msg=“共面”;else msg=“平行”;return null;return l.a+length(foot(l.a,s)l.a)/x *(l.b l.a);ASPnHBl先判断是否有唯一解（不平行不共面），再利用投影和垂足求解线与39先判断是否有唯一解（不平行），再取面上不与另一面平行的两条线，与另一面交于两点，确定交线注：若两条线恰好交于同一点，需要特殊处理面与面交面与面交线线TS先判断是否有唯一解（不平行），再取面上不与另一面平行的两条线40求距离求位置关系求垂足求交点、交线求夹角点点线线面面问题问题分分类类求距离点线面问题分类41利用投影（也可以利用叉积或余弦定理）应用：两直线的位置关系，射线夹角（注意方向即可）线线与与线夹线夹角角double angle(CLine l,CLine m)return acos(fabs(project(l.b l.a,m.b m.a)/length(l.b l.a);lm利用投影（也可以利用叉积或余弦定理）线与线夹角double 42先判断是否平行。若不平行，取一平面上一点（不在另一平面上），利用该点到另一平面的距离与到二面交线的距离来计算夹角拓展：求二面角时，可通过判断垂足是否在另一个半平面上来确定二面角是锐角还是钝角面与面面与面夹夹角角S2S1PH先判断是否平行。若不平行，取一平面上一点（不在另一平面上），43以上是有关点线面的一些基本问题这些问题若单独考虑都比较简单,但若组合起来,却能构成十分复杂的问题同样,再复杂的点线面问题,几乎都能分解成上述问题进行求解下面是几道相关的例题小小结结以上是有关点线面的一些基本问题小结44POJ 2624已知平行四边形的两条邻边，求第四个点的坐标矢量和4th Point4th PointPOJ 26244th Point45POJ 2007乱序给出凸多边形的顶点坐标，要求按逆时针顺序输出各顶点利用叉积排序Scrambled PolygonScrambled PolygonPOJ 2007Scrambled Polygon46POJ 3462已知望远镜的方向和最大视角范围，求空间中指定点是否可以被看到点积求夹角How I Wonder What You Are!How I Wonder What You Are!POJ 3462How I Wonder What You 47POJ 1569平面上有一些点（很少），求以这些点为顶点的三角形中，内部无其他点的面积最大的三角形是哪个枚举三角形三个顶点，用叉积判断其他点是否在三角形内Myacm TrianglesMyacm TrianglesPOJ 1569Myacm Triangles48POJ 1292平面上有一些墙，人可以在墙上走，也可以在两堵墙间架木板走到另一堵墙上，求从起点到终点至少要带多长的木板主要问题在于求两条线段的距离：若相交则为0，否则可转化为点到线段的距离Will Indiana Jones Get There?Will Indiana Jones Get There?POJ 1292Will Indiana Jones Get49POJ 3944空间内有一些可反射光线的球，现从某一点向某一方向射出一束光，求光线与球的最后一次碰撞点本题重点在于如何求反射后的直线，具体做法是：利用点与线的距离求线与球的交点，再求起点关于法线的对称点（利用点到线的垂足）Spherical MirrorsSpherical MirrorsOBAPAPOJ 3944Spherical MirrorsOBAPA50POJ 1039在平面上有一根由线段（至多20根）组成的折线管道，管道任意处上边界比下边界高1，求是否存在一束光能穿过管道枚举一个上边界的顶点和一个下边界的顶点，组成一束光，利用线与线的交点判断是否在管内PipePipePOJ 1039Pipe51POJ 1066在正方形区域内有一些墙（至多30堵），每堵墙都是贯穿整个区域的且不会有超过两堵墙相交在同一点，求从正方形外走到形内指定点至少要穿越多少堵墙求出所有交点，将墙分为线段，取每条线段的中点，若两中点间没有其他直线（利用叉积判断）则连边，最后求最短路即可Treasure HuntTreasure HuntPOJ 1066Treasure Hunt52空间中两个三角形是否有公共点若共面，问题转化为二维：分两种情况考虑：一个三角形的顶点在另一个三角形内（利用叉积）一个三角形的边与另一个三角形的边相交（利用线与线的交点）否则，求二面交线，然后求出交线与三角形相交的区间（利用线与线交点），最后判断两个区间是否有公共点FireworksFireworks空间中两个三角形是否有公共点Fireworks53进阶进阶多多边边形、半平面形、半平面从抽象到具体进阶多边形、半平面从抽象到具体54之前我们提到的都是抽象的三个基本元素，不需要什么特定的算法就能够解决绝大多数问题但接下来，我们需要面对的是更加具体的元素多边形、半平面在这一部分中，我们将学习一些固定的算法来解决一些竞赛中常见的问题多多边边形形、半平面半平面之前我们提到的都是抽象的三个基本元素，不需要什么特定的算法就55点与多边形的位置关系凸包半平面交问题问题列表列表点与多边形的位置关系问题列表56点与多边形的位置关系凸包半平面交问题问题列表列表点与多边形的位置关系问题列表57点在多边形内点在多边形上点在多边形外点与多点与多边边形的位置关系形的位置关系点在多边形内点与多边形的位置关系58点在多边形内射线与多边形有奇数个交点如何求交点？先视为直线与直线求交点利用点积判断该点是否同时在射线和线段上射射线线法法点在多边形内射线与多边形有奇数个交点射线法59特殊情况与顶点相交与边重合射射线线法法特殊情况射线法60平移：将射线稍微上升或下降一个很小的量分类讨论不同的边水平边：直接无视其余边：包含较高的端点，不包含较低的端点射射线线法法平移：将射线稍微上升或下降一个很小的量射线法61射射线线法法射线法62沿多边形走一圈，累计绕点旋转了多少角度0：点在形外2：点在形内角度计算=cos-1(ab)/(|a|b|)转转角法角法沿多边形走一圈，累计绕点旋转了多少角度转角法63射线法运算速度快，精度高特殊情况较多转角法几乎没有特殊情况需要反三角函数、开方等，精度低，速度较慢射射线线法与法与转转角法角法射线法射线法与转角法64点与多边形的位置关系凸包半平面交问题问题列表列表点与多边形的位置关系问题列表65定义给定一个平面点集要求找到一个最小的凸多边形，满足点集中的所有点都在该凸多边形的内部或边上性质任意两点的连线都在凸包内凸包凸包定义凸包66先求出k个点的凸包，加入第k+1个点，得到新的凸包多用于三维凸包增量法增量法先求出k个点的凸包，加入第k+1个点，得到新的凸包增量法67使用叉积判断新加入的点与之前每条边的位置关系若点在某条边的“外面”，则将该边删除否则保留此边最终若没有边被删除，说明点在多边形内部，直接舍弃否则将新的点与相邻两个点连接成为新的凸包时间复杂度O(n2)，二分优化后为O(nlogn)增量法增量法使用叉积判断新加入的点与之前每条边的位置关系增量法68从最左最低点P0出发找一点P1，使得P0P1与水平方向夹角最小找一点P2，使得P0P2与P0P1夹角最小最终，P0P1P2Pm-1构成凸包卷包裹法卷包裹法P0P1P0P1P2P0P1P2P3从最左最低点P0出发卷包裹法P0P1P0P1P2P0P1P269使用叉积便可找到夹角最小的矢量时间复杂度O(n2)每一步得到的都是最终凸包上的一条边卷包裹法卷包裹法使用叉积便可找到夹角最小的矢量卷包裹法70将点排序极角序水平序Graham Graham 扫扫描法描法将点排序Graham 扫描法71按顺序将点添加入栈中若新的点在上一条边的“外面”，则将栈顶的点弹出不断重复此操作直至栈中无边或点在上一条边的“里面”，将新点入栈Graham Graham 扫扫描描法法按顺序将点添加入栈中Graham 扫描法72同样通过叉积判断点和边的位置关系时间复杂度排序O(nlogn)扫描O(n)总计O(nlogn)不排序可能导致错误Graham Graham 扫扫描法描法同样通过叉积判断点和边的位置关系Graham 扫描法73点与多边形的位置关系凸包半平面交问题问题列表列表点与多边形的位置关系问题列表74一条直线将平面分为两个半平面半平面交求被所有给定半平面包含的点的集合性质半平面交的结果是一个凸区域应用线性规划多边形的核半平面交半平面交一条直线将平面分为两个半平面半平面交75先求出k个半平面交，加入第k+1个半平面，得到新的半平面交合并方法删去原半平面交上所有不在新半平面上的顶点求原半平面交与新半平面的交点将新的交点添加到半平面交上的合适位置时间复杂度O(n2)，二分优化后为O(nlogn)增量法增量法先求出k个半平面交，加入第k+1个半平面，得到新的半平面交增76按极角排序注意半平面是有方向的相同极角保留被包含的半平面排序增量算法排序增量算法按极角排序排序增量算法77建立双端队列对于每个新半平面队首两个半平面的交点在新半平面之外，删除队首半平面；不断重复此任务队尾两个半平面的交点在新半平面之外，删除队尾半平面；不断重复此任务将新半平面加入队尾最后用类似的方式删除队首和队尾的无用半平面排序增量算法排序增量算法建立双端队列排序增量算法78排序增量算法排序增量算法队首队尾XXX排序增量算法队首队尾XXX79时间复杂度排序O(nlogn)扫描O(n)总计O(nlogn)排序增量算法排序增量算法时间复杂度排序增量算法80POJ 1113给定n个点，要求建尽量短的、包围所有点的围墙，且每个点到围墙的最短距离不得小于8英尺求凸包的周长，然后加上一个圆的周长即可WallWallPOJ 1113Wall81POJ 3528空间内有一些点（点数不超过500）,任意四点不共面，求能包含所有点的立体图形的最小表面积三维凸包（增量法）：每插入一个点判断现有凸包的每个面是否被这个点“看到”（利用面的法向量），若能则删去这个面若有一条边相邻的两个面恰好有一个被删除，则让这条边与新加入的点构成一个新的面Ultimate WeaponUltimate WeaponPOJ 3528Ultimate Weapon82POJ 3384在凸包内放两个半径为r的圆，使得被这两个圆覆盖的总面积最大直观的想法就是：让这两个圆圆心距离尽可能远先求可以放置圆心的区域：每条边向里平移r，求半平面交在半平面交上找最远点对作为两个圆的圆心即可Feng ShuiFeng ShuiPOJ 3384Feng Shui83POJ 3525求一个凸多边形内部点与边界的距离的最大值二分答案，半平面交，若有解则继续增大距离；否则减小距离；直到恰好有一个点Most Most Distant PointDistant Pointfrom from the Seathe SeaPOJ 3525Most Distant Pointfro84POJ 1755铁人三项比赛中，已知每个人在每种项目中的速度，问是否可以故意调整每种项目的路程来使特定的人获得冠军固定一种项目的路程，则对于任意两个人A和B，若A胜B，则剩余两种项目的路程需要满足一个二元一次不等式，这样问题就转化为判定半平面交是否存在TriathlonTriathlonPOJ 1755Triathlon85谢谢86