CGAL 6.2 - Combinatorial Maps

Loading...
Searching...
No Matches
List of all members | Public Attributes
CombinatorialMap Concept Reference
Reference Manual » Concepts

## Definition

The concept `CombinatorialMap` defines a d-dimensional combinatorial map.

Refines
  `GenericMap`

Has models
  `CGAL::Combinatorial_map<d,Items,Alloc>`

For a combinatorial map, the function `next` is equal to \( \beta_1\), `previous` is equal to \( \beta_0\) and the function `opposite<i>` is equal to \( \beta_i\).

## Public Attributes
Dart_descriptor | null_dart_descriptor
| The null dart descriptor constant.

## Access Member Functions
Dart_descriptor | beta (Dart_descriptor d, int i, int j)
| Returns \( \beta_j\)( \( \beta_i\)(`d`)).
Dart_const_descriptor | beta (Dart_const_descriptor d, int i, int j) const
| Returns \( \beta_j\)( \( \beta_i\)(`d`)).
template<int i, int j>
Dart_descriptor | beta (Dart_descriptor d)
| Returns \( \beta_j\)( \( \beta_i\)(`d`)).
template<int i, int j>
Dart_const_descriptor | beta (Dart_const_descriptor d) const
| Returns \( \beta_j\)( \( \beta_i\)(`d`)).
Dart_descriptor | opposite (Dart_descriptor d)
| Returns a descriptor to a dart belonging to the same edge than dart `d`, and not to the same vertex.
Dart_const_descriptor | opposite (Dart_const_descriptor d) const
| Returns a const descriptor to a dart belonging to the same edge than dart `d`, and not to the same vertex, when the dart is const.
bool | is_valid () const
| Returns true iff the combinatorial map is valid.

## Modifiers
template<unsigned int i>
void | link_beta (Dart_descriptor d1, Dart_descriptor d2)
| Links `d1` and `d2` by \( \beta_i\).
template<unsigned int i>
void | unlink_beta (Dart_descriptor d)
| Unlinks `d` and \( \beta_i\)(`d`) by \( \beta_i\).

## Operations
template<unsigned int i>
bool | is_sewable (Dart_const_descriptor d1, Dart_const_descriptor d2) const
| Returns true iff `d1` can be i-sewn with `d2` by keeping the generic map valid.
template<unsigned int i>
void | sew (Dart_descriptor d1, Dart_descriptor d2)
| i-sew darts `d1` and `d2`, by keeping the generic map valid.
template<unsigned int i>
void | unsew (Dart_descriptor d)
| i-unsew darts `d` and `opposite<i>(d)`, by keeping the generic map valid.
void | reverse_orientation ()
| Reverse the orientation (swap \( \beta_0\) and \( \beta_1\) links) of the entire map.
void | reverse_orientation_connected_component (Dart_descriptor d)
| Reverse the orientation (swap \( \beta_0\) and \( \beta_1\) links) of the connected component containing the given dart.

## Member Function Documentation

## ◆ beta() [1/4]

template<int i, int j>

Dart_const_descriptor CombinatorialMap::beta | ( | Dart_const_descriptor | d | ) | const

Returns \( \beta_j\)( \( \beta_i\)(`d`)).

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 `d` \( \in\) `darts()`.

## ◆ beta() [2/4]

Dart_const_descriptor CombinatorialMap::beta | ( | Dart_const_descriptor | d,
|  | int | i,
|  | int | j
| ) |  | const

Returns \( \beta_j\)( \( \beta_i\)(`d`)).

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 `d` \( \in\) `darts()`.

## ◆ beta() [3/4]

template<int i, int j>

Dart_descriptor CombinatorialMap::beta | ( | Dart_descriptor | d | ) |

Returns \( \beta_j\)( \( \beta_i\)(`d`)).

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>(d)`= \( \beta_1\)(`d`), and `beta<1,2,3,0>(d)`= \( \beta_0\)( \( \beta_3\)( \( \beta_2\)( \( \beta_1\)(`d`)))).

Precondition
  0 \( \leq\) i \( \leq\) `dimension`, 0 \( \leq\) j \( \leq\) `dimension` and `d` \( \in\) `darts()`.

## ◆ beta() [4/4]

Dart_descriptor CombinatorialMap::beta | ( | Dart_descriptor | d,
|  | int | i,
|  | int | j
| ) |  |

Returns \( \beta_j\)( \( \beta_i\)(`d`)).

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(d,1)`= \( \beta_1\)(`d`), and `beta(d,1,2,3,0)`= \( \beta_0\)( \( \beta_3\)( \( \beta_2\)( \( \beta_1\)(`d`)))).

Precondition
  0 \( \leq\) i \( \leq\) `dimension`, 0 \( \leq\) j \( \leq\) `dimension` and `d` \( \in\) `darts()`.

## ◆ is_sewable()

template<unsigned int i>

bool CombinatorialMap::is_sewable | ( | Dart_const_descriptor | d1,
|  | Dart_const_descriptor | d2
| ) |  | const

Returns true iff `d1` can be i-sewn with `d2` by keeping the generic 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{}\)(d1) and D2= \( \langle{}\) \( \beta_1\), \( \ldots\), \( \beta_{i-2}\), \( \beta_{i+2}\), \( \ldots\), \( \beta_d\) \( \rangle{}\)(d2) satisfying:

- f(d1)=d2,
- \( \forall \) e \( \in\) D1, \( \forall \) 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`, `d1` \( \in \) `darts()`, and `d2` \( \in \) `darts()`.

## ◆ is_valid()

bool CombinatorialMap::is_valid | ( |  | ) | const

Returns true iff the combinatorial map is valid.

A combinatorial map is valid (see Sections Mathematical Definitions 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, \( \forall\) j, such that 0 \( \leq\) i \( \leq\) `dimension`-2 and i+2 \( \leq\) j \( \leq\) `dimension`: \( \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.

## ◆ link_beta()

template<unsigned int i>

void CombinatorialMap::link_beta | ( | Dart_descriptor | d1,
|  | Dart_descriptor | d2
| ) |  |

Links `d1` and `d2` by \( \beta_i\).

The combinatorial map can be no longer valid after this operation. If `are_attributes_automatically_managed()``==true`, non void attributes of `d1` and `d2` 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 `d1` is associated to `d2`.

Precondition
  0 \( \leq\) i \( \leq\) `dimension`, `d1` \( \in\) `darts()`, `d2` \( \in\) `darts()` and (i \( <\) 2 or `d1` \( \neq\)`d2`).

## ◆ opposite() [1/2]

Dart_const_descriptor CombinatorialMap::opposite | ( | Dart_const_descriptor | d | ) | const

Returns a const descriptor to a dart belonging to the same edge than dart `d`, and not to the same vertex, when the dart is const.

`null_descriptor` if such a dart does not exist.

## ◆ opposite() [2/2]

Dart_descriptor CombinatorialMap::opposite | ( | Dart_descriptor | d | ) |

Returns a descriptor to a dart belonging to the same edge than dart `d`, and not to the same vertex.

`null_descriptor` if such a dart does not exist.

## ◆ sew()

template<unsigned int i>

void CombinatorialMap::sew | ( | Dart_descriptor | d1,
|  | Dart_descriptor | d2
| ) |  |

i-sew darts `d1` and `d2`, by keeping the generic 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{}\)(`d1`) and D2= \( \langle{}\) \( \beta_0\), \( \beta_2\), \( \ldots\), \( \beta_{i-2}\), \( \beta_{i+2}\), \( \ldots\), \( \beta_d\) \( \rangle{}\)(`d2`) such that d2=f(d1), where f is the bijection between D1 and D2 satisfying: f(d1)=d2, 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 generic 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_descriptor` and the other not, the non `null_descriptor` attribute is associated to all the darts of the resulting cell. When the two attributes are non `null_descriptor`, 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 generic map.

Precondition
  `is_sewable<i>`(`d1`,`d2`).

Advanced

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

## ◆ unlink_beta()

template<unsigned int i>

void CombinatorialMap::unlink_beta | ( | Dart_descriptor | d | ) |

Unlinks `d` and \( \beta_i\)(`d`) by \( \beta_i\).

The combinatorial map can be no longer valid after this operation. Attributes of `d` and \( \beta_i\)(`d`) are not modified.

Precondition
  0 \( \leq\) i \( \leq\) `dimension`, `d` \( \in\) `darts()`, and `d` is not i-free.

## ◆ unsew()

template<unsigned int i>

void CombinatorialMap::unsew | ( | Dart_descriptor | d | ) |

i-unsew darts `d` and `opposite<i>(d)`, by keeping the generic 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{}\)(`d`).

If `are_attributes_automatically_managed()``==true`, when necessary, non void attributes are updated to ensure the validity of the generic 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`, `d` \( \in \) `darts()` and `d` is not i-free.

Advanced

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

## Member Data Documentation

## ◆ null_dart_descriptor

Dart_descriptor CombinatorialMap::null_dart_descriptor

The null dart descriptor constant.

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