计算几何课件

概述基础——点、线、面进阶——多边形、半平面内容概述走近计算几何计算几何ComputationalGeometry研究几何形体的计算机表示、分析与综合“计算几何”——以计算为主的几何什么是计算几何图形学辅助

设计数字

可视化机器人

技术地理

信息集成

电路辅助

工程计算机

视觉计算几何有何用题目比较长图形抽象，需要良好的数学基础和空间想象能力有许多容易忽视的特殊情况，而且往往需要单独处理，代码量大需要考虑浮点运算时产生的精度误差可以与其他类型的题目结合，从而更加复杂常作为压轴题目出现在程序设计竞赛中计算几何题的特点基础——点、线、面用矢量描述计算几何中的基本元素几何图形的表示计算机如何理解沿用解析几何中的表示方法？点P(x,y,z)线x=axt+bx,y=ayt+by,z=azt+bz面ax+by+cz+d=0几何图形的表示特殊情况太多有没有更好的办法？表示简单功能强大特殊情况少，思维难度较低函数可重复利用（即所谓的“模版”）尽可能避免除法和三角函数，精度高，效率高矢量法矢量表示classCVector{doublex,y,z;}矢量的基本运算CVectoroperator+(CVectorp,CVectorq){

returnCVector(p.x+q.x,p.y+q.y,

p.z+q.z);}CVectoroperator-(CVectorp,CVectorq){

returnCVector(p.x-q.x,p.y-q.y,

p.z-q.z);}CVectoroperator*(doublek,CVectorp){

returnCVector(k*p.x,k*p.y,k*p.z);}性质：p·q=|p||q|cos<p,q>功能：求距离；求同向还是异向；求投影；判断是否在半空间上矢量的点积double

operator

*(CVectorp,CVectorq){

returnp.x*q.x+p.y*q.y+p.z*q.z;}性质：在二维情况中，|p×q|=|p||q|sin<p,q>功能：求面积（体积）；求顺时针方向还是逆时针方向；判断是否在半平面上矢量的叉积CVector

operator

^(CVectorp,CVectorq){

returnCVector(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(CVectorp){

returnsqrt(p*p);}矢量除以自身的长度矢量单位化CVectorunit(CVectorp){

return

1/length(p)*p;}矢量与该方向单位矢量的点积注意：负数表示反方向矢量的投影长度double

project(CVectorp,CVectorn){

returndot(p,unit(n));}npp’两个矢量的叉积的模长的一半注意：得到的面积为有向面积，可能为负doublearea(CVectorp,CVectorq){

returnlength(vector(p,q))/2;}两个矢量所围成的三角形面积pq点、线、面的表示classCPoint{

doublex,y,z;}classCLine{

CPointa,b;}classCSurface{

CPointa,b,c;}常用常数与函数doublePI=acos(-1);doubleINF=1e20;doubleEPS=1e-6;CPointO(0,0,0);boolisZero(doublex){

return–EPS<x&&x<EPS;}从A点指向B点的矢量AB可用B-A来表示将A点沿矢量p移动到B可以用A+p来表示点与矢量CVectoroperator-(CPointb,CPointa){

returnCVector(b.x–a.x,b.y–a.y,

b.z–a.z);}CPointoperator+(CPointa,CVectorp){

returnCPoint(a.x+p.x,a.y+p.y,

a.z+p.z);}任取平面上两条不平行的矢量求叉积，即可得到一个法向量面的法向量doublenormal(CSurfaces){

return(s.b

–s.a)^(s.c–s.a);}BACS求距离求位置关系求垂足求交点、交线求夹角点线面问题分类求距离求位置关系求垂足求交点、交线求夹角点线面问题分类利用两点间矢量的模长应用：圆与点的位置关系点与点距离doubledist(CPointp,CPointq){

returnlength(p–q);}利用叉积求面积，然后除以底即为高应用：求直线与球的交点拓展：点与线段距离（需考虑顶点位置）点与线距离doubledist(CPointp,CLinel){

returnfabs((p–l.a)^(l.b–l.a))

/length(l.b–l.a);}PABl利用面的法向量拓展：线段与面的距离（需考虑顶点位置）点与面距离doubledist(CPointp,CSurfaces){

returnfabs(project(p–s.a,normal(s)));}ASPn先求公垂线，然后在两直线上各找一点，求这两点间的矢量在公垂线上的投影注：若两直线平行，则可将问题转变为点与线的距离线与线距离doubledist(CLinel,CLinem){

CVectorn=(l.b–l.a)^(m.b–m.a);

if(isZero(length(n))

returndist(l.a,m);

returnfabs(project(l.a–m.a,n));}n求距离求位置关系求垂足求交点、交线求夹角点线面问题分类旋转矢量AB到AC注：在xy平面上逆时针旋转α角（弧度制）点绕点旋转(二维)CPointrotate(CPointb,CPointa,

doublealpha){

CVectorp=b–a;

returnCPoint(a.x+(p.x*cos(alpha)

-p.y*sin(alpha));

a.y+(p.x*sin(alpha)

+p.y*cos(alpha));}ABCα应用：过点作面的垂线（即法向量的平行线）过点作线的平行线CLineparrllel(CPointp,CLinel){returnCLine(p,p+(l.b–l.a));}lP拓展：过点作与线成α角的线（二维）过点作线的垂线（二维）CLineVertical(CPointp,CLinel){returnCLine(p,

p+(rotate(l.b,l.a,PI/2)–l.a));}lP求距离求位置关系求垂足求交点、交线求夹角点线面问题分类利用点积求投影，进而求出垂足应用：求对称点注：在平面上也可作垂线，利用线与线交点(后面会提到)来求点到线的垂足CPointfoot(CPointp,CLinel){returnl.a+project(p–l.a,l.b–l.a)

*unit(l.b–l.a);}PHlBA利用点积求投影，进而求出垂足应用：求对称点点到面的垂足CPointfoot(CPointp,CSurfaces){return

p+project(s.a-p,normal(s))

*unit(normal(s));}ASPnH求距离求位置关系求垂足求交点、交线求夹角点线面问题分类先判断是否有唯一解（不平行），再利用叉积求解线与线交点（二维）CPointintersect(CLinel,CLinem,stringmsg){

doublex=area(m.a–l.a,l.b–l.a);

doubley=area(l.b–l.a,m.b–l.a);

if(isZero(x+y)){

if(isZero(dist(l,m))msg=“重合”;

elsemsg=“平行”;

returnnull;

}returnm.a+x/(x+y)*(m.b–m.a);}lmPyx先判断是否有唯一解（不平行不共面），再利用投影和垂足求解线与面交点CPointintersect(CLinel,CSurfaces,stringmsg){CVectorn=normal(s);

doublex=project(l.b–l.a,n);

if(isZero(x)){

if(isZero(dist(l.a,s)))msg=“共面”;

elsemsg=“平行”;

returnnull;

}

returnl.a+length(foot(l.a,s)–l.a)/x

*(l.b–l.a);}ASPnHBl先判断是否有唯一解（不平行），再取面上不与另一面平行的两条线，与另一面交于两点，确定交线注：若两条线恰好交于同一点，需要特殊处理面与面交线TS求距离求位置关系求垂足求交点、交线求夹角点线面问题分类利用投影（也可以利用叉积或余弦定理）应用：两直线的位置关系，射线夹角（注意方向即可）线与线夹角doubleangle(CLinel,CLinem){returnacos(fabs(

project(l.b–l.a,m.b–m.a)

/length(l.b–l.a)));}lmα先判断是否平行。若不平行，取一平面上一点（不在另一平面上），利用该点到另一平面的距离与到二面交线的距离来计算夹角拓展：求二面角时，可通过判断垂足是否在另一个半平面上来确定二面角是锐角还是钝角面与面夹角S2S1PH以上是有关点线面的一些基本问题这些问题若单独考虑都比较简单,但若组合起来,却能构成十分复杂的问题同样,再复杂的点线面问题,几乎都能分解成上述问题进行求解下面是几道相关的例题小结POJ2624已知平行四边形的两条邻边，求第四个点的坐标矢量和4thPointPOJ2019乱序给出凸多边形的顶点坐标，要求按逆时针顺序输出各顶点利用叉积排序ScrambledPolygonPOJ3462已知望远镜的方向和最大视角范围，求空间中指定点是否可以被看到点积求夹角HowIWonderWhatYouAre!POJ1569平面上有一些点（很少），求以这些点为顶点的三角形中，内部无其他点的面积最大的三角形是哪个枚举三角形三个顶点，用叉积判断其他点是否在三角形内MyacmTrianglesPOJ1292平面上有一些墙，人可以在墙上走，也可以在两堵墙间架木板走到另一堵墙上，求从起点到终点至少要带多长的木板主要问题在于求两条线段的距离：若相交则为0，否则可转化为点到线段的距离WillIndianaJonesGetThere?POJ3944空间内有一些可反射光线的球，现从某一点向某一方向射出一束光，求光线与球的最后一次碰撞点本题重点在于如何求反射后的直线，具体做法是：利用点与线的距离求线与球的交点，再求起点关于法线的对称点（利用点到线的垂足）SphericalMirrorsOBAPA'POJ1039在平面上有一根由线段（至多20根）组成的折线管道，管道任意处上边界比下边界高1，求是否存在一束光能穿过管道枚举一个上边界的顶点和一个下边界的顶点，组成一束光，利用线与线的交点判断是否在管内PipePOJ1066在正方形区域内有一些墙（至多30堵），每堵墙都是贯穿整个区域的且不会有超过两堵墙相交在同一点，求从正方形外走到形内指定点至少要穿越多少堵墙求出所有交点，将墙分为线段，取每条线段的中点，若两中点间没有其他直线（利用叉积判断）则连边，最后求最短路即可TreasureHunt空间中两个三角形是否有公共点若共面，问题转化为二维：分两种情况考虑：一个三角形的顶点在另一个三角形内（利用叉积）一个三角形的边与另一个三角形的边相交（利用线与线的交点）否则，求二面交线，然后求出交线与三角形相交的区间（利用线与线交点），最后判断两个区间是否有公共点Fireworks进阶——多边形、半平面从抽象到具体之前我们提到的都是抽象的三个基本元素，不需要什么特定的算法就能够解决绝大多数问题但接下来，我们需要面对的是更加具体的元素——多边形、半平面在这一部分中，我们将学习一些固定的算法来解决一些竞赛中常见的问题多边形、半平面点与多边形的位置关系凸包半平面交问题列表点与多边形的位置关系凸包半平面交问题列表点在多边形内点在多边形上点在多边形外点与多边形的位置关系点在多边形内射线与多边形有奇数个交点如何求交点？先视为直线与直线求交点利用点积判断该点是否同时在射线和线段上射线法特殊情况与顶点相交与边重合射线法平移：将射线稍微上升或下降一个很小的量分类讨论不同的边水平边：直接无视其余边：包含较高的端点，不包含较低的端点射线法射线法沿多边形走一圈，累计绕点旋转了多少角度0：点在形外±2π：点在形内角度计算θ=cos-1((a·b)/(|a||b|))转角法射线法运算速度快，精度高特殊情况较多转角法几乎没有特殊情况需要反三角函数、开方等，精度低，速度较慢射线法与转角法点与多边形的位置关系凸包半平面交问题列表定义给定一个平面点集要求找到一个最小的凸多边形，满足点集中的所有点都在该凸多边形的内部或边上性质任意两点的连线都在凸包内凸包先求出k个点的凸包，加入第k+1个点，得到新的凸包多用于三维凸包增量法使用叉积判断新加入的点与之前每条边的位置关系若点在某条边的“外面”，则将该边删除否则保留此边最终若没有边被删除，说明点在多边形内部，直接舍弃否则将新的点与相邻两个点连接成为新的凸包时间复杂度O(n2)，二分优化后为O(nlogn)增量法从最左最低点P0出发找一点P1，使得P0P1与水平方向夹角最小找一点P2，使得P0P2与P0P1夹角最小……最终，P0P1P2…Pm-1构成凸包卷包裹法P0P1P0P1P2P0P1P2P3使用叉积便可找到夹角最小的矢量时间复杂度O(n2)每一步得到的都是最终凸包上的一条边卷包裹法将点排序极角序水平序Graham扫描法按顺序将点添加入栈中若新的点在上一条边的“外面”，则将栈顶的点弹出不断重复此操作直至栈中无边或点在上一条边的“里面”，将新点入栈Graham扫描法同样通过叉积判断点和边的位置关系时间复杂度排序O(nlogn)扫描O(n)总计O(nlogn)不排序可能导致错误Graham扫描法点与多边形的位置关系凸包半平面交问题列表一条直线将平面分为两个半平面半平面交求被所有给定半平面包含的点的集合性质半平面交的结果是一个凸区域应用线性规划多边形的核半平面交先求出k个半平面交，加入第k+1个半平面，得到新的半平面交合并方法删去原半平面交上所有不在新半平面上的顶点求原半平面交与新半平面的交点将新的交点添加到半平面交上的合适位置时间复杂度O(n2)，二分优化后为O(nlogn)增量法按极角排序