2.1 Why Use Data Structures?

As an introduction, we look at a "naive" algorithm that can be used to construct a triangulation. Let consider a set of points , each of which contained (to simplify even more) in a single initial triangle. The algorithm consists of finding, for each and any point P, the triangle K enclosing it and then to subdivide K into three new triangles by connecting P to the three vertices of K:

• For all

  • Find triangle K containing point P,

  • Subdivide this triangle into three.

• End

While very simple, this algorithm raises several questions. Among these, we simply mention the need to define the concept of a triangulation and how to represent it, for instance, by using adjacency relationships between the triangles. Another question is related to the quick identification of the triangle containing the point P to be inserted. Should we examine all triangles of the current triangulation or take into account the fact that any triangle is obtained by subdividing its parent?

This simple example gives some indications on how to proceed and what to know to implement such an algorithm (simple as it may be). This is not indeed restricted to defining the operations required to code this algorithm, but also to finding the data structure(s) adapted to the problem, in such a way as to define a Program. According to [Wirth-1986], we have the following paradigm:

There is obviously a close link between...