{< katex />}

第一章 计算几何基础 #

1.1 基本几何对象 #

• 点、向量、直线、线段、射线
• 多边形：简单多边形、凸多边形、星形多边形
• 圆、椭圆、抛物线、双曲线

1.2 几何变换 #

• 平移、旋转、缩放变换
• 仿射变换与投影变换
• 齐次坐标系统

1.3 数值精度问题 #

• 浮点数精度误差分析
• 稳健计算技术
• 精确几何计算

第二章 基本几何算法 #

2.1 点与向量运算 #

• 向量加减法与数乘
• 点积与叉积计算
• 向量夹角与方向判断

2.2 距离计算 #

• 点到直线距离
• 点到线段距离
• 线段到线段距离
• 点与多边形位置关系

2.3 相交检测 #

• 直线与直线相交
• 线段与线段相交
• 直线与多边形相交
• 多边形与多边形相交

第三章 凸包算法 #

3.1 凸包定义与性质 #

• 凸集与凸包概念
• 凸包的性质与应用
• 极值点与支撑线

3.2 经典凸包算法 #

• Graham扫描算法
• Jarvis步进法（礼品包装算法）
• QuickHull快速凸包算法
• 增量算法与分治算法

3.3 动态凸包 #

• 动态凸包维护
• 在线凸包算法
• 凸包合并操作

第四章 多边形算法 #

4.1 多边形表示 #

• 简单多边形与复杂多边形
• 多边形顶点表示法
• 多边形三角剖分

4.2 多边形操作 #

• 多边形求交与合并
• 多边形偏移与膨胀
• 多边形简化与光滑

4.3 多边形包含检测 #

• 射线法（奇偶规则）
• 环绕数法
• 凸多边形快速包含检测

第五章 三角剖分 #

5.1 三角剖分基础 #

• Delaunay三角剖分
• 约束三角剖分
• 三角网格数据结构

5.2 三角剖分算法 #

• 增量Delaunay三角剖分
• 分治Delaunay三角剖分
• 约束Delaunay三角剖分

5.3 Voronoi图 #

• Voronoi图定义与性质
• Voronoi图与Delaunay三角剖分对偶
• Voronoi图构造算法

第六章 几何搜索与查询 #

6.1 范围查询 #

• 点定位问题
• 区域查询算法
• 最近邻查询

6.2 空间分割技术 #

• KD树结构与算法
• 四叉树与八叉树
• BSP树（二叉空间分割树）

6.3 线段与射线查询 #

• 线段树与区间树
• 射线投射算法
• 可见性计算

第七章 运动规划 #

7.1 路径规划基础 #

• 配置空间概念
• 障碍物表示与建模
• 自由空间计算

7.2 路径规划算法 #

• 可见图法
• 细胞分解法
• 势场法

7.3 高级运动规划 #

• 概率路线图（PRM）
• 快速探索随机树（RRT）
• 多机器人路径规划

第八章 计算几何应用 #

8.1 计算机图形学应用 #

• 隐藏面消除
• 光线追踪
• 碰撞检测

8.2 地理信息系统 #

• 地图叠加分析
• 空间索引技术
• 地形建模与分析

8.3 机器人学与CAD/CAM #

• 机器人导航与避障
• 数控加工路径规划
• 三维建模与逆向工程

第九章 高级专题 #

9.1 计算几何复杂度 #

• 算法时间复杂度分析
• 下界证明技术
• 并行计算几何

9.2 几何数据结构 #

• 持久化数据结构
• 动态几何数据结构
• 外部存储算法

9.3 新兴研究方向 #

• 流形学习与几何
• 计算拓扑学
• 几何深度学习