Quadtree-Based Triangular Mesh Generation for Finite Element Analysis of Heterogeneous Spatial Data.
Prabhakar Reddy Gvs, Hubert J. Montas · 2001
Abstract. Applying mathematical models to practical situations often requires the use of discrete geometrical models of the solution domain. In some cases destructive measurements of the objects under examination is acceptable, but in several areas of research the measurements comes from imaging techniques such as X-ray, computer assisted tomography (CAT), magnetic resonance imaging (MRI), satellite imagery, or aerial photographs. A crucial preprocessing step for such analysis involves the extraction of measurements/features from these images, which form the basis of geometrical models and finite element mesh. In this paper, we describe a simple algorithm for triangulating the solution domain represented in images without a need for such prior feature extraction, albeit such a step may reduce the size of the resulting mesh. The proposed algorithm generates quality triangular meshes with: (a) provably good angle bounds between 26.565 o and 90 o , and (b) an aspect ratio of at most 2.5. The proposed mesh generation algorithm (imageMesher) extends the mesh generation technique of Bern et al. (1990) to images as input. Previous algorithms with shape and size bounds have all been based on triangulating domains that are either: (a) vertex set, (b) lines, (c) polygons, or (d) planar straight line graphs (PSLGs). The proposed algorithm matches their bounds, but uses a fundamentally different kind of input. The implementation of the algorithm is discussed and the theoretical bounds on the size and shape of the triangular patches are evaluated. As an intermediate result, we also describe an improved algorithm for constructing balanced quadtree. Finally, we illustrate real-time applications of the proposed approach, which demonstrates its ability to use the solution domain described in images to fit directly into the finite element analysis