二维任意域内点集的Delaunay三角划分的研究

THE DELAUNAY TRIANGULATION OF A POINT SET WITHIN AN ARBITRARY 2D DOMAIN

传统的Ｄｅｌａｕｎａｙ三角划分不适合许多实际的应用．本文提出了二维任意域内点集的Ｄｅｌａｕｎａｙ三角划分（简记为ＤＴＡＤ）的概念，研究了其存在性、唯一性的条件以及一个三角划分是ＤＴＡＤ的充要条件．ＤＴＡＤ具有最小角最大以及平均形态比最大的性质，因此它是给定区域和点集的最佳三角划分．本文同时阐述了它的对偶图：任意域内点集的Ｖｏｒｏｎｏｉ图的概念和性质．ＤＴＡＤ突破了传统的Ｄｅｌａｕｎａｙ三角划分的限制，为有限元网格划分等实际应用提供了理论基础．

The concept of Delaunay triangulation of a point set within an arbitrary 2D domain (denoted as DTAD for short) is presented in this paper. The paper proves its existence and discusses the condition of its uniqueness and the sufficient and necessary condition for a triangulation to be a DTAD. The DTAD maximizes both the minimum internal angle and the average aspect ratio, which turns out that the DTAD is the optimal one among all triangUlations of a given point set within a domain. The concept and properties of Voronoi diagram of a point set within an arbitrary 2D domain, i. e.. the line dual of the DTAD, are also discussed. The DTAD eliminates the constraints of the traditional Delaunay triangulation within the hull of a given point set, and hence supplies a theoretic basis for practical applications such as finite element mesh generation.