计算几何教程课件.pptx

1、计算几何教程Computational Geometry计算几何的恶心之处代码长，难写。需要讨论各种边界情况。后面所介绍的算法，有些对于边界情况的处理很完美，不需要再做讨论；有些则不然，需要自行处理边界情况。精度误差二维矢量2-Dimension Vector矢量既有大小又有方向的量。又称为向量。大家初中都毕业了我就不多说了。矢量的表示点积夹角矢量的垂直矢量的缩放矢量的投影矢量的对称二维叉积有向面积有向面积的符号点积和二维叉积的方向性利用点积可以判断矢量的前后。利用二维叉积可以判断矢量的左右。二维矢量的旋转二维矢量的极角二维计算几何2-Dimension Computational Geome

2、try约定直线点到直线的距离分点三角形的面积两直线交点两线段交点求出直线的交点，然后其判断是否在两条线段上即可。若判断两线段是否相交，则要注意平行不一定不相交，两条线段可能有重合部分或重合点。三角形的重心多边形多边形是平面上由有限线段（大于 2）组成，且首尾连接起来划出的封闭图形。教程后面的多边形一般指简单多边形，即边不相交的多边形。多边形的记录一般以顺次记录其顶点的方式完成，即顺次记录组成多边形的线段。方向一般为逆时针。判断点在多边形内外以要判断的点为起点任作一射线，计算该射线与多边形的交点数目。若有偶数个交点则在形外，否则在形内。若与线段在端点处相交或重合，则要进行复杂的判断。此时可另取一

3、射线。求多边形的面积基本的思路是进行三角剖分。求多边形的面积如果用普通面积的累加来计算的话，三角剖分就变得十分复杂。但是使用有向面积的话，这个过程就变得简单自然通用。算法算法演示算法演示算法演示算法演示算法演示算法演示算法演示算法演示算法演示三角剖分三角剖分即将多边形分为若干三角形部分，其中既有“正部分”亦有“负部分”。利用这种方法可以解决很多问题。例题：求多边形的重心名前通，给定一个简单多边形，求其重心之所在。预备知识：求质点组的重心解答利用三角剖分，计算各个三角形的面积和重心，将此三角形化为一个质量为其面积，坐标为其重心的质点。若此三角形属于“负部分”，则其拥有“负质量”。最后计算质点组的

4、重心即可。凸集凸集举例空集直线、射线、线段凸多边形圆及内部、二次曲线及内部若干种原料，每种原料含 A 成分和 B 成分的比例不同；混合这些原料能得到的产品的 A, B 两种成分的比例凸包对于点集 S，包含 S 中所有点的最小的凸集称为 S 的凸包。若 S 是有限集，则其凸包是凸多边形。直观来看，把 S 中所有点钉在一个木板上，用一个橡皮筋框起所有点来，一撒手，橡皮筋就表示出了 S 的凸包。凸包水平序 Graham 扫描算法Graham 扫描算法有水平序和极角序两种。极角序算法能一次确定整个凸包，但是计算极角需要用到三角函数，速度较慢，精度较差，特殊情况较多。水平序算法需要扫描两次，但排序简单，

5、讨论简单，不易出错。算法流程算法演示首先将所有点排序。算法演示将 1 和 2 压入栈。算法演示2 被弹出栈，3 进栈。算法演示没有点被弹出栈，4 进栈。算法演示4 被弹出栈，5 进栈。算法演示5 被弹出栈，6 进栈。算法演示6 被弹出栈，7 进栈。算法演示如此直到下凸壳被找到。算法演示倒序进行扫描找到上凸壳。Graham 扫描的时间复杂度这太傻缺了。算法的瓶颈在排序，所以时间复杂度是 O(N log N)。若坐标均为整数，可以用基数排序将复杂度优化到 O(N)。旋转卡壳算法如何计算 N 个点中，距离最大的两个点的距离？要求 O(N log N) 的算法。容易证明距离最大的两个点一定是凸包上的两

6、个点，很明显是先求凸包然后做文章啦。对踵点若凸包上的两个顶点能落在一对平行切线上，则称它们为对踵点。容易证明，答案一定是一对对踵点之间的距离。对踵点的枚举从一对对踵点逆时针枚举下一对对踵点的话，只需要观察下图中 角和 角的大小，选择其中较小的一个转过去就行了。算法最左侧点和最右侧点一定是对踵点。从此点对开始枚举即可。注意不只有“点 点”的情况，还有“点 边”和“边 边”的情况。这些情况下要枚举所有的点对。虽然看上去很简单，但是写起来还是要颇费一番周折的。旋转卡壳练习题POJ 2178 求点集中最远点POJ 3608 求两凸包间的最近点POJ 2079 求以点集中的点为顶点组成的三角形的最大面积

7、，要求 O(N2) 算法。半平面半平面的表示半平面的交半平面是凸集，所以半平面的交也是凸集。有限个半平面的交可能是空集、点、直线、射线、线段、凸多边形、有“开口”的形状甚至一个半平面。朴素的每次 O(N) 算法为了保证结果是凸多边形或其退化，首先建立一个非常大的边框。你懂的。每次顺次枚举多边形的边，与半平面求交，并将交的部分加入新多边形。在得到半平面边界与凸多边形所交形成的边时，立即将其加入新多边形。算法演示值得注意的边界情况 1值得注意的边界情况 2值得注意的边界情况 3合计 O(NlogN) 的算法这是朱泽园在其国家集训队论文半平面交的新算法及其实用价值中提出的算法。由于建立了非常大的边框

8、，半平面交的结果一定是一个凸多边形。而凸多边形分为下凸壳和上凸壳。如果分开处理这两部分，就会获得非常好的性质。下凸壳与上凸壳分别排序按照极角，筛选出可能属于下凸壳和上凸壳的半平面分别按极角大小从小到大排序。上凸壳排序时，极角位于第三象限的半平面要加上 2.扫清障碍对于极角相同的半平面，选择最靠左的一个，并将剩下的舍弃。这样即保证所有的半平面的极角皆不相同。处理下凸壳算法演示首先将前两个半平面进栈。算法演示x0 x1，将新的半平面压入栈。算法演示x0 x1，将栈顶弹出。算法演示x0 x1，将新的半平面压入栈。依此类推。处理上凸壳上下凸壳的合并只要凸壳中有不止一个半平面，就有可能出现没有用的半平面

9、。如图，下图中的 p1 半平面没有用。滤除没有用的半平面先滤除左侧的半平面。指针 p1 指向下凸壳的最左侧，p2 指向上凸壳的最左侧。若下凸壳中还有至少两个半平面，检查 p2 与 p1 的边界的交，以及下凸壳中 p1 右侧的半平面与 p1 的边界的交。若这两个交的并集为空或只有一个端点，则舍弃半平面 p1，将指针 p1 右移。处理完 p1 后类似处理 p2。若 p2 右移了，就重复处理 p1，依此类推，直到二者都不右移了为止。类似滤除右侧没有用的半平面。实际上“这两个交的并集为空或只有一个端点”仍然只是讨论交点的坐标大小。但是，这两个交点的 x 坐标可能相同，但 y 坐标不相同。所以不能像前面

10、一样只讨论 x 坐标。算法演示p1 上二者的交为空集。右移 p1。算法演示p2 上二者的交为空集。右移 p2，重新检查 p1。算法演示p1 和 p2 均满足要求，结束对左侧的检查。总结算法的瓶颈仍然在于排序，所以时间复杂度为 O(N log N)。若使用桶排序，甚至能得到 O(N) 的半平面交算法，但是并不会有明显的性能提升。总体来说讨论比较辛苦，写起来不算很难。精度存在比较大的问题，而且半平面交的题目一般都容许 O(N2) 算法，所以并不是很常用。半平面交练习题POJ 1279 求多边形的核。核中的点满足其到多边形边界上任一点之间的线段只与多边形在那一点相交。POJ 3525 求凸多边形最大

11、内切圆半径。POJ 2451 裸的半平面交。朱泽园专门为他的算法出的题，要求 O(N log N) 算法。POJ 3384 求在凸多边形内部放两个半径为 r 的圆所能覆盖的最大面积。两圆可以重叠，但不能与多边形相交。需要用到旋转卡壳。圆到定点 O 距离等于定值 r 的点的集合。有时根据上下文也包含内部的点。O 即为圆心，r 即为半径。圆只需要用这两个东西表示就行了。圆与直线的交点圆与直线的交点圆与圆的交点圆与圆的交点圆与圆的交点圆的面积并题目：SPOJ CIRU给出 N (N 1000) 个圆，求其并集的面积。要求 O(N2 log N) 的算法。后面给出的算法由 AekdyCoin 原创。分

12、析如图，最后形成的图形是由很多弓形和多边形组成的。弓形可以单独计算，多边形利用叉积亦可以分各边计算，所以我们可以单独考虑每个圆。每个圆的情形不连通？由于各个连通块中的弓形和多边形的边实际上都得到了很好的处理，所以图形不连通没有问题。有“洞”？发生了非常 NB 的事情。由于我们累加的是有向面积，而“洞”中多边形是反向 (顺时针) 旋转的，所以“洞”会被自动抵消！时间复杂度对于每个圆，要求 O(N) 次交，从而出现了 O(N) 个交点。要找出未被覆盖的弧的话，要对交点进行排序，所以每个圆要花费 O(N log N) 的时间进行处理。总时间复杂度 O(N2 log N)。算法扩展SPOJ CIRUT

13、 求恰好被覆盖 1 次、2 次、N 次的面积。算法的本质在于对“裸露”部分进行处理。这种方法也可以用于求很多圆与很多凸多边形的面积并但是情况复杂得多，要讨论的情况也多得多。三维矢量3-Dimension Vector第三维度三维叉积左手系与右手系x, y, z 轴的方向，传统上应该满足右手系。即伸出右手，将四指由 x 轴指向沿小于平角转到 y 轴指向，拇指所指即为 z 轴指向。类似也可以定义左手系。三个不共面的矢量必然满足左手系与右手系中的一种。文字游戏注意“a, b, c 成右手系”和“b, a, c 成右手系”是截然相反的两个命题。但是“a, b, c 成右手系”和“b, c, a 成右手

14、系”是同一个命题。画图看一下这是为什么。三维叉积的性质在三维空间我们失去的极角。在三维空间中描述矢量的方向不能只用一个角度，实际上需要使用两个角度。左右。在三维空间中，两个矢量间没有左与右的概念。取而代之的是三个矢量间左手系与右手系的概念。混合积有向体积如图。a, b, c 的混合积的模，即为 a, b, c 所成的平行六面体的体积。考虑符号的话，混合积又称为有向体积。a, b, c 所成三棱锥的体积为平行六面体的 1 / 6.一切的本质：行列式三维计算几何3-Dimension Computational Geometry三维直线三维直线的表示法与二维类似。计算点到直线的距离的方法与二维相同

15、。计算分点的方式也与二维相同。异面直线但是在三维空间中，直线除平行与相交之外有着第三种位置关系：异面。异面直线的距离即为两条直线上距离最小的两点之距离。你们都知道这就是两条直线的公垂线段的长度。异面直线的距离异面直线的距离两直线的交点先求它们的距离。若不为 0，显然木有交点。否则，若它们的方向矢量平行，它们重合。否则，它们是相交的。推荐利用后面所讲的投影技术将其转化为二维问题。平面平面是到两点距离相等的点的轨迹。具体是个啥乃们应该清楚点法式与平面垂直，即与平面上一切矢量垂直的非零矢量叫做平面的法矢量。可以证明平面的所有法矢量平行。记录平面的一个法矢量 v，再记录平面上一点 P，就可以完整表示整

16、个平面了。点到平面的距离直线与平面的交点直线与平面的交点平面与平面的交线二面角就是两个平面的法矢量的夹角啦。平面上点的二维投影平面上点的二维投影平面上点的二维投影多面体多面体是指三维空间中由平面和直边组成的几何形体。以上是科学定义。我不觉得这么一句废话有什么用。我们假定多面体的每个面都是三角形的。凸多面体若一个多面体是凸集，则它是凸多面体。如同凸多边形是半平面的交一样，凸多面体也可以看做半空间的交。求半空间的交非常复杂，在此不多做介绍。不过有关于半空间的基本知识仍要加以讲解。半空间的表示如同半平面可以用两个互异的有序点来表示一样，半空间可以用三个不共线的有序点来表示。半空间的表示简单判别法若要

17、判断点 P 在内侧还是外侧，则从点 P 向平面看去。若半空间的三个有序点成逆时针，则点 P 在外侧；否则点 P 就在内侧。凸多面体的表示表示一个凸多面体需要记录其所有的面。对于所有的面，要正确记录这个面上点的顺序。根据假设，每个面都是三角形的，即包含三个点，所以每个面都表示了一个半空间。凸多面体应为这些半空间内侧的交。可视若 P 在半空间 A 的外侧，则称半空间 A，或 A 所代表的平面对 P 是可视的。我们在观察一个凸多面体的时候，看到的面即为视点的可视面。凸多面体各个面的点的顺序应该保证，从多面体内部的任意一点看去，所有的面都不可视。若将左右手系用行列式的符号替代，则可视的概念能推广到高维

18、。若多面体有非三角面这样的面记录的时候要保证，其上所有点从多面体的内部看去成顺时针排列。此时这个面仍然能有效地表示一个半空间。三维凸包从凸包的定义出发推断，一坨三维空间中的点的凸包是一个凸多面体。事已至此我们只好想办法求它了。但是不难发现由于失去了左右这一概念，Graham 扫描法彻底报废了。那怎么办？为了方便起见，我们假定没有四点共面的情况。暴力方法O(N3) 枚举所有的点的三元组，将其看做半空间。若所有其它的点都在这个半空间的内侧，则这个面是凸包的一个面。时间复杂度 O(N4)。非常好写！ 增量法增量法作为求凸包的有力算法，可以解决任意维度的凸包问题。最坏情况下其时间复杂度为 O(N2)。

19、算法流程取出点集中的四个点，这四个点组成的四个面都是初始凸包的面。调整各个面上点的顺序使得从内部看去各个面均不可视。之后添加其它各点。如果从这个点看去，所有的面均不可视，则此点在凸包内部。什么都不做，跳过该点。否则算法流程算法演示建立初始凸包，并试图添加第一个点。算法演示添加第一个点完毕。算法演示试图添加第二个点。算法演示添加第二个点完毕。如此添加所有点即可。随机增量三维凸包练习题POJ 3528 裸的三维凸包，且不含四点共面。三维凸包的出题概率很低，就不提供更多的练习题了。球在三维空间中，到定点距离等于定值的点的轨迹即为球。球可以用球心 O 和半径 r 来表示。二维球面上的几何学称为球面几何，是非欧几何的一种。自然我们不会研究如此高深的问题。球与直线的交点球与平面或球的交圆既然已经到了如此程度，想必大家已经可以自己来求了吧。先求交圆的圆心，再求交圆的半径。由于这个圆是在三维空间中的，需要标明其在哪个平面上。经纬度经纬度到三维坐标的转换三维旋转确认旋转之后坐标轴的位置，利用旋转矩阵求解即可。