Applied Research On Triangulation

Triangulation is an important part of a computer aided geometric design. It is widely used in the fields of finite element analysis﹑information visualization and so on. The data set that contains discrete points can be unconstrained discrete point Delaunay triangulation are strong triangular mesh; when the data model including data points and restrained rules, it is necessary to triangulation data sets for constructing triangular mesh by constraints guide, and defined this method as constrained triangulation . In this paper, it has produced new triangulation and the skeleton extraction, basing on interactive user input. Research contents of this paper reads as follows:First, it has introduced fundamental theories of the discrete points delaunay triangulation and Voronoi map, including the optimization criteria for Delaunay triangulation, related definitions as Delaunay triangular mesh, as the dual relationship between Delaunay triangulation and Voronoi diagram, it has analyzed the Voronoi diagram algorithmsSecondly, it has researched mainly a scattered point set in the plane with constraint and unconstraint triangulation algorithm, by timing constraint triangulation algorithm classified two type algorithms ,the one is the discrete data points and triangulation constraints at the same time, the other one , first discrete point triangulation, and then adding constraints, many algorithms has researched the latter method.The main part of this article is the fourth chapter, the triangulation was applied, the plane triangulation of data points destroyed the topological compatibility of data ,for the contour lines, carried out skeleton extraction algorithm using constrained triangulation of its regional division, and extracting the corresponding skeleton. Effectively avoiding the contour area of the external subdivision, and the skeleton of this extraction method is applied to the extraction of Chinese characters. after modifing this skeleton, upgraded the skeleton points,connected the boundary points related to form a curve, then select the appropriate point for triangulation, and finally formed the triangle mesh surface.