计算几何讲义

· · 个人记录

计算几何入门

计算几何 Computational Geometry

总体来说参考了 mak 学长的 pdf 和 lrj 神犇的蓝书。

Aizu Online Judge 这个板子库挺不错。

可以结合代码模板看看，这里讲的内容和模板代码大致对应。

如果有锅的话轻喷。

前置

浮点数计算

计算机中的浮点数表示无法做到完全精确，所以需要使用 long double 或者设置 EPS 表示误差量来避免浮点误差的问题。必要时需要使用手写分数类。

（EPS les leq equ）

三角函数

如图。\angle ABC=90\degree,c=4,a=3。

则有 b=5。以角 \alpha 为例，锐角三角函数定义如下：

由于 C++ 里的内置函数使用弧度制，所以还要讲讲弧度制与角度制的转化：

$1\degree=\dfrac \pi{180}\operatorname{rad}\approx 0.01745\operatorname{rad}$； $1\operatorname{rad}=\left(\dfrac{180}\pi\right)\degree\approx57.30\degree=57\degree18'$。 （`PI dtor rtod`） 正弦定理：对于任意 $\triangle ABC,a,b,c$ 分别为 $\angle A,\angle B,\angle C$ 的对边，$R$ 为 $\triangle ABC$ 的外接圆半径，则有： $\dfrac a {\sin \angle A}=\dfrac b {\sin\angle B}=\dfrac c {\sin\angle C}=2R$。 余弦定理：定义同上。 $c^2=a^2+b^2-2ab\cos\angle C$。 注意其包括了勾股定理。 其他公式如和差公式自行百度。 ## 二维计算几何 ### 点和向量 #### 定义 在**平面直角坐标系 the Plane Rectangular Coordinate System/Cartesian Coordinate System**中，一个横坐标为 $x$，纵坐标为 $y$ 的二维**点 point** 通常被表示为有序对 $(x, y)$。用字母表示时，通常使用大写字母表示，如点 $P(x,y)$。 **向量（矢量）vector** 可以被视为有向线段，一个向量通常用带箭头小写字母表示，如向量 $\vec a$；起点为 $A$ 终点为 $B$ 的向量也可以表示成 $\vec{AB}$。或者也可以用小写粗体字母，如向量 $\mathbf a$。 二维向量也可以用有序对 $(x,y)$ 表示：起点为原点 $(0,0)$，终点为 $(x,y)$ 的向量。所以在现在的程序实现中可以将他们统一实现，但是要注意他们在概念上的本质区别。 （后面可能会学到用仿射变换来区分点和向量，但是我自己也没研究过，大概是用矩阵来维护变换） （`struct point(vect)`） #### 基本运算 - 点 + 向量 = 点，向量 + 向量 = 向量。 - 点 - 点 = 向量，向量 - 向量 = 向量。 - 向量 * 实数 = 向量。 - 向量 / 实数 = 向量。 （`point::operator + - * /`） 向量的**模 norm**：$\vec a=(x,y),|\vec a|=\sqrt{x^2+y^2}$。（几何意义为向量的长度） 令 $\vec a=(x_1,y_1),\vec b=(x_2,y_2),\theta$ 为这两个向量的夹角，则有 - **点积（数量积）dot（`dot`）**：$\vec a\cdot \vec b=x_1x_2+y_1y_2=|\vec a||\vec b|\cos\theta$。（`ang`） - **叉积（向量积）cross（`cross`）**：$\vec a\times \vec b=x_1y_2-x_2y_1,|\vec a\times\vec b|=|\vec a||\vec b|\sin\theta$。 叉积也等于两个向量围成的有向平行四边形面积。（`triarea`） 叉积的正负性：对于 $k=\vec a\times \vec b$，相对于 $\vec a$，若 $\vec b$ 在左侧，则 $k>0$。若 $\vec b$ 在右侧，则 $k<0$。若共线，则 $k=0$。（这个可以用来判断所在侧） 判断向量**平行 parallel**，**垂直 perpendicular/orthogonal** 的方法： $\vec a\cdot \vec b=0\Leftrightarrow a\perp b \vec a\times \vec b=0\Leftrightarrow a\Vert b

（islinepara islineorth）

向量旋转 rotate：对于向量 (x,y)，其逆时针旋转 \alpha 度以后所得向量 (x',y') 为 x'=x\cos\alpha-y\sin\alpha,y'=x\sin\alpha+y\cos\alpha。（rotate normal）

点和线

定义

直线 line 也是几何学中的基本概念。在二维平面内，直线是一个点在平 面内沿着一定方向和其相反方向运动的轨迹，是不弯曲的线。

线段 segment 是指直线上两点间的有限部分（包括两个端点）。

射线 ray 是指由线段的一端无限延长所形成的直的线。

在实现的时候我们不使用解析几何的方式存储他们，而是选择一个点 P_0 和一个向量 \vec v 来表示之：P=P_0+k\vec v。所有满足条件的点 P 构成的几何即为一条线，其中：

（struct line(segment)）

基本运算

  1. 直线/线段交点 intersection：（lineintersect）

    联立 l_1:P=P_0+k_1\vec v,l_2:P=P_1+k_2\vec w，则有 P_0+k_1\vec v=P_1+k_2\vec w，P_0-P_1=k_2\vec w-k_1\vec v，令 u=P_0-P_1，则可解得 k_1=\dfrac{\vec w\times \vec u}{\vec v\times \vec w}。回代即可解出交点。

  2. 点到直线的距离 distance：（distoline）

    在直线上抠出两个点，和给定点搞出一个三角形，然后用叉积算出面积，求出高即可。

    注意由于面积是有向的，这个距离也可以是有向的，相对于直线的方向向量 \vec v。但是模板里的实现是无向的非负值。

  3. 点在直线上的投影 projection：（lineproj）

    作出直线的单位法线 normal，然后将给定点加上单位法线乘以点到直线距离即可。

  4. 点到线段的距离：（distoseg）

    首先判掉退化成点的情况。然后判断点在直线上的投影是否在线段上，若是则为 (2)，否则为到最近的端点距离。

  5. 判断线段是否相交：（issegintersect onseg）

    线段相交的充要条件是每条线段的两个端点都在另一条线段的两侧，然后这个可以直接用叉积相乘以后的符号来判断。

    需要注意的是线段的不规范相交，即交点在端点上。这个时候需要再写一个 onseg 判断点是否在线段上，相信大家都会。

多边形

定义

由三条或三条以上的线段首尾顺次连接所组成的平面图形叫做多边形 polygon。实现时用 vector<point> 搞就好了。一般是按顺序存储点，这个顺序一般是逆时针顺序。

（polygon）

运算

  1. 求多边形面积：（polygonarea）

    随便取一个点将 n 个点的多边形分成若干个三角形，取其有向面积之和即为多边形面积。

  2. 判断点是否在多边形上：（ispointinpoly）

    介绍两种做法：

    • 射线法：从一条边开始引出一条射线，看和多边形的相交次数，记作穿越数 Crossing Number。如果为奇数，就在内部，否则在外部。这个可以考虑射线一进一出。不方便处理点在多边形上，多边形有圆弧，或者射线卡在（自交）多边形角上的情况。

    • 转角法（实现采用）：用一个点绕着多边形转一圈，看这个点在这个过程中相对于给定点转过的度数。0\degree 表示点在多边形外，180\degree 表示点在多边形上，360\degree 表示点在多边形内。这种方法没有上述转角法的问题。

      实现时因为浮点误差原因不直接计算角度，而是计算其顺时针和逆时针穿过一条从给定点引出的射线几次，将逆时针看做 +1，顺时针看做 -1，统计出绕数 Winding Number。若其为 0，则表明转角和为 0\degree，反之则表示非 0\degree。判断转角方向还是用叉积。

  3. 凸包 Convex Hull：（convexhull）

    嗯，下面有请 The God of Convex Hull - Kai Yu 上台讲课（

    凸多边形有个性质：从最下面的点开始逆时针遍历每一条边，所得直线的斜率单调上升。下面介绍 Andrew 算法（实现采用）：

    1. 首先将点按照 x 坐标为第一关键字，y 坐标为第二关键字排序。

    2. 将左边前两个点先扔进凸包。然后从左到右扫描并维护一个斜率不增的单调栈，扫描完成后栈内所得点即为凸包的上凸壳。

    3. 从右到左在如上扫描一次求出下凸壳，合并即为所求。

    排序为时间复杂度瓶颈，总复杂度 O(n\log n)。

    应俞开要求，也讲一下 Graham 扫描法：

    1. 找出 y 坐标最小的点，若有多个，找出 x 坐标最小的点。

    2. 将其作为原点进行极角排序。

    3. 将这个点和排序所得的第一个点放入栈，然后用单调栈维护斜率单调点，扫描一遍，最后在单调栈里的点即为所求。

  4. 线性时间求凸包直径：（convpolydia）

    凸包直径指在凸包上取两个点所得直线距离的最大值，可以使用旋转卡壳 Rotating Calipers 算法来解决。（说白了就是在凸包上跑双指针。）

    容易发现如果在凸包上固定一个点，另一个点绕凸包走的距离和两个点的直线距离形成的函数是单峰的，然后这个就可以三分。然后用双指针维护峰顶位置即可。

半平面/平面区域

定义

用一条直线把平面分割成两部分，其中一部分就叫做半平面 Half-Plane。它可以用上述有向直线表示，其左侧即为它所代表的半平面。

平面上的很多线段会构成一个平面直线图 Planar Straight-Line Graph, PSLG，它代表了了一个平面区域划分，其中每个区域都是一个多边形。

（pslg）

运算

  1. 半平面交 Half-Plane Intersection（hfplintersect）

    字面意思，多个半平面的交集。

    首先要知道，凸集的交是凸的，所以半平面交所得的图形也是凸的，不过它有可能是无界多边形或者空集。这个时候可能需要在外面框出一个表示无穷大的半平面。（polyplane pslgplane）同理的，任何一个凸多边形也可以表示为若干半平面的交。（polytopslg）

    半平面交可以使用单调队列来维护。具体的，首先按照极角排序，然后依次加入半平面，用单调队列维护之。如果两条直线平行且同向，取内侧的一条。最后删除无用平面，判断空集即可。

圆

定义

在平面内，到定点 O 的距离等于定长 r 的点的集合叫做圆 circle。只要知道圆心 O 和半径 r （或圆上一点）就能确定一个圆。三点也可以确定一个圆。

（struct circle）

运算

  1. 给定极角求圆上一点：（circle::gprad）

    直接来吧。

  2. 求直线与圆的交点：（linecircintersect）

    首先根据圆心和直线的距离判断相交，相切和相离。然后根据圆心在直线上的投影移一下就好了。

  3. 求圆与圆的交点：（circintersect）

    首先判断重合无数个，内含，相离零个，内外切一个。然后连结两圆圆心，余弦定理求出两交点的圆心角即可。

  4. 过一点求圆的切线：（getcirctang(point,circle)）

    判掉点在圆内，在圆上，然后用 sin 求出两切线夹角，旋转即可。

  5. 求两圆的公切线：（getcirctang(circle,circle)）

    判掉重合 (0)，内含 (0)。再判掉内切 (1)。此时一定有两条外公切线。如果外离 (4)，那两圆中间应夹着两条切线。如果外切 (3)，那这两条这会重合。否则为相交 (2)，不存在内切线。

  6. 三角形的内心，外心，质心，垂心：（incenter circumcenter centroid orthocenter）

    内心为三角形三条角平分线交点。外心为三边中垂线交点。重心为三条中线交点，垂心为三条垂线交点。按定义模拟即可。

三维计算几何

内容相对很少，需要的话请自行学习。

点，向量和线

定义

在空间直角坐标系the Space Rectangular Coordinate System/Cartesian Coordinate System中，一个横坐标为 x，纵坐标为 y，竖坐标为 z 的三维点通常被表示为有序对 (x,y,z)。用字母表示时，通常使用大写字母表示，如点 P(x,y,z)。

三维向量也可以用有序对 (x,y,z) 表示：起点为原点 (0,0,0)，终点为 (x,y,z) 的向量。

（struct point3(vect3)）

基本运算

其他的和二维情况基本相同。只是要注意三维叉积的特殊形式：

\vec a=(x_1,y_1,z_1),\vec b=(x_2,y_2,z_2) \vec c=\vec a\times \vec b=(y_1z_2-y_2z_1,z_1x_2-z_2x_1,x_1y_2-x_2y_1)

性质：|\vec c|=|\vec a||\vec b|\sin\theta，并垂直于 \vec a,\vec b 所在平面，方向满足右手定则：手四指弯向 \vec a\to\vec b 方向时大拇指的指向。

所以其他函数都和二维的写的一样，只是 cross(a,b) 要写成 cross(a,b).len()

平面

定义

在空间中，到两点距离相同的点构成的轨迹为平面 Plane。不共线的三点也可确定一个平面。其可以用平面上任意一点和平面的法向量 normal vector 来表示。

注意到叉积的定义，所以三点确定平面时法向量取叉积即可。

（struct plane）

运算

  1. 点到平面距离：（distoplane）

    由点积定义可得：向量长度与另一条向量在其上投影的长度之积。除以法向量长度即可。

  2. 点在平面上的投影：（planeproj）

    和点在直线上的垂足类似。有了法向量和距离不难得出。

  3. 直线与平面交点：（lineplaneintersect）

    先用点积判掉平行的情况（因为是法向量 \vec n）（islineplanepara），然后类似二维直线与直线交点，联立直线方程 l:P=P_1+k\vec v 和平面方程 a:\vec n\cdot(P-P_0)=0 得 k=\dfrac{\vec n\cdot (P_0-P_1)}{n\cdot \vec v}。

  4. 求四面体体积：（tetravolumn）

    设四个顶点为 P_0,P_1,P_2,P_3，则 V=\frac 1 3Sh=\frac 1 6((\vec{P_0P_1}\times \vec{P_0P_2})\cdot \vec{P_0P_3})。

GL&HF