Guillaume Damiand
A dD linear cell complex allows to represent an orientable subdivided dD object having linear geometry: each vertex of the subdivision is associated with a point. The geometry of each edge is a segment whose end points are associated with the two vertices of the edge, the geometry of each 2-cell is obtained from all the segments associated to the edges describing the boundary of the 2-cell and so on.
The combinatorial part of a linear cell complex is described by a dD combinatorial map (it is strongly recommended to first read the combinatorial maps chapter for definitions). To add the linear geometrical embedding, a point (a model of CGAL::Point_2 or CGAL::Point_3 or CGAL::Point_d) is associated to each vertex of the combinatorial map.
Note that the dimension of the combinatorial map d is not necessarily equal to the dimension of the ambient space d2. Indeed, we can use for example a 2D combinatorial map in a 2D ambient space to describe a planar graph (d=d2=2), or a 2D combinatorial map in a 3D ambient space to describe a surface in 3D space (d=2, d2=3) (case of the Polyhedron_3 package), or a 3D combinatorial map in a 3D ambient space (d=d2=3) and so on.
The diagram in Figure 28.3 shows the main classes of the package. CGAL::Linear_cell_complex is the main class (see Section 28.2.1), which inherits from the CGAL::Combinatorial_map class. Attributes can be associated to some cells of the linear cell complex thanks to an items class (see Section 28.2.4), which defines the dart type and the attributes types. These types may be different for different dimensions of cells, and they may also be void. In the class CGAL::Linear_cell_complex, it is required that specific attributes are associated to all vertices of the combinatorial map. These attributes must contain a point (a model of CGAL::Point_2 or CGAL::Point_3 or CGAL::Point_d), and can be represented by instances of class CGAL::Cell_attribute_with_point (see Section 28.2.2).
The CGAL::Linear_cell_complex<d,d2,LCCTraits,CMItems,Alloc> class is a model of the CombinatorialMap concept. It guarantees that each vertex of the combinatorial map is associated with an attribute containing a point. This class can be used in geometric algorithms (it plays the same role as Polyhedron_3 for HalfedgeDS).
This class has five template parameters standing for the dimension of the combinatorial map, the dimension of the ambient space, a traits class (a model of the LinearCellComplexTraits concept, see Section 28.2.3), an items class (a model of the LinearCellComplexItems concept, see Section 28.2.4), and an allocator which must be a model of the allocator concept of STL. Default classes are provided for the traits, items, and for the allocator classes, and by default d2=d.
A linear cell complex is valid, if it is a valid combinatorial map where each dart is associated with an attribute containing a point (i.e. an instance of a model of the CellAttributeWithPoint concept). Note that there are no validity constraints on the geometry (test on self intersection, planarity of 2-cells...). We can see two examples of CGAL::Linear_cell_complex in Figure 28.4.
The CGAL::Cell_attribute_with_point<LCC,Info_,Tag,OnMerge,OnSplit> class is a model of the CellAttributeWithPoint concept, which is a refinement of the CellAttribute concept. It represents an attribute associated with a cell, which can contain an information (depending on whether Info_==void or not), but which always contains a point, an instance of LCC::Point.
The LinearCellComplexTraits geometric traits concept defines the required types and functors used in the Linear_cell_complex class. For example it defines Point, the type of points used, and Vector, the corresponding vector type. It also defines all the required functors used for constructions and operations, as for example Construct_translated_point or Construct_sum_of_vectors.
The class CGAL::Linear_cell_complex_traits<d,K> is a model of LinearCellComplexTraits. It defines the different types which are obtained from K that, depending on d, is a model of the concept Kernel if d==2 or d==3, and a model of the concept Kernel_d otherwise.
The LinearCellComplexItems concept refines the CombinatorialMapItems concept by adding the requirement that 0-attributes are enabled, and associated with a type of attribute being a model of the CellAttributeWithPoint concept.
The class CGAL::Linear_cell_complex_min_items<d> is a model of LinearCellComplexItems. It uses CGAL::Dart<d>, and instances of CGAL::Cell_attribute_with_point (which contain no information) associated to each vertex. All other attributes are void.
Several operations defined in the combinatorial maps package can be used on a linear cell complex. This is the case for all the iteration operations that do not modify the model (see example in Section 28.4.1). This is also the case for all the operations that do not create new 0-cells: sew, unsew, remove_cell, insert_cell_1_in_cell_2, insert_cell_2_in_cell_3. Indeed, all these operations update non void attributes, and thus update vertex attributes of a linear cell complex. Note that some existing 0-attributes can be duplicated by the unsew method, but these 0-attributes are not new but copies of existing old 0-attributes.
However, operations that create a new 0-cell can not be directly used since the new 0-cell would not be associated with a vertex attribute. Indeed, it is not possible for these operations to automatically decide which point to create. These operations are: insert_cell_0_in_cell_1, insert_cell_0_in_cell_2 insert_dangling_cell_1_in_cell_2, plus all the creation operations. For these operations, new versions are proposed taking some points as additional parameters. Lastly, some new operations are defined, which use the geometry (see sections 28.3.2 and 28.3.3).
All the operations given in this section guarantee that given a valid linear cell complex and a possible operation, the result is a valid linear cell complex. As for a combinatorial map, it is also possible to use low level operations but additional operations may be needed to restore the validity conditions.
As explained in the combinatorial map user manual, Section 27.5.1, it is possible to glue two i-cells along an (i-1)-cell by using the sew<i> method. Since this method updates non void attributes, and since points are specific attributes, they are automatically updated during the sew<i> method. Thus the sewing of two i-cells could deform the geometry of the concerned objects.
For example, in Figure 28.5, we want to 3-sew the two initial 3-cells. sew<3>(1,5) links by β3 the pairs of darts (1,5), (2,8), (3,7) and (4,6). The eight vertex attributes around the facet between the two 3-cells before the sew are merged by pair during the sew operation (and the On_merge functor is called four times). Thus, after the sew, there are only four 0-attributes around the facet. By default, the attributes associated with the first dart of the sew operation are kept (but this can be modified by defining your own functor in the attribute class as explained in the package combinatorial map, Section 27.5.1). Intuitively, the geometry of the second 2-cell is deformed to fit to the first 2-cell.
This is similar for the unsew operation, which removes βi links of all the darts in ⟨β1,…,βi-2,βi+2,…,βd⟩(d0), and updates non void attributes which are no more associated to a same cell due to the unlinks. If we take the linear cell complex given in Figure 28.5 (Right), and we call unsew<3>(2), we obtain the linear cell complex in Figure 28.5 (Left) except for the coordinates of the new four vertices, which by default are copies of original vertices (this behavior can be modified thanks to the functor On_split in the attribute class). The unsew<3> operation has removed the four β3 links, and has duplicated the 0-attributes since vertices are split in two after the unsew operation.
There are several member functions allowing to insert specific configurations of darts into a linear cell complex. These functions return a Dart_handle to the new object. Note that the dimension of the linear cell complex must be large enough: darts must contain all the β used by the operation. All these methods add new darts in the current linear cell complex, existing darts are not modified. These functions are make_segment, make_triangle, make_tetrahedron and make_hexahedron.
There are two functions allowing to build a linear cell complex from two other Cgal data types:
Lastly, the function import_from_plane_graph(lcc,ais) adds in lcc all the cells reconstructed from the planar graph read in ais, a std::istream (see the reference manual for the file format).
Some methods are defined in Linear_cell_complex class to modify a linear cell complex and update the vertex attributes. In the following, we denote by dh0, dh1, dh2 the dart handles for the darts d0, d1, d2, respectively. That is d0 == *dh0.
lcc.insert_barycenter_in_cell<unsigned int i>(dh0) adds the barycenter of the i-cell containing dart d0. This operation is possible if d0∈lcc.darts() (see examples on Figure 28.6 and Figure 28.7).
lcc.insert_point_in_cell<unsigned int i>(dh0,p) is an operation similar to the previous operation, the only difference being that the coordinates of the new point are here given by p instead of being computed as the barycenter of the i-cell. Currently, these two operations are only defined for i=1 to insert a point in an edge, or i=2 to insert a point in a facet.
lcc.insert_dangling_cell_1_in_cell_2(dh0,p) adds a 1-cell in the 2-cell containing dart d0, the 1-cell being attached by only one of its vertex to the 0-cell containing dart d0. The second vertex of the new edge is associated with a new 0-attribute containing a copy of p as point. This operation is possible if d0∈lcc.darts() (see example on Figure 28.8).
Some examples of use of these operations are given in Section 28.4.2.
This example uses a 3-dimensional linear cell complex. It creates two tetrahedra and displays all the points of the linear cell complex thanks to a Vertex_attribute_const_range. Then, the two tetrahedra are 3-sewn and we translate all the points of the second tetrahedron along vector v(3,1,1). Since the two tetrahedra are 3-sewn, this translation moves also the 2-cell of the first tetrahedron shared with the second one. This is illustrated by displaying all the points of each 3-cell. For that we use a std::for_each and the Display_vol_vertices functor.
File: examples/Linear_cell_complex/linear_cell_complex_3.cpp
#include <CGAL/Linear_cell_complex.h>
#include <CGAL/Linear_cell_complex_operations.h>
#include <iostream>
#include <algorithm>
typedef CGAL::Linear_cell_complex<3> LCC_3;
typedef LCC_3::Dart_handle Dart_handle;
typedef LCC_3::Point Point;
typedef LCC_3::FT FT;
// Functor used to display all the vertices of a given volume.
template<class LCC>
struct Display_vol_vertices : public std::unary_function<LCC, void>
{
Display_vol_vertices(const LCC& alcc) :
lcc(alcc),
nb_volume(0)
{}
void operator() (typename LCC::Dart& d)
{
std::cout<<"Volume "<<++nb_volume<<" : ";
for (typename LCC::template One_dart_per_incident_cell_range<0,3>::
const_iterator it=lcc.template one_dart_per_incident_cell<0,3>
(lcc.dart_handle(d)).begin(),
itend=lcc.template one_dart_per_incident_cell<0,3>
(lcc.dart_handle(d)).end();
it!=itend; ++it)
{
std::cout << LCC_3::point(it) << "; ";
}
std::cout<<std::endl;
}
private:
const LCC& lcc;
unsigned int nb_volume;
};
int main()
{
LCC_3 lcc;
// Create two tetrahedra.
Dart_handle d1 = lcc.make_tetrahedron(Point(-1, 0, 0), Point(0, 2, 0),
Point(1, 0, 0), Point(1, 1, 2));
Dart_handle d2 = lcc.make_tetrahedron(Point(0, 2, -1),
Point(-1, 0, -1),
Point(1, 0, -1),
Point(1, 1, -3));
// Display all the vertices of the lcc by iterating on the
// Vertex_attribute container.
CGAL::set_ascii_mode(std::cout);
std::cout<<"Vertices: ";
for (LCC_3::Vertex_attribute_const_range::iterator
v=lcc.vertex_attributes().begin(),
vend=lcc.vertex_attributes().end();
v!=vend; ++v)
std::cout << v->point() << "; ";
std::cout<<std::endl;
// Display the vertices of each volume by iterating on darts.
std::for_each(lcc.one_dart_per_cell<3>().begin(),
lcc.one_dart_per_cell<3>().end(),
Display_vol_vertices<LCC_3>(lcc));
// 3-Sew the 2 tetrahedra along one facet
lcc.sew<3>(d1, d2);
// Display the vertices of each volume by iterating on darts.
std::for_each(lcc.one_dart_per_cell<3>().begin(),
lcc.one_dart_per_cell<3>().end(),
Display_vol_vertices<LCC_3>(lcc));
// Translate the second tetrahedra by a given vector
LCC_3::Vector v(3,1,1);
for (LCC_3::One_dart_per_incident_cell_range<0,3>::iterator
it=lcc.one_dart_per_incident_cell<0,3>(d2).begin(),
itend=lcc.one_dart_per_incident_cell<0,3>(d2).end();
it!=itend; ++it)
{
LCC_3::point(it)=LCC_3::Traits::Construct_translated_point_3()
(LCC_3::point(it),v);
}
// Display the vertices of each volume by iterating on darts.
std::for_each(lcc.one_dart_per_cell<3>().begin(),
lcc.one_dart_per_cell<3>().end(),
Display_vol_vertices<LCC_3>(lcc));
// We display the lcc characteristics.
std::cout<<"LCC characteristics: ";
lcc.display_characteristics(std::cout) << ", valid=" << lcc.is_valid()
<< std::endl;
return EXIT_SUCCESS;
}
The output is:
Vertices: 1 1 2; 1 0 0; 0 2 0; -1 0 0; 1 1 -3; 1 0 -1; -1 0 -1; 0 2 -1; Volume 1 : -1 0 0; 0 2 0; 1 0 0; 1 1 2; Volume 2 : 0 2 -1; -1 0 -1; 1 0 -1; 1 1 -3; Volume 1 : -1 0 0; 0 2 0; 1 0 0; 1 1 2; Volume 2 : 0 2 0; -1 0 0; 1 0 0; 1 1 -3; Volume 1 : 2 1 1; 3 3 1; 4 1 1; 1 1 2; Volume 2 : 3 3 1; 2 1 1; 4 1 1; 4 2 -2; LCC characteristics: #Darts=24, #0-cells=5, #1-cells=9, #2-cells=7, #3-cells=2, #ccs=1, valid=1
The first line gives the points of the linear cell complex before the sew<3>. There are eight points, four for each tetrahedron. After the sew, six vertices are merged two by two, thus there are five vertices. We can see the points of each 3-cell (lines Volume 1 and Volume 2) before the sew, after the sew and after the translation of the second volume. We can see that this translation has also modified the three common points between the two 3-cells. The last line shows the number of cells of the linear cell complex, the number of connected components, and finally a Boolean to show the validity of the linear cell complex.
This example uses a 4-dimensional linear cell complex embedded in a 5-dimensional ambient space. It creates two tetrahedra having 5D points and sews the two tetrahedra by β4. Then we use some high level operations, display the number of cells of the linear cell complex, and check its validity. Last we use the reverse operations to get back to the initial configuration.
File: examples/Linear_cell_complex/linear_cell_complex_4.cpp
#include <CGAL/Linear_cell_complex.h>
#include <CGAL/Linear_cell_complex_constructors.h>
#include <iostream>
#include <vector>
typedef CGAL::Linear_cell_complex<4,5> LCC_4;
typedef LCC_4::Dart_handle Dart_handle;
typedef LCC_4::Point Point;
typedef LCC_4::Vector Vector;
typedef LCC_4::FT FT;
int main()
{
LCC_4 lcc;
// Create two tetrahedra.
FT p1[5]={ 0, 0, 0, 0, 0}; std::vector<FT> v1(p1,p1+5);
FT p2[5]={ 0, 2, 0, 0, 0}; std::vector<FT> v2(p2,p2+5);
FT p3[5]={ 0, 1, 2, 0, 0}; std::vector<FT> v3(p3,p3+5);
FT p4[5]={ 2, 1, 0, 0, 0}; std::vector<FT> v4(p4,p4+5);
FT p5[5]={-1, 0, 0, 0, 0}; std::vector<FT> v5(p5,p5+5);
FT p6[5]={-1, 2, 0, 0, 0}; std::vector<FT> v6(p6,p6+5);
FT p7[5]={-1, 1, 2, 0, 0}; std::vector<FT> v7(p7,p7+5);
FT p8[5]={-3, 1, 2, 0, 0}; std::vector<FT> v8(p8,p8+5);
Dart_handle d1 = lcc.make_tetrahedron(Point(5, v1.begin(), v1.end()),
Point(5, v2.begin(), v2.end()),
Point(5, v3.begin(), v3.end()),
Point(5, v4.begin(), v4.end()));
Dart_handle d2 = lcc.make_tetrahedron(Point(5, v5.begin(), v5.end()),
Point(5, v6.begin(), v6.end()),
Point(5, v7.begin(), v7.end()),
Point(5, v8.begin(), v8.end()));
lcc.display_characteristics(std::cout);
std::cout<<", valid="<<lcc.is_valid()<<std::endl;
lcc.sew<4>(d1,d2);
lcc.display_characteristics(std::cout);
std::cout<<", valid="<<lcc.is_valid()<<std::endl;
// Add one vertex on the middle of the edge containing dart d1.
Dart_handle d3 = lcc.insert_barycenter_in_cell<1>(d1);
CGAL_assertion( lcc.is_valid() );
lcc.display_characteristics(std::cout);
std::cout<<", valid="<<lcc.is_valid()<<std::endl;
// Add one edge to cut the face containing dart d3 in two.
Dart_handle d4 = CGAL::insert_cell_1_in_cell_2(lcc,d3,d1->beta(0));
CGAL_assertion( lcc.is_valid() );
lcc.display_characteristics(std::cout);
std::cout<<", valid="<<lcc.is_valid()<<std::endl;
// We use removal operations to get back to the initial configuration.
CGAL::remove_cell<LCC_4,1>(lcc,d4);
CGAL_assertion( lcc.is_valid() );
CGAL::remove_cell<LCC_4,0>(lcc,d3);
CGAL_assertion( lcc.is_valid() );
lcc.unsew<4>(d1);
lcc.display_characteristics(std::cout);
std::cout<<", valid="<<lcc.is_valid()<<std::endl;
return EXIT_SUCCESS;
}
The output is:
#Darts=24, #0-cells=8, #1-cells=12, #2-cells=8, #3-cells=2, #4-cells=2, #ccs=2, valid=1 #Darts=24, #0-cells=4, #1-cells=6, #2-cells=4, #3-cells=1, #4-cells=2, #ccs=1, valid=1 #Darts=28, #0-cells=5, #1-cells=7, #2-cells=4, #3-cells=1, #4-cells=2, #ccs=1, valid=1 #Darts=32, #0-cells=5, #1-cells=8, #2-cells=5, #3-cells=1, #4-cells=2, #ccs=1, valid=1 #Darts=24, #0-cells=8, #1-cells=12, #2-cells=8, #3-cells=2, #4-cells=2, #ccs=2, valid=1
This example illustrates the way to use a 3D linear cell complex by adding another information to vertices. For that, we need to define our own items class. The difference with the CGAL::Linear_cell_complex_min_items class is about the definition of the vertex attribute where we use a CGAL::Cell_attribute_with_point with a non void info. In this example, the ``vextex color'' is just given by an int (the second template parameter of the CGAL::Cell_attribute_with_point). Lastly, we define the Average_functor class in order to set the color of a vertex resulting of the merging of two vertices to the average of the two initial values. This functor is associated with the vertex attribute by passing it as template parameter. Using this items class instead of the default one is done during the instantiation of template parameters of the CGAL::Linear_cell_complex class.
Now we can use LCC_3 in which each vertex is associated with an attribute containing both a point and an information. In the following example, we create two cubes, and set the color of the vertices of the first cube to 1 and of the second cube to 19 (by iterating through two One_dart_per_incident_cell_range<0, 3> ranges). Then we 3-sew the two cubes along one facet. This operation merges some vertices (as in the example of Figure 28.5). We insert a vertex in the common 2-cell between the two cubes, and set the information of the new 0-attribute to 5. In the last loop, we display the point and the information of each vertex of the linear cell complex.
File: examples/Linear_cell_complex/linear_cell_complex_3_with_colored_vertices.cpp
#include <CGAL/Linear_cell_complex.h>
#include <CGAL/Linear_cell_complex_operations.h>
#include <iostream>
#include <algorithm>
struct Average_functor
{
template<class CellAttribute>
void operator()(CellAttribute& ca1,const CellAttribute& ca2)
{ ca1.info()=(ca1.info()+ ca2.info())/2; }
};
struct Myitem
{
template<class Refs>
struct Dart_wrapper
{
typedef CGAL::Dart<3, Refs > Dart;
typedef CGAL::Cell_attribute_with_point< Refs, int, CGAL::Tag_true,
Average_functor >
Vertex_attribute;
typedef CGAL::cpp0x::tuple<Vertex_attribute> Attributes;
};
};
typedef CGAL::Linear_cell_complex_traits
<3, CGAL::Exact_predicates_inexact_constructions_kernel> Traits;
typedef CGAL::Linear_cell_complex<3,3,Traits,Myitem> LCC_3;
typedef LCC_3::Dart_handle Dart_handle;
typedef LCC_3::Point Point;
typedef LCC_3::FT FT;
Dart_handle make_iso_cuboid(LCC_3& lcc, const Point& basepoint, FT lg)
{
return lcc.make_hexahedron(basepoint,
Traits::Construct_translated_point()
(basepoint,Traits::Vector(lg,0,0)),
Traits::Construct_translated_point()
(basepoint,Traits::Vector(lg,lg,0)),
Traits::Construct_translated_point()
(basepoint,Traits::Vector(0,lg,0)),
Traits::Construct_translated_point()
(basepoint,Traits::Vector(0,lg,lg)),
Traits::Construct_translated_point()
(basepoint,Traits::Vector(0,0,lg)),
Traits::Construct_translated_point()
(basepoint,Traits::Vector(lg,0,lg)),
Traits::Construct_translated_point()
(basepoint,Traits::Vector(lg,lg,lg)));
}
int main()
{
LCC_3 lcc;
// Create two iso_cuboids.
Dart_handle d1 = make_iso_cuboid(lcc, Point(-2, 0, 0), 1);
Dart_handle d2 = make_iso_cuboid(lcc, Point(0, 0, 0), 1);
// Set the "color" of all vertices of the first cube to 1.
for (LCC_3::One_dart_per_incident_cell_range<0, 3>::iterator
it=lcc.one_dart_per_incident_cell<0,3>(d1).begin(),
itend=lcc.one_dart_per_incident_cell<0,3>(d1).end(); it!=itend; ++it)
{ LCC_3::vertex_attribute(it)->info()=1; }
// Set the "color" of all vertices of the second cube to 19.
for (LCC_3::One_dart_per_incident_cell_range<0, 3>::iterator it=
lcc.one_dart_per_incident_cell<0,3>(d2).begin(),
itend=lcc.one_dart_per_incident_cell<0,3>(d2).end(); it!=itend; ++it)
{ LCC_3::vertex_attribute(it)->info()=19; }
// 3-Sew the two cubes along one facet.
lcc.sew<3>(d1->beta(1)->beta(1)->beta(2), d2->beta(2));
// Barycentric triangulation of the facet between the two cubes.
Dart_handle d3=lcc.insert_barycenter_in_cell<2>(d2->beta(2));
// Set the color of the new vertex to 5.
LCC_3::vertex_attribute(d3)->info()=5;
// Display all the vertices of the map.
for (LCC_3::Vertex_attribute_range::iterator
it=lcc.vertex_attributes().begin(),
itend=lcc.vertex_attributes().end();
it!=itend; ++it)
{
std::cout<<"point: "<<it->point()<<", "<<"color: "<<it->info()
<<std::endl;
}
return EXIT_SUCCESS;
}
The output is:
point: -1 1 1, color: 10 point: -1 0 1, color: 10 point: -2 0 1, color: 1 point: -2 1 1, color: 1 point: -2 1 0, color: 1 point: -1 1 0, color: 10 point: -1 0 0, color: 10 point: -2 0 0, color: 1 point: 1 1 1, color: 19 point: 1 0 1, color: 19 point: -1 0.5 0.5, color: 5 point: 1 1 0, color: 19 point: 1 0 0, color: 19
Before applying the sew operation, the eight vertices of the first cube are colored by 1, and the eight vertices of the second cube by 19. After the sew operation, there are eight vertices which are merged two by two, and due to the average functor, the color of the four resulting vertices is now 10. Then we insert a vertex in the center of the common 2-cell between the two cubes. The coordinates of this vertex are initialized with the barycenter of the 2-cell (-1,0.5,0.5), and its color is not initialized by the method, thus we set its color manually by using the result of insert_barycenter_in_cell<2> which is a dart incident to the new vertex.
This package was developed by Guillaume Damiand, with the help of Andreas Fabri, Sébastien Loriot and Laurent Rineau. Monique Teillaud and Bernd Gärtner contributed to the manual.