第1章 绪论 1
1.1 如何使用本书 1
1.2 关于数值计算的若干问题 1
1.2.1 低层问题 2
1.2.2 高层问题 3
1.3 各章内容概要 4
第2章 矩阵和线性系统 6
2.1 导言 6
2.1.1 动机 6
2.1.2 组织 9
2.1.3 符号约定 10
2.2 多元组 10
2.2.1 定义 10
2.2.2 算术运算 11
2.3 矩阵 11
2.3.1 符号与术语 12
2.3.2 转置 12
2.3.3 算术运算 13
2.3.4 矩阵乘法 14
2.4.1 线性方程 17
2.4 线性系统 17
2.4.2 两个未知数的线性系统 19
2.4.3 一般线性系统 20
2.4.4 减行、阶梯形和秩 21
2.5 方阵 22
2.5.1 对角矩阵 23
2.5.2 三角形矩阵 23
2.5.3 行列式 24
2.5.4 逆矩阵 26
2.6 线性空间 28
2.6.2 定义和性质 29
2.6.1 数域 29
2.6.3 子空间 30
2.6.4 线性组合和生成空间 30
2.6.5 线性无关、维数和基底 31
2.7 线性映射 32
2.7.1 映射基础 32
2.7.2 线性映射 34
2.7.3 线性映射的矩阵表示 35
2.7.4 克莱姆定理 35
2.8 特征值和特征向量 37
2.9.1 内积空间 38
2.9 欧几里得空间 38
2.9.2 正交和标准正交集 39
2.10 最小二乘法 40
2.11 推荐的阅读材料 43
第3章 向量代数 44
3.1 向量基础 44
3.1.1 向量等价 44
3.1.2 向量加法 45
3.1.4 向量数乘 46
3.1.3 向量减法 46
3.1.5 向量加法和数乘的性质 47
3.2 向量空间 48
3.2.1 生成空间 49
3.2.2 线性无关 49
3.2.3 基底、子空间和维数 49
3.2.4 方向 51
3.2.5 基底变化 52
3.2.6 线性变换 53
3.3 仿射空间 56
3.3.1 欧几里得几何 59
3.3.2 体积、行列式和数量三重积 66
3.3.3 坐标系 67
3.4 仿射变换 69
3.4.1 仿射映射的类型 72
3.4.2 仿射映射的合成 72
3.5 重心坐标和单形 73
3.5.1 重心坐标和子空间 74
3.5.2 仿射无关 74
4.2 点和向量的矩阵表示 76
第4章 矩阵、向量代数和变换 76
4.1 导言 76
4.3 加法、减法和乘法 78
4.3.1 向量加法和减法 79
4.3.2 点与向量的加法和减法 79
4.3.3 点的减法 80
4.3.4 数乘 80
4.4 向量乘积 80
4.4.1 点积 80
4.4.2 叉积 81
7.5.3 椭圆之间的相交 1 83
4.4.4 正交运算符和正交点积 84
4.4.3 张量积 84
4.5 仿射变换的矩阵表示 88
7.7 轴分离方法 1 88
4.6 基底变化／帧／坐标系统 89
4.7 向量几何和仿射变换 92
4.7.1 标记法 93
4.7.2 平移 93
4.7.3 旋转 95
4.7.4 缩放 100
4.7.5 反射 104
4.7.6 剪切 108
4.8 投影 111
4.8.1 正射投影 112
4.8.2 斜轴投影 113
4.8.3 透视投影 114
4.9 变换法线向量 116
推荐的阅读材料 118
第5章 二维几何图元 120
5.1 线形对象 120
5.1.1 隐含形式 120
5.1.2 参数形式 121
5.2 三角形 122
5.1.3 表示法之间的转换 122
5.3 矩形 124
5.4 折线和多边形 124
5.5 二次曲线 127
5.5.1 圆 129
5.5.2 椭圆 129
5.6 多项式曲线 130
5.6.1 贝塞尔曲线 130
5.6.3 非均匀有理B样条曲线 131
5.6.2 B样条曲线 131
第6章 二维距离 133
6.1 点到线形对象的距离 133
6.1.1 点到直线的距离 133
6.1.2 点到射线的距离 134
6.1.3 点到线段的距离 135
6.2 点到折线的距离 136
6.3.1 点到三角形的距离 138
6.3 点到多边形的距离 138
6.3.2 点到矩形的距离 150
6.3.3 点到正交平截面的距离 151
6.3.4 点到凸多边形的距离 154
6.4 点到二次曲线的距离 155
6.5 点到多项式曲线的距离 156
6.6 线形对象之间的距离 157
6.6.1 直线到直线的距离 157
6.6.2 直线到射线的距离 158
6.6.3 直线到线段的距离 159
6.6.4 射线到射线的距离 159
6.6.5 射线到线段的距离 162
6.6.6 线段到线段的距离 162
6.7 线形对象到折线或多边形的距离 163
6.8 线形对象到二次曲线的距离 164
6.9 线形对象到多项式曲线的距离 166
6.10 GJK算法 166
6.10.1 集合运算 167
6.10.2 算法概述 168
6.10.3 其他算法 170
7.1 线形对象之间的相交 171
第7章 二维相交 171
7.2 线形对象与折线的相交 174
7.3.1 线形对象与一般二次曲线的相交 175
7.3 线形对象与二次曲线的相交 175
7.3.2 线形对象与圆形曲线的相交 176
7.4 线形对象与多项式曲线的相交 176
7.4.1 代数方法 177
7.4.2 折线逼近 178
7.4.3 分级包围 178
7.4.4 单调分解 179
7.4.5 栅格方法 180
7.5.1 一般二次曲线之间的相交 181
7.5 二次曲线之间的相交 181
7.5.2 圆形二次曲线之间的相交 182
7.6 多项式曲线之间的相交 186
7.6.1 代数方法 186
7.6.2 折线逼近 186
7.6.3 分级包围 186
7.6.4 栅格方法 187
7.7.1 投影到直线上的分离 188
7.7.2 固定凸多边形的分离 189
7.7.3 运动凸多边形的分离 194
7.7.4 固定凸多边形的交集 196
7.7.5 运动凸多边形的接触点集 197
第8章 其他二维问题 204
8.1 三点确定的圆 204
8.2 与三条直线相切的圆 204
8.3 与圆相切于给定点的直线 205
8.4 通过给定点并与圆相切的直线 205
8.5 与两圆相切的直线 208
8.6 两点和给定半径决定的圆 213
8.7 通过一点并与一条直线相切且具有给定半径的圆 214
8.8 与两条直线相切且具有给定半径的圆 216
8.9 经过一点并与一个圆相切且具有给定半径的圆 218
8.10 具有给定半径并与一条直线和一个圆相切的圆 222
8.11 具有给定半径并与两圆相切的圆 225
8.12 与一条给定直线垂直并通过一个给定点的直线 227
8.13 位于两点之间并与该两点等距的直线 228
8.14 与一条给定直线平行且相距指定值的直线 229
8.15 与给定直线平行且垂直（水平）距离为指定值的直线 230
8.16 与给定圆相切并与给定直线垂直的直线 232
第9章 三维几何图元 234
9.1 线形对象 234
9.2 平面对象 235
9.2.1 平面 235
9.2.2 相对于一个平面的坐标系统 237
9.2.3 平面上的二维对象 238
9.3 多边形网格、多面体和有限多面体 240
9.3.1 顶点一边一面表 244
9.3.2 互连网格 244
9.3.3 复式网格 246
9.3.4 闭合网格 247
9.3.5 一致次序 247
9.3.6 柏拉图立体 249
9.4 二次曲面 253
9.4.1 三个非零特征值 253
9.4.2 两个非零特征值 254
9.4.3 一个非零特征值 256
9.5 环面 256
9.6 多项式曲线 257
9.6.1 贝塞尔曲线 258
9.6.2 B样条曲线 258
9.6.3 非均匀有理B样条曲线 259
9.7 多项式曲面 259
9.7.1 贝塞尔曲面 260
9.7.2 B样条曲面 262
9.7.3 非均匀有理B样条曲面 263
10.2 点到线形对象的距离 264
10.1 导言 264
第10章 三维距离 264
10.2.1 点到直线或射线的距离 265
10.2.2 点到折线的距离 267
10.3 点到平面对象的距离 270
10.3.1 点到平面的距离 270
10.3.2 点到三角形的距离 272
10.3.3 点到矩形的距离 277
10.3.4 点到多边形的距离 278
10.3.5 点到圆或圆盘的距离 281
10.4.1 一般问题 283
10.4 点到多面体的距离 283
10.4.2 点到有向有界箱的距离 285
10.4.3 点到正交平截体的距离 287
10.5 点到二次曲面的距离 291
10.5.1 点到一般二次曲面的距离 291
10.5.2 点到椭球面的距离 292
10.6 点到多项式曲线的距离 293
10.7 点到多项式曲面的距离 295
10.8 线形对象之间的距离 297
10.8.1 直线与直线之间的距离 297
10.8.2 线段／线段、直线／射线、直线／线段、射线／射线、射线／线段之间的距离 299
10.8.3 计算线段到线段的距离的另一种方法 310
10.9.1 线形对象到三角形的距离 316
10.9 线形对象与三角形、矩形、四面体和有向有界箱之间的距离 316
10.9.2 线形对象到矩形的距离 322
10.9.3 线形对象到四面体的距离 326
10.9.4 线形对象到有向有界箱的距离 328
10.10 直线到二次曲面的距离 341
10.11 直线到多项式曲面的距离 342
10.12 GJK算法 343
10.13 杂项 343
10.13.1 直线与平面曲线之间的距离 343
10.13.2 直线与平面实心物体之间的距离 345
10.13.3 平面曲线之间的距离 345
10.13.4 曲面上的测地距离 349
第11章 三维相交 352
11.1 线形对象与平面对象的相交 352
11.1.1 线形对象与平面的相交 352
11.1.2 线形对象与三角形的相交 354
11.1.3 线形对象与多边形的相交 357
11.1.4 线形对象与圆盘的相交 360
11.2 线形对象与多面体的相交 361
11.3 线形对象与二次曲面的相交 365
11.3.1 线形对象与一般二次曲面的相交 365
11.3.2 线形对象与球面的相交 367
11.3.3 线形对象与椭球面的相交 369
11.3.4 线形对象与圆柱面的相交 372
11.3.5 线形对象与圆锥面的相交 375
11.4 线形对象与多项式曲面的相交 380
11.4.1 代数曲面 381
11.4.2 自由形态曲面 382
11.5 平面对象之间的相交 388
11.5.1 两个平面之间的相交 388
11.5.2 三个平面之间的相交 390
11.5.3 三角形与平面的相交 392
11.5.4 三角形与三角形的相交 396
11.6 平面对象与多面体的相交 398
11.6.1 三角网格 399
11.6.2 一般多面体 400
11.7 平面对象与二次曲面的相交 401
11.7.1 平面与一般二次曲面的相交 401
11.7.2 平面与球面的相交 402
11.7.3 平面与圆柱面的相交 404
11.7.4 平面与圆锥面的相交 413
11.7.5 三角形与圆锥面的相交 428
11.8 平面对象与多项式曲面的相交 431
11.8.1 埃尔米特曲线 432
11.8.2 几何定义 433
11.8.3 计算曲线 434
11.8.4 算法 435
11.9.1 一般相交问题 437
11.8.5 实现要点 437
11.9 二次曲面之间的相交 437
11.9.2 椭球面 443
11.10 多项式曲面之间的相交 446
11.10.1 细分方法 447
11.10.2 格子评测 447
11.10.3 解析方法 448
11.10.4 步进方法 448
11.11 轴分离方法 448
11.11.1 固定凸多面体的分离 448
11.11.2 运动凸多面体的分离 451
11.11.4 固定凸多面体的接触集 453
11.11.3 固定凸多面体的交集 453
11.12 杂项 459
11.12.1 有向有界箱与正交平截体的相交 459
11.12.2 线形对象与轴对齐有界箱的相交 461
11.12.3 线形对象与有向有界箱的相交 464
11.12.4 平面与轴对齐有界箱的相交 467
11.12.5 平面对象与有向有界箱的相交 468
11.12.6 轴对齐有界箱之间的相交 470
11.12.7 有向有界箱之间的相交 470
11.12.8 球面与轴对齐有界箱的相交 474
11.12.9 圆柱面之间的相交 475
11.12.10 线形对象与环面的相交 485
第12章 其他三维问题 488
12.1 点在平面上的投影 488
12.2 向量在平面上的投影 489
12.3 直线与平面的夹角 490
12.4 两平面之间的夹角 491
12.5 以一条直线为法线并通过一给定点的平面 491
12.6 三点决定的平面 492
12.7 两条直线之间的夹角 493
第13章 关于计算几何学的话题 495
13.1 二维空间分区二叉树 495
13.1.1 多边形的空间分区二叉树表示 495
13.1.2 最小分解与平衡树 501
13.1.3 用空间分区二叉树进行点在多边形内的检测 502
13.1.4 用空间分区二叉树分解线段 503
13.2 三维空间分区二叉树 505
13.2.1 多面体的空间分区二叉树表示 506
13.2.2 最小分解与平衡树 507
13.2.3 用空间分区二叉树进行点在多面体内的检测 508
13.2.4 用空间分区二叉树分解线段 509
13.2.5 用空间分区二叉树分解凸多边形 510
13.3 点在多边形内的检测 511
13.3.1 点在三角形内的检测 512
13.3.2 点在凸多边形内的检测 513
13.3.3 点在一般多边形内的检测 515
13.3.5 栅格方法 520
13.3.4 点在多边形内的快速检测法 520
13.4 点在多面体内的检测 521
13.4.1 点在四面体内的检测 521
13.4.2 点在凸多面体内的检测 522
13.4.3 点在一般多面体内的检测 524
13.5 与多边形有关的布尔运算 526
13.5.1 抽象运算 526
13.5.2 两种基础运算 528
13.5.3 使用空间分区二叉树的布尔运算 529
13.5.4 其他算法 532
13.6.2 使用空间分区二叉树的布尔运算 534
13.6 与多面体有关的布尔运算 534
13.6.1 抽象运算 534
13.7 凸包 536
13.7.1 二维凸包 537
13.7.2 三维凸包 548
13.7.3 高维凸包 552
13.8 德洛奈三角剖分 556
13.8.1 二维增量构建 558
13.8.2 一般维度增量构建 561
13.8.3 用凸包实现构建 564
13.9.1 一个简单多边形的可见性图 565
13.9 多边形分解 565
13.9.2 三角剖分 568
13.9.3 水平分解三角剖分 571
13.9.4 凸分解 582
13.10 外接球与内切球 589
13.10.1 外接球 590
13.10.2 内切球 591
13.11 点集的最小区域 592
13.11.1 最小面积矩形 592
13.11.2 最小体积箱体 595
13.11.3 最小面积的圆 595
13.11.4 最小体积的球 599
13.11.5 杂项 600
13.12 面积和体积测量 602
13.12.1 二维多边形的面积 602
13.12.2 三维多边形的面积 605
13.12.3 多面体的体积 608
附录A 数值方法 610
附录B 三角几何 682
附录C 几何图元基础公式 700
参考文献 709
图索引 720
表索引 735