Chapter 9A Few Basic Algorithms and Formulae

The goal of this chapter is that the reader1 should not find themselves faced with a triangulation or mesh2 like a deer in the headlight but, instead, will be able to work on examples beyond the purely academic. To do this, we must be able to manipulate the mesh obtained via such and such a software. We must be able to read the mesh, extract the pertinent information from it and be able to use this to construct the information that we truly need.

It seems particularly important to be able to construct the “table” of neighboring relationships3 between elements. In short, if we are able to construct this table, we can, in principle, find any topological information (ball, shell, etc.) based on which we can write the algorithms (for computations, etc.) that we wish to study. Writing one or more programs is, therefore, imperative. We must essentially be able to read the mesh and then use a reduced number of programming techniques to arrive at our objectives. In practice, if we understand what “hashing” is and if we are able to manipulate a stack or a queue4, as the case may be, and a linked list, we are ahead of the game and what remains is quite simple. These few techniques are used in many algorithms but will only be illustrated through insertion algorithms.

Before looking in detail, and from this angle, at the algorithm for insertion of points, for construction of neighbors, balls etc., we first look at elements of higher orders, ...

Get Meshing, Geometric Modeling and Numerical Simulation 1 now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.