《计算几何若干方法及其在空间数据挖掘中的套用》是以2003年国家科技成果重点推广计画项目——集成化组合构件式知识发现软体系统（ICCKDSS，项目编号2003EC000001）为背景而编写的。ICCKDSS是基于内在机理的知识发现理论（Knowledge Discoververy Theory 13ased On InnerMechanism，KDTIM）在空间数据挖掘领域的进一步扩展。《计算几何若干方法及其在空间数据挖掘中的套用》主要对计算几何中的一些理论与方法进行研究，并尝试将这些理论与方法套用于空间数据挖掘中，解决空间数据挖掘中的一些问题。

1 相关领域研究与发展现状

1.1 计算几何概述

1.1.1 计算几何简介

1.1.2 计算几何的研究内容

1.1.3 计算几何的发展与现状

1.1.4 计算几何与其他学科的关係

1.2 知识发现概述

1.2.1 KDD的产生与发展

1.2.2 KDD技术研究和套用存在的问题与发展趋势

1.2.3 基于内在认知机理的知识发现理论

1.3 空间数据挖掘概述

1.3.1 空间数据挖掘的研究现状与发展

1.3.2 空间数据结构和空间资料库

1.3.3 GIs资料库的特点

1.3.4 空间资料库模型

1.3.5 空间查询与空间索引

2 平麵点集的凸壳

2.1 凸壳问题简介

2.2 凸壳的套用

2.2.1 混合物勾兑

2.2.2 加速碰撞检测

2.3 平麵点集凸壳的已有算法

2.3.1 卷包裹法

2.3.2 格雷厄姆算法

2.3.3 快速凸壳算法

2.3.4 分治算法

2.3.5 增量算法

2.3.6 周培德算法

2.3.7 实时凸壳算法

2.4 海量平麵点集凸壳的解决方案

2.4.1 平麵点集凸壳的城堡定理

2.4.2 城墙快速搜寻算法

2.5 平麵点集凸壳的一种高效算法

2.5.1 算法的基本思想

2.5.2 算法设计与实现

2.5.3 算法的效率分析与实验验证

2.5.4 快速凸壳算法的进一步最佳化

2.6 子凸壳的外直角三角定理

2.6.1 子凸壳的外直角三角定理

2.6.2 改进后的快速凸壳算法

2.6.3 实验结果

2.7 平麵点集凸壳的两种近似算法

2.7.1 现有的近似凸壳算法

2.7.2 凸壳的近似度度量

2.7.3 点集坐标旋转法

2.7.4 多方向极值算法

3 平麵点集的Delaunay三角剖分与Voronoi图

3.1 平麵点集三角剖分简介

3.2 平麵点集三角剖分的已有算法

3.2.1 逐点插入法

3.2.2 三角网生长法

3.2.3 分治方法

3.3 Delaunay三角剖分

3.3.1 Delaunay三角剖分简介

3.3.2 Delaunay三角网构建方法

3.3.3 约束Delaunay三角网

3.3.4 一致性约束：Delaunay三角网

3.4 Voronoi图

3.4.1 Voronoi图简介

3.4.2 Voronoi图的构建

3.5 平麵点集三角剖分的两条性质

4 多边形的三角剖分

4.1 多边形三角剖分简介

4.2 多边形三角剖分的已有算法

4.2.1 算法1

4.2.2 算法2

4.2.3 算法3

4.2.4 算法4

4.2.5 其他算法

4.3 简单多边形的快速单调剖分算法

4.3.1 算法相关概念与基本思想

4.3.2 算法描述

4.3.3 实现与验证

4.4 多边形的Delaunay三角剖分

5 艺术画廊问题

5.1 艺术画廊问题简介

5.1.1 艺术画廊问题及其数学模型

5.1.2 艺术画廊问题的诸多变种

5.1.3 艺术画廊问题解决现状综述

5.2 基于可见传播规则的艺术画廊问题的求解方法

5.2.1 可见传播规则

5.2.2 艺术画廊问题的求解步骤

5.2.3 实验验证

5.2.4 算法效率分析

5.3 基于顶点可见关係矩阵的艺术画廊问题解决方法

5.3.1 可见关係矩阵及其性质

5.3.2 多边形两个顶点可见性的判定

5.3.3 多边形顶点可见关係矩阵的自动建立

5.3.4 监视顶点问题求解——初步解

5.3.5 艺术画廊问题解的判定——最终解

5.3.6 实验及结论

5.3.7 监视点可位于多边形内部或边界上的艺术画廊问题

6 计算几何与空间数据挖掘

6.1 概述

6.2 凸壳与空间数据分类

6.3 基于Delaunay三角网的可视化空间数据聚类

6.3.1 算法的基本思想

6.3.2 算法的设计与实现

6.3.3 算法效率与特点分析

6.4 基于Delaunay三角网的高维空间数据聚类

6.4.1 算法的基本思想

6.4.2 该算法的相关定义

6.4.3 算法描述

参考文献