第一章 基础几何概念与数据结构
#
1.1 基本几何对象
#
- 点、向量、直线、射线、线段
- 平面、多边形、多面体
- 圆、椭圆、球体、圆柱体
- 曲线与曲面表示方法
1.2 几何数据结构
#
- 点集数据结构
- 多边形表示方法
- 网格数据结构
- 空间索引结构
1.3 计算几何基础
#
- 浮点数精度问题
- 几何谓词计算
- 退化情况处理
- 鲁棒性几何计算
第二章 基本几何算法
#
2.1 点与向量运算
#
- 向量加减法与数乘
- 点积与叉积计算
- 向量投影与反射
- 距离与角度计算
2.2 直线与线段算法
#
- 直线方程表示
- 线段相交检测
- 点到直线距离
- 直线交点计算
2.3 多边形算法
#
- 多边形面积计算
- 点与多边形位置关系
- 多边形凸性判断
- 多边形三角剖分
第三章 凸包算法
#
3.1 二维凸包算法
#
- 礼品包装算法
- Graham扫描算法
- QuickHull算法
- 增量算法
3.2 三维凸包算法
#
- 礼品包装算法扩展
- 增量构造方法
- 分治算法
- 随机增量算法
3.3 凸包应用
#
第四章 几何查找与搜索
#
4.1 范围查询
#
- 正交范围查询
- 圆形范围查询
- 多边形范围查询
- k-d树与四叉树
4.2 最近邻查询
#
- 最近点对问题
- k-最近邻查询
- Voronoi图构造
- 德劳内三角剖分
4.3 点定位算法
#
第五章 计算几何中的图论
#
5.1 平面图理论
#
5.2 可见性图
#
- 艺术画廊问题
- 可见性图构造
- 最短路径计算
- 最小守卫集
5.3 德劳内三角剖分
#
- 空圆性质
- 翻转算法
- 约束德劳内三角剖分
- 三维德劳内四面体化
第六章 几何优化问题
#
6.1 最小包围问题
#
- 最小包围球
- 最小包围盒
- 最小面积包围矩形
- 最小周长包围多边形
6.2 几何覆盖问题
#
- 集合覆盖问题
- 圆盘覆盖问题
- 直线覆盖问题
- 艺术画廊定理
6.3 几何分割问题
#
第七章 运动规划与碰撞检测
#
7.1 路径规划算法
#
- 可见性图方法
- 势场方法
- 单元分解方法
- 随机路图方法
7.2 碰撞检测
#
7.3 运动规划应用
#
- 机器人路径规划
- 车辆导航系统
- 动画角色运动
- 虚拟现实交互
第八章 计算机图形学中的几何算法
#
8.1 曲线与曲面
#
- Bézier曲线与曲面
- B样条曲线与曲面
- NURBS表示
- 细分曲面
8.2 网格处理
#
8.3 光线追踪
#
- 光线与几何体求交
- 包围体层次结构
- 空间细分结构
- 加速数据结构
第九章 三维几何处理
#
9.1 三维建模
#
9.2 三维重建
#
9.3 三维布尔运算
#
- 并集、交集、差集
- 实体裁剪
- 网格布尔运算
- 鲁棒性布尔运算
第十章 几何算法应用领域
#
10.1 计算机辅助设计
#
- CAD系统几何核心
- 参数化建模
- 特征识别
- 工程分析集成
10.2 地理信息系统
#
10.3 计算机视觉
#
10.4 机器人学
#
- 运动学计算
- 工作空间分析
- 抓取规划
- 传感器数据处理