计算几何课件.pptx

1、计算几何ppt课件概述基础点、线、面进阶多边形、半平面图形学辅助设计数字可视化机器人技术地理信息集成电路辅助工程计算机视觉题目比较长图形抽象，需要良好的数学基础和空间想象能力有许多容易忽视的特殊情况，而且往往需要单独处理，代码量大需要考虑浮点运算时产生的精度误差可以与其他类型的题目结合，从而更加复杂常作为压轴题目出现在程序设计竞赛中用矢量描述计算几何中的基本元素计算机如何理解计算机如何理解沿用解析几何中的表示方法？点 P(x,y,z)线 x=axt+bx,y=ayt+by,z=azt+bz面 ax+by+cz+d=0特殊特殊情况情况太多太多表示简单功能强大特殊情况少，思维难度较低函数可重复利用

2、（即所谓的“模版”）尽可能避免除法和三角函数，精度高，效率高class CVector double x,y,z;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);性质：pq=|p|q|cos功能

3、：求距离；求同向还是异向；求投影；判断是否在半空间上double operator*(CVector p,CVector q)return p.x*q.x+p.y*q.y+p.z*q.z;性质：在二维情况中，|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);矢量与自身点积double length(CVector p)return sqrt(p*p);

4、矢量除以自身的长度CVector unit(CVector p)return 1/length(p)*p;矢量与该方向单位矢量的点积注意：负数表示反方向double project(CVector p,CVector n)return dot(p,unit(n);npp两个矢量的叉积的模长的一半注意：得到的面积为有向面积，可能为负double area(CVector p,CVector q)return length(vector(p,q)/2;pqclass CPoint double x,y,z;class CLine CPoint a,b;class CSurface CPoint a

5、,b,c;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;从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.

6、z);任取平面上两条不平行的矢量求叉积，即可得到一个法向量double normal(CSurface s)return(s.b s.a)(s.c s.a);BACS求距离求位置关系求垂足求交点、交线求夹角求距离求位置关系求垂足求交点、交线求夹角利用两点间矢量的模长应用：圆与点的位置关系double dist(CPoint p,CPoint q)return length(p q);利用叉积求面积，然后除以底即为高应用：求直线与球的交点拓展：点与线段距离（需考虑顶点位置）double dist(CPoint p,CLine l)return fabs(p l.a)(l.b l.a)/lengt

7、h(l.b l.a);PABl利用面的法向量拓展：线段与面的距离（需考虑顶点位置）double dist(CPoint p,CSurface s)return fabs(project(p s.a,normal(s);ASPn先求公垂线，然后在两直线上各找一点，求这两点间的矢量在公垂线上的投影注：若两直线平行，则可将问题转变为点与线的距离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求距离

8、求位置关系求垂足求交点、交线求夹角旋转矢量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应用：过点作面的垂线（即法向量的平行线）CLine parrllel(CPoint p,CLine l)return CLine(p,p+(l.b l.a);lP拓展：过点作与线成角的线（二维）CLine Vertic

9、al(CPoint p,CLine l)return CLine(p,p+(rotate(l.b,l.a,PI/2)l.a);lP求距离求位置关系求垂足求交点、交线求夹角利用点积求投影，进而求出垂足应用：求对称点注：在平面上也可作垂线，利用线与线交点(后面会提到)来求CPoint foot(CPoint p,CLine l)return l.a+project(p l.a,l.b l.a)*unit(l.b l.a);PHlBA利用点积求投影，进而求出垂足应用：求对称点CPoint foot(CPoint p,CSurface s)return p+project(s.a-p,normal(s

10、)*unit(normal(s);ASPnH求距离求位置关系求垂足求交点、交线求夹角先判断是否有唯一解（不平行），再利用叉积求解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先判断是否有唯一解（不平行不共面），再利用投影和垂足求解

11、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先判断是否有唯一解（不平行），再取面上不与另一面平行的两条线，与另一面交于两点，确定交线注：若两条线恰好交于同一点，需要特殊处理TS求距离求位置关系求垂足求交点、交线

12、求夹角利用投影（也可以利用叉积或余弦定理）应用：两直线的位置关系，射线夹角（注意方向即可）double angle(CLine l,CLine m)return acos(fabs(project(l.b l.a,m.b m.a)/length(l.b l.a);lm先判断是否平行。若不平行，取一平面上一点（不在另一平面上），利用该点到另一平面的距离与到二面交线的距离来计算夹角拓展：求二面角时，可通过判断垂足是否在另一个半平面上来确定二面角是锐角还是钝角S2S1PH以上是有关点线面的一些基本问题这些问题若单独考虑都比较简单,但若组合起来,却能构成十分复杂的问题同样,再复杂的点线面问题,几乎都能

13、分解成上述问题进行求解下面是几道相关的例题POJ 2624已知平行四边形的两条邻边，求第四个点的坐标矢量和POJ 2007乱序给出凸多边形的顶点坐标，要求按逆时针顺序输出各顶点利用叉积排序POJ 3462已知望远镜的方向和最大视角范围，求空间中指定点是否可以被看到点积求夹角POJ 1569平面上有一些点（很少），求以这些点为顶点的三角形中，内部无其他点的面积最大的三角形是哪个枚举三角形三个顶点，用叉积判断其他点是否在三角形内POJ 1292平面上有一些墙，人可以在墙上走，也可以在两堵墙间架木板走到另一堵墙上，求从起点到终点至少要带多长的木板主要问题在于求两条线段的距离：若相交则为0，否则可转化

14、为点到线段的距离POJ 3944空间内有一些可反射光线的球，现从某一点向某一方向射出一束光，求光线与球的最后一次碰撞点本题重点在于如何求反射后的直线，具体做法是：利用点与线的距离求线与球的交点，再求起点关于法线的对称点（利用点到线的垂足）OBAPAPOJ 1039在平面上有一根由线段（至多20根）组成的折线管道，管道任意处上边界比下边界高1，求是否存在一束光能穿过管道枚举一个上边界的顶点和一个下边界的顶点，组成一束光，利用线与线的交点判断是否在管内POJ 1066在正方形区域内有一些墙（至多30堵），每堵墙都是贯穿整个区域的且不会有超过两堵墙相交在同一点，求从正方形外走到形内指定点至少要穿越多

15、少堵墙求出所有交点，将墙分为线段，取每条线段的中点，若两中点间没有其他直线（利用叉积判断）则连边，最后求最短路即可空间中两个三角形是否有公共点若共面，问题转化为二维：分两种情况考虑：一个三角形的顶点在另一个三角形内（利用叉积）一个三角形的边与另一个三角形的边相交（利用线与线的交点）否则，求二面交线，然后求出交线与三角形相交的区间（利用线与线交点），最后判断两个区间是否有公共点从抽象到具体之前我们提到的都是抽象的三个基本元素，不需要什么特定的算法就能够解决绝大多数问题但接下来，我们需要面对的是更加具体的元素多边形、半平面在这一部分中，我们将学习一些固定的算法来解决一些竞赛中常见的问题点与多边形的

16、位置关系凸包半平面交点与多边形的位置关系凸包半平面交点在多边形内点在多边形上点在多边形外点在多边形内射线与多边形有奇数个交点如何求交点？先视为直线与直线求交点利用点积判断该点是否同时在射线和线段上特殊情况与顶点相交与边重合平移：将射线稍微上升或下降一个很小的量分类讨论不同的边水平边：直接无视其余边：包含较高的端点，不包含较低的端点沿多边形走一圈，累计绕点旋转了多少角度0：点在形外2：点在形内角度计算=cos-1(ab)/(|a|b|)射线法运算速度快，精度高特殊情况较多转角法几乎没有特殊情况需要反三角函数、开方等，精度低，速度较慢点与多边形的位置关系凸包半平面交定义给定一个平面点集要求找到一个

17、最小的凸多边形，满足点集中的所有点都在该凸多边形的内部或边上性质任意两点的连线都在凸包内先求出k个点的凸包，加入第k+1个点，得到新的凸包多用于三维凸包使用叉积判断新加入的点与之前每条边的位置关系若点在某条边的“外面”，则将该边删除否则保留此边最终若没有边被删除，说明点在多边形内部，直接舍弃否则将新的点与相邻两个点连接成为新的凸包时间复杂度O(n2)，二分优化后为O(nlogn)从最左最低点P0出发找一点P1，使得P0P1与水平方向夹角最小找一点P2，使得P0P2与P0P1夹角最小最终，P0P1P2Pm-1构成凸包P0P1P0P1P2P0P1P2P3使用叉积便可找到夹角最小的矢量时间复杂度O(

18、n2)每一步得到的都是最终凸包上的一条边将点排序极角序水平序按顺序将点添加入栈中若新的点在上一条边的“外面”，则将栈顶的点弹出不断重复此操作直至栈中无边或点在上一条边的“里面”，将新点入栈同样通过叉积判断点和边的位置关系时间复杂度排序O(nlogn)扫描O(n)总计O(nlogn)不排序可能导致错误点与多边形的位置关系凸包半平面交一条直线将平面分为两个半平面半平面交求被所有给定半平面包含的点的集合性质半平面交的结果是一个凸区域应用线性规划多边形的核先求出k个半平面交，加入第k+1个半平面，得到新的半平面交合并方法删去原半平面交上所有不在新半平面上的顶点求原半平面交与新半平面的交点将新的交点添加

19、到半平面交上的合适位置时间复杂度O(n2)，二分优化后为O(nlogn)按极角排序注意半平面是有方向的相同极角保留被包含的半平面建立双端队列对于每个新半平面队首两个半平面的交点在新半平面之外，删除队首半平面；不断重复此任务队尾两个半平面的交点在新半平面之外，删除队尾半平面；不断重复此任务将新半平面加入队尾最后用类似的方式删除队首和队尾的无用半平面队首队尾XXX时间复杂度排序O(nlogn)扫描O(n)总计O(nlogn)POJ 1113给定n个点，要求建尽量短的、包围所有点的围墙，且每个点到围墙的最短距离不得小于8英尺求凸包的周长，然后加上一个圆的周长即可POJ 3528空间内有一些点（点数不

20、超过500）,任意四点不共面，求能包含所有点的立体图形的最小表面积三维凸包（增量法）：每插入一个点判断现有凸包的每个面是否被这个点“看到”（利用面的法向量），若能则删去这个面若有一条边相邻的两个面恰好有一个被删除，则让这条边与新加入的点构成一个新的面POJ 3384在凸包内放两个半径为r的圆，使得被这两个圆覆盖的总面积最大直观的想法就是：让这两个圆圆心距离尽可能远先求可以放置圆心的区域：每条边向里平移r，求半平面交在半平面交上找最远点对作为两个圆的圆心即可POJ 3525求一个凸多边形内部点与边界的距离的最大值二分答案，半平面交，若有解则继续增大距离；否则减小距离；直到恰好有一个点POJ 1755铁人三项比赛中，已知每个人在每种项目中的速度，问是否可以故意调整每种项目的路程来使特定的人获得冠军固定一种项目的路程，则对于任意两个人A和B，若A胜B，则剩余两种项目的路程需要满足一个二元一次不等式，这样问题就转化为判定半平面交是否存在