Catálogo de publicaciones - libros

Triangulations are widely used as a basis for representing geometries and other information appearing in a huge variety of applications. In geographical information systems (GIS), triangulations are used to represent terrain surfaces and relations between geographical objects. Systems for modeling geological structures in the oil and gas industry use triangulations for representing surfaces that separate different geological structures, and for representing properties of these structures. Computer aided design (CAD) systems with triangulation features are common in the manufacturing industry and in particular within the automotive industry, which has been a driving force for this research for many decades. We also find applications using triangulations within engineering fields that simulate physical phenomena using finite element methods (FEM). Finally, we will mention the importance of triangulation in visualization and computer graphics.

The of a triangulation can be described by graph theoretic concepts such that a clear distinction is made between the topological structure and the geometric embedding information. The topological elements of a triangulation are nodes (or vertices), edges and triangles, and the geometric embedding information, which is associated with these elements, is points, curves (or straight-line segments) and surface patches respectively. Likewise, a distinction can be made between topological and geometric . By considering triangulations as , we can benefit from an extensive theory and a variety of interesting algorithms operating on graphs. In particular, we will see that , or , provide useful algebraic tools to consider triangulations at an abstract level. Common data structures for representing triangulations on computers are outlined and compared in view of storage requirements and efficiency of carrying out topological operations.

This chapter is devoted to two important constructs in computational geometry, the Voronoi diagram and the Delaunay triangulation. These constructions are dual in the sense that one can be defined, or derived, from the other. They have been used in a number of applications, and the theory has been studied over many years and is well understood. In the following sections, we present a unified discussion of the classical theory of Voronoi diagrams and Delaunay triangulations in the plane, and thus provide a theoretical basis for designing algorithms for Delaunay triangulation.

Several algorithms have been developed for Delaunay triangulation based on the definitions and the theory of the previous chapter. The popularity of the Delaunay triangulation is twofold. It yields “good shaped” triangles (in the plane) and the theory, mainly based on its dual, the Voronoi diagram, is well established. Other types of triangulation, such as triangulations that are optimal in the sense of the MinMax angle criterion, are difficult to compute in reasonable time from a large number of points. In fact, the Delaunay swapping criteria, which were shown to be equivalent in Section 3.6, are the only known criteria that can be used in Lawson’s local optimization procedure (LOP) to guarantee a globally optimal triangulation.

Although Delaunay triangulations have well-shaped triangles in the plane and satisfy an optimum principle by the MaxMin angle criterion, they are not necessarily optimal as domains for surfaces. In this chapter we are concerned with surfaces in 3D space defined over triangulations, and in particular surfaces represented by piecewise linear functions over triangulations in the plane. The main concern in this respect is to construct triangulations from 3D point sets where the triangulations are optimal according to local and global cost functions which are designed to reflect properties of the underlying physical model from which the points have been sampled.

The theory of Delaunay triangulation can be generalized to account for constrained edges also referred to as prespecified edges or break lines. This leads to the notion of (CDT). Constrained edges may represent rivers, roads, lake boundaries and mountain ridges in cartography, or linear features in finite element grids. CDT may also be used to construct triangulations with holes and triangulations with arbitrarily shaped (non-convex) boundaries, while preserving Delaunay properties on the interior of the triangulation away from holes and boundaries.

Refinement of triangulations is motivated by grid generation for the finite element method (FEM). Having said this, it is important to note that these techniques are also applicable in visualization, scattered data interpolation and other applications demanding triangulations with well-shaped triangles. The refinement scheme presented in this chapter successively refines a constrained triangulation by node insertion until the triangulation satisfies certain criteria on the shape of triangles. Roughly speaking, we aim at creating triangulations with triangles as equilateral as possible while simultaneously satisfying given constraints. As the title indicates, Delaunay properties will be maintained throughout the refinement process.

Surface reconstruction from scattered data in applications like reverse engineering, geographic information systems and geological modeling usually involves huge amount of data. Creating surface triangulations with vertices in every given data point may be too memory demanding and time consuming, and is usually not required in such cases. Data acquired with scanning devices or data from seismic surveys may also contain considerable noise. Therefore a “good” approximation to the measured data is often sought instead of exact interpolation. Approximation by least squares is a common approach to constructing surfaces from measured data and in this chapter least squares approximation is applied to fit surface triangulations to data.

Triangulations can be dealt with algebraically using the principles of G-maps introduced in Chapter 2. High-level abstraction of functions operating on triangulations is achieved using G-maps, which are algebraically defined based on a limited number of clear concepts. At an abstract level, the topology of a triangulation can be described by using only one single topological element, the . Furthermore, the three α-iterators, α, α and α, are the only operations needed for traversing the triangulation.