Mesh Generation
Including coverage of mesh modification tools, evaluation criteria, optimization, and more, this book provides a comprehensive survey of the different algorithms and data structures for triangulation and meshing construction.
TABLE OF CONTENTS Mesh Generation
2.6: Two and Three-Dimensional Data Structures
2.6 Two and Three-Dimensional Data Structures
After one-dimensional data structures, we now turn to multi-dimensional data structures. Here, we find grids and trees (quadtrees and octrees). Described in this section as data structures, these structures will be viewed again (Chapters 5 and 8) as they also help meshing algorithms.
In this section, we show how several ideas developed for one-dimensional data structures can be reused in two and three dimensions to handle more complex objects such as points, polygons, etc.
Grid-Based Data Structures
Grid-based data structures are the two and three-dimensional equivalent of the one-dimensional bucket-like data structure. Notably, their performances vary greatly depending on the kind of items processed. If points are stored in two-or three-dimensional grids, very precise theoretical results have been known for a while, see [Devroye-1986] for example, that give indications about the behavior of the operations involved with such grids. However, when more complex objects are involved, such as polygons, many theoretical results remain to be established and justified experimentally. The aim of this section is precisely to present guidelines for the efficient use of grid-like partitions for applications such as mesh generation. A good starting point for further reading is [Cazals, Puech-1997].
Let ? = ? x ? y ? z = [ x min, x max] [ y min, y max] [ z min, z max] be Some three-dimensional domain containing a set ? of n objects,...
Copyright ISTE Ltd 2008 under license agreement with Books24x7
