北京大学ACM暑期课讲义-计算几何教程

计算几何教程ComputationalGeometry计算几何的恶心之处代码长，难写。需要讨论各种边界情况。后面所介绍的算法，有些对于边界情况的处理很完美，不需要再做讨论；有些则不然，需要自行处理边界情况。精度误差计算几何问题中，很多时候需要繁杂的浮点运算和三角函数运算，这样会产生人神共愤的精度问题。因此，我们采取以下措施尽量避免精度误差（其中ε是个小量，多取10–8）：𝑎=𝑏⇔𝑎−𝑏𝜖𝑎𝑏⇔𝑎−𝑏−𝜖𝑎≤𝑏⇔𝑎−𝑏𝜖2-DimensionVector二维矢量矢量既有大小又有方向的量。又称为向量。大家初中都毕业了我就不多说了。矢量的表示在n维空间下，矢量经常被表达为n个数的元组𝒂=(𝑎1,𝑎2,…,𝑎𝑛)。在二维空间下则以(𝑥,𝑦)一对整数表示。在高等代数中，n维矢量一般表示为列矢量的形式𝑎1𝑎2…𝑎𝑛𝑇，即n×1的矩阵。点积两个n维矢量的点积是一个标量，有𝑎1,𝑎2,…,𝑎𝑛⋅𝑏1,𝑏2,…,𝑏𝑛≝𝑎1𝑏1+𝑎2𝑏2+⋯+𝑎𝑛𝑏𝑛。由此，矢量的模（即长度）定义为𝒂≝𝒂⋅𝒂=𝒂2。点积满足交换律。夹角点积之另一定义为𝒂⋅𝒃=𝒂𝒃cos𝜃，其中θ为a和b之夹角。如下图，a与b的点积的值实际上就是a的模乘b在a上的投影的“模”，但是若其投影与a方向相反则为负。矢量的垂直垂直的矢量有𝜃=𝜋2，即cos𝜃=0.所以a和b垂直定义为𝒂⋅𝒃=0。矢量的缩放矢量𝒂𝒂是与a同向的单位矢量，即模长是1的矢量。所以与a同向，但长度是l的矢量，为𝑙𝒂𝒂。而与a共线但方向相反，长度是l的矢量为−𝑙𝒂𝒂。矢量的投影b在a上的投影的“模”是𝒂⋅𝒃𝒂。所以b在a上的投影即为𝒂⋅𝒃𝒂𝒂𝒂=𝒂𝒂⋅𝒃𝒂2。矢量的对称记b在a上的投影为𝒔=𝒂𝒂⋅𝒃𝒂2。则b关于a的对称为𝒃−2𝒃−𝒔=2𝒔−𝒃=2𝒂𝒂⋅𝒃𝒂2−𝒃。二维叉积两个二维矢量的二维叉积是一个标量，定义为𝑥1,𝑦1×𝑥2,𝑦2≝𝑥1𝑦2−𝑥2𝑦1。二维叉积满足逆交换律：𝒂×𝒃=−𝒃×𝒂。二维叉积是计算几何中最常用的概念。有向面积经过计算可以知道，a和b所成的平行四边形的面积即为𝒂×𝒃的值。去掉绝对值符号，二维叉积则定义为有向面积。有向面积的符号伸出右手，将四指由a沿小于平角转到b。若拇指指向纸面上方，则𝒂×𝒃为正，否则为负。若a与b共线，则𝒂×𝒃=0。利用有向面积可以非常简单自然地计算简单多边形的面积。后面我们会详述这一点。点积和二维叉积的方向性利用点积可以判断矢量的前后。利用二维叉积可以判断矢量的左右。二维矢量的旋转将矢量看做列矢量，即2×1的矩阵。则将矢量a逆时针旋转θ之后的矢量为cos𝜃−sin𝜃sin𝜃cos𝜃𝒂.记矩阵T𝜃=cos𝜃−sin𝜃sin𝜃cos𝜃.二维矢量的极角极角指示矢量的方向，以x轴正半轴逆时针转过的角度来指示。即矢量𝑥,𝑦的极角为atan2(𝑦,𝑥)。极角的取值范围是−𝜋,𝜋。2-DimensionComputationalGeometry二维计算几何约定虽然点与矢量有着本质的不同，但是为了方便起见，本教程中坐标为(𝑥,𝑦)的点也作为矢量(𝑥,𝑦)使用，反之亦然。比如，A和B的中点𝑀=𝐴+𝐵2.直线在二维空间中，直线用两个相异点A和B表示。则∀𝜆∈ℝ,𝜆𝐴+1−𝜆𝐵代表直线上一点。若λ0，则此点在B外侧；若λ1，则此点在A外侧。视情况，有时也用一个点P和一个方向矢量v来表示。则∀𝜆∈ℝ,𝑃+𝜆𝒗代表直线上一点。点到直线的距离若要计算点P到直线AB的距离，只需要计算𝐴𝑃与它到𝐴𝐵的投影之差的模即可。即𝐴𝑃−𝐴𝐵𝐴𝐵⋅𝐴𝑃𝐴𝐵2。𝐴𝑃−𝐴𝐵𝐴𝐵⋅𝐴𝑃𝐴𝐵2后面称为P到AB的垂直矢量。注意，这名字是我自己起的。分点如下图，若A,C,B共线，且AC𝐶𝐵=𝜆1𝜆2，则𝐶=𝜆2𝐴+𝜆1𝐵𝜆1+𝜆2。特别地，若C在A外侧，则𝜆10；若C在B外侧，则𝜆20。此时上式仍然成立。三角形的面积利用二维叉积即得SΔ𝐴𝐵𝐶=𝐴𝐵×𝐴𝐶2。两直线交点先排除平行或重合的情况。𝐴𝑂𝑂𝐵=S(Δ𝐴𝐷𝐶)S(Δ𝐵𝐶𝐷)=𝐴𝐷×𝐴𝐶𝐵𝐶×𝐵𝐷.计算分点即可得到点O.注意上式中A和B叉积顺序相反。按照有向面积，此方法在交点不在线段AB上，甚至也不在线段CD上时亦成立。两线段交点求出直线的交点，然后其判断是否在两条线段上即可。若判断两线段是否相交，则要注意平行不一定不相交，两条线段可能有重合部分或重合点。三角形的重心众所周知，三角形的重心G是三条中线的交点，即AM与BN的交点。而𝑀=𝐵+𝐶2，𝐴𝐺𝐺𝑀=2。故𝐺=2𝑀+𝐴3=𝐴+𝐵+𝐶3。多边形多边形是平面上由有限线段（大于2）组成，且首尾连接起来划出的封闭图形。教程后面的多边形一般指简单多边形，即边不相交的多边形。多边形的记录一般以顺次记录其顶点的方式完成，即顺次记录组成多边形的线段。方向一般为逆时针。判断点在多边形内外以要判断的点为起点任作一射线，计算该射线与多边形的交点数目。若有偶数个交点则在形外，否则在形内。若与线段在端点处相交或重合，则要进行复杂的判断。此时可另取一射线。求多边形的面积基本的思路是进行三角剖分。求多边形的面积如果用普通面积的累加来计算的话，三角剖分就变得十分复杂。但是使用有向面积的话，这个过程就变得简单自然通用。算法按逆时针方向顺次为各边指定方向。对于每条边𝐴𝐵，累加𝐴×𝐵2的值。最后得到的结果即为多边形的面积。当然也可以累加𝐴×𝐵的值，最后再除以2。算法演示算法演示算法演示算法演示算法演示算法演示算法演示算法演示算法演示三角剖分三角剖分即将多边形分为若干三角形部分，其中既有“正部分”亦有“负部分”。利用这种方法可以解决很多问题。例题：求多边形的重心名前通り，给定一个简单多边形，求其重心之所在。预备知识：求质点组的重心n个位置分别为𝐴1,𝐴2,…,𝐴𝑛，质量为𝑚1,𝑚2,…,𝑚𝑛的质点构成的质点组的重心为𝑚𝑘𝐴𝑘𝑛𝑘=1𝑚𝑘𝑛𝑘=1解答利用三角剖分，计算各个三角形的面积和重心，将此三角形化为一个质量为其面积，坐标为其重心的质点。若此三角形属于“负部分”，则其拥有“负质量”。最后计算质点组的重心即可。凸集对于一个点集S，若∀𝑎,𝑏∈𝑆,𝜆∈[0,1]，有𝜆𝑎+1−𝜆𝑏∈𝑆，则称S是凸集。说人话的话，就是对于点集中任意两点，以两点为端点的线段上的所有点也属于这个点集。若多边形及其内点是凸集，则称这个多边形为凸多边形。可以证明凸集的交也是凸集。凸集举例空集直线、射线、线段凸多边形圆及内部、二次曲线及内部若干种原料，每种原料含A成分和B成分的比例不同；混合这些原料能得到的产品的A,B两种成分的比例凸包对于点集S，包含S中所有点的最小的凸集称为S的凸包。若S是有限集，则其凸包是凸多边形。直观来看，把S中所有点钉在一个木板上，用一个橡皮筋框起所有点来，一撒手，橡皮筋就表示出了S的凸包。凸包水平序Graham扫描算法Graham扫描算法有水平序和极角序两种。极角序算法能一次确定整个凸包，但是计算极角需要用到三角函数，速度较慢，精度较差，特殊情况较多。水平序算法需要扫描两次，但排序简单，讨论简单，不易出错。算法流程对顶点按x为第一关键字，y为第二关键字进行排序。准备一个空栈，并将前两个点压入栈。对于每一个顶点A，只要栈顶中还有至少两个顶点，记栈顶为T，栈中第二个为U。若𝑈𝑇×𝑇𝐴≤0，则将T弹出。重复此过程。直到上一步不再弹出顶点，将A压入栈。扫描完一遍之后得到凸包的下凸壳。将点集倒过来再进行一次，得到凸包的上凸壳，组合起来即可。算法演示首先将所有点排序。算法演示将1和2压入栈。算法演示2被弹出栈，3进栈。算法演示没有点被弹出栈，4进栈。算法演示4被弹出栈，5进栈。算法演示5被弹出栈，6进栈。算法演示6被弹出栈，7进栈。算法演示如此直到下凸壳被找到。算法演示倒序进行扫描找到上凸壳。Graham扫描的时间复杂度这太傻缺了。算法的瓶颈在排序，所以时间复杂度是O(NlogN)。若坐标均为整数，可以用基数排序将复杂度优化到O(N)。旋转卡壳算法如何计算N个点中，距离最大的两个点的距离？要求O(NlogN)的算法。容易证明距离最大的两个点一定是凸包上的两个点，很明显是先求凸包然后做文章啦。对踵点若凸包上的两个顶点能落在一对平行切线上，则称它们为对踵点。容易证明，答案一定是一对对踵点之间的距离。对踵点的枚举从一对对踵点逆时针枚举下一对对踵点的话，只需要观察下图中α角和β角的大小，选择其中较小的一个转过去就行了。算法最左侧点和最右侧点一定是对踵点。从此点对开始枚举即可。注意不只有“点–点”的情况，还有“点–边”和“边–边”的情况。这些情况下要枚举所有的点对。虽然看上去很简单，但是写起来还是要颇费一番周折的。旋转卡壳练习题POJ2178求点集中最远点POJ3608求两凸包间的最近点POJ2079求以点集中的点为顶点组成的三角形的最大面积，要求O(N2)算法。半平面半平面指一条直线的一侧的点构成的点集，一般包含直线上的点。在解析几何中直线多以𝐴𝑥+𝐵𝑦+𝐶=0表示(其中A,B,C是常数，A,B不全等于0)。半平面交即以𝐴𝑥+𝐵𝑦+𝐶≥0表示。半平面的表示半平面一般用一个点P和方向矢量v来代表。满足𝒗×𝐴−𝑃≥0的点A在半平面上。v的极角即为半平面的极角。半平面的交半平面是凸集，所以半平面的交也是凸集。有限个半平面的交可能是空集、点、直线、射线、线段、凸多边形、有“开口”的形状甚至一个半平面。朴素的每次O(N)算法为了保证结果是凸多边形或其退化，首先建立一个非～常～大的边框。你懂的。每次顺次枚举多边形的边，与半平面求交，并将交的部分加入新多边形。在得到半平面边界与凸多边形所交形成的边时，立即将其加入新多边形。算法演示值得注意的边界情况1值得注意的边界情况2值得注意的边界情况3合计O(NlogN)的算法这是朱泽园在其国家集训队论文《半平面交的新算法及其实用价值》中提出的算法。由于建立了非～常～大的边框，半平面交的结果一定是一个凸多边形。而凸多边形分为下凸壳和上凸壳。如果分开处理这两部分，就会获得非常好的性质。下凸壳与上凸壳下凸壳中矢量的极角在−𝜋2,𝜋2之间。上凸壳极角取值为其补集。分别排序按照极角，筛选出可能属于下凸壳和上凸壳的半平面分别按极角大小从小到大排序。上凸壳排序时，极角位于第三象限的半平面要加上2π.扫清障碍对于极角相同的半平面，选择最靠左的一个，并将剩下的舍弃。这样即保证所有的半平面的极角皆不相同。处理下凸壳准备一个空栈，并将前两个半平面压入栈。扫描排好序的半平面。对于每个半平面，只要栈中还有两个半平面，即检查其边界直线与栈顶边界直线的交点的横坐标(记为𝑥1)与栈中前两个边界直线的交点的横坐标(记为𝑥0)。若𝑥0≥𝑥1，则弹出栈顶。重复此过程。若上一步没有弹栈，则将当前半平面压入栈。扫描完成之后栈中即为组成下凸壳的半平面。算法演示首先将前两个半平面进栈。算法演示x0x1，将新的半平面压入栈。算法演示x0≥x1，将栈顶弹出。算法演示x0x1，将新的半平面压入栈。依此类推。处理上凸壳处理上凸壳的方式完全类似。只是弹栈的条件变为𝑥0≤𝑥1.上下凸壳的合并只要凸壳中有不止一个半平面，就有可能出现没有用的半平面。如图，下