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