37.3 Thiết kế phần mềm dựa trên lưới tam giác CGAL

37.3   Thiết kế phần mềm

The triangulations classes of Cgal provide high-level geometric functionalities such as location of a point in the triangulation, insertion, removal, or displacement of a point. They are build as a layer on top of a data structure called the triangulation data structure. The triangulation data structure can be thought of as a container for the faces and vertices of the triangulation. This data structure also takes care of all the combinatorial aspects of the triangulation.
This separation between the geometric aspect and the combinatorial part is reflected in the software design by the fact that the triangulation classes have two template parameters:

• the first parameter stands for a geometric traits class providing the geometric primitives (points, segments and triangles) of the triangulation and the elementary operations (predicate or constructions) on those objects.
• the second parameter stands for a triangulation data structure class. The concept of triangulation data structure is described in Section 38.2 of Chapter 38. The triangulation data structure defines the types used to represent the faces and vertices of the triangulation, as well as additional types (handles, iterators and circulators) to access and visit the faces and vertices. Cgal provides the class Triangulation_data_structure_2<Vb,Fb>as a default model of triangulation data structure. The class Triangulation_data_structure_2<Vb,Fb>has two template parameters standing for a vertex class and a face class. Cgal defines concepts for these template parameters and provide default models for these concepts. The vertex and base classes are templated by the geometric traits which allows them to have some knowledge of the geometric primitives of the triangulation. Those default vertex and face base classes can be replaced by user customized base classes in order, for example, to deal with additional properties attached to the vertices or faces of a triangulation. See section 37.11for more details on the way to make use of this flexibility.

The Figure 37.3 summarizes the design of the triangulation package, showing the three layers (base classes, triangulation data structure and triangulation) forming this design.


Figure 37.3:  The triangulations software design.
The top triangulation level, responsible for the geometric embedding of the triangulation comes in different flavors according to the different kind of triangulations: basic, Delaunay, regular, constrained or constrained Delaunay. Each kind of triangulations correspond to a different class. Figure 37.4 summarizes the derivation dependencies of Cgal 2D triangulations classes. Any 2D triangulation class is parametrized by a geometric traits and a triangulation data structure. While a unique concept TriangulationDataStructure_2describes the triangulation data structure requirements for any triangulation class, the concept of geometric traits actually depends on the triangulation class. In general, the requirements for the vertex and face base classes are described by the basic concepts TriangulationVertexBase_2and TriangulationFaceBase_2. However, some triangulation classes requires base classes implementing refinements of the basic concepts.


Figure 37.4:  The derivation tree of 2D triangulations.

Link nguồn: http://www.cgal.org/