The Theory And Method Research Of Restrained Triangulation

Restrained triangulation plays an important role in the fields of finite element analysis, information visualization and etc. At the same time, it is also a hot problem in computational geometry and computer aided geometric design. Restrained triangulation develops from triangulation, because users define complete discrete data, but the requirement is continuous patches (surface) which are nearly closed to the practical instance. However as a result of complexity of practical simulative scene and special shape on surface of object, triangulation will inevitably produce false triangulation result in practical applications. For avoiding this happening, an important effectual approach is defining some restrained terms in advance to direct and restrain the idiographic process of triangulation, which is restrained triangulation. By dint of Delaunay rule, we may have the best triangulation from the discrete data on the plane. While users define the restrained terms, these restrained terms must appear in the final triangulation result, which will greatly destroy local optimality. At present there are many fine algorithms for this kind of plane restrained triangulation. There is a best triangulation rule (Delaunay rule) in plane triangulation. But spatial triangulation is hard to find out the relevant optimality. Most algorithms take triangulation which doesn't violate the practical instance as the rule. From discrete data, triangulation will always breach practical instance of object surface in practical applications. Especially, in the peculiar case such as cavity, curve, helix, chine, valley of object and scene in practical applications, here we adopt traditional triangulation algorithms may take a false triangulation result. This paper firstly classifies restrained triangulation, and introduces classical algorithms for each kind of restrained triangulation, then advances innovative amelioration to these algorithms'localization (especially the spatial triangulation). Comparing to plane restrained triangulation of paper with former algorithms, it saves the process of calculating circumcircle, it will greatly cut down time complexity. At the aspect of spatial triangulation, we lay and sum up the restrained rules of spatial restrained triangulation in details, detailedly analyze the connections of each restriction in restrained rules especially much-restrained rules, then produce triangulation method to each restriction. Besides, to the characteristic points of exterior restrained triangulation in this paper, we extend its applied field to amend surface of three-dimensional object by using exterior restrained triangulation. In practice, we give results of each important restriction which mentioned in the paper, then analyze the results. Finally, we have summarized the pending problems and farther work.