The generation of computational grids on complex two-dimensional geometries is a field of vivid research and development. In fact there is so much work going on in this field that just a very incomplete overview can be given here. Very efficient methods for grid generation and adaptive grid refinement in non-planar structures are common knowledge, both in TCAD and in other engineering and scientific disciplines.
The grid structures that have proven useful for the spatial discretization of two-dimensional problems with complex geometries are mapping methods, partly regular grids, and irregular grids. Mapping methods create the computational grid by some sort of transformation of a regular grid (which is often (but not always [96]) a rectangular tensor-product grid) onto the geometry to be discretized [97] [98] [99] [100] [101] [102]. Partly regular grids use regular structures to create a basic grid that is refined at boundaries and interfaces using irregular structures [103] [104] [105] [106] [107] [108] [109] [110]. Often the basic regular grid is orthogonal and is locally decomposed into triangular substructures. Irregular grids do not exhibit any regular structures when the underlying geometry is irregular (in almost all known cases these grids are triangular) and are rather seldom used [111] [112] (and to some extent the well-known Bank's method [113] [114]). Due to the vast background and evolution of algorithms and techniques, it is hardly feasible to properly classify the grid structures and grid generation methods any further.
What can be learned is that the most efficient algorithms are typically employing structures that allow hierarchical decompositions of the geometrical domain, like, e.g., quadtree methods.
Although both, considerable theoretical work and implementations, are available that deal with geometry-conforming grid generation, the focus is on initial grid generation. Most of the commonly used gridding tools generate the grid in one step from scratch, without the ability to re-use already existing grid points. What all these aforementioned methods and implementations have in common is the major aim of the generated grid, that is to solve a partial differential equation.
There are other methods applicable for grid generation which, in essence, tessellate a given domain through the triangulation of point clouds [115] [116]. At a close look, these methods are driven by entirely different (or at least differently posed) problems and applications like, e.g., the interpolation of measured and (increasingly less seldom) calculated values on given irregular distributed points in two- and three-dimensional space.
In principle, the problem statement in Section 6.1.3 suggests a close similarity to the latter area of problems and applications so that it seems reasonable to consider the use of a re-triangulation of all ``input points'' as a rigorous method for the generation of single-segment, mutually consistent, boundary-conforming triangular grids. The most prominent candidate for the actual triangulation task is, for several reasons, the so-called Delaunay triangulation.