GIS中的计算几何算法研究

论文摘要

GIS的内容主要包括:空间数据的获取,空间数据的表达,空间数据的处理,空间数据的分析,空间数据的显示与可视化。而这些内容的实现将用到许多计算几何中基本算法。计算几何是理论计算机科学领域中一个新的极有生命力的子领域,计算几何的研究成果已在空间分析,计算机图形学,化学,统计分析,模式识别,地理数据库以及其他许多领域中得到了广泛的应用。计算几何研究的典型问题有几何基元(geometric primitives)、查找、优化等问题类组成。其中,几何基元包括凸壳和Voronoi图,多边形的三角剖分、划分问题与相交问题。几何查找包括点定位,可视化、区域查找等问题。在几何基元中的凸壳和三角剖分的算法研究过程中,本文发现了当前简单多边形凸壳的主流算法存在的错误,并加以改正,使得改正后的算法更加合理,效率更高;本文还提出了基于径向扫描排序和凸壳技术的散乱点的Delaunay三角网生成算法。该方法在得到散乱点的三角网的同时得到了该三角网的凸壳。同时根据该算法推导出一个三角形个数、离散点的个数及凸壳上的点的个数三者之间的一个关系式,并通过实验验证了该关系式的正确性。在几何查找中的算法研究中,本文对其中一个重要的点定位算法——点在多边形内外检测算法进行了改进,提出将矢量和射线法结合,解决了射线法所具有的奇异情况。当对同一个多边形需要多次进行内外检测时,提出了一个基于单调链判断点在多边形内外的方法。该方法的预处理简单。实验结果证明,该方法具有易实现和效率高等优点。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 前言
• 1.1.1 GIS中常用的几个计算几何算法
• 1.1.2 计算几何的简介
• 1.2 研究内容和现状
• 1.2.1 点在多边形内外判断算法
• 1.2.2 Delaunay三角网生成算法
• 1.2.3 凸壳生成算法
• 1.3 论文的组织
• 第二章 判断点在多边形内外的算法研究
• 2.1 基本概念
• 2.2 点在多边形内外算法研究
• 2.3 小结
• 第三章 Delaunay三角网生成算法研究
• 3.1 Delaunay算法研究
• 3.1.1 Delaunay三角网的基本概念
• 3.1.2 散乱点集Delaunay三角网算法研究
• 3.2 动态Delaunay算法研究
• 3.3 小结
• 第四章 凸壳生成算法研究
• 4.1 基本概念
• 4.2 简单多边形凸壳算法研究
• 4.3 散乱点集凸包算法研究
• 4.4 小结
• 第五章 总结与展望
• 5.1 论文的总结
• 5.2 今后工作展望
• 参考文献
• 攻读硕士期间的主要研究成果
• 致谢