A WEIGHTING ALGORITHM FOR DECOMPOSING A SIMPLE POLYGON INTO SET OF TRIANGLES AND CONVEX QUADRILATERALS

摘要

In the computational geometry and the finite element mesh generation of computational mechanics, the sub-domains decomposition of simple polygon is one of the basic problems. In the finite element mesh generation, the sub-domains decomposition is usually done manually. So the mapping method is usually considered as a semi-automatic method. On the one hand, in order to avoid the sub-domains decomposition, a great deal of automatic mesh generation methods are proposed, such as, Delaunay triangulation, Modified quadtree method, Advancing front technique. Because of several problems, say, control of mesh generation process and the shape quality of the resulting meshes, among these methods, the mapping method is applied in most commercial code, By the mapping method, the resulting elements are generally well shaped and numerical methods can be expected to perform well. The most obvious deficiency of mapping method is that the region to be discretized should be divided into super-elements manually. So automatic sub-domains decomposition is a practical problem. An algorithm for decomposing a simple polygon into set of triangles and convex quadrilaterals was proposed in this paper. The algorithm was guided by a weighting function and estimation factor of shape quality. It is possible to make fewer numbers and better aspect ratio of the resulting triangles and convex quadrilaterals. The algorithm run very efficiently and fit to use in practice.