● 摘要
本文对黎曼空间中的Voronoi网格剖分问题进行了系统的研究，建立了一套黎曼流形Voronoi网格剖分的理论体系，包括基本概念、性质、定理以及生成算法等。在该理论体系的支撑下，黎曼流形Voronoi网格生成算法能够按照黎曼度量要求处理复杂黎曼流形，并且能够保证算法生成的最终网格是正确的。 首先，在介绍网格剖分和黎曼流形理论背景知识的基础上，本文对现有欧氏空间、黎曼空间中Voronoi及其对偶网格剖分的研究现状进行了综述，讨论了现有理论和算法的特点和优势。同时，结合实际应用情况分析了目前算法的一些局限性，总结了研究黎曼空间中Voronoi网格剖分的重要意义，并在此基础上提出了本文的研究目标和主要研究内容。 然后，在介绍欧氏空间Voronoi及其对偶网格剖分方法和黎曼流形基础理论的基础上，本文对黎曼流形的特点进行了详细分析，总结出研究黎曼流形Voronoi网格剖分存在的难点。针对这些难点并借鉴欧氏空间中的理论和方法，最终提出本文研究黎曼流形Voronoi网格剖分的总体思路。以总体思路为主线，本文将黎曼流形Voronoi网格剖分研究分为两部分，第一部分研究黎曼流形Voronoi网格的基础理论，第二部分研究黎曼流形Voronoi网格的生成算法。 基础理论部分主要包括黎曼流形Voronoi及其对偶网格的基本概念、性质以及判定定理。本文研究了黎曼空间中点集外接测地球唯一存在的条件。结合目前的研究成果提出了针对n维黎曼流形上n+1个点的外接测地球的唯一存在性判定定理，该定理是本文研究的一个基础性定理。此外，本文提出了球组合、空球组合及最小Voronoi邻近点集等概念。这些概念不仅能够解决黎曼流形上定义Voronoi对偶网格的困难，而且能够很好地描述黎曼空间中Voronoi及其对偶网格的本质特点，完全能够满足本文研究的需要。在基本概念基础上，本文给出了最小Voronoi邻近点集的判定定理，同时也是Voronoi图与空球组合对偶的判定定理，此定理是下面研究网格生成算法的基础。 以黎曼流形Voronoi及其对偶网格的基本概念和定理为基础，本文借鉴欧氏空间中的Delaunay增量算法，提出了采用增量方法生成黎曼流形Voronoi网格的算法思路。算法思路中详细分析了黎曼空间与欧氏空间生成Voronoi图的不同，并充分考虑黎曼流形的特点，设计了黎曼流形Voronoi网格生成算法。黎曼流形Voronoi网格生成算法包括网格全局生成算法和网格局部生成算法，这两个算法分别适用于不同情况。此外，对于黎曼流形上初始点集分布的各种情况，Voronoi网格生成算法能够统一处理。对于以上算法，本文证明了其正确性，并讨论了算法效率和收敛性。本文的基础理论保证了算法最终生成Voronoi网格的两个相邻Voronoi核能够唯一确定一条测地线。 最后，本文讨论了黎曼流形Voronoi网格生成算法基于坐标卡实现过程中遇到的一些关键问题，并简要介绍了将具体模型初始数据解释为黎曼流形的一种方法。基于给定模型的黎曼流形定义，并采用黎曼流形Voronoi网格生成算法，文中给出了算法的应用实例。