第1章 绪论 1
1.1 引言 1
1.2 Voronoi图基本概念 3
1.3 Voronoi图的推广 5
1.3.1 距离的推广 5
1.3.2 生长元的推广 6
1.3.3 移动点的Voronoi图 6
1.3.4 Poisson Voronoi图 6
1.4 Voronoi图生成技术 6
1.5 Voronoi图的国内研究现状 10
1.6 限定Voronoi图的生成 11
1.7 本书的研究目的、内容及意义 11
1.8 本书的组织 12
第2章 限定Voronoi剖分相关基本概念、理论 14
2.1 Delaunay三角化 14
2.1.1 Delaunay三角化的特性 14
2.1.2 经典的Delaunay三角化算法 16
2.2 带权的Delaunay三角化和带权的Voronoi图 18
2.3 限定Delaunay三角剖分 21
2.3.1 平面限定Delaunay三角化 21
2.3.2 曲面限定Delaunay三角化 23
2.4 限定Voronoi图 24
2.4.1 二维／三维限定条件 24
2.4.2 限定Voronoi图的生成 26
第3章 二维限定Voronoi网格的研究 28
3.1 平面限定Voronoi网格生成算法 28
3.1.1 控制圆算法 28
3.1.2 二维Voronoi细化算法——矩形控制带算法 34
3.1.3 二维Voronoi细化算法的改进算法——梯形检测带算法 40
3.2 二维网格单元质量和尺度控制技术 46
3.2.1 网格单元质量、尺度的评价标准 46
3.2.2 控制算法的预处理 46
3.2.3 Voronoi网格的尺寸控制 49
3.2.4 Voronoi网格的质量控制 51
3.2.5 算法实例 52
第4章 重叠域条件下的限定Voronoi网格生成 54
4.1 引言 54
4.2 复杂限定条件下的Delaunay三角剖分 54
4.2.1 内部复杂限定条件 54
4.2.2 重叠域限定条件 55
4.2.3 复杂限定条件下限定Delaunay三角剖分解决思路 56
4.2.4 复杂限定条件下的Delaunay三角剖分算法 60
4.3 复杂限定条件下限定Voronoi图的生成 60
4.3.1 算法思路 60
4.3.2 算法描述 61
4.3.3 算法的效率 61
4.4 算法使用的新的数据结构 62
第5章 三维限定Voronoi网格生成的研究 64
5.1 三维限定Voronoi网格的限定条件 64
5.2 三维限定Voronoi网格生成算法 65
5.2.1 阶段性算法 65
5.2.2 改进性算法 72
5.3 三维限定Voronoi网格生成实例 82
第6章 曲面限定Delaunay三角化的研究 85
6.1 算法思路 85
6.2 算法关键问题 86
6.3 算法描述 88
6.4 曲面限定Delaunay三角化实例 90
第7章 黎曼流形上的Voronoi剖分的研究 92
7.1 黎曼流形的基础知识 92
7.1.1 微分流形与黎曼流形的基本概念 92
7.1.2 黎曼流形下的Delaunay三角化和Voronoi图 94
7.2 存在性研究 94
7.2.1 存在性 94
7.2.2 一些性质 95
7.3 生成算法研究 96
7.4 基于坐标卡的生成算法 97
7.4.1 建立坐标卡 97
7.4.2 生成网格 98
7.5 黎曼流形的Voronoi剖分实例 99
第8章 算法平台的研究 101
8.1 系统的实现方案 101
8.1.1 GLView——具有OpenGL绘图功能的MFCView 101
8.1.2 GLView中OpenGL环境的保护 104
8.1.3 GLRC的维护 105
8.2 实例 105
第9章 限定Voronoi剖分技术的应用 108
9.1 PEBI网格生成 108
9.1.1 PEBI网格应用背景 108
9.1.2 PEBI网格模块 110
9.1.3 PEBI网格生成研究现状 112
9.1.4 PEBI网格生成实例 114
9.2 机器人路径规划 123
9.2.1 引言 123
9.2.2 GVG生成研究现状 124
9.2.3 本章算法 126
9.2.4 算法实例 128
9.3 移动通信 129
9.3.1 引言 129
9.3.2 小区覆盖问题 130
参考文献 132