1 相关领域研究与发展现状 1
1.1 计算几何概述 1
1.1.1 计算几何简介 1
1.1.2 计算几何的研究内容 2
1.1.3 计算几何的发展与现状 3
1.1.4 计算几何与其他学科的关系 4
1.2 知识发现概述 5
1.2.1 KDD的产生与发展 5
1.2.2 KDD技术研究和应用存在的问题与发展趋势 6
1.2.3 基于内在认知机理的知识发现理论 8
1.3 空间数据挖掘概述 9
1.3.1 空间数据挖掘的研究现状与发展 9
1.3.2 空间数据结构和空间数据库 33
1.3.3 GIS数据库的特点 45
1.3.4 空间数据库模型 46
1.3.5 空间查询与空间索引 50
2 平面点集的凸壳 57
2.1 凸壳问题简介 57
2.2 凸壳的应用 58
2.2.1 混合物勾兑 58
2.2.2 加速碰撞检测 58
2.3 平面点集凸壳的已有算法 59
2.3.1 卷包裹法 59
2.3.2 格雷厄姆算法 60
2.3.3 快速凸壳算法 62
2.3.4 分治算法 63
2.3.5 增量算法 65
2.3.6 周培德算法 67
2.3.7 实时凸壳算法 70
2.4 海量平面点集凸壳的解决方案 73
2.4.1 平面点集凸壳的城堡定理 73
2.4.2 城墙快速搜索算法 77
2.5 平面点集凸壳的一种高效算法 82
2.5.1 算法的基本思想 83
2.5.2 算法设计与实现 87
2.5.3 算法的效率分析与实验验证 88
2.5.4 快速凸壳算法的进一步优化 92
2.6 子凸壳的外直角三角定理 93
2.6.1 子凸壳的外直角三角定理 93
2.6.2 改进后的快速凸壳算法 95
2.6.3 实验结果 96
2.7 平面点集凸壳的两种近似算法 97
2.7.1 现有的近似凸壳算法 97
2.7.2 凸壳的近似度度量 99
2.7.3 点集坐标旋转法 100
2.7.4 多方向极值算法 105
3 平面点集的Delaunay三角剖分与Voronoi图 113
3.1 平面点集三角剖分简介 113
3.2 平面点集三角剖分的已有算法 113
3.2.1 逐点插入法 113
3.2.2 三角网生长法 114
3.2.3 分治方法 114
3.3 Delaunay三角剖分 114
3.3.1 Delaunay三角剖分简介 114
3.3.2 Delaunay三角网构建方法 115
3.3.3 约束Delaunay三角网 118
3.3.4 一致性约束Delaunay三角网 119
3.4 Voronoi图 120
3.4.1 Voronoi图简介 120
3.4.2 Voronoi图的构建 121
3.5 平面点集三角剖分的两条性质 121
4 多边形的三角剖分 124
4.1 多边形三角剖分简介 124
4.2 多边形三角剖分的已有算法 127
4.2.1 算法1 127
4.2.2 算法2 128
4.2.3 算法3 128
4.2.4 算法4 129
4.2.5 其他算法 130
4.3 简单多边形的快速单调剖分算法 130
4.3.1 算法相关概念与基本思想 131
4.3.2 算法描述 133
4.3.3 实现与验证 135
4.4 多边形的Delaunay三角剖分 136
5 艺术画廊问题 138
5.1 艺术画廊问题简介 138
5.1.1 艺术画廊问题及其数学模型 138
5.1.2 艺术画廊问题的诸多变种 139
5.1.3 艺术画廊问题解决现状综述 139
5.2 基于可见传播规则的艺术画廊问题的求解方法 143
5.2.1 可见传播规则 144
5.2.2 艺术画廊问题的求解步骤 145
5.2.3 实验验证 145
5.2.4 算法效率分析 147
5.3 基于顶点可见关系矩阵的艺术画廊问题解决方法 147
5.3.1 可见关系矩阵及其性质 147
5.3.2 多边形两个顶点可见性的判定 150
5.3.3 多边形顶点可见关系矩阵的自动建立 152
5.3.4 监视顶点问题求解——初步解 153
5.3.5 艺术画廊问题解的判定——最终解 156
5.3.6 实验及结论 158
5.3.7 监视点可位于多边形内部或边界上的艺术画廊问题 160
6 计算几何与空间数据挖掘 162
6.1 概述 162
6.2 凸壳与空间数据分类 162
6.3 基于Delaunay三角网的可视化空间数据聚类 163
6.3.1 算法的基本思想 164
6.3.2 算法的设计与实现 165
6.3.3 算法效率与特点分析 168
6.4 基于Delaunay三角网的高维空间数据聚类 169
6.4.1 算法的基本思想 170
6.4.2 该算法的相关定义 171
6.4.3 算法描述 173
参考文献 176