\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.6 - Combinatorial Maps
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CombinatorialMap Concept Reference

Definition

The concept CombinatorialMap defines a d-dimensional combinatorial map.

Has Models:
CGAL::Combinatorial_map<d,Items,Alloc>

Creation

 CombinatorialMap ()
 Default constructor creating an empty combinatorial map.
 
template<typename CMap >
 CombinatorialMap (const CMap &cmap)
 Construct a new combinatorial map from another one. More...
 

Types

typedef unspecified_type Dart
 Dart type, a model of the Dart concept.
 
typedef unspecified_type Dart_handle
 Dart handle type, equal to Dart::Dart_handle.
 
typedef unspecified_type Dart_const_handle
 Dart const handle type, equal to Dart::Dart_const_handle.
 
typedef unspecified_type size_type
 Size type (an unsigned integral type).
 

Constants

static unsigned int dimension
 The dimension d of the combinatorial map, equal to Dart::dimension.
 
static size_type NB_MARKS
 The number of available Boolean marks of the combinatorial map.
 
Dart_handle null_dart_handle
 The null dart handle constant. More...
 

Types for Attributes

typedef unspecified_type Attributes
 The tuple of cell attributes. More...
 
template<unsigned int i>
using Attribute_type = unspecified_type
 Attribute_type<i>::type is the type of i-attributes, a model of CellAttribute concept. More...
 
template<unsigned int i>
using Attribute_handle = unspecified_type
 Attribute_handle<i>::type is a handle to i-attributes, equal to Dart::Attribute_handle<i>::type . More...
 
template<unsigned int i>
using Attribute_const_handle = unspecified_type
 Attribute_handle<i>::type is a const handle to i-attributes, equal to Dart::Attribute_const_handle<i>::type . More...
 

Range Types

typedef unspecified_type Dart_range
 Range of all the darts of the combinatorial map. More...
 
typedef unspecified_type Dart_const_range
 Const range of all the darts of the combinatorial map. More...
 
template<unsigned int i>
using Attribute_range = unspecified_type
 Attribute_range<i>::type is the range of all the i-attributes. More...
 
template<unsigned int i>
using Attribute_const_range = unspecified_type
 Attribute_const_range<i>::type is the const range of all the i-attributes. More...
 
template<unsigned int... Beta>
using Dart_of_orbit_range = unspecified_type
 Range of all the darts of the <Beta...> orbit. More...
 
template<unsigned int... Beta>
using Dart_of_orbit_const_range = unspecified_type
 Const range of all the darts of the <Beta...> orbit. More...
 
template<unsigned int i, unsigned int dim = dimension>
using Dart_of_cell_range = unspecified_type
 Range of all the darts of an i-cell. More...
 
template<unsigned int i, unsigned int dim = dimension>
using Dart_of_cell_const_range = unspecified_type
 Const range of all the darts of the i-cell. More...
 
template<unsigned int i, unsigned int j, unsigned int dim = dimension>
using One_dart_per_incident_cell_range = unspecified_type
 Range of one dart of each i-cell incident to one j-cell. More...
 
template<unsigned int i, unsigned int j, unsigned int dim = dimension>
using One_dart_per_incident_cell_const_range = unspecified_type
 Const range of one dart of each i-cell incident to one j-cell. More...
 
template<unsigned int i, unsigned int dim = dimension>
using One_dart_per_cell_range = unspecified_type
 Range of one dart of each i-cell of the combinatorial map. More...
 
template<unsigned int i, unsigned int dim = dimension>
using One_dart_per_cell_const_range = unspecified_type
 Const range of one dart of each i-cell of the combinatorial map. More...
 

Access Member Functions

bool is_empty () const
 Returns true iff the combinatorial map is empty, i.e. it contains no dart.
 
bool is_valid () const
 Returns true iff the combinatorial map is valid. More...
 
bool is_without_boundary (unsigned int i) const
 Returns true iff the combinatorial map is without i-boundary. More...
 
bool is_without_boundary () const
 Returns true iff the combinatorial map is without boundary in all dimensions.
 
size_type number_of_darts () const
 Returns the number of darts in the combinatorial map.
 
template<unsigned int i>
size_type number_of_attributes () const
 Returns the number of i-attributes in the combinatorial map. More...
 
Dart_handle beta (Dart_handle dh, int i, int j)
 Returns \( \beta_j\)( \( \beta_i\)(*dh)). More...
 
Dart_const_handle beta (Dart_const_handle dh, int i, int j) const
 Returns \( \beta_j\)( \( \beta_i\)(*dh)). More...
 
template<int i, int j>
Dart_handle beta (Dart_handle dh)
 Returns \( \beta_j\)( \( \beta_i\)(*dh)). More...
 
template<int i, int j>
Dart_const_handle beta (Dart_const_handle dh) const
 Returns \( \beta_j\)( \( \beta_i\)(*dh)). More...
 
bool is_free (Dart_const_handle dh, unsigned int i) const
 Returns true iff dart *dh is i-free. More...
 
template<unsigned int i>
bool is_free (Dart_const_handle dh) const
 Returns true iff dart *dh is i-free. More...
 
int highest_nonfree_dimension (Dart_const_handle dh) const
 Returns the highest dimension i such that dart *dh is not i-free. More...
 
Dart_handle opposite (Dart_handle dh)
 Returns a handle to a dart belonging to the same edge than dart *dh, and not to the same vertex. More...
 
Dart_const_handle opposite (Dart_const_handle dh) const
 Returns a const handle to a dart belonging to the same edge than dart *dh, and not to the same vertex, when the dart is const. More...
 
Dart_handle other_extremity (Dart_handle dh)
 Returns a handle to a dart belonging to the other vertex of the edge containing dart *dh (but contrary to opposite() not necessarily to the same edge). More...
 
Dart_const_handle other_extremity (Dart_const_handle dh) const
 Returns a const handle to a dart belonging to the other vertex of the edge containing dart *dh, when the dart is const (but contrary to opposite() not necessarily to the same edge). More...
 
std::ostream & display_characteristics (std::ostream &os) const
 Displays on os the number of elements of the combinatorial map. More...
 

Attributes Access Member Functions

template<unsigned int i>
Attribute_handle< i >::type attribute (Dart_handle dh)
 Returns a handle to the i-attribute associated to dart *dh. More...
 
template<unsigned int i>
Attribute_const_handle< i >::type attribute (Dart_const_handle dh) const
 Returns a const handle to the i-attribute associated to dart *dh, when the dart is const. More...
 
template<unsigned int i>
Dart_handle dart_of_attribute (typename Attribute_handle< i >::type ah)
 Returns one dart of the cell associated to the i-attribute *ah. More...
 
template<unsigned int i>
Dart_const_handle dart_of_attribute (typename Attribute_const_handle< i >::type ah) const
 Returns one dart of the cell associated to the const i-attribute *ah. More...
 
template<unsigned int i>
Attribute_type< i >::type::Info & info_of_attribute (typename Attribute_handle< i >::type ah)
 Returns the information of the i-attribute *ah. More...
 
template<unsigned int i>
const Attribute_type< i >
::type::Info & 
info_of_attribute (typename Attribute_const_handle< i >::type ah) const
 Returns the information of the const i-attribute *ah. More...
 
template<unsigned int i>
Attribute_type< i >::type::Info & info (Dart_handle adart)
 A shorcut for info_of_attribute<i>(attribute<i>(adart)). More...
 
template<unsigned int i>
const Attribute_type< i >
::type::Info & 
info (Dart_const_handle adart) const
 A shorcut for info_of_attribute<i>(attribute<i>(adart)) for const handle. More...
 
template<unsigned int i>
Dart_handledart (Dart_handle adart)
 A shorcut for dart_of_attribute<i>(attribute<i>(adart)). More...
 
template<unsigned int i>
Dart_const_handle dart (Dart_const_handle adart) const
 A shorcut for dart_of_attribute<i>(attribute<i>(adart)) for const handle. More...
 

Transformations Between Handles and Instances

Dart_handle dart_handle (Dart &d)
 Returns the dart handle of d. More...
 
Dart_const_handle dart_handle (const Dart &d) const
 Returns the dart const handle of d. More...
 

Range Access Member Functions

Dart_rangedarts ()
 Returns a range of all the darts in the combinatorial map.
 
Dart_const_rangedarts () const
 Returns a const range of all the darts in the combinatorial map.
 
template<unsigned int i>
Attribute_range< i >::type & attributes ()
 Returns a range of all the i-attributes in the combinatorial map. More...
 
template<unsigned int i>
Attribute_const_range< i >::type & attributes () const
 Returns a const range of all the i-attributes in the combinatorial map. More...
 
template<unsigned int... Beta>
Dart_of_orbit_range darts_of_orbit (Dart_handle dh)
 Returns a range of all the darts of the orbit <Beta...>(*dh). More...
 
template<unsigned int... Beta>
Dart_of_orbit_const_range darts_of_orbit (Dart_const_handle dh) const
 Returns a const range of all the darts of the orbit <Beta...>(*dh). More...
 
template<unsigned int i, unsigned int dim = dimension>
Dart_of_cell_range darts_of_cell (Dart_handle dh)
 Returns a range of all the darts of the i-cell containing *dh. More...
 
template<unsigned int i, unsigned int dim = dimension>
Dart_of_cell_const_range darts_of_cell (Dart_const_handle dh) const
 Returns a const range of all the darts of the i-cell containing *dh. More...
 
template<unsigned int i, unsigned int j, unsigned int dim = dimension>
One_dart_per_incident_cell_range one_dart_per_incident_cell (Dart_handle dh)
 Returns a range of one dart of each i-cell incident to the j-cell containing *dh. More...
 
template<unsigned int i, unsigned int j, unsigned int dim = dimension>
One_dart_per_incident_cell_const_range one_dart_per_incident_cell (Dart_const_handle dh) const
 Returns a const range of one dart of each i-cell incident to the j-cell containing *dh. More...
 
template<unsigned int i, unsigned int dim = dimension>
One_dart_per_cell_range one_dart_per_cell ()
 Returns a range of one dart of each i-cell in the combinatorial map. More...
 
template<unsigned int i, unsigned int dim = dimension>
One_dart_per_cell_const_range one_dart_per_cell () const
 Returns a const range of one dart of each i-cell in the combinatorial map. More...
 

Modifiers

template<typename T1 >
Dart_handle create_dart (T1 t1)
 Creates a new dart in the combinatorial map, and returns the corresponding handle. More...
 
void erase_dart (Dart_handle dh)
 Removes *dh from the combinatorial map. More...
 
template<unsigned int i, typename T1 >
Attribute_handle< i >::type create_attribute (T1 t1)
 Creates a new i-attribute in the combinatorial map, and returns the corresponding handle. More...
 
template<unsigned int i>
void erase_attribute (Attribute_handle< i >::type ah)
 Removes the i-attribute *ah from the combinatorial map. More...
 
template<unsigned int i>
void set_attribute (Dart_handle dh, Attribute_handle< i >::type ah)
 Associates the i-attribute of all the darts of the i-cell containing *dh to *ah. More...
 
void clear ()
 Deletes all the darts and all the attributes of the combinatorial map.
 
CombinatorialMapoperator= (const CombinatorialMap &cmap)
 Assignment operator. More...
 
void swap (CombinatorialMap &cmap)
 Swap the current combinatorial map with cmap. More...
 

Attributes management

bool are_attributes_automatically_managed () const
 Returns the status of the management of the attributes of the combinatorial map. More...
 
void set_automatic_attributes_management (bool update_attributes)
 Set the status of the managment of the attributes of the combinatorial map. More...
 
void correct_invalid_attributes ()
 Correct the invalid attributes of the combinatorial map. More...
 

Operations

template<unsigned int i>
bool is_sewable (Dart_const_handle dh1, Dart_const_handle dh2) const
 Returns true iff *dh1 can be i-sewn with *dh2 by keeping the combinatorial map valid. More...
 
template<unsigned int i>
void sew (Dart_handle dh1, Dart_handle dh2)
 i-sew darts *dh1 and *dh2, by keeping the combinatorial map valid. More...
 
template<unsigned int i>
void unsew (Dart_handle dh)
 i-unsew darts *dh and \( \beta_i\)(*dh), by keeping the combinatorial map valid. More...
 
template<unsigned int i>
void link_beta (Dart_handle dh1, Dart_handle dh2)
 Links *dh1 and *dh2 by \( \beta_i\). More...
 
template<unsigned int i>
void unlink_beta (Dart_handle dh)
 Unlinks *dh and \( \beta_i\)(*dh) by \( \beta_i\). More...
 
void reverse_orientation ()
 Reverse the orientation (swap \( \beta_0\) and \( \beta_1\) links) of the entire map.
 
void reverse_orientation_connected_component (Dart_handle adart)
 Reverse the orientation (swap \( \beta_0\) and \( \beta_1\) links) of the connected component containing the given dart.
 

Dynamic Onmerge/Onsplit functors

template<int i>
boost::function< void(typename
Attribute_type< i >::type
&, typename Attribute_type< i >
::type &)> & 
onsplit_function ()
 Return the current dynamic onsplit function associated with i-attributes. More...
 
template<int i>
const boost::function< void(typename
Attribute_type< i >::type
&, typename Attribute_type< i >
::type &)> & 
onsplit_function () const
 Return the current dynamic onsplit function associated with i-attributes, when *this is const. More...
 
template<int i>
boost::function< void(typename
Attribute_type< i >::type
&, typename Attribute_type< i >
::type &)> & 
onmerge_function ()
 Return the current dynamic onmerge function associated with i-attributes. More...
 
template<int i>
const boost::function< void(typename
Attribute_type< i >::type
&, typename Attribute_type< i >
::type &)> & 
onmerge_function () const
 Return the current dynamic onmerge function associated with i-attributes, when *this is const. More...
 

Boolean Marks

int get_new_mark () const
 Reserves a new mark. More...
 
bool is_reserved (int m) const
 Returns true iff m is a reserved mark of the combinatorial map. More...
 
bool is_marked (Dart_const_handle dh, int m) const
 Returns true iff *dh is marked for m. More...
 
void mark (Dart_const_handle dh, int m) const
 Marks *dh for m. More...
 
void unmark (Dart_const_handle dh, int m) const
 Unmarks *dh for the mark m. More...
 
void negate_mark (int m) const
 Inverse the mark m for all the darts of the combinatorial map. More...
 
void unmark_all (int m) const
 Unmarks all the darts of the combinatorial map for m. More...
 
size_type number_of_marked_darts (int m) const
 Returns the number of marked darts for m. More...
 
size_type number_of_unmarked_darts (int m) const
 Return the number of unmarked darts for m. More...
 
void free_mark (int m) const
 Frees mark m. More...
 

Member Typedef Documentation

Attribute_handle<i>::type is a const handle to i-attributes, equal to Dart::Attribute_const_handle<i>::type .

Precondition
0 \( \leq\)i \( \leq\)dimension and i-attributes are non void.
Note
It can be implemented using a nested template class.

Attribute_const_range<i>::type is the const range of all the i-attributes.

Attribute_const_range<i>::type is a model of ConstRange concept, its iterator type is bidirectional and its value type is Attribute_type<i>::type.

Precondition
0 \( \leq\)i \( \leq\)dimension and i-attributes are non void.
Note
It can be implemented using a nested template class.
template<unsigned int i>
using CombinatorialMap::Attribute_handle = unspecified_type

Attribute_handle<i>::type is a handle to i-attributes, equal to Dart::Attribute_handle<i>::type .

Precondition
0 \( \leq\)i \( \leq\)dimension and i-attributes are non void.
Note
It can be implemented using a nested template class.
template<unsigned int i>
using CombinatorialMap::Attribute_range = unspecified_type

Attribute_range<i>::type is the range of all the i-attributes.

Attribute_range<i>::type is a model of Range concept, its iterator type is bidirectional and its value type is Attribute_type<i>::type .

Precondition
0 \( \leq\)i \( \leq\)dimension and i-attributes are non void.
Note
It can be implemented using a nested template class.
template<unsigned int i>
using CombinatorialMap::Attribute_type = unspecified_type

Attribute_type<i>::type is the type of i-attributes, a model of CellAttribute concept.

Attribute_type<i>::type::Dart_handle is equal to Dart_handle, and Attribute_type<i>::type::Dart_const_handle is equal to Dart_const_handle.

Precondition
0 \( \leq\)i \( \leq\)dimension and i-attributes are non void.
Note
It can be implemented using a nested template class.

The tuple of cell attributes.

It contains at most dimension+1 types (one for each possible cell of the combinatorial map). Each type of the tuple must be either a model of the CellAttribute concept or void. The first type corresponds to 0-attributes, the second to 1-attributes and so on. If the i th type in the tuple is void, (i-1)-attributes are disabled. Otherwise, (i-1)-attributes are enabled and have the given type. If the size of the tuple is k, with k \( <\)dimension+1, \( \forall\)i: k \( \leq\)i \( \leq\)dimension, i-attributes are disabled.

Const range of all the darts of the combinatorial map.

This type is a model of ConstRange concept, its iterator type is bidirectional and its value type is Dart.

template<unsigned int i, unsigned int dim = dimension>
using CombinatorialMap::Dart_of_cell_const_range = unspecified_type

Const range of all the darts of the i-cell.

Cells are considered in dim dimension, with 0 \( \leq\)i \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension. If i==dim+1, range of all the darts of a connected component. This type is a model of ConstRange concept, its iterator type is forward and its value type is Dart.

template<unsigned int i, unsigned int dim = dimension>
using CombinatorialMap::Dart_of_cell_range = unspecified_type

Range of all the darts of an i-cell.

Cells are considered in dim dimension, with 0 \( \leq\)i \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension. If i==dim+1, range of all the darts of a connected component. This type is a model of Range concept, its iterator type is forward and its value type is Dart.

template<unsigned int... Beta>
using CombinatorialMap::Dart_of_orbit_const_range = unspecified_type

Const range of all the darts of the <Beta...> orbit.

This type is a model of ConstRange concept, its iterator type is forward and its value type is Dart.

template<unsigned int... Beta>
using CombinatorialMap::Dart_of_orbit_range = unspecified_type

Range of all the darts of the <Beta...> orbit.

This type is a model of Range concept, its iterator type is forward and its value type is Dart.

Range of all the darts of the combinatorial map.

This type is a model of Range concept, its iterator type is bidirectional and its value type is Dart.

template<unsigned int i, unsigned int dim = dimension>
using CombinatorialMap::One_dart_per_cell_const_range = unspecified_type

Const range of one dart of each i-cell of the combinatorial map.

Cells are considered in dim dimension, with 0 \( \leq\)i \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension. If i==dim+1, consider each connected component instead of each i-cell. This type is a model of ConstRange concept, its iterator type is forward and its value type is Dart.

template<unsigned int i, unsigned int dim = dimension>
using CombinatorialMap::One_dart_per_cell_range = unspecified_type

Range of one dart of each i-cell of the combinatorial map.

Cells are considered in dim dimension, with 0 \( \leq\)i \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension. If i==dim+1, consider each connected component instead of each i-cell. This type is a model of Range concept, its iterator type is forward and its value type is Dart.

template<unsigned int i, unsigned int j, unsigned int dim = dimension>
using CombinatorialMap::One_dart_per_incident_cell_const_range = unspecified_type

Const range of one dart of each i-cell incident to one j-cell.

Cells are considered in dim dimension, with 0 \( \leq\)i \( \leq\)dim+1, 0 \( \leq\)j \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension. If i==dim+1, consider each connected component instead of each i-cell. If j==dim+1, consider one connected component instead of one j-cell. This type is a model of ConstRange concept, its iterator type is forward and its value type is Dart.

template<unsigned int i, unsigned int j, unsigned int dim = dimension>
using CombinatorialMap::One_dart_per_incident_cell_range = unspecified_type

Range of one dart of each i-cell incident to one j-cell.

Cells are considered in dim dimension, with 0 \( \leq\)i \( \leq\)dim+1, 0 \( \leq\)j \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension. If i==dim+1, consider each connected component instead of each i-cell. If j==dim+1, consider one connected component instead of one j-cell. This type is a model of Range concept, its iterator type is forward and its value type is Dart.

Constructor & Destructor Documentation

template<typename CMap >
CombinatorialMap::CombinatorialMap ( const CMap &  cmap)

Construct a new combinatorial map from another one.

The new combinatorial map is created by copying the darts and the non void attributes of cmap. CMap must be a model of CombinatorialMap concept, which can be defined with a different dimension and/or different attributes than *this. In this case, only permutations that are common to cmap and *this, and only non void i-attributes of cmap whose info type is the same to the info of non void i-attributes of *this, are copied.

Member Function Documentation

bool CombinatorialMap::are_attributes_automatically_managed ( ) const

Returns the status of the management of the attributes of the combinatorial map.

true if the high level operations update the non void attributes (default value); false otherwise.

template<unsigned int i>
Attribute_handle<i>::type CombinatorialMap::attribute ( Dart_handle  dh)

Returns a handle to the i-attribute associated to dart *dh.

Precondition
0 \( \leq\)i \( \leq\)dimension, and i-attributes are non void.
template<unsigned int i>
Attribute_const_handle<i>::type CombinatorialMap::attribute ( Dart_const_handle  dh) const

Returns a const handle to the i-attribute associated to dart *dh, when the dart is const.

Precondition
0 \( \leq\)i \( \leq\)dimension, and i-attributes are non void.
template<unsigned int i>
Attribute_range<i>::type& CombinatorialMap::attributes ( )

Returns a range of all the i-attributes in the combinatorial map.

Precondition
0 \( \leq\)i \( \leq\)dimension, and i-attributes are non void.
template<unsigned int i>
Attribute_const_range<i>::type& CombinatorialMap::attributes ( ) const

Returns a const range of all the i-attributes in the combinatorial map.

Precondition
0 \( \leq\)i \( \leq\)dimension, and i-attributes are non void.
Dart_handle CombinatorialMap::beta ( Dart_handle  dh,
int  i,
int  j 
)

Returns \( \beta_j\)( \( \beta_i\)(*dh)).

Overloads of this member function are defined that take from one to nine integer as arguments. For each function, betas are applied in the same order as their indices are given as parameters.

For example beta(dh,1)= \( \beta_1\)(*dh), and beta(dh,1,2,3,0)= \( \beta_0\)( \( \beta_3\)( \( \beta_2\)( \( \beta_1\)(*dh)))).

Precondition
0 \( \leq\)i \( \leq\)dimension, 0 \( \leq\)j \( \leq\)dimension and *dh \( \in\)darts().
Dart_const_handle CombinatorialMap::beta ( Dart_const_handle  dh,
int  i,
int  j 
) const

Returns \( \beta_j\)( \( \beta_i\)(*dh)).

Overloads of this member function are defined that take from one to nine integer as arguments.

Precondition
0 \( \leq\)i \( \leq\)dimension, 0 \( \leq\)j \( \leq\)dimension and *dh \( \in\)darts().
template<int i, int j>
Dart_handle CombinatorialMap::beta ( Dart_handle  dh)

Returns \( \beta_j\)( \( \beta_i\)(*dh)).

Overloads of this member function are defined that take from one to nine integer as template arguments. For each function, betas are applied in the same order as their indices are given as template arguments.

For example beta<1>(dh)= \( \beta_1\)(*dh), and beta<1,2,3,0>(dh)= \( \beta_0\)( \( \beta_3\)( \( \beta_2\)( \( \beta_1\)(*dh)))).

Precondition
0 \( \leq\)i \( \leq\)dimension, 0 \( \leq\)j \( \leq\)dimension and *dh \( \in\)darts().
template<int i, int j>
Dart_const_handle CombinatorialMap::beta ( Dart_const_handle  dh) const

Returns \( \beta_j\)( \( \beta_i\)(*dh)).

Overloads of this member function are defined that take from one to nine integer as template arguments.

Precondition
0 \( \leq\)i \( \leq\)dimension, 0 \( \leq\)j \( \leq\)dimension and *dh \( \in\)darts().
void CombinatorialMap::correct_invalid_attributes ( )

Correct the invalid attributes of the combinatorial map.

We can have invalid attribute either if we have called set_automatic_attributes_management(false) before to use some modification operations or if we have modified the combinatorial map by using low level operations.

\( \forall i \), 0 \( \leq \) i \( \leq \) dimension such that the i-attributes are non void, \( \forall \) d \( \in\)darts():

  • if there exists a dart d2 in the same i-cell than d with a different i-attribute, then the i-attribute of d2 is set to the i-attribute of d;
  • if there exists a dart d2 in a different i-cell than d with the same i-attribute, then the i-attribute of all the darts in i-cell(d) is set to a new i-attribute (copy of the original attribute);
  • ensures that dart_of_attribute(d) \( \in \) i-cell(d).
template<unsigned int i, typename T1 >
Attribute_handle<i>::type CombinatorialMap::create_attribute ( T1  t1)

Creates a new i-attribute in the combinatorial map, and returns the corresponding handle.

Calls the constructor of i-attribute having T1 as parameter. Overloads of this member function are defined that take from zero to nine arguments. With zero argument, create_attribute<i>() creates a new i-attribute by using the default constructor.

Precondition
0 \( \leq\)i \( \leq\)dimension, and i-attributes are non void.
template<typename T1 >
Dart_handle CombinatorialMap::create_dart ( T1  t1)

Creates a new dart in the combinatorial map, and returns the corresponding handle.

Calls the constructor of dart having T1 as parameter. A new dart is initialized to be i-free, \( \forall\)i: 0 \( \leq\)i \( \leq\)dimension, and to have no associated attribute for each non void attribute. Overloads of this member function are defined that take from zero to nine arguments. With zero argument, create_dart() creates a new dart by using the default constructor.

template<unsigned int i>
Dart_handle& CombinatorialMap::dart ( Dart_handle  adart)

A shorcut for dart_of_attribute<i>(attribute<i>(adart)).

Precondition
attribute<i>(adart)!=NULL.
template<unsigned int i>
Dart_const_handle CombinatorialMap::dart ( Dart_const_handle  adart) const

A shorcut for dart_of_attribute<i>(attribute<i>(adart)) for const handle.

Precondition
attribute<i>(adart)!=NULL.
Dart_handle CombinatorialMap::dart_handle ( Dart d)

Returns the dart handle of d.

Precondition
d \( \in\)darts().
Dart_const_handle CombinatorialMap::dart_handle ( const Dart d) const

Returns the dart const handle of d.

Precondition
d \( \in\)darts().
template<unsigned int i>
Dart_handle CombinatorialMap::dart_of_attribute ( typename Attribute_handle< i >::type  ah)

Returns one dart of the cell associated to the i-attribute *ah.

NULL if Supports_cell_dart of i-attributes is equal to Tag_false.

Precondition
0 \( \leq\)i \( \leq\)dimension, i-attributes are non void and ah!=NULL.
template<unsigned int i>
Dart_const_handle CombinatorialMap::dart_of_attribute ( typename Attribute_const_handle< i >::type  ah) const

Returns one dart of the cell associated to the const i-attribute *ah.

NULL if Supports_cell_dart of i-attributes is equal to Tag_false.

Precondition
0 \( \leq\)i \( \leq\)dimension, i-attributes are non void and ah!=NULL.
template<unsigned int i, unsigned int dim = dimension>
Dart_of_cell_range CombinatorialMap::darts_of_cell ( Dart_handle  dh)

Returns a range of all the darts of the i-cell containing *dh.

The first element in the range points onto *dh. i-cells are considered in dim dimension. If i==dim+1, range of all the darts of the connected component containing dh.

Precondition
*dh \( \in\)darts(), 0 \( \leq\)i \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension.
template<unsigned int i, unsigned int dim = dimension>
Dart_of_cell_const_range CombinatorialMap::darts_of_cell ( Dart_const_handle  dh) const

Returns a const range of all the darts of the i-cell containing *dh.

The first element in the range points onto *dh. i-cells are considered in dim dimension. If i==dim+1, const range of all the darts of the connected component containing *dh.

Precondition
Same as for the non const version.
template<unsigned int... Beta>
Dart_of_orbit_range CombinatorialMap::darts_of_orbit ( Dart_handle  dh)

Returns a range of all the darts of the orbit <Beta...>(*dh).

The first element in the range points onto *dh.

Precondition
*dh \( \in\)darts() and Beta... is a sequence of integers \( i_1\), \( \ldots\), \( i_k\), such that 0 \( \leq\) \( i_1\) \( <\) \( i_2\) \( <\) \( \ldots\) \( <\) \( i_k\) \( \leq\)dimension, and ( \( i_1\) \( \neq\) 0 or \( i_2\) \( \neq\) 1).
template<unsigned int... Beta>
Dart_of_orbit_const_range CombinatorialMap::darts_of_orbit ( Dart_const_handle  dh) const

Returns a const range of all the darts of the orbit <Beta...>(*dh).

The first element in the range points onto *dh.

Precondition
Same as for the non const version.
std::ostream& CombinatorialMap::display_characteristics ( std::ostream &  os) const

Displays on os the number of elements of the combinatorial map.

Its number of darts, its number of i-cells, for each i, 0 \( \leq\)i \( \leq\)dimension, and its number of connected components.

Example of output for a 3D combinatorial map containing two disjoint combinatorial tetrahedra:

#Darts=24, #0-cells=8, #1-cells=12, #2-cells=8, #3-cells=2, #ccs=2

template<unsigned int i>
void CombinatorialMap::erase_attribute ( Attribute_handle< i >::type  ah)

Removes the i-attribute *ah from the combinatorial map.

Precondition
0 \( \leq\)i \( \leq\)dimension, i-attributes are non void, and *ah \( \in\)attributes<i>().
void CombinatorialMap::erase_dart ( Dart_handle  dh)

Removes *dh from the combinatorial map.

Precondition
*dh \( \in\)darts().
void CombinatorialMap::free_mark ( int  m) const

Frees mark m.

Precondition
is_reserved(m).
int CombinatorialMap::get_new_mark ( ) const

Reserves a new mark.

Returns its index. Returns -1 if there is no more available free mark.

int CombinatorialMap::highest_nonfree_dimension ( Dart_const_handle  dh) const

Returns the highest dimension i such that dart *dh is not i-free.

-1 if dh is free for any dimension.

template<unsigned int i>
Attribute_type<i>::type::Info& CombinatorialMap::info ( Dart_handle  adart)

A shorcut for info_of_attribute<i>(attribute<i>(adart)).

Precondition
attribute<i>(adart)!=NULL.
template<unsigned int i>
const Attribute_type<i>::type::Info& CombinatorialMap::info ( Dart_const_handle  adart) const

A shorcut for info_of_attribute<i>(attribute<i>(adart)) for const handle.

Precondition
attribute<i>(adart)!=NULL.
template<unsigned int i>
Attribute_type<i>::type::Info& CombinatorialMap::info_of_attribute ( typename Attribute_handle< i >::type  ah)

Returns the information of the i-attribute *ah.

Defined only if Info of i-attributes is not void.

Precondition
0 \( \leq\)i \( \leq\)dimension, i-attributes are non void and ah!=NULL.
template<unsigned int i>
const Attribute_type<i>::type::Info& CombinatorialMap::info_of_attribute ( typename Attribute_const_handle< i >::type  ah) const

Returns the information of the const i-attribute *ah.

Defined only if Info of i-attributes is not void.

Precondition
0 \( \leq\)i \( \leq\)dimension, i-attributes are non void and ah!=NULL.
bool CombinatorialMap::is_free ( Dart_const_handle  dh,
unsigned int  i 
) const

Returns true iff dart *dh is i-free.

Precondition
0 \( \leq\)i \( \leq\)dimension.
template<unsigned int i>
bool CombinatorialMap::is_free ( Dart_const_handle  dh) const

Returns true iff dart *dh is i-free.

Precondition
0 \( \leq\)i \( \leq\)dimension.
bool CombinatorialMap::is_marked ( Dart_const_handle  dh,
int  m 
) const

Returns true iff *dh is marked for m.

Precondition
is_reserved(m) and *dh \( \in\)darts().
bool CombinatorialMap::is_reserved ( int  m) const

Returns true iff m is a reserved mark of the combinatorial map.

Precondition
0 \( \leq\)m \( <\)NB_MARKS.
template<unsigned int i>
bool CombinatorialMap::is_sewable ( Dart_const_handle  dh1,
Dart_const_handle  dh2 
) const

Returns true iff *dh1 can be i-sewn with *dh2 by keeping the combinatorial map valid.

This is true if there is a bijection f between all the darts of the orbit D1= \( \langle{}\) \( \beta_1\), \( \ldots\), \( \beta_{i-2}\), \( \beta_{i+2}\), \( \ldots\), \( \beta_d\) \( \rangle{}\)(*dh1) and D2= \( \langle{}\) \( \beta_1\), \( \ldots\), \( \beta_{i-2}\), \( \beta_{i+2}\), \( \ldots\), \( \beta_d\) \( \rangle{}\)(*dh2) satisfying: f(*dh1)=*dh2, and for all e \( \in\)D1, for all j \( \in\){1, \( \ldots\),i-2,i+2, \( \ldots\),d}, f( \( \beta_j\)(e))= \( \beta_j^{-1}\)(f(e)).

Precondition
0 \( \leq\)i \( \leq\)dimension, *dh1 \( \in\)darts(), and *dh2 \( \in\)darts().
bool CombinatorialMap::is_valid ( ) const

Returns true iff the combinatorial map is valid.

A combinatorial map is valid (see Sections Combinatorial Map and Darts and Combinatorial Map Properties) if for all its darts d \(\in\)darts():

  • d is 0-free, or \( \beta_1(\beta_0(d))=d\);
  • d is 1-free, or \( \beta_0(\beta_1(d))=d\);
  • \( \forall\)i, 2 \( \leq\)i \( \leq\)dimension: d is i-free, or \( \beta_i(\beta_i(d))=d\);
  • \( \forall\)i, j, 0 \( \leq\)i \( <\)i+2 \( \leq\)j \( \leq\)dimension such that j \( \geq\) 3: \( \beta_j(\beta_i(d))=\varnothing\) or ; \( \beta_j(\beta_i(\beta_j(\beta_i(d))))=d\);
  • \( \forall\)i, 0 \( \leq\)i \( \leq\)dimension such that i-attributes are non void:
    • \( \forall\)d2 in the same i-cell than d: d and d2 have the same i-attribute;
    • \( \forall\)d2 in a different i-cell than d: d and d2 have different i-attributes.
bool CombinatorialMap::is_without_boundary ( unsigned int  i) const

Returns true iff the combinatorial map is without i-boundary.

The map is without i-boundary if there is no i-free dart.

Precondition
1 \( \leq\)i \( \leq\)dimension.
template<unsigned int i>
void CombinatorialMap::link_beta ( Dart_handle  dh1,
Dart_handle  dh2 
)

Links *dh1 and *dh2 by \( \beta_i\).

The combinatorial map can be no more valid after this operation. If are_attributes_automatically_managed()==true, non void attributes of *dh1 and *dh2 are updated: if one dart has an attribute and the second dart not, the non null attribute is associated to the dart having a null attribute. If both darts have an attribute, the attribute of *dh1 is associated to *dh2.

Precondition
0 \( \leq\)i \( \leq\)dimension, *dh1 \( \in\)darts(), *dh2 \( \in\)darts() and (i \( <\) 2 or dh1 \( \neq\)dh2).
void CombinatorialMap::mark ( Dart_const_handle  dh,
int  m 
) const

Marks *dh for m.

Precondition
is_reserved(m) and *dh \( \in\)darts().
void CombinatorialMap::negate_mark ( int  m) const

Inverse the mark m for all the darts of the combinatorial map.

All the marked darts become unmarked and all the unmarked darts become marked.

Precondition
is_reserved(m).
template<unsigned int i>
size_type CombinatorialMap::number_of_attributes ( ) const

Returns the number of i-attributes in the combinatorial map.

Precondition
0 \( \leq\)i \( \leq\)dimension, and i-attributes are non void.
size_type CombinatorialMap::number_of_marked_darts ( int  m) const

Returns the number of marked darts for m.

Precondition
is_reserved(m).
size_type CombinatorialMap::number_of_unmarked_darts ( int  m) const

Return the number of unmarked darts for m.

Precondition
is_reserved(m).
template<unsigned int i, unsigned int dim = dimension>
One_dart_per_cell_range CombinatorialMap::one_dart_per_cell ( )

Returns a range of one dart of each i-cell in the combinatorial map.

Cells are considered in dim dimension. If i==dim+1, range of one dart of each connected component in the combinatorial map.

Precondition
0 \( \leq\)i \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension.
template<unsigned int i, unsigned int dim = dimension>
One_dart_per_cell_const_range CombinatorialMap::one_dart_per_cell ( ) const

Returns a const range of one dart of each i-cell in the combinatorial map.

Cells are considered in dim dimension. If i==dim+1, const range of one dart of each connected component in the combinatorial map.

Precondition
Same as for the non const version.
template<unsigned int i, unsigned int j, unsigned int dim = dimension>
One_dart_per_incident_cell_range CombinatorialMap::one_dart_per_incident_cell ( Dart_handle  dh)

Returns a range of one dart of each i-cell incident to the j-cell containing *dh.

The first element in the range points onto *dh. Cells are considered in dim dimension. If i==dim+1, consider each connected component instead of each i-cell. If j==dim+1, consider the connected component containing *dh instead of the j-cell.

Precondition
*dh \( \in\)darts(), 0 \( \leq\)i \( \leq\)dim+1, 0 \( \leq\)j \( \leq\)dim+1 and 0 \( \leq\)dim \( \leq\)dimension.
template<unsigned int i, unsigned int j, unsigned int dim = dimension>
One_dart_per_incident_cell_const_range CombinatorialMap::one_dart_per_incident_cell ( Dart_const_handle  dh) const

Returns a const range of one dart of each i-cell incident to the j-cell containing *dh.

The first element in the range points onto *dh. Cells are considered in dim dimension. If i==dim+1, consider each connected component instead of each i-cell. If j==dim+1, consider the connected component containing *dh instead of the j-cell.

Precondition
Same as for the non const version.
template<int i>
boost::function<void(typename Attribute_type< i >::type&, typename Attribute_type< i >::type&)>& CombinatorialMap::onmerge_function ( )

Return the current dynamic onmerge function associated with i-attributes.

This is a boost:function returning void and having two references to Attribute_type<i>::type as parameters. The onmerge function is returned by reference so that we can modify it.

template<int i>
const boost::function<void(typename Attribute_type< i >::type&, typename Attribute_type< i >::type&)>& CombinatorialMap::onmerge_function ( ) const

Return the current dynamic onmerge function associated with i-attributes, when *this is const.

This is a boost:function returning void and having two references to Attribute_type<i>::type as parameters.

template<int i>
boost::function<void(typename Attribute_type< i >::type&, typename Attribute_type< i >::type&)>& CombinatorialMap::onsplit_function ( )

Return the current dynamic onsplit function associated with i-attributes.

This is a boost:function returning void and having two references to Attribute_type<i>::type as parameters. The onsplit function is returned by reference so that we can modify it.

template<int i>
const boost::function<void(typename Attribute_type< i >::type&, typename Attribute_type< i >::type&)>& CombinatorialMap::onsplit_function ( ) const

Return the current dynamic onsplit function associated with i-attributes, when *this is const.

This is a boost:function returning void and having two references to Attribute_type<i>::type as parameters.

CombinatorialMap& CombinatorialMap::operator= ( const CombinatorialMap cmap)

Assignment operator.

All darts and attributes are duplicated, and the former combinatorial map is deleted.

Dart_handle CombinatorialMap::opposite ( Dart_handle  dh)

Returns a handle to a dart belonging to the same edge than dart *dh, and not to the same vertex.

NULL if such a dart does not exist.

Dart_const_handle CombinatorialMap::opposite ( Dart_const_handle  dh) const

Returns a const handle to a dart belonging to the same edge than dart *dh, and not to the same vertex, when the dart is const.

NULL if such a dart does not exist.

Dart_handle CombinatorialMap::other_extremity ( Dart_handle  dh)

Returns a handle to a dart belonging to the other vertex of the edge containing dart *dh (but contrary to opposite() not necessarily to the same edge).

NULL if such a dart does not exist.

Dart_const_handle CombinatorialMap::other_extremity ( Dart_const_handle  dh) const

Returns a const handle to a dart belonging to the other vertex of the edge containing dart *dh, when the dart is const (but contrary to opposite() not necessarily to the same edge).

NULL if such a dart does not exist.

template<unsigned int i>
void CombinatorialMap::set_attribute ( Dart_handle  dh,
Attribute_handle< i >::type  ah 
)

Associates the i-attribute of all the darts of the i-cell containing *dh to *ah.

Precondition
*dh \( \in\)darts(), 0 \( \leq\)i \( \leq\)dimension, i-attributes are non void, and *ah \( \in\)attributes<i>().
void CombinatorialMap::set_automatic_attributes_management ( bool  update_attributes)

Set the status of the managment of the attributes of the combinatorial map.

Advanced

After calling set_automatic_attributes_management(false), all high level operations will not update non void attributes, until the call of set_automatic_attributes_management(true). The call of set_automatic_attributes_management(true) call the correct_invalid_attributes() function.

template<unsigned int i>
void CombinatorialMap::sew ( Dart_handle  dh1,
Dart_handle  dh2 
)

i-sew darts *dh1 and *dh2, by keeping the combinatorial map valid.

Links by \( \beta_i\) two by two all the darts of the orbit D1= \( \langle{}\) \( \beta_1\), \( \ldots\), \( \beta_{i-2}\), \( \beta_{i+2}\), \( \ldots\), \( \beta_d\) \( \rangle{}\)(*dh1) and D2= \( \langle{}\) \( \beta_0\), \( \beta_2\), \( \ldots\), \( \beta_{i-2}\), \( \beta_{i+2}\), \( \ldots\), \( \beta_d\) \( \rangle{}\)(*dh2) such that d2=f(d1).

f is the bijection between D1 and D2 satisfying: f(*dh1)=*dh2, and for all e \( \in\)D1, for all j \( \in\){1, \( \ldots\),i-2,i+2, \( \ldots\),d}, f( \( \beta_j\)(e))= \( \beta_j^{-1}\)(f(e)).

If are_attributes_automatically_managed()==true, when necessary, non void attributes are updated to ensure the validity of the combinatorial map: for each j-cells c1 and c2 which are merged into one j-cell during the sew, the two associated attributes attr1 and attr2 are considered. If one attribute is NULL and the other not, the non NULL attribute is associated to all the darts of the resulting cell. When the two attributes are non NULL, functor Attribute_type<i>::type::On_merge is called on the two attributes attr1 and attr2. If set, the dynamic onmerge function of i-attributes is also called on attr1 and attr2. Then, the attribute attr1 is associated to all darts of the resulting j-cell. Finally, attribute attr2 is removed from the combinatorial map.

Precondition
is_sewable<i>(dh1,dh2).
Advanced

If are_attributes_automatically_managed()==false, non void attributes are not updated; thus the combinatorial map can be no more valid after this operation.

void CombinatorialMap::swap ( CombinatorialMap cmap)

Swap the current combinatorial map with cmap.

There is no copy of darts and attributes thus this method runs in constant time.

template<unsigned int i>
void CombinatorialMap::unlink_beta ( Dart_handle  dh)

Unlinks *dh and \( \beta_i\)(*dh) by \( \beta_i\).

The combinatorial map can be no more valid after this operation. Attributes of *dh and \( \beta_i\)(*dh) are not modified.

Precondition
0 \( \leq\)i \( \leq\)dimension, *dh \( \in\)darts(), and *dh is not i-free.
void CombinatorialMap::unmark ( Dart_const_handle  dh,
int  m 
) const

Unmarks *dh for the mark m.

Precondition
is_reserved(m) and *dh \( \in\)darts().
void CombinatorialMap::unmark_all ( int  m) const

Unmarks all the darts of the combinatorial map for m.

Precondition
is_reserved(m).
template<unsigned int i>
void CombinatorialMap::unsew ( Dart_handle  dh)

i-unsew darts *dh and \( \beta_i\)(*dh), by keeping the combinatorial map valid.

Unlinks by \( \beta_i\) all the darts in the orbit \( \langle{}\) \( \beta_1\), \( \ldots\), \( \beta_{i-2}\), \( \beta_{i+2}\), \( \ldots\), \( \beta_d\) \( \rangle{}\)(*dh). If are_attributes_automatically_managed()==true, when necessary, non void attributes are updated to ensure the validity of the combinatorial map: for each j-cell c split in two j-cells c1 and c2 by the operation, if c is associated to a j-attribute attr1, then this attribute is duplicated into attr2, and all the darts belonging to c2 are associated with this new attribute. Finally, the functor Attribute_type<i>::type::On_split is called on the two attributes attr1 and attr2. If set, the dynamic onsplit function of i-attributes is also called on attr1 and attr2.

Precondition
0 \( \leq\)i \( \leq\)dimension, *dh \( \in\)darts() and *dh is not i-free.
Advanced

If are_attributes_automatically_managed()==false, non void attributes are not updated thus the combinatorial map can be no more valid after this operation.

Member Data Documentation

Dart_handle CombinatorialMap::null_dart_handle

The null dart handle constant.

A dart d is i-free if beta(d, i)==null_dart_handle. Note that *null_dart_handle \( \notin\)darts().

Deprecated:
null dart handle is no longer static since CGAL 4.4. You can define the CGAL_CMAP_DEPRECATED macro to keep the old behavior.