CombinatorialMap

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

CombinatorialMap

Definition

The concept CombinatorialMap defines a d-dimensional combinatorial map.

Creation

CombinatorialMap cm;
	Default constructor.

Types

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

Constants

static unsigned int	dimension;	The dimension d of cm, equal to Dart::dimension.
static size_type	NB_MARKS;	The number of available Boolean marks of cm.
static Dart_handle	null_dart_handle;	The null dart handle constant: a dart d0 is i-free if d0.beta(i)==null_dart_handle. Note that null_dart_handle∉cm.darts()*.

Types for attributes

CombinatorialMap::Attributes

The tuple of attributes, containing 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, ∀i: k≤i≤dimension, i-attributes are disabled.

template<unsigned int i>

CombinatorialMap:: Attribute_type::type

Type of i-attributes, a model of CellAttribute concept. Attribute_type::type::Dart_handle is equal to Dart_handle, and Attribute_type::type::Dart_const_handle is equal to Dart_const_handle.

Precondition:

0≤i≤dimension and i-attributes are non void.

template<unsigned int i>

CombinatorialMap:: Attribute_handle::type

Handle to i-attributes, equal to Dart::Attribute_handle::type.

Precondition:

0≤i≤dimension and i-attributes are non void.

template<unsigned int i>

CombinatorialMap:: Attribute_const_handle::type

Const handle to i-attributes, equal to Dart::Attribute_const_handle::type.

Precondition:

0≤i≤dimension and i-attributes are non void.

Range types

CombinatorialMap::Dart_range
	Range of all the darts of cm. This type is a model of Range concept, its iterator type is bidirectional and its value type is Dart.
CombinatorialMap::Dart_const_range
	Const range of all the darts of cm. This type is a model of ConstRange concept, its iterator type is bidirectional and its value type is Dart.

template<unsigned int i>
CombinatorialMap:: Attribute_range<i>::type
	Range of all the i-attributes (which must be non void), with 0≤i≤dimension. This type is a model of Range concept, its iterator type is bidirectional and its value type is Attribute_type<i>::type.
template<unsigned int i>
CombinatorialMap:: Attribute_const_range<i>::type
	Const range of all the i-attributes (which must be non void), with 0≤i≤dimension. This type is a model of ConstRange concept, its iterator type is bidirectional and its value type is Attribute_type<i>::type.

template<unsigned int ... Beta>
CombinatorialMap:: Dart_of_orbit_range
	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.
template<unsigned int ... Beta>
CombinatorialMap:: Dart_of_orbit_const_range
	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 i,unsigned int dim=dimension>
CombinatorialMap:: Dart_of_cell_range
	Range of all the darts of an i-cell in dim dimension (with 0≤i≤dim+1 and 0≤dim≤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 i,unsigned int dim=dimension>
CombinatorialMap:: Dart_of_cell_const_range
	Const range of all the darts of the i-cell in dim dimension (with 0≤i≤dim+1 and 0≤dim≤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 j,unsigned int dim=dimension>
CombinatorialMap:: One_dart_per_incident_cell_range
	Range of one dart of each i-cell incident to one j-cell. Cells are considered in dim dimension (with 0≤i≤dim+1, 0≤j≤dim+1 and 0≤dim≤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.
template<unsigned int i,unsigned int j,unsigned int dim=dimension>
CombinatorialMap:: One_dart_per_incident_cell_const_range
	Const range of one dart of each i-cell incident to one j-cell. Cells are considered in dim dimension (with 0≤i≤dim+1, 0≤j≤dim+1 and 0≤dim≤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 dim=dimension>
CombinatorialMap:: One_dart_per_cell_range
	Range of one dart of each i-cell of cm. Cells are considered in dim dimension (with 0≤i≤dim+1 and 0≤dim≤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 dim=dimension>
CombinatorialMap:: One_dart_per_cell_const_range
	Const range of one dart of each i-cell of cm. Cells are considered in dim dimension (with 0≤i≤dim+1 and 0≤dim≤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.

Access Member Functions

bool	cm.is_empty () const	Returns true iff cm is empty, i.e. it contains no dart.

bool	cm.is_valid () const	Returns true iff cm is valid.

A combinatorial map cm is valid (see Sections 27.2.1 and 27.2.4) if for all dart handle dh such that *dh∈cm.darts():

dh->is_free(0), or dh->beta(0)->beta(1)==dh;
dh->is_free(1), or dh->beta(1)->beta(0)==dh;
∀i, 2≤i≤dimension: dh->is_free(i), or dh->beta(i)->beta(i)==dh;
∀i,j, 0≤i<i+2≤j≤dimension such that j≥3: dh->beta(i)->beta(j)==null_dart_handle or dh->beta(i)->beta(j)->beta(i)->beta(j)==dh;
∀i, 0≤i≤dimension such that i-attributes are non void: ∀dh2 such that *dh2 belong to the same i-cell than *dh: dh2->attribute()==dh->attribute().

bool

cm.is_without_boundary ( unsigned int i) const

Returns true iff cm is wihout i-boundary (i.e. there is no i-free dart).

Precondition:

1≤i≤dimension.

bool

cm.is_without_boundary () const

Returns true iff cm is without boundary in all dimensions.

size_type

cm.number_of_darts () const

Returns the number of darts in cm.

Dart_handle

cm.dart_handle ( Dart& adart)

Returns the dart handle of adart.

Dart_const_handle

cm.dart_handle ( Dart adart) const

Returns the dart const handle of adart.

template <unsigned int i>

size_type

cm.number_of_attributes () const

Returns the number of i-attributes in cm.

Precondition:

0≤i≤dimension, and i-attributes are non void.

template <unsigned int i>

bool

cm.is_sewable ( Dart_const_handle dh1, Dart_const_handle dh2) const

Returns true iff dh1 can be i-sewn with dh2 by keeping cm valid, i.e. if there is a bijection f between all the darts of the orbit D1=⟨β₁,…,β_i-2,β_i+2,…,β_d⟩(dh1) and D2=⟨β₁,…,β_i-2,β_i+2,…,β_d⟩(dh2) satisfying: f(dh1)=dh2, and for all e∈D1, for all j∈{1,…,i-2,i+2,…,d}, f(β_j(e))=β_j^-1(f(e)).

Precondition:

0≤i≤dimension, *dh1∈cm.darts(), and *dh2∈cm.darts().

std::ostream&

cm.display_characteristics ( std::ostream & os) const

Displays on os the characteristics of cm: its number of darts, its number of i-cells, for each i, 0≤i≤CMap::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

Range Access Member Functions

Dart_range&

cm.darts ()

Returns a range of all the darts in cm.

Dart_const_range&

cm.darts () const

Returns a const range of all the darts in cm.

template<unsigned int i>

Attribute_range::type &

cm.attributes ()

Returns a range of all the i-attributes in cm.

Precondition:

0≤i≤dimension, and i-attributes are non void.

template<unsigned int i>

Attribute_const_range::type &

cm.attributes () const

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

Precondition:

0≤i≤dimension, and i-attributes are non void.

template<unsigned int ... Beta>

Dart_of_orbit_range

cm.darts_of_orbit ( Dart_handle dh)

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

Precondition:

*dh∈cm.darts() and Beta... is a sequence of integers i₁,…,i_k, such that 0≤i₁<i₂<…<i_k≤dimension, and (i₁≠0 or i₂≠1).

template<unsigned int ... Beta>

Dart_of_orbit_const_range

cm.darts_of_orbit ( Dart_const_handle dh) const

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

Precondition:

Same as for the non const version.

template<unsigned int i,unsigned int dim=dimension>

Dart_of_cell_range

cm.darts_of_cell ( Dart_handle dh)

Returns a range of all the darts of the i-cell containing 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∈cm.darts(), 0≤i≤dim+1 and 0≤dim≤dimension.

template<unsigned int i,unsigned int dim=dimension>

Dart_of_cell_const_range

cm.darts_of_cell ( Dart_const_handle dh) const

Returns a const range of all the darts of the i-cell containing 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 i,unsigned int j,unsigned int dim=dimension>

One_dart_per_incident_cell_range

cm.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. 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∈cm.darts(), 0≤i≤dim+1, 0≤j≤dim+1 and 0≤dim≤dimension.

template<unsigned int i,unsigned int j,unsigned int dim=dimension>

One_dart_per_incident_cell_const_range

cm.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. 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<unsigned int i,unsigned int dim=dimension>

One_dart_per_cell_range

cm.one_dart_per_cell ()

Returns a range of one dart of each i-cell in cm. Cells are considered in dim dimension. If i==dim+1, range of one dart of each connected component in cm.

Precondition:

0≤i≤dim+1 and 0≤dim≤dimension.

template<unsigned int i,unsigned int dim=dimension>

One_dart_per_cell_const_range

cm.one_dart_per_cell () const

Returns a const range of one dart of each i-cell in cm. Cells are considered in dim dimension. If i==dim+1, const range of one dart of each connected component in cm.

Precondition:

Same as for the non const version.

Modifiers

Dart_handle

cm.create_dart ()

Creates a new dart in cm, and returns the corresponding handle. A new dart is initialized to be i-free, ∀i: 0≤i≤dimension, and to have no associated attribute for each non void attribute.

void

cm.erase_dart ( Dart_handle dh)

Removes *dh from cm.

template<unsigned int i>

Attribute_handle::type

cm.create_attribute ()

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

Precondition:

0≤i≤dimension, and i-attributes are non void.

template<unsigned int i,class A>

Attribute_handle::type

cm.create_attribute ( A a)

Creates a new i-attribute in cm initialized by the constructor A(a), and returns the corresponding handle. A must be a type compatible with the information contained in the i-attributes (compatible means that there is a constructor for the information type taking an A as parameter).

Precondition:

0≤i≤dimension, and i-attributes are non void.

template <unsigned int i>

void

cm.erase_attribute ( Attribute_handle::type ah)

Removes the i-attribute *ah from cm.

Precondition:

0≤i≤dimension, i-attributes are non void, and *ah∈cm.attributes().

template <unsigned int i>

void

cm.set_attribute ( Dart_handle dh, Attribute_handle::type ah)

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

Precondition:

*dh∈cm.darts(), 0≤i≤dimension, i-attributes are non void, and *ah∈cm.attributes().

void

cm.clear ()

Deletes all the darts and all the attributes of cm.

Operations

template <unsigned int i>

void

cm.sew ( Dart_handle dh1, Dart_handle dh2, bool update_attributes=true)

Links by β_i two by two all the darts of the orbit D1=⟨β₁,…,β_i-2,β_i+2,…,β_d⟩(dh1) and D2=⟨β₀,β₂,…,β_i-2,β_i+2,…,β_d⟩ (dh2) such that d2=f(d1), f being the bijection between D1 and D2 satisfying: f(dh1)=dh2, and for all e∈D1, for all j∈{1,…,i-2,i+2,…,d}, f(β_j(e))=β_j^-1(f(e)).

If update_attributes is true, when necessary, non void attributes are updated to ensure the validity of cm: 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::type::On_merge is called on the two attributes attr1 and attr2. Then, the attribute attr1 is associated to all darts of the resulting j-cell. Finally, attribute attr2 is removed from cm.

Precondition:

cm.is_sewable(dh1,dh2).

If update_attributes is false, non void attributes are not updated; thus cm can be no more valid after this modification.

template <unsigned int i>

void

cm.unsew ( Dart_handle dh, bool update_attributes=true)

Unlinks by β_i all the darts in the orbit ⟨β₁,…,β_i-2,β_i+2,…,β_d⟩(dh). If update_attributes is true, when necessary, non void attributes are updated to ensure the validity of cm: 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::type::On_split is called on the two attributes attr1 and attr2.

Precondition:

0≤i≤dimension, *dh∈cm.darts() and dh is not i-free.

If update_attributes is false, non void attributes are not updated thus cm can be no more valid after this modification.

template <unsigned int i>

void

cm.link_beta ( Dart_handle dh1, Dart_handle dh2, bool update_attributes=true)

Links dh1 and dh2 by β_i. cm can be no more valid after this modification. If update_attributes is 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≤i≤dimension, *dh1∈cm.darts(), *dh2∈cm.darts() and (i<2 or dh1≠dh2).

template <unsigned int i>

void

cm.unlink_beta ( Dart_handle dh)

Unlinks dh and β_i(dh) by β_i. cm can be no more valid after this modification. Attributes of dh and β_i(dh) are not modified.

Precondition:

0≤i≤dimension, *dh∈cm.darts(), and dh is not i-free.

Boolean marks

int

cm.get_new_mark () const

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

bool

cm.is_reserved ( int amark) const

Returns true iff amark is a reserved mark of cm.

Precondition:

0≤amark<NB_MARKS.

bool

cm.is_marked ( Dart_const_handle dh, int amark) const

Returns true iff dh is marked for amark.

Precondition:

is_reserved(amark) and *dh∈cm.darts().

void

cm.mark ( Dart_const_handle dh, int amark) const

Marks dh for amark.

Precondition:

is_reserved(amark) and *dh∈cm.darts().

void

cm.unmark ( Dart_const_handle dh, int amark) const

Unmarks dh for the mark amark.

Precondition:

is_reserved(amark) and *dh∈cm.darts().

void

cm.negate_mark ( int amark) const

Inverse the mark amark for all the darts of cm. All the marked darts become unmarked and all the unmarked darts become marked.

Precondition:

is_reserved(amark).

void

cm.unmark_all ( int amark) const

Unmarks all the darts of cm for amark.

Precondition:

is_reserved(amark).

size_type

cm.number_of_marked_darts ( int amark) const

Returns the number of marked darts for amark.

Precondition:

is_reserved(amark).

size_type

cm.number_of_unmarked_darts ( int amark) const

Return the number of unmarked darts for amark.

Precondition:

is_reserved(amark).

void

cm.free_mark ( int amark) const

Frees amark.

Precondition:

is_reserved(amark).

Has Models

CGAL::Combinatorial_map<d,CMItems,Alloc>

Next: Dart

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

CGAL Open Source Project. Release 4.0.1. 2 July 2012.