A Study Of 2D Delaunay Mesh Generation Algorithms

Many complicated physical phenomena in science and engineering can be modeled by partial differential equations(PDEs).When we can't get a real solution because of the complicated boundary conditons of the equations or the complicated shape of the domain,a numerical approximation of the solution is important. Numerical methods for sloving PDEs such as finite different method finite volume method and finite element method all depend on mesh generation. Meshes can be categorized as structured or unstructured by the topology. Althrough structured mesh can be easily stored and manipulated,it is not suitable for the complicated domain. Unstructured mesh is a common option for the subdivision of complicated domains.The generation algorithms of unstructured mesh can be divided into three classes:Delaunay triangulation methods advancing front methods and methods based on quadtrees.Not all meshes are suitable for numerical computation.Some meshes with poor quality can lead to a low speed in computation or even crash.So,it's necessary to research mesh generation algorithms that produce high quality meshes and run quickly. Delaunay mesh and its generation algorithms have strong mathematical theorys.That's why we choose this method for a deeply analyze and research.The work we have done are as follows:1. In this dissertation we discussed the algorithm design and analysis of the main operations in the process of 2D Delaunay mesh generation in detail.We designed an edge recovery algorithm for 2D Delaunay mesh generation and proved its correctness. We also estimated the asymptotic time complexity of the algorithm. This algorithm can effiectively reduce the number of intersection test.2. We did some comparative experiments about different algorithms for the same problems,and choosed preferable ones according to experiment results.At last we get a effective robust 2D Delaunay mesh generation program.3. We also developed an algorithm for 2D Delaunay mesh generation from digital image.We can extract the domain we are interested in from digital image,then get 2D Delaunay mesh of the domain. Experiment shows that this algorithm can successfully capture important characters of complicated domains and get 2D Delaunay mesh of high quality.4. In chapter 4 we did some comparative experiments between other people's similar work and our work.