Skip to main content
main-content

Über dieses Buch

This book is entirely about triangulations. With emphasis on computational issues, we present the basic theory necessary to construct and manipulate triangulations. In particular, we make a tour through the theory behind the Delaunay triangulation, including algorithms and software issues. We also discuss various data structures used for the representation of triangulations. Throughout the book we relate the theory to selected applications, in part- ular surface construction, meshing and visualization. The ?eld of triangulation is part of the huge area of computational ge- etry, and over many years numerous books and articles have been written on the subject. Important results on triangulations have appeared in theore- cal books and articles, mostly within the realm of computational geometry. However, many important results on triangulations have also been presented in publications within other research areas, where they have played and play an important role in solving speci?c scienti?c and applied problems. We will touch upon some of these areas in this book. Triangulations, almost everywhere. The early development of triangulation comes from surveying and the art of constructing maps – cartography. S- veyors and cartographers used triangles as the basic geometric feature for calculating distances between points on the Earth’s surface and a position’s elevation above sea level.

Inhaltsverzeichnis

Frontmatter

1. Triangles and Triangulations

Abstract
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.
Øyvind Hjelle, Morten Dæhlen

2. Graphs and Data Structures

Abstract
The topology 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 operators. By considering triangulations as planar graphs, we can benefit from an extensive theory and a variety of interesting algorithms operating on graphs. In particular, we will see that generalized maps, or G-maps, 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.
Øyvind Hjelle, Morten Dæhlen

3. Delaunay Triangulations and Voronoi Diagrams

Abstract
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.
Øyvind Hjelle, Morten Dæhlen

4. Algorithms for Delaunay Triangulation

Abstract
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.
Øyvind Hjelle, Morten Dæhlen

5. Data Dependent Triangulations

Abstract
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.
Øyvind Hjelle, Morten Dæhlen

6. Constrained Delaunay Triangulation

Abstract
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 constrained Delaunay triangulation1 (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.
Øyvind Hjelle, Morten Dæhlen

7. Delaunay Refinement Mesh Generation

Abstract
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.
Øyvind Hjelle, Morten Dæhlen

8. Least Squares Approximation of Scattered Data

Abstract
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.
Øyvind Hjelle, Morten Dæhlen

9. Programming Triangulations: The Triangulation Template Library (TTL)

Abstract
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 dart. Furthermore, the three α-iterators, α0, α1 and α2, are the only operations needed for traversing the triangulation.
Øyvind Hjelle, Morten Dæhlen

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise