计算几何教程课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/2/18,#,计算几何教程,Computational Geometry,计算几何教程Computational Geometry,1,计算几何的恶心之处,代码长，难写。,需要讨论各种边界情况。后面所介绍的算法，有些对于边界情况的处理很完美，不需要再做讨论；有些则不然，需要自行处理边界情况。,计算几何的恶心之处代码长，难写。,2,精度误差,精度误差,3,二维矢量,2,-Dimension Vector,二维矢量2-Dimension Vector,4,矢量,既有大小又有方向的量。,又,称为,向量,。,大家初中都毕业了我就不多说了。,矢量既有大小又有方向的量。,5,矢量的表示,矢量的表示,6,点积,点积,7,夹角,夹角,8,矢量的垂直,矢量的垂直,9,矢量的缩放,矢量的缩放,10,矢量的投影,矢量的投影,11,矢量的对称,矢量的对称,12,二维叉积,二维叉积,13,有向面积,有向面积,14,有向面积的符号,有向面积的符号,15,点,积和二维叉积的方向性,利用点积可以判断矢量的,前后,。,利用二维叉积可以判断矢量的,左右,。,点积和二维叉积的方向性利用点积可以判断矢量的前后。,16,二维,矢量的旋转,二维矢量的旋转,17,二维矢量的极角,二维矢量的极角,18,二维计算几何,2-Dimension Computational Geometry,二维计算几何2-Dimension Computationa,19,约定,约定,20,直线,直线,21,点到直线的距离,点到直线的距离,22,分点,分点,23,三角形的面积,三角形的面积,24,两直线交点,两直线交点,25,两线段交点,求出直线的交点，然后其判断是否在两条线段上即可。,若判断两线段是否相交，则要注意平行不一定不相交，两条线段可能有重合部分或重合点。,两线段交点求出直线的交点，然后其判断是否在两条线段上即可。,26,三角形的重心,三角形的重心,27,多边形,多边形,是平面上由,有限线段（,大于,2,）组成，且首尾连接起来划出,的封闭图形。,教程后面的多边形一般指,简单多边形,，即边不相交的多边形。,多边形的记录一般以,顺次,记录其顶点的方式完成，即顺次记录组成多边形的线段。方向一般为逆时针。,多边形多边形是平面上由有限线段（大于 2）组成，且首尾连接起,28,判断点在多边形内外,以要判断的点为起点任作一射线，计算该射线与多边形的交点数目。,若,有偶数个交点则在形外，否则在形内。,若与线段在端点处相交或重合，则要进行复杂的判断。此时可另取一射线。,判断点在多边形内外以要判断的点为起点任作一射线，计算该射线与,29,求多边形的面积,基本的思路是进行,三角剖分,。,求多边形的面积基本的思路是进行三角剖分。,30,求多边形的面积,如果用普通面积的累加来计算的话，三角剖分就变得十分复杂。,但是使用有向面积的话，这个过程就变得简单自然通用。,求多边形的面积如果用普通面积的累加来计算的话，三角剖分就变得,31,算法,算法,32,算法演示,算法演示,33,算法演示,算法演示,34,算法演示,算法演示,35,算法演示,算法演示,36,算法演示,算法演示,37,算法演示,算法演示,38,算法演示,算法演示,39,算法演示,算法演示,40,算法演示,算法演示,41,三角剖分,三角剖分即将多边形分为若干三角形部分，其中既有“正部分”亦有“负部分”。,利用这种方法可以解决很多问题。,三角剖分三角剖分即将多边形分为若干三角形部分，其中既有“正部,42,例题：求多边形的重心,名前通,，给定一个简单多边形，求其重心之所在。,例题：求多边形的重心名前通，给定一个简单多边形，求其重心之,43,预备知识：求质点组的重心,预备知识：求质点组的重心,44,解答,利用三角剖分，计算各个三角形的面积和重心，将此三角形化为一个质量为其面积，坐标为其重心的质点。,若此三角形属于“负部分”，则其拥有“负质量”。,最后计算质点组的重心即可。,解答利用三角剖分，计算各个三角形的面积和重心，将此三角形化为,45,凸集,凸集,46,凸集举例,空集,直线、射线、线段,凸多边形,圆及内部、二次曲线及内部,若干,种原料，每种原料含,A,成分和,B,成分的比例不同；混合这些原料能得到的产品的,A, B,两种成分的比例,凸集举例空集,47,凸包,对于点集,S,，包含,S,中所有点的最小的凸集称为,S,的凸包。,若,S,是,有限集，则其凸包是凸多边形。,直观来看，把,S,中所有点钉在一个木板上，用一个橡皮筋框起所有点来，一撒手，橡皮筋就表示出了,S,的凸包。,凸包对于点集 S，包含 S 中所有点的最小的凸集称为 S 的,48,凸包,凸包,49,水平序,Graham,扫描算法,Graham,扫描算法有水平序和极角序两种。,极角,序算法能一次确定整个凸包，但是计算极角需要用到三角函数，速度较慢，精度较差，特殊情况较多。,水平,序算法需要扫描两次，但排序简单，讨论简单，不易出错。,水平序 Graham 扫描算法Graham 扫描算法有水平序,50,算法流程,算法流程,51,算法演示,首先将所有点排序。,算法演示首先将所有点排序。,52,算法演示,将,1,和,2,压入栈。,算法演示将 1 和 2 压入栈。,53,算法演示,2,被弹出栈，,3,进栈。,算法演示2 被弹出栈，3 进栈。,54,算法演示,没有点被弹出栈，,4,进栈。,算法演示没有点被弹出栈，4 进栈。,55,算法演示,4,被弹出栈，,5,进栈。,算法演示4 被弹出栈，5 进栈。,56,算法演示,5,被弹出栈，,6,进栈。,算法演示5 被弹出栈，6 进栈。,57,算法演示,6,被弹出栈，,7,进栈。,算法演示6 被弹出栈，7 进栈。,58,算法演示,如此直到下凸壳被找到。,算法演示如此直到下凸壳被找到。,59,算法演示,倒序进行扫描找到上凸壳。,算法演示倒序进行扫描找到上凸壳。,60,Graham,扫描的时间复杂度,这太傻缺了。算法的瓶颈在排序，所以时间复杂度是,O(,N,log,N,),。,若坐标均为整数，可以用基数排序将复杂度优化到,O(,N,),。,Graham 扫描的时间复杂度这太傻缺了。算法的瓶颈在排序，,61,旋转卡壳算法,如何计算,N,个点中，距离最大的两个点的距离？,要求,O(,N,log,N,),的算法。,容易证明距离最大的两个点一定是凸包上的两个点，很明显是先求凸包然后做文章啦。,旋转卡壳算法如何计算 N 个点中，距离最大的两个点的距离？,62,对踵点,若凸包上的两个顶点能落在一对平行切线上，则称它们为对踵点。,容易,证明，答案一定是一对对踵点之间的距离。,对踵点若凸包上的两个顶点能落在一对平行切线上，则称它们为对踵,63,对踵点的枚举,从一对对踵点逆时针枚举下一对对踵点的话，只需要观察下图中,角和,角的大小，选择其中较小的一个转过去就行了。,对踵点的枚举从一对对踵点逆时针枚举下一对对踵点的话，只需要观,64,算法,最左侧点和最右侧点一定是对踵点。从此点对开始枚举即可。,注意不只有“点,点”的情况，还有“点,边”和“边,边”的情况。这些情况下要枚举所有的点对。,虽然看上去很简单，但是写起来还是要颇费一番周折的。,算法最左侧点和最右侧点一定是对踵点。从此点对开始枚举即可。,65,旋转卡壳练习题,POJ 2178,求点集中最远点,POJ 3608,求两凸包间的最近点,POJ 2079,求以点集中的点为顶点组成的三角形的最大面积，要求,O(,N,2,),算法。,旋转卡壳练习题POJ 2178 求点集中最远点,66,半平面,半平面,67,半平面的表示,半平面的表示,68,半平面的交,半平面是凸集，所以半平面的交也是凸集。,有限个半平面的交可能是空集、点、直线、射线、线段、凸多边形、有“开口”的形状甚至一个半平面。,半平面的交半平面是凸集，所以半平面的交也是凸集。,69,朴素的每次,O(N),算,法,为了保证结果是凸多边形或其退化，首先建立一个非常大的边框。你懂的。,每次顺次枚举多边形的边，与半平面求交，并将交的部分加入新多边形。,在,得到,半平面边界与凸多边形所交形成的边时，立即将其加入新多边形。,朴素的每次 O(N) 算法为了保证结果是凸多边形或其退化，首,70,算法演示,算法演示,71,值得注意的边界情况,1,值得注意的边界情况 1,72,值得注意的边界情况,2,值得注意的边界情况 2,73,值得注意的边界情况,3,值得注意的边界情况 3,74,合计,O(NlogN),的算法,这是朱泽园在其国家集训队论文,半平面交的新算法及其实用价值,中提出的算法。,由于建立了非常大的边框，半平面交的结果一定是一个凸多边形。,而凸多边形分为下凸壳和上凸壳。如果分开处理这两部分，就会获得非常好的性质。,合计 O(NlogN) 的算法这是朱泽园在其国家集训队论文,75,下凸壳与上凸壳,下凸壳与上凸壳,76,分别排序,按照极角，筛选出可能属于下凸壳和上凸壳的半平面分别按极角大小从小到大排序。,上凸壳排序时，极角位于第三象限的半平面要加上,2.,分别排序按照极角，筛选出可能属于下凸壳和上凸壳的半平面分别按,77,扫清障碍,对于极角相同的半平面，选择最靠左的一个，并将剩下的舍弃。,这样即保证所有的半平面的极角皆不相同。,扫清障碍对于极角相同的半平面，选择最靠左的一个，并将剩下的舍,78,处理下凸壳,处理下凸壳,79,算法演示,首先将前两个半平面进栈。,算法演示首先将前两个半平面进栈。,80,算法演示,x,0,x,1,，将新的半平面压入栈。,算法演示x0 x1，将新的半平面压入栈。,81,算法演示,x,0,x,1,，将栈顶弹出。,算法演示x0 x1，将栈顶弹出。,82,算法演示,x,0,x,1,，将新的半平面压入栈,。依此类推。,算法演示x0 x1，将新的半平面压入栈。依此类推。,83,处理上凸壳,处理上凸壳,84,上下凸壳的合并,只要凸壳中有不止一个半平面，就有可能出现没有用的半平面。,如,图，下图中的,p1,半平面没有用。,上下凸壳的合并只要凸壳中有不止一个半平面，就有可能出现没有用,85,滤,除没有用的半平面,先滤除左侧的半平面。指针,p1,指向下凸壳的最左侧，,p2,指向上凸壳的最左侧。,若下凸壳中还有至少两个半平面，检查,p2,与,p1,的边界的交，以及下凸壳中,p1,右侧的半平面与,p1,的边界的交。,若这两个交的并集为空或只有一个端点,，则舍弃半平面,p1,，将指针,p1,右移。,处理完,p1,后类似处理,p2,。若,p2,右移了，就重复处理,p1,，依此类推，直到二者都不右移了为止。,类似滤除右侧没有用的半平面。,滤除没有用的半平面先滤除左侧的半平面。指针 p1 指向下凸壳,86,实际上,“这两个交的并集为空或只有一个,端点”仍然只是讨论交点的坐标大小。,但是，这两个交点的,x,坐标可能相同，但,y,坐标不相同。所以不能像前面一样只讨论,x,坐标。,实际上“这两个交的并集为空或只有一个端点”仍然只是讨论交,87,算法演示,p1,上二者的交为空集。右移,p1,。,算法演示p1 上二者的交为空集。右移 p1。,88,算法演示,p2,上二者的交为空集。右移,p2,，重新检查,p1,。,算法演示p2 上二者的交为空集。右移 p2，重新检查 p1。,89,算法演示,p1,和,p2,均满足要求，结束对左侧的检查,。,算法演示p1 和 p2 均满足要求，结束对左侧的检查。,90,总结,算法的瓶颈仍然在于排序，所以时间复杂度为,O(,N,log,N,),。若使用桶排序，甚至能得到,O(,N,),的半平面交算法，但是并不会有明显的性能提升。,总体来说讨论比较辛苦，写起来不算很难。,精度存在比较大的问题，而且半平面交的题目一般都容许,O(,N,2,),算法，所以并不是很常用。,总结算法的瓶颈仍然在于排序，所以时间复杂度为 O(N log,91,半平面交练习题,POJ 1279,求多边形的核。核中的点满足其到多边形边界上任一点之间的线段只与多边形在那一点相交。,POJ 3525,求凸多边形最大内切圆半径。,POJ 2451,裸的半平面交,。,朱泽园专门为他的算法出的题，要求,O(,N,log,N,),算法。,POJ 3384,求在凸多边形内部放两个半径为,r,的圆所能覆盖的最大面积。两圆可以重叠，但不能与多边形相交。需要用到旋转卡壳。,半平面交练习题POJ 1279 求多边形的核。核中的点满足,92,圆,到定点,O,距离等于定值,r,的点的集合。,有时根据上下文也包含内部的点。,O,即为,圆心,，,r,即为,半径,。,圆只需要用这两个东西表示就行了。,圆到定点 O 距离等于定值 r 的点的集合。,93,圆与直线的交点,圆与直线的交点,94,圆与直线的交点,圆与直线的交点,95,圆与圆的交点,圆与圆的交点,96,圆与圆的交点,圆与圆的交点,97,圆与圆的交点,圆与圆的交点,98,圆的面积并,题目：,SPOJ CIRU,给出,N,(,N,1000,),个圆，求其并集的面积。,要求,O(,N,2,log,N,),的算法。,后面给出的算法由,AekdyCoin,原创。,圆的面积并题目：SPOJ CIRU,99,分析,如图，最后形成的图形是由很多弓形和多边形组成的。,弓形可以单独计算，多边形利用叉积亦可以分各边计算，所以我们可以单独考虑每个圆。,分析如图，最后形成的图形是由很多弓形和多边形组成的。,100,每个圆的情形,每个圆的情形,101,不,连通？,由于各个连通块中的弓形和多边形的边实际上都得到了很好的处理，所以图形,不连通没有,问题。,不连通？由于各个连通块中的弓形和多边形的边实际上都得到了很好,102,有“洞”？,发生了非常,NB,的事情。由于我们累加的是,有向面积,，而“洞”中多边形是反向,(,顺时针,),旋转的，所以“洞”会被,自动抵消,！,有“洞”？发生了非常 NB 的事情。由于我们累加的是有向面积,103,时间复杂度,对于每个圆，要求,O(,N,),次交，从而出现了,O(,N,),个交点。要找出未被覆盖的弧的话，要对交点进行排序，所以每个圆要花费,O(,N,log,N,),的时间进行处理。,总时间复杂度,O(,N,2,log,N,),。,时间复杂度对于每个圆，要求 O(N) 次交，从而出现了 O(,104,算法扩展,SPOJ CIRUT,求恰好被覆盖,1,次、,2,次、,、,N,次的面积。,算法的本质在于对“裸露”部分进行处理。这种方法也可以用于求很多圆与很多凸多边形的面积并,但是情况复杂得多，要讨论的情况也多得多。,算法扩展SPOJ CIRUT 求恰好被覆盖 1 次、2 次,105,三维矢量,3-Dimension Vector,三维矢量3-Dimension Vector,106,第三维度,第三维度,107,三维叉积,三维叉积,108,左手系与右手系,x,y,z,轴的方向，传统上应该满足,右手系,。,即,伸出右手，将四指由,x,轴指向沿小于平角转到,y,轴指向，,拇指所,指即,为,z,轴指向。,类似也可以定义左手系。三个不共面的矢量必然满足左手系与右手系中的一种。,左手系与右手系x, y, z 轴的方向，传统上应该满足右手系,109,文字游戏,注意“,a,b,c,成右手系”和“,b,a,c,成右手系”是截然相反的两个命题。,但是“,a,b,c,成右手系”和“,b,c,a,成右手系,”是同一个命题。,画图看一下这是为什么。,文字游戏注意“a, b, c 成右手系”和“b, a, c,110,三维叉积的性质,三维叉积的性质,111,在三维空间我们失去的,极角,。在三维空间中描述矢量的方向不能只用一个角度，实际上需要使用两个角度。,左右,。在三维空间中，,两个矢量间,没有左与右的概念。取而代之的是,三个矢量间,左手系,与,右手系,的概念。,在三维空间我们失去的极角。在三维空间中描述矢量的方向不能只用,112,混合积,混合积,113,有向体积,如图。,a,b,c,的混合积的模，即为,a,b,c,所成的,平行六面体,的体积。,考虑符号的话，混合积又称为,有向体积,。,a,b,c,所,成三棱锥的体积为,平行六面体的,1 / 6,.,有向体积如图。a, b, c 的混合积的模，即为 a, b,114,一切的本质：行列式,一切的本质：行列式,115,三维计算几何,3,-Dimension Computational Geometry,三维计算几何3-Dimension Computationa,116,三维直线,三维直线的表示法与二维类似。,计算点到直线的距离的方法与二维相同。,计算分点的方式也与二维相同。,三维直线三维直线的表示法与二维类似。,117,异面直线,但是在三维空间中，直线除平行与相交之外有着第三种位置关系：,异面,。,异,面直线的距离即为两条直线上距离最小的两点之距离。你们都知道这就是两条直线的,公垂线段,的长度。,异面直线但是在三维空间中，直线除平行与相交之外有着第三种位置,118,异面直线的距离,异面直线的距离,119,异面直线的距离,异面直线的距离,120,两直线的交点,先求它们的距离。若不为,0,，显然木有交点。,否则，若它们的方向矢量平行，它们重合。,否则，它们是相交的。推荐利用后面所讲的,投影技术,将其转化为二维问题。,两直线的交点先求它们的距离。若不为 0，显然木有交点。,121,平面,平面是到两点距离相等的点的轨迹,。,具体是个啥乃们应该清楚,平面平面是到两点距离相等的点的轨迹。,122,点法式,与平面垂直，即与平面上一切矢量垂直的非零矢量叫做平面的,法矢量,。可以证明平面的所有法矢量平行。,记录平面的一个法矢量,v,，再记录平面上一点,P,，就可以完整表示整个平面了。,点法式与平面垂直，即与平面上一切矢量垂直的非零矢量叫做平面的,123,点到平面的距离,点到平面的距离,124,直线与平面的交点,直线与平面的交点,125,直线与平面的交点,直线与平面的交点,126,平面与平面的交线,平面与平面的交线,127,二面角,就是两个平面的法矢量的夹角啦。,二面角就是两个平面的法矢量的夹角啦。,128,平面上点的二维投影,平面上点的二维投影,129,平面上点的二维投影,平面上点的二维投影,130,平面上点的二维投影,平面上点的二维投影,131,多面体,多面体是指三维空间中由平面和直边组成的几何形体,。,以上是科学定义。我不觉得这么一句废话有什么用。,我们假定多面体的每个面都是,三角形,的。,多面体多面体是指三维空间中由平面和直边组成的几何形体。,132,凸多面体,若一个多面体是凸集，则它是凸多面体。,如同凸多边形是半平面的交一样，凸,多面体,也可以看做,半空间,的交。,求半空间的交非常复杂，在此不多做介绍。不过有关于半空间的基本知识仍要加以讲解。,凸多面体若一个多面体是凸集，则它是凸多面体。,133,半空间的表示,如同半平面可以用,两个互异的有序点,来表示一样，半空间可以用,三个不共线的有序点,来表示。,半空间的表示如同半平面可以用两个互异的有序点来表示一样，半空,134,半空间的表示,半空间的表示,135,简单判别法,若要判断点,P,在内侧还是外侧，则从点,P,向平面看去。,若半空间的三个有序点成,逆时针,，则点,P,在,外侧,；否则点,P,就在,内侧,。,简单判别法若要判断点 P 在内侧还是外侧，则从点 P 向平面,136,凸多面体的表示,表示一个凸多面体需要记录其所有的面。对于所有的面，要正确记录这个面上点的顺序。,根据假设，每个面都是三角形的，即包含三个点，所以每个面都表示了一个半空间。,凸多面体,应,为这些半空间,内侧,的交。,凸多面体的表示表示一个凸多面体需要记录其所有的面。对于所有的,137,可视,若,P,在半空间,A,的外侧，则称半空间,A,，或,A,所代表的平面,对,P,是,可视,的。,我们在,观察一个凸多面体的时候，看到的面即为视点的可视面。,凸多面体各个面的点的顺序应该保证，从多面体内部的任意一点看去，所有的面都不可视。,若将左右手系用行列式的符号替代，则可视的概念能推广到高维。,可视若 P 在半空间 A 的外侧，则称半空间 A，或 A 所,138,若多面体有非三角面,这样的面记录的时候要保证，其上所有点从多面体的内部看去成,顺时针,排列。,此时这个面仍然能有效地表示一个半空间。,若多面体有非三角面这样的面记录的时候要保证，其上所有点从多面,139,三维凸包,从凸包的定义出发推断，一坨三维空间中的点的凸包是一个凸多面体。,事已,至此我们只好想办法求它了。,但是,不难发现由于失去了左右这一概念，,Graham,扫描法彻底报废了。,那怎么办？,为了方便起见，我们假定没有四点共面的情况。,三维凸包从凸包的定义出发推断，一坨三维空间中的点的凸包是一个,140,暴力方法,O(,N,3,),枚举所有的点的三元组，将其看做半空间。若所有其它的点都在这个半空间的内侧，则这个面是凸包的一个面。,时间复杂,度,O(,N,4,),。非常好写！,暴力方法O(N3) 枚举所有的点的三元组，将其看做半空间。若,141,增量法,增量法作为求凸包的有力算法，可以解决任意维度的凸包问题。,最坏情况下其时间复杂度为,O(,N,2,),。,增量法增量法作为求凸包的有力算法，可以解决任意维度的凸包问题,142,算法流程,取出点集中的四个点，这四个点组成的四个面都是初始凸包的面。调整各个面上点的顺序使得从内部看去各个面均不可视。,之后添加其它各点。如果从这个点看去，所有的面均不可视，则此点在凸包内部。什么都不做，跳过该点。,否则,算法流程取出点集中的四个点，这四个点组成的四个面都是初始凸包,143,算法流程,算法流程,144,算法演示,建立初始凸包，并试图添加第一个点。,算法演示建立初始凸包，并试图添加第一个点。,145,算法演示,添加第一个点完毕。,算法演示添加第一个点完毕。,146,算法演示,试图添加第二个点。,算法演示试图添加第二个点。,147,算法演示,添加第二个点完毕。如此添加所有点即可。,算法演示添加第二个点完毕。如此添加所有点即可。,148,随机增量,随机增量,149,三维凸包练习题,POJ 3528,裸的三维凸包，且不含四点共面。,三维凸包的出题概率很低，就不提供更多的练习题了。,三维凸包练习题POJ 3528 裸的三维凸包，且不含四点共,150,球,在三维空间中，到定点距离等于定值的点的轨迹即为球。,球可以用球心,O,和半径,r,来表示。,二维球面,上的几何学称为球面几何，是非欧几何的一种。自然我们不会研究如此高深的问题。,球在三维空间中，到定点距离等于定值的点的轨迹即为球。,151,球与直线的交点,球与直线的交点,152,球与平面或球的交圆,既然已经到了如此程度，想必大家已经可以自己来求了吧。,先,求交圆的圆心，再求交圆的半径。由于这个圆是在三维空间中的，需要标明其在哪个平面上,。,球与平面或球的交圆既然已经到了如此程度，想必大家已经可以自己,153,经纬度,经纬度,154,经纬度到三维坐标的转换,经纬度到三维坐标的转换,155,三维旋转,确认旋转之后坐标轴的位置，利用旋转矩阵求解即可。,三维旋转确认旋转之后坐标轴的位置，利用旋转矩阵求解即可。,156,