Computational Geometry

Presentation on theme: "Computational Geometry"— Presentation transcript:

1 Computational Geometry
计算几何教程

2 计算几何的恶心之处 代码长，难写。 需要讨论各种边界情况。后面所介绍的算 法，有些对于边界情况的处理很完美，不 需要再做讨论；有些则不然，需要自行处 理边界情况。

3 精度误差 计算几何问题中，很多时候需要繁杂的浮点运 算和三角函数运算，这样会产生人神共愤的精 度问题。
因此，我们采取以下措施尽量避免精度误差 （其中ε是个小量，多取 10–8）： 𝑎=𝑏⇔ 𝑎−𝑏 <𝜖 𝑎<𝑏⇔𝑎−𝑏<−𝜖 𝑎≤𝑏⇔𝑎−𝑏<𝜖

4 二维矢量 2-Dimension Vector

5 矢量 既有大小又有方向的量。 又称为向量。 大家初中都毕业了我就不多说了。

6 矢量的表示 在 n 维空间下，矢量经常被表达为 n 个数 的元组 𝒂=( 𝑎 1 , 𝑎 2 ,…, 𝑎 𝑛 )。
在二维空间下则以 (𝑥,𝑦) 一对整数表示。 在高等代数中，n 维矢量一般表示为列矢 量的形式 𝑎 1 𝑎 2 … 𝑎 𝑛 𝑇 ，即 n×1 的矩阵。

7 点积 两个 n 维矢量的点积是一个标量，有 𝑎 1 , 𝑎 2 , …, 𝑎 𝑛 ⋅ 𝑏 1 , 𝑏 2 ,…, 𝑏 𝑛 ≝ 𝑎 1 𝑏 1 + 𝑎 2 𝑏 2 +…+ 𝑎 𝑛 𝑏 𝑛 。 由此，矢量的模（即长度）定义为 𝒂 ≝ 𝒂⋅𝒂 = 𝒂 2 。 点积满足交换律。

8 夹角 点积之另一定义为 𝒂⋅𝒃= 𝒂 𝒃 cos𝜃，其 中 θ为 a和 b之夹角。
如下图，a与 b的点积的值实际上就是 a的 模乘 b在 a上的投影的“模”，但是若其投 影与 a方向相反则为负。

9 矢量的垂直 垂直的矢量有 𝜃= 𝜋 2 ，即 cos𝜃=0. 所以 a和 b垂直定义为 𝒂⋅𝒃=0。

10 矢量的缩放 矢量 𝒂 𝒂 是与 a同向的单位矢量，即模长是 1 的矢量。 所以与 a同向，但长度是 l的矢量，为𝑙 𝒂 𝒂 。

11 矢量的投影 b在 a上的投影的“模”是 𝒂⋅𝒃 𝒂 。 所以 b在 a上的投影即为 𝒂⋅𝒃 𝒂 𝒂 𝒂 =𝒂 𝒂⋅𝒃 𝒂 2 。

12 矢量的对称 记 b在 a上的投影为 𝒔=𝒂 𝒂⋅𝒃 𝒂 2 。

13 二维叉积 两个二维矢量的二维叉积是一个标量，定 义为 𝑥 1 , 𝑦 1 × 𝑥 2 , 𝑦 2 ≝ 𝑥 1 𝑦 2 − 𝑥 2 𝑦 1 。
两个二维矢量的二维叉积是一个标量，定 义为 𝑥 1 , 𝑦 1 × 𝑥 2 , 𝑦 2 ≝ 𝑥 1 𝑦 2 − 𝑥 2 𝑦 1 。 二维叉积满足逆交换律：𝒂×𝒃=−𝒃×𝒂。 二维叉积是计算几何中最常用的概念。

14 有向面积 经过计算可以知道，a和 b所成的平行四边 形的面积即为 𝒂×𝒃 的值。 去掉绝对值符号，二维叉积则定义为有向 面积。

15 有向面积的符号 伸出右手，将四指由 a沿小于平角转到 b。 若拇指指向纸面上方，则 𝒂×𝒃为正，否则 为负。
利用有向面积可以非常简单自然地计算简 单多边形的面积。后面我们会详述这一点。

16 点积和二维叉积的方向性 利用点积可以判断矢量的前后。 利用二维叉积可以判断矢量的左右。

17 二维矢量的旋转 将矢量看做列矢量，即 2×1 的矩阵。
则将矢量 a逆时针旋转 θ之后的矢量为 cos𝜃 −sin𝜃 sin𝜃 cos𝜃 𝒂. 记矩阵 T 𝜃 = cos𝜃 −sin𝜃 sin𝜃 cos𝜃 .

18 二维矢量的极角 极角指示矢量的方向，以 x轴正半轴逆时针 转过的角度来指示。 即矢量 𝑥, 𝑦 的极角为 atan2(𝑦,𝑥)。
极角的取值范围是 −𝜋,𝜋 。

19 二维计算几何 2-Dimension Computational Geometry

20 约定 虽然点与矢量有着本质的不同，但是为了 方便起见，本教程中坐标为 (𝑥,𝑦) 的点也 作为矢量 (𝑥,𝑦)使用，反之亦然。
比如，A和 B的中点 𝑀= 𝐴+𝐵 2 .

21 直线 在二维空间中，直线用两个相异点 A和 B 表示。则 ∀𝜆∈ℝ,𝜆𝐴+ 1−𝜆 𝐵 代表直线 上一点。
若 λ < 0，则此点在 B外侧；若 λ > 1，则 此点在 A外侧。 视情况，有时也用一个点 P和一个方向矢 量v来表示。则 ∀𝜆∈ℝ,𝑃+𝜆𝒗代表直线上 一点。

22 点到直线的距离 若要计算点 P到直线 AB的距离，只需要计 算 𝐴𝑃 与它到 𝐴𝐵 的投影之差的模即可。
即 𝐴𝑃 − 𝐴𝐵 𝐴𝐵 ⋅ 𝐴𝑃 𝐴𝐵 2 。 𝐴𝑃 − 𝐴𝐵 𝐴𝐵 ⋅ 𝐴𝑃 𝐴𝐵 2 后面称为 P到 AB的垂直矢 量。注意，这名字是我自己起的。

23 分点 如下图，若 A, C, B共线，且 AC 𝐶𝐵 = 𝜆 1 𝜆 2 ，则 𝐶= 𝜆 2 𝐴+ 𝜆 1 𝐵 𝜆 1 + 𝜆 2 。
特别地，若 C 在 A 外侧，则 𝜆 1 <0；若 C 在 B 外侧，则 𝜆 2 <0。此时上式仍然成立。

24 三角形的面积 利用二维叉积即得 S Δ𝐴𝐵𝐶 = 𝐴𝐵 × 𝐴𝐶 2 。

25 两直线交点 先排除平行或重合的情况。 𝐴𝑂 𝑂𝐵 = S(Δ𝐴𝐷𝐶) S(Δ𝐵𝐶𝐷) = 𝐴𝐷 × 𝐴𝐶 𝐵𝐶 × 𝐵𝐷 .
计算分点即可得到点 O. 注意上式中 A和 B叉积顺序相反。 按照有向面积，此方法在交点不在线段 AB 上，甚至也不在线段 CD上时亦成立。

26 两线段交点 求出直线的交点，然后其判断是否在两条 线段上即可。
若判断两线段是否相交，则要注意平行不 一定不相交，两条线段可能有重合部分或 重合点。

27 三角形的重心 众所周知，三角形的重心 G是三条中线的 交点，即 AM与 BN的交点。 而 𝑀= 𝐵+𝐶 2 ， 𝐴𝐺 𝐺𝑀 =2。
而 𝑀= 𝐵+𝐶 2 ， 𝐴𝐺 𝐺𝑀 =2。 故 𝐺= 2𝑀+𝐴 3 = 𝐴+𝐵+𝐶 3 。

28 多边形 多边形是平面上由有限线段（大于 2）组 成，且首尾连接起来划出的封闭图形。 教程后面的多边形一般指简单多边形，即 边不相交的多边形。
多边形的记录一般以顺次记录其顶点的方 式完成，即顺次记录组成多边形的线段。 方向一般为逆时针。

29 判断点在多边形内外 以要判断的点为起点任作一射线，计算该 射线与多边形的交点数目。 若有偶数个交点则在形外，否则在形内。
若与线段在端点处相交或重合，则要进行 复杂的判断。此时可另取一射线。

30 求多边形的面积 基本的思路是进行三角剖分。

31 求多边形的面积 如果用普通面积的累加来计算的话，三角 剖分就变得十分复杂。 但是使用有向面积的话，这个过程就变得 简单自然通用。

32 算法 按逆时针方向顺次为各边指定方向。 对于每条边 𝐴𝐵 ，累加 𝐴×𝐵 2 的值。 最后得到的结果即为多边形的面积。
对于每条边 𝐴𝐵 ，累加 𝐴×𝐵 2 的值。 最后得到的结果即为多边形的面积。 当然也可以累加 𝐴×𝐵 的值，最后再除以 2。

33 算法演示

34 算法演示

35 算法演示

36 算法演示

37 算法演示

38 算法演示

39 算法演示

40 算法演示

41 算法演示

42 三角剖分 三角剖分即将多边形分为若干三角形部分， 其中既有“正部分”亦有“负部分”。 利用这种方法可以解决很多问题。

43 例题：求多边形的重心 名前通り，给定一个简单多边形，求其重 心之所在。

44 预备知识：求质点组的重心 n个位置分别为 𝐴 1 , 𝐴 2 ,…, 𝐴 𝑛 ，质量为 𝑚 1 , 𝑚 2 ,…, 𝑚 𝑛 的质点构成的质点组的重心 为 𝑘=1 𝑛 𝑚 𝑘 𝐴 𝑘 𝑘=1 𝑛 𝑚 𝑘

45 解答 利用三角剖分，计算各个三角形的面积和 重心，将此三角形化为一个质量为其面积， 坐标为其重心的质点。
若此三角形属于“负部分”，则其拥有 “负质量”。 最后计算质点组的重心即可。

46 凸集 对于一个点集 S，若 ∀𝑎,𝑏∈𝑆,𝜆∈[0,1]， 有 𝜆𝑎+ 1−𝜆 𝑏∈𝑆，则称 S是凸集。
说人话的话，就是对于点集中任意两点， 以两点为端点的线段上的所有点也属于这 个点集。 若多边形及其内点是凸集，则称这个多边 形为凸多边形。 可以证明凸集的交也是凸集。

47 凸集举例 空集 直线、射线、线段 凸多边形 圆及内部、二次曲线及内部
若干种原料，每种原料含 A 成分和 B 成分 的比例不同；混合这些原料能得到的产品 的 A, B 两种成分的比例

48 凸包 对于点集 S，包含 S 中所有点的最小的凸 集称为 S 的凸包。 若 S 是有限集，则其凸包是凸多边形。

49 凸包

50 水平序 Graham 扫描算法 Graham 扫描算法有水平序和极角序两种。
极角序算法能一次确定整个凸包，但是计 算极角需要用到三角函数，速度较慢，精 度较差，特殊情况较多。 水平序算法需要扫描两次，但排序简单， 讨论简单，不易出错。

51 算法流程 对顶点按 x为第一关键字，y为第二关键字进行排 序。 准备一个空栈，并将前两个点压入栈。
对于每一个顶点 A，只要栈顶中还有至少两个顶 点，记栈顶为 T，栈中第二个为 U。若 𝑈𝑇 × 𝑇𝐴 ≤0，则将 T 弹出。重复此过程。 直到上一步不再弹出顶点，将 A压入栈。扫描完 一遍之后得到凸包的下凸壳。 将点集倒过来再进行一次，得到凸包的上凸壳， 组合起来即可。

52 算法演示 首先将所有点排序。

53 算法演示 将 1 和 2 压入栈。

54 算法演示 2 被弹出栈，3 进栈。

55 算法演示 没有点被弹出栈，4 进栈。

56 算法演示 4 被弹出栈，5 进栈。

57 算法演示 5 被弹出栈，6 进栈。

58 算法演示 6 被弹出栈，7 进栈。

59 算法演示 如此直到下凸壳被找到。

60 算法演示 倒序进行扫描找到上凸壳。

61 Graham 扫描的时间复杂度 这太傻缺了。算法的瓶颈在排序，所以时 间复杂度是 O(N log N)。

62 旋转卡壳算法 如何计算 N 个点中，距离最大的两个点的 距离？ 要求 O(N log N) 的算法。
容易证明距离最大的两个点一定是凸包上 的两个点，很明显是先求凸包然后做文章 啦。

63 对踵点 若凸包上的两个顶点能落在一对平行切线 上，则称它们为对踵点。 容易证明，答案一定是一对对踵点之间的 距离。

64 对踵点的枚举 从一对对踵点逆时针枚举下一对对踵点的 话，只需要观察下图中 α 角和 β 角的大小， 选择其中较小的一个转过去就行了。

65 算法 最左侧点和最右侧点一定是对踵点。从此 点对开始枚举即可。
注意不只有“点 – 点”的情况，还有“点 – 边”和“边 – 边”的情况。这些情况下 要枚举所有的点对。 虽然看上去很简单，但是写起来还是要颇 费一番周折的。

66 旋转卡壳练习题 POJ 2178 求点集中最远点 POJ 3608 求两凸包间的最近点
POJ 求以点集中的点为顶点组成的 三角形的最大面积，要求 O(N2) 算法。

67 半平面 半平面指一条直线的一侧的点构成的点集， 一般包含直线上的点。
在解析几何中直线多以 𝐴𝑥+𝐵𝑦+𝐶=0 表示 (其中 A, B, C是常数，A, B不全等于 0)。半平面交即以 𝐴𝑥+𝐵𝑦+𝐶≥0 表示。

68 半平面的表示 半平面一般用一个点 P和方向矢量 v来代表。 满足 𝒗× 𝐴−𝑃 ≥0 的点 A在半平面上。 v的极角即为半平面的极角。

69 半平面的交 半平面是凸集，所以半平面的交也是凸集。
有限个半平面的交可能是空集、点、直线、 射线、线段、凸多边形、有“开口”的形 状甚至一个半平面。

70 朴素的每次 O(N) 算法 为了保证结果是凸多边形或其退化，首先 建立一个非～常～大的边框。你懂的。
每次顺次枚举多边形的边，与半平面求交， 并将交的部分加入新多边形。 在得到半平面边界与凸多边形所交形成的 边时，立即将其加入新多边形。

71 算法演示

72 值得注意的边界情况 1

73 值得注意的边界情况 2

74 值得注意的边界情况 3

75 合计 O(NlogN) 的算法 这是朱泽园在其国家集训队论文《半平面 交的新算法及其实用价值》中提出的算法。
由于建立了非～常～大的边框，半平面交 的结果一定是一个凸多边形。 而凸多边形分为下凸壳和上凸壳。如果分 开处理这两部分，就会获得非常好的性质。

76 下凸壳与上凸壳 下凸壳中矢量的极角在 − 𝜋 2 , 𝜋 2 之间。 上凸壳极角取值为其补集。

77 分别排序 按照极角，筛选出可能属于下凸壳和上凸 壳的半平面分别按极角大小从小到大排序。
上凸壳排序时，极角位于第三象限的半平 面要加上 2π.

78 扫清障碍 对于极角相同的半平面，选择最靠左的一 个，并将剩下的舍弃。 这样即保证所有的半平面的极角皆不相同。

79 处理下凸壳 准备一个空栈，并将前两个半平面压入栈。
扫描排好序的半平面。对于每个半平面，只要 栈中还有两个半平面，即检查其边界直线与栈 顶边界直线的交点的横坐标 (记为 𝑥 1 ) 与栈中 前两个边界直线的交点的横坐标 (记为 𝑥 0 )。 若 𝑥 0 ≥ 𝑥 1 ，则弹出栈顶。重复此过程。 若上一步没有弹栈，则将当前半平面压入栈。 扫描完成之后栈中即为组成下凸壳的半平面。

80 算法演示 首先将前两个半平面进栈。

81 算法演示 x0 < x1，将新的半平面压入栈。

82 算法演示 x0 ≥ x1，将栈顶弹出。

83 x0 < x1，将新的半平面压入栈。依此类推。
算法演示 x0 < x1，将新的半平面压入栈。依此类推。

84 处理上凸壳 处理上凸壳的方式完全类似。 只是弹栈的条件变为 𝑥 0 ≤ 𝑥 1 .

85 上下凸壳的合并 只要凸壳中有不止一个半平面，就有可能 出现没有用的半平面。 如图，下图中的 p1 半平面没有用。

86 滤除没有用的半平面 先滤除左侧的半平面。指针 p1 指向下凸壳的最左 侧，p2 指向上凸壳的最左侧。
若下凸壳中还有至少两个半平面，检查 p2 与 p1 的边界的交，以及下凸壳中 p1 右侧的半平面与 p1 的边界的交。若这两个交的并集为空或只有一 个端点，则舍弃半平面 p1，将指针 p1 右移。 处理完 p1 后类似处理 p2。若 p2 右移了，就重复 处理 p1，依此类推，直到二者都不右移了为止。 类似滤除右侧没有用的半平面。

87 实际上…… “这两个交的并集为空或只有一个端点” 仍然只是讨论交点的坐标大小。
但是，这两个交点的 x 坐标可能相同，但 y 坐标不相同。所以不能像前面一样只讨论 x 坐标。

88 算法演示 p1 上二者的交为空集。右移 p1。

89 p2 上二者的交为空集。右移 p2，重新检查 p1。
算法演示 p2 上二者的交为空集。右移 p2，重新检查 p1。

90 算法演示 p1 和 p2 均满足要求，结束对左侧的检查。

91 总结 算法的瓶颈仍然在于排序，所以时间复杂 度为 O(N log N)。若使用桶排序，甚至能得 到 O(N) 的半平面交算法，但是并不会有明 显的性能提升。 总体来说讨论比较辛苦，写起来不算很难。 精度存在比较大的问题，而且半平面交的 题目一般都容许 O(N2) 算法，所以并不是 很常用。

92 半平面交练习题 POJ 1279 求多边形的核。核中的点满足其到多边形边 界上任一点之间的线段只与多边形在那一点相交。
POJ 裸的半平面交。朱泽园专门为他的算法出的 题，要求 O(N log N) 算法。 POJ 求在凸多边形内部放两个半径为 r 的圆所能 覆盖的最大面积。两圆可以重叠，但不能与多边形相交。 需要用到旋转卡壳。

93 圆 到定点 O 距离等于定值 r 的点的集合。 有时根据上下文也包含内部的点。 O 即为圆心，r 即为半径。
圆只需要用这两个东西表示就行了。

94 圆与直线的交点 先求圆心到直线的距离 h。若 ℎ>𝑟 则圆与 直线木有交点。
否则……

95 圆与直线的交点 否则记 𝐻=(𝑥,𝑦)，且 H逆时针旋转 𝜋 2 为 𝑯 𝟎 = −𝑦,𝑥 。
记 𝑑= 𝑟 2 − ℎ 2 为垂足到交点的距离，则 两个交点分别为 𝑂+𝑯+ 𝑑 𝑯 𝟎 ℎ ，𝑂+𝑯− 𝑑 𝑯 𝟎 ℎ 。 ↑ 注意 𝑯 𝟎 =ℎ。

96 圆与圆的交点 先求二圆的圆心距 d，并记二圆的半径为 r1 和 r2。若 𝑑> 𝑟 1 + 𝑟 2 ，则二圆外离；若 𝑑< 𝑟 1 − 𝑟 2 ，则二圆内含。这些情况下都 不会有交点。 上面不等式若取等号，则二圆分别为外切 和内切。处理方式见下页。 否则……

97 圆与圆的交点 如图所示，据余弦定理有 cos 𝜃 = 𝑟 1 2 + 𝑑 2 − 𝑟 2 2 2 𝑟 1 𝑑 .
否则……

98 圆与圆的交点 设 D逆时针旋转 𝜋 2 为 D0. 而 sin 𝜃 = 1− cos 2 𝜃 ，故两个交点分别为 𝑂 1 + 𝑫 𝑟 1 cos 𝜃 𝑑 + 𝑫 𝟎 𝑟 1 sin 𝜃 𝑑 ， 𝑂 1 + 𝑫 𝑟 1 cos 𝜃 𝑑 − 𝑫 𝟎 𝑟 1 sin 𝜃 𝑑 .

99 圆的面积并 题目：SPOJ CIRU 给出 N (N ≤ 1000) 个圆，求其并集的面积。 要求 O(N2 log N) 的算法。
后面给出的算法由 AekdyCoin 原创。

100 分析 如图，最后形成的图 形是由很多弓形和多 边形组成的。
弓形可以单独计算， 多边形利用叉积亦可 以分各边计算，所以 我们可以单独考虑每 个圆。

101 每个圆的情形 如图，对于每个圆，用其他的圆与之求交， 找到所有没有被覆盖过的圆弧。圆弧须以 逆时针序表示。
对于每条圆弧 𝐴𝐵 ，累加其弓形的面积，以 及这条边的有向面积 𝐴×𝐵 2 . 半径为 r，角度为 θ的 　弓形面积为 𝑟 2 (𝜃− sin 𝜃 ) 2 .

102 不连通？ 由于各个连通块中的弓形和多边形的边实 际上都得到了很好的处理，所以图形不连 通没有问题。

103 有“洞”？ 发生了非常 NB 的事 情。由于我们累加的 是有向面积，而“洞” 中多边形是反向 (顺 时针) 旋转的，所以 “洞”会被自动抵消！

104 时间复杂度 对于每个圆，要求 O(N) 次交，从而出现了 O(N) 个交点。要找出未被覆盖的弧的话， 要对交点进行排序，所以每个圆要花费 O(N log N) 的时间进行处理。 总时间复杂度 O(N2 log N)。

105 算法扩展 SPOJ CIRUT 求恰好被覆盖 1 次、2 次、…、N 次的面积。
算法的本质在于对“裸露”部分进行处理。 这种方法也可以用于求很多圆与很多凸多 边形的面积并——但是情况复杂得多，要 讨论的情况也多得多。

106 三维矢量 3-Dimension Vector

107 第三维度 三维矢量用(𝑥,𝑦,𝑧) 表示。 点积和标量乘法天然是在多维上定义的概 念，所以在三维空间中可以立即使用。
矢量的模，夹角，垂直，缩放，投影，对 称等扩展概念和计算方法也立刻投入了我 们的怀抱。

108 三维叉积 但是二维叉积却不适用了。在此我们要定义三 维叉积。 三维叉积的结果是三维矢量。
我们有 𝑥 1 , 𝑦 1 , 𝑧 1 × 𝑥 2 , 𝑦 2 , 𝑧 2 =( 𝑦 1 𝑧 2 − 𝑦 2 𝑧 1 ,− 𝑥 1 𝑧 2 + 𝑥 2 𝑧 1 , 𝑥 1 𝑦 2 − 𝑥 2 𝑦 1 ). 本质是行列式，原式 = 𝒊 𝒋 𝒌 𝑥 1 𝑦 1 𝑧 1 𝑥 2 𝑦 2 𝑧 2 ，其中 𝒊= 1,0,0 ,𝒋= 0,1,0 ,𝒌=(0,0,1).

109 左手系与右手系 x, y, z 轴的方向，传统上应该满足右手系。
类似也可以定义左手系。三个不共面的矢 量必然满足左手系与右手系中的一种。

110 文字游戏 注意“a, b, c 成右手系”和“b, a, c 成右手 系”是截然相反的两个命题。
但是“a, b, c 成右手系”和“b, c, a 成右手 系”是同一个命题。 画图看一下这是为什么。

111 三维叉积的性质 若 𝒂×𝒃=𝒄，则 𝒂⋅𝒄=𝒃⋅𝒄=0，即叉积 的结果与原矢量垂直。
a, b和 𝒂×𝒃 应满足右手系。即伸出右手， 将四指由 a沿小于平角转到 b，拇指所指的 方向即为 𝒂×𝒃的方向。 𝒂×𝒃 的值在数值上等于 a和 b所夹的平 行四边形的面积。

112 在三维空间我们失去的 极角。在三维空间中描述矢量的方向不能 只用一个角度，实际上需要使用两个角度。
左右。在三维空间中，两个矢量间没有左 与右的概念。取而代之的是三个矢量间左 手系与右手系的概念。

113 混合积 𝒂×𝒃 ⋅𝒄 称为矢量 a, b, c的混合积。 又记为 (𝒂,𝒃,𝒄)。 当矢量 a, b, c成右手系时，混合积的值为正。
但是这到底是个什么玩意儿？

114 有向体积 如图。a, b, c 的混合积的模，即为 a, b, c 所成的平行六面体的体积。 考虑符号的话，混合积又称为有向体积。
　平行六面体的 1 / 6.

115 一切的本质：行列式 若 𝒂= 𝑥 1 , 𝑦 1 , 𝑧 1 ,𝒃= 𝑥 2 , 𝑦 2 , 𝑧 2 ,𝒄= ( 𝑥 3 , 𝑦 3 , 𝑧 3 )，那么 𝒂×𝒃 ⋅𝒄= 𝑥 1 𝑦 1 𝑧 1 𝑥 2 𝑦 2 𝑧 2 𝑥 3 𝑦 3 𝑧 3 由此我们可以得到左右手系的新定义：若上面 行列式为正，则 a, b, c成右手系，否则成左手 系。 这个结论和定义可以扩展到高维！

116 三维计算几何 3-Dimension Computational Geometry

117 三维直线 三维直线的表示法与二维类似。 计算点到直线的距离的方法与二维相同。 计算分点的方式也与二维相同。

118 异面直线 但是在三维空间中，直线除平行与相交之 外有着第三种位置关系：异面。
异面直线的距离即为两条直线上距离最小 的两点之距离。你们都知道这就是两条直 线的公垂线段的长度。

119 异面直线的距离 设两条直线的方向矢量分别为 a和b。若 𝒂×𝒃=𝟎，则两直线平行，它们一定共面， 其距离为 0. 否则……

120 异面直线的距离 否则两条直线上各任 取一点 A和 B。 矢量 𝐵−𝐴 在 𝒂×𝒃 上的投影的模即为所 求。

121 两直线的交点 先求它们的距离。若不为 0，显然木有交 点。 否则，若它们的方向矢量平行，它们重合。
否则，它们是相交的。推荐利用后面所讲 的投影技术将其转化为二维问题。

122 平面 平面是到两点距离相等的点的轨迹。 具体是个啥乃们应该清楚……

123 点法式 与平面垂直，即与平面上一切矢量垂直的 非零矢量叫做平面的法矢量。可以证明平 面的所有法矢量平行。
记录平面的一个法矢量 v，再记录平面上一 点 P，就可以完整表示整个平面了。

124 点到平面的距离 点 A到平面的距离，即为 𝐴−𝑃 在 v上的投 影长度。 𝑃−𝐴 在 v上的投影我们也称做垂直矢量。 注意，我自己起的名字。

125 直线与平面的交点 设直线经过点 A，方向矢量为 v. 记 A到平 面的垂直矢量为 h。
若 𝒗⋅𝒉=0，则直线与平面平行。直线可 能落在平面上，也可能与平面没有重合部 分。 否则……

126 直线与平面的交点 目的是通过缩放 v 得 到 v0，使得 v0到 h的 投影等于 h。即 𝒗 0 ⋅ 𝒉= 𝒉 2 .
故 𝒗 0 =𝒗 𝒉 2 𝒗⋅𝒉 ，𝐴+ 𝒗 0 即为所求交点。

127 平面与平面的交线 设两个平面的法矢量为 h1, h2. 若它们平行， 则两平面平行。它们可能重合，或者没有 公共点。
可以随机生成一条在第一个平面上的，且 不与第二个平面平行的直线与第二个平面 求交来确定此点。

128 二面角 就是两个平面的法矢量的夹角啦。

129 平面上点的二维投影 有时一些几何对象出现在同一个平面上。 我们希望给予平面上每一个点一个二维坐 标，从而把问题转化为一个二维问题加以 解决。
我们需要在平面上指定一个点 O作为原点， 以及一个矢量 x作为横轴。即 𝒗⋅𝒙=0.

130 平面上点的二维投影 此时，取 𝒚=𝒗×𝒙 作为纵轴，即可保证 x, y, v成右手系。
对于平面上的每一个点 A，在这套坐标系 下其横坐标即为 𝐴−𝑂 在 x上的投影长度 𝐴−𝑂 ⋅𝑥 𝑥 ，纵坐标亦然。

131 平面上点的二维投影 为了避免每次计算 𝒙 , 𝒚 ，我们可以将 x, y的模缩放为 1。
这样 A的坐标即为 ( 𝐴−𝑂 ⋅𝒙, 𝐴−𝑂 ⋅𝒚). 若已知平面上一点以此坐标系投影的坐标 (𝑎,𝑏)，则其三维坐标即为 𝑂+𝑎𝒙+𝑏𝒚.

132 多面体 多面体是指三维空间中由平面和直边组成 的几何形体。 ……以上是科学定义。我不觉得这么一句废 话有什么用。
我们假定多面体的每个面都是三角形的。

133 凸多面体 若一个多面体是凸集，则它是凸多面体。 如同凸多边形是半平面的交一样，凸多面 体也可以看做半空间的交。
求半空间的交非常复杂，在此不多做介绍。 不过有关于半空间的基本知识仍要加以讲 解。

134 半空间的表示 如同半平面可以用两 个互异的有序点来表 示一样，半空间可以 用三个不共线的有序 点来表示。

135 半空间的表示 如图，在点 A的一侧， 矢量 𝐴𝑋 , 𝐴𝑌 , 𝐴𝑍 成左 手系，我们称这一侧 为半空间的外侧。
类似地，在 B的一侧 三个矢量成右手系， 这一侧即为半空间的 内侧。

136 简单判别法 若要判断点 P 在内侧 还是外侧，则从点 P 向平面看去。

137 凸多面体的表示 表示一个凸多面体需要记录其所有的面。 对于所有的面，要正确记录这个面上点的 顺序。
根据假设，每个面都是三角形的，即包含 三个点，所以每个面都表示了一个半空间。 凸多面体应为这些半空间内侧的交。

138 可视 若 P 在半空间 A 的外侧，则称半空间 A，或 A 所代表的平面对 P 是可视的。
我们在观察一个凸多面体的时候，看到的面即 为视点的可视面。 凸多面体各个面的点的顺序应该保证，从多面 体内部的任意一点看去，所有的面都不可视。 若将左右手系用行列式的符号替代，则可视的 概念能推广到高维。

139 若多面体有非三角面 这样的面记录的时候要保证，其上所有点 从多面体的内部看去成顺时针排列。 此时这个面仍然能有效地表示一个半空间。

140 三维凸包 从凸包的定义出发推断，一坨三维空间中 的点的凸包是一个凸多面体。
事已至此我们只好想办法求它了。但是不 难发现由于失去了左右这一概念，Graham 扫描法彻底报废了。 那怎么办？ 为了方便起见，我们假定没有四点共面的 情况。

141 暴力方法 O(N3) 枚举所有的点的三元组，将其看做半 空间。若所有其它的点都在这个半空间的 内侧，则这个面是凸包的一个面。

142 增量法 增量法作为求凸包的有力算法，可以解决 任意维度的凸包问题。 最坏情况下其时间复杂度为 O(N2)。

143 算法流程 取出点集中的四个点，这四个点组成的四 个面都是初始凸包的面。调整各个面上点 的顺序使得从内部看去各个面均不可视。
之后添加其它各点。如果从这个点看去， 所有的面均不可视，则此点在凸包内部。 什么都不做，跳过该点。 否则……

144 算法流程 设当前点是 P。 找到可视面和不可视 面的分界线。删除掉 所有的可视面，对于 不可视境界线上的每 条边 𝐴→𝐵，建立过 此边和当前点的面 𝐴→𝐵→𝑃.

145 算法演示 建立初始凸包，并试图添加第一个点。

146 算法演示 添加第一个点完毕。

147 算法演示 试图添加第二个点。

148 算法演示 添加第二个点完毕。如此添加所有点即可。

149 随机增量 可以证明，在平均情况下算法的期望时间 复杂度是 𝑂(𝑁 𝑁 ). 所以可以先随即打乱初始点集中点的顺序 来得到期望复杂度。
可以证明，在平均情况下算法的期望时间 复杂度是 𝑂(𝑁 𝑁 ). 所以可以先随即打乱初始点集中点的顺序 来得到期望复杂度。 这即为随机增量算法。

150 三维凸包练习题 POJ 裸的三维凸包，且不含四点共 面。 三维凸包的出题概率很低，就不提供更多 的练习题了。

151 球 在三维空间中，到定点距离等于定值的点 的轨迹即为球。 球可以用球心 O 和半径 r 来表示。
二维球面上的几何学称为球面几何，是非 欧几何的一种。自然我们不会研究如此高 深的问题。

152 球与直线的交点 首先求球心到直线的距离 h和垂足。 若 ℎ>𝑟，则直线与球相离。
否则在直线上垂足到交点的距离为 𝑟 2 − ℎ 2 ，缩放直线的方向矢量计算这两 个点即可。

153 球与平面或球的交圆 既然已经到了如此程度，想必大家已经可 以自己来求了吧。
先求交圆的圆心，再求交圆的半径。由于 这个圆是在三维空间中的，需要标明其在 哪个平面上。

154 经纬度 大家参考地理课所学。 在球面上，一点的纬度范围为 0,𝜋 ，经度 范围为 −𝜋,𝜋 . 北极的纬度是 0，赤道的纬度是 π / 2.
在球面上，一点的纬度范围为 0,𝜋 ，经度 范围为 −𝜋,𝜋 . 北极的纬度是 0，赤道的纬度是 π / 2. 本初子午线的经度是 0.

155 经纬度到三维坐标的转换 若球心在原点，则 z轴指向北极，x轴指向 本初子午线的话，则球上经度为 𝜙，纬度 为 𝜃 的一点的三维坐标为
𝑂+𝑟 sin 𝜃 cos 𝜙 , sin 𝜃 sin 𝜙 , cos 𝜃 若非如此，需要进行三维旋转。

156 三维旋转 确认旋转之后坐标轴的位置，利用旋转矩 阵求解即可。