8273/doc/Combinatorial_map/index.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<link rel="canonical" href="https://doc.cgal.org/latest/Combinatorial_map/index.html"/>

<link rel="icon" type="image/png" href="../Manual/g-196x196-doc.png">
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=11">
<meta name="generator" content="Doxygen 1.9.6">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>CGAL 6.1 - Combinatorial Maps: User Manual</title>
<!-- <link href="../Manual/tabs.css" rel="stylesheet" type="text/css"/> -->
<script type="text/javascript" src="../Manual/jquery.js"></script>
<script type="text/javascript" src="../Manual/dynsections.js"></script>
<script src="../Manual/hacks.js" type="text/javascript"></script>
<!-- Manually include treeview and search to avoid bloat and to fix
     paths to the directory Manual . -->
<!-- $.treeview -->
<!-- $.search -->
<link href="navtree.css" rel="stylesheet" type="text/css">
<script type="text/javascript" src="../Manual/resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
</script>
<link href="../Manual/search/search.css" rel="stylesheet" type="text/css">
<script type="text/javascript" src="../Manual/search/searchdata.js"></script>
<script type="text/javascript" src="../Manual/search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { init_search(); });
</script>
<link href="../Manual/search/search.css" rel="stylesheet" type="text/css">
<script type="text/javascript" src="../Manual/search/search.js"></script>
<!-- Manually done below. -->
<link href="../Manual/doxygen.css" rel="stylesheet" type="text/css">
<!-- This should probably be an extrastylesheet instead of hardcoded. -->
<link href="../Manual/cgal_stylesheet.css" rel="stylesheet" type="text/css">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
  jax: ["input/TeX","output/HTML-CSS"],
});
//<![CDATA[
MathJax.Hub.Config(
{
  TeX: {
      Macros: {
          qprel: [ "{\\gtreqless}", 0],
          qpx: [ "{\\mathbf{x}}", 0],
          qpl: [ "{\\mathbf{l}}", 0],
          qpu: [ "{\\mathbf{u}}", 0],
          qpc: [ "{\\mathbf{c}}", 0],
          qpb: [ "{\\mathbf{b}}", 0],
          qpy: [ "{\\mathbf{y}}", 0],
          qpw: [ "{\\mathbf{w}}", 0],
          qplambda: [ "{\\mathbf{\\lambda}}", 0],
          ssWpoint: [ "{\\bf #1}", 1],
          ssWeight: [ "{w_{#1}}", 1],
          dabs: [ "{\\parallel\\! #1 \\!\\parallel}", 1],
          E: [ "{\\mathrm{E}}", 0],
          A: [ "{\\mathrm{A}}", 0],
          R: [ "{\\mathrm{R}}", 0],
          N: [ "{\\mathrm{N}}", 0],
          Q: [ "{\\mathrm{Q}}", 0],
          Z: [ "{\\mathrm{Z}}", 0],
          ccSum: [ "{\\sum_{#1}^{#2}{#3}}", 3],
          ccProd: [ "{\\prod_{#1}^{#2}{#3}}", 3],
          pyr: [ "{\\operatorname{Pyr}}", 0],
          aff: [ "{\\operatorname{aff}}", 0],
          Ac: [ "{\\cal A}", 0],
          Sc: [ "{\\cal S}", 0],
      },
      equationNumbers: { autoNumber: "AMS" }
  }
}
);
MathJax.Hub.Register.StartupHook("TeX Jax Ready",function () {
  var PARSE = MathJax.InputJax.TeX.Parse,
      TEXT = PARSE.prototype.InternalText;
  PARSE.Augment({
    InternalText: function (text,def) {
      text = text.replace(/\\/g,"");
      return TEXT.call(this,text,def);
    }
  });
});
//]]>
</script>
<script type="text/javascript" async="async" src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js"></script>
<script src="modules.js" type="text/javascript"></script>
<link href="cgal_stylesheet.css" rel="stylesheet" type="text/css">
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="back-nav">
  <ul>
    <li><a href="https://www.cgal.org/">cgal.org</a></li>
    <li><a href="../Manual/index.html">Top</a></li>
    <li><a href="../Manual/general_intro.html">Getting Started</a></li>
    <li><a href="../Manual/tutorials.html">Tutorials</a></li>
    <li><a href="../Manual/packages.html">Package Overview</a></li>
    <li><a href="../Manual/how_to_cite_cgal.html">Acknowledging CGAL</a></li>
  </ul>
  <!-- In a package SEARCHENGINE = false, so we cannot use 
       insertion. That's why we have to do it manually here. Notice
       that we also take pngs from the Manual. -->
  <div id="MSearchBox" class="MSearchBoxInactive">
      <span class="left">
         <span id="MSearchSelect" onmouseover="return searchBox.OnSearchSelectShow()" onmouseout="return searchBox.OnSearchSelectHide()"> 
        </span>
        <input type="text" id="MSearchField" value="" placeholder="Search" accesskey="S" onfocus="searchBox.OnSearchFieldFocus(true)" onblur="searchBox.OnSearchFieldFocus(false)" onkeyup="searchBox.OnSearchFieldChange(event)">
      </span>
      <span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="../Manual/search/close.svg" alt=""></a>
      </span>
  </div>
</div>
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr id="projectrow">
  <td id="projectalign">
   <div id="projectname">CGAL 6.1 - Combinatorial Maps
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- Code below is usually inserted by doxygen when SEARCHENGINE =
     true. Notice that the path to the search directory is adjusted to
     the top-level.-->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "../Manual/search/",'.html');
</script>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow" onmouseover="return searchBox.OnSearchSelectShow()" onmouseout="return searchBox.OnSearchSelectHide()" onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.9.6 -->
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync" style="display: none"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&amp;dn=expat.txt MIT */
$(document).ready(function(){initNavTree('index.html',''); initResizable(); });
/* @license-end */
</script>
<div id="doc-content">
<div><div class="header">
  <div class="headertitle"><div class="title">User Manual </div></div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p><a class="anchor" id="Chapter_Combinatorial_Maps"></a><a class="anchor" id="ChapterCombinatorialMap"></a> </p><dl class="section author"><dt>Author</dt><dd>Guillaume Damiand  <div id="autotoc" class="toc"></div> </dd></dl>
<h1><a class="anchor" id="Combinatorial_mapIntroduction"></a>
Introduction</h1>
<p>A <em>d</em>-dimensional combinatorial map is a data structure representing an orientable subdivided <em>d</em>-dimensional object obtained by taking <em>d</em>D cells, and allowing to glue <em>d</em>D cells along <em>(d-1)</em>D cells. It provides a description of all the cells of the subdivision (for example vertices and edges), together with incidence and adjacency relationships. This package is a generalization of the <a class="elRef" href="../HalfedgeDS/index.html#chapterHalfedgeDS">halfedge data structure</a> to higher dimension. Indeed, a 2D combinatorial map is equivalent to a halfedge data structure: there is a one-to-one mapping between elements of both data structures, halfedges corresponding to darts.</p>
<p>Note that you can use the <a class="elRef" href="../Generalized_map/index.html#ChapterGeneralizedMap">Generalized Map package</a> if you need to represent non-orientable objects.</p>
<p>We denote <em>i</em>-cell for an <em>i</em>-dimensional cell (for example in 3D, 0-cells are <em>vertices</em>, 1-cells are <em>edges</em>, 2-cells are <em>facets</em>, and 3-cells are <em>volumes</em>). A <em>boundary relation</em> is defined on these cells, giving for each <em>i</em>-cell <em>c</em> the set of <em>(i-1)</em>-cells contained in the boundary of <em>c</em>. Two cells <em>c1</em> and <em>c2</em> are <em>incident</em> if there is a path of cells, starting from the cell of highest dimension to the other cell, such that each cell of the path (except the first one) belongs to the boundary of the previous cell in the path. Two <em>i</em>-cells <em>c3</em> and <em>c4</em> are <em>adjacent</em> if there is an <em>(i-1)</em>-cell incident to both <em>c3</em> and <em>c4</em>. You can see an example of a 2D object and a 3D object in <a class="el" href="index.html#fig__fig_cmap_example_subdivisions">Figure 29.1</a> showing some cells of the subdivision and some adjacency and incidence relations.</p>
<p><a class="anchor" id="fig__fig_cmap_example_subdivisions"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_example_subdivisions.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_example_subdivisions">Figure 29.1</a> Example of subdivided objects that can be described by combinatorial maps. Left: A 2D object composed of three facets (2-cells), named <em>f1</em>, <em>f2</em> and <em>f3</em>, nine edges (1-cells) and seven vertices (0-cells). <em>f1</em> and <em>f2</em> are adjacent along edge <em>e1</em>, thus <em>e1</em> is incident both to <em>f1</em> and <em>f2</em>. Vertex <em>v1</em> is incident to edge <em>e1</em>, thus <em>v1</em> is incident to <em>f1</em> and <em>f2</em> by transitivity. Right: A 3D object (only partially represented for vertices and edges) composed of three volumes (3-cells), named <em>vol1</em>, <em>vol2</em> and <em>vol3</em>, twelve facets (2-cells) (there is one facet <em>f4</em> between <em>vol1</em> and <em>vol2</em>, and similarly between <em>vol1</em> and <em>vol3</em> and <em>vol2</em> and <em>vol3</em>), sixteen edges (1-cells), and eight vertices (0-cells). <em>vol1</em> and <em>vol2</em> are adjacent along facet <em>f4</em>, thus <em>f4</em> is incident both to <em>vol1</em> and <em>vol2</em>. Edge <em>e4</em> is incident to the three facets between <em>vol1</em> and <em>vol2</em>, <em>vol1</em> and <em>vol3</em>, and <em>vol2</em> and <em>vol3</em>. <em>e4</em> is also incident to the three volumes by transitivity. </p> </div> <p> <br>
</p>
<p>A combinatorial map is an edge-centered data structure, describing the cells and the incidence and adjacency relations. It uses only one basic element called <em>dart</em>, and a set of <em>pointers</em> between these darts. A dart can be thought as a part of an oriented edge (1-cell), together with a part of incident cells of dimensions 0, 2, 3, ..., <em>d</em>. When a dart <em>d0</em> describes a part of an <em>i</em>-cell <em>c</em>, we say that <em>d0</em> <em>belongs</em> to <em>c</em>, and that <em>c</em> <em>contains</em> <em>d0</em>. Let us look at the example in <a class="el" href="index.html#fig__fig_cmap_examples">Figure 29.2</a> showing the 2D and 3D combinatorial maps describing the two objects of <a class="el" href="index.html#fig__fig_cmap_example_subdivisions">Figure 29.1</a>.</p>
<p><a class="anchor" id="fig__fig_cmap_examples"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_examples.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_examples">Figure 29.2</a> Combinatorial maps representing the objects given in <a class="el" href="index.html#fig__fig_cmap_example_subdivisions">Figure 29.1</a>. Left: The 2D combinatorial map which contains 12 darts. Right: The 3D combinatorial map which contains 54 darts (18 for each volume). </p> </div> <p> <br>
</p>
<p>First let us start in 2D (<a class="el" href="index.html#fig__fig_cmap_examples">Figure 29.2</a> (Left)). Facet <em>f1</em> contains four darts. These darts are linked together with pointers. Starting from a dart and following a \( \beta_1\) pointer, we get to a dart which belongs to the same facet but to the next edge (1-cell, which explains the index 1 of \( \beta_1\)). Starting from any dart and following \( \beta_1\) pointers, we can reach exactly all the darts belonging to the facet. Starting from a dart and following a \( \beta_2\) pointer, we get to a dart which belongs to the same edge but to the neighboring facet (2-cell, which explains the index 2 of \( \beta_2\)). Starting from any dart and following \( \beta_2\) pointers, we can reach exactly all the darts that belong to the edge (in 2D one or two darts).</p>
<p>Things are slightly different for vertices. Indeed, each \( \beta_i\) points to a dart belonging to a different <em>i</em>-cell, but also to a different 0-cell (vertex). This is so because two linked darts have opposite orientations. For this reason, starting from any dart belonging to a vertex <em>v</em>, we have to follow \( \beta_2\) then \( \beta_1\) to reach exactly the darts belonging to vertex <em>v</em>. In fact, by composing two \( \beta_i\)s, we always obtain a dart belonging to the same vertex (if we do not start by following a \( \beta_1\) pointer).</p>
<p>The main interest of combinatorial map definition based on darts and \( \beta_i\) pointers is to be able to increase the dimension <em>only</em> by adding new pointers. This is illustrated thanks to the 3D example given in <a class="el" href="index.html#fig__fig_cmap_examples">Figure 29.2</a> (Right). In addition to \( \beta_1\) and \( \beta_2\) of the 2D case, there is a new pointer \( \beta_3\).</p>
<p>If we take a closer look at the central edge <em>e4</em> shown in <a class="el" href="index.html#fig__fig_cmap_examples_zoom">Figure 29.3</a> (Left), we can see that it contains six darts linked together. Starting from a dart and following a \( \beta_3\) pointer, we get to a dart which belongs to the same edge, to the same facet, but to the neighboring volume (a 3-cell, which explains the index 3 in \( \beta_3\)). Similarly, starting from a dart and following a \( \beta_2\) pointer, we get to a dart which belongs to the same edge, to the same volume, but to the neighboring facet (2-cell). Starting from any of these six darts and following \( \beta_2\) and \( \beta_3\) pointers, we can reach exactly the six darts that belong to edge <em>e4</em>.</p>
<p><a class="anchor" id="fig__fig_cmap_examples_zoom"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_examples_zoom.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_examples_zoom">Figure 29.3</a> Two zooms on the 3D combinatorial map given in <a class="el" href="index.html#fig__fig_cmap_examples">Figure 29.2</a> (Right). Left: Zoom around the central edge <em>e4</em> which details the six darts belonging to the edge. Right: Zoom around the facet between volumes <em>vol2</em> and <em>vol3</em> which details the eight darts belonging to the facet. </p> </div> <p> <br>
</p>
<p>For facets, by following a \( \beta_1\) pointer, we get to a dart which belongs to the same facet, to the same volume, but to the next edge (1-cell, which explains the index 1 of \( \beta_1\)). Starting from any dart and following \( \beta_1\) and \( \beta_3\) pointers, we can reach exactly all the darts belonging to the facet (see <a class="el" href="index.html#fig__fig_cmap_examples_zoom">Figure 29.3</a> (Right)). For volumes, starting from any dart and following \( \beta_1\) and \( \beta_2\) pointers, we can reach exactly all the darts belonging to the volume.</p>
<p>For vertices, we have to follow \( \beta_2\) then \( \beta_1\), and \( \beta_3\) then \( \beta_1\) to reach exactly the darts belonging to the vertex <em>v</em>. Indeed, as in 2D, we have to compose two \( \beta_i\)s to obtain a dart belonging to the same vertex (if we do not start by following a \( \beta_1\) pointer).</p>
<p>In some cases, the general rule that by following a \( \beta_i\) we get a dart which belongs to the neighboring <em>i</em>-cell is not true, as for example for darts belonging to the boundary of the represented object. For example, in <a class="el" href="index.html#fig__fig_cmap_example_subdivisions">Figure 29.1</a> (Left), any dart <em>d0</em> that does not belong to edge <em>e1</em>, <em>e2</em> and <em>e3</em> belongs to a 2-cell, and there is no neighboring facet along the edge containing <em>d0</em>. Another example is in <a class="el" href="index.html#fig__fig_cmap_example_subdivisions">Figure 29.1</a> (Right), for any dart <em>d0</em> that belongs to facet <em>f5</em>. <em>d0</em> belongs to volume <em>vol2</em>, but there is no neighboring volume along this facet. The general rule is also not true for unbounded cells. For example if we remove a dart in <a class="el" href="index.html#fig__fig_cmap_examples">Figure 29.2</a> (Left), we obtain an unbounded facet having a dart without next dart for \( \beta_1\), and if we remove a facet in <a class="el" href="index.html#fig__fig_cmap_examples">Figure 29.2</a> (Right), we obtain an unbounded volume having some darts without neighboring facet for \( \beta_2\). In such a case, there is a particular value called \( \varnothing\) used to describe that a dart <em>d0</em> is not linked to another dart in dimension <em>i</em>.</p>
<p>Combinatorial maps are defined in any dimension. A 0D combinatorial map is a set of isolated darts describing isolated vertices. A 1D combinatorial map describes paths or cycles of darts corresponding to paths or cycles of edges, and equivalent to double linked lists. The most useful cases are 2D and 3D combinatorial maps. Since 2D combinatorial maps are equivalent to halfedge data structure, notions are illustrated in 3D in the following examples to help the reader understand this specific case. But it is important to keep in mind that one main interest of combinatorial maps is their generic definition in any dimension, and that everything presented in this manual is valid in any dimension.</p>
<p>A <em>d</em>D combinatorial map is useful when you want to describe <em>d</em>D objects and the adjacency relations between these objects, and you want to be able to efficiency traverse these objects by using the different relations. For example, we can use a 3D combinatorial map to describe a 3D segmented image: each 3-cell corresponds to a region in the image and each 2-cell corresponds to a contact area between two regions.</p>
<p>A combinatorial map does not contain any geometric information. However, this package allows to associate any information to the cells of the combinatorial map. A specific information, which is often used in practice, consists in adding linear geometry to a combinatorial map by associating a point to each vertex of the map: this is the object of the <a class="elRef" href="../Linear_cell_complex/index.html#ChapterLinearCellComplex">Linear cell complex</a> package (when an object has a point associated to each vertex, each edge is thus a straight line segment, which explains the name <em>linear geometry</em>). The <a class="elRef" href="../Linear_cell_complex/index.html#ChapterLinearCellComplex">Linear cell complex</a> package can for example be useful to describe 3D buildings as set of walls, rooms, doors and windows (both combinatorial and geometric descriptions) and all the adjacency relations between these elements allowing for example to move a camera in a given building from rooms to rooms by traversing doors.</p>
<h1><a class="anchor" id="sec_presentation"></a>
Data Structure Presentation</h1>
<p>In this section, we describe <em>d</em>D combinatorial maps in terms of data structure and operations. Mathematical definitions are provided in Section <a class="el" href="index.html#sec_definition">Mathematical Definitions</a>, and a package description is given in Section <a class="el" href="index.html#secsoftwaredesign">Software Design</a>.</p>
<h2><a class="anchor" id="sseccombimapanddarts"></a>
Combinatorial Map and Darts</h2>
<p>A <em>d</em>D combinatorial map is a set of darts <em>D</em>. A dart <em>d0</em> is an element that can be <em>linked</em> with <em>d</em>+1 darts by pointers called \( \beta_i\), with 0 \( \leq \) <em>i</em> \( \leq \) <em>d</em>. Dart <em>d0</em> is said <em>i-free</em> when \( \beta_i\)(<em>d0</em>)= \( \varnothing\). Each \( \beta_i\), for 2 \( \leq \) <em>i</em> \( \leq \) <em>d</em>, is its own inverse, i.e., if dart <em>d0</em> is not <em>i</em>-free, then \( \beta_i\)( \( \beta_i\)(<em>d0</em>))=<em>d0</em>. This is different for \( \beta_0\) and \( \beta_1\): \( \beta_0\) is the inverse of \( \beta_1\), i.e., if darts <em>d1</em> and <em>d2</em> are such that \( \beta_1\)(<em>d1</em>)=<em>d2</em>, then \( \beta_0\)(<em>d2</em>)=<em>d1</em>. Given dart <em>d1</em>, if there is no dart <em>d2</em> such that \( \beta_1\)(<em>d2</em>)=<em>d1</em>, then \( \beta_0\)(<em>d1</em>)= \( \varnothing\). \( \varnothing\) is a constant, which does not belong to the set of darts <em>D</em> of the combinatorial map. However, by definition \( \varnothing\) is linked with itself for all \( \beta_i\)s: \( \forall \) <em>i</em>, 0 \( \leq \) <em>i</em> \( \leq \) <em>d</em>, \( \beta_i\)( \( \varnothing)\)= \( \varnothing\).</p>
<p>A combinatorial map is <em>without i-boundary</em> if there is no <em>i</em>-free dart, and it is <em>without boundary</em> if it is without <em>i</em>-boundary for all dimensions 1 \( \leq \) <em>i</em> \( \leq \)<em>d</em>.</p>
<p>We show in <a class="el" href="index.html#fig__fig_cmap_detailed_example">Figure 29.4</a> a 3D object and the corresponding 3D combinatorial map. This map has 40 darts represented by arrows, some darts being numbered. In this combinatorial map, we have for example \( \beta_1\)(1)=2, \( \beta_2\)(1)=10, and \( \beta_3\)(1)=5. This combinatorial map is without 1-boundary and 2-boundary, but has some 3-boundary, because some darts are 3-free, for example \( \beta_3\)(10)= \( \varnothing\) and \( \beta_3\)(12)= \( \varnothing\).</p>
<p><a class="anchor" id="fig__fig_cmap_detailed_example"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_detailed_example.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_detailed_example">Figure 29.4</a> Example of a 3D combinatorial map. Left: A 3D object made of two volumes adjacent along facet <em>f2</em>. Right: The corresponding 3D combinatorial map. Darts are drawn with arrows, sometimes numbered. Two darts linked by \( \beta_1\) are drawn consecutively (for example \( \beta_1\)(10)=11), and two darts linked by \( \beta_2\) are drawn parallel, in reverse orientations, with a little gray segment joining them (for example \( \beta_2\)(1)=10). \( \beta_3\) pointers are represented by blue segments (for example \( \beta_3\)(1)=5). </p> </div> <p> <br>
</p>
<h2><a class="anchor" id="sseccellsinmap"></a>
Cells as Sets of Darts</h2>
<p>A cell in a <em>d</em>D combinatorial map is implicitly represented by a subset of darts. In this section, we will see how to retrieve all cells containing a given dart, how to retrieve all darts belonging to a cell containing a given dart, and how incidence and adjacency relations are defined in terms of darts.</p>
<p>The first important property of a combinatorial map is that each dart belongs to an <em>i</em>-cell, \( \forall \) <em>i</em>, 0 \( \leq \) <em>i</em> \( \leq \) <em>d</em>. For example in 3D, a dart belongs to a vertex, an edge, a facet, and a volume. This means that a 3D combinatorial map containing an isolated dart contains exactly one vertex, one edge, one facet and one volume.</p>
<p>The second important property is that cells of a combinatorial map correspond to specific <em>orbits</em>. Given a set <em>S</em> \( \subseteq\){ \( \beta_1\),..., \( \beta_d\)} and a dart <em>d0</em>, the <em>orbit</em> \( \langle{}\) <em>S</em> \( \rangle{}\)(<em>d0</em>) is the set of darts that can be reached from <em>d0</em> by following any combination of any \( \beta_i\)'s in <em>S</em> and their inverses (to simplify notations, we can use for example \( \langle{}\) \( \beta_1\), \( \beta_4\) \(\rangle{}\)(<em>d0</em>) to denote \( \langle{}\) <em>S</em> \( \rangle{}\)(<em>d0</em>) with <em>S</em>={ \( \beta_1\), \( \beta_4\)}).</p>
<p>Given a dart <em>d0</em>, in general, \( \beta_i\)(<em>d0</em>) (with 1 \( \leq \) <em>i</em> \( \leq \) <em>d</em>) belongs to the same cells as <em>d0</em>, only the <em>i</em>-cell and 0-cell are different. There are two exceptions: </p><ol type="1">
<li>
if <em>d0</em> is <em>i</em>-free, then \( \beta_i\)(<em>d0</em>)= \( \varnothing\); </li>
<li>
if \( \beta_i\)(<em>d0</em>) belongs to the same <em>i</em>-cell as <em>d0</em> (case of multi-incidence). For example if an edge is an isolated loop, it is incident twice to the same vertex, then given a dart <em>d0</em> belonging to this edge, \( \beta_1\)(<em>d0</em>) goes to the next edge, which is in fact the same edge. </li>
</ol>
<p>Since \( \beta_i\)(<em>d0</em>) (with 1 \( \leq \) <em>i</em> \( \leq \) <em>d</em>) allows to change the current <em>i</em>-cell, all the darts that can be reached from <em>d0</em> by using any combination of \( \beta_j\)'s, \( \forall \) <em>j</em>, 1 \( \leq \) <em>j</em> \( \leq \) <em>d</em> and <em>j</em> \( \neq \) <em>i</em> and their inverse are contained in the same <em>i</em>-cell as <em>d0</em>. The <em>i</em>-cell containing <em>d0</em> is defined in terms of orbit by \( \langle{}\) \( \beta_1\),..., \( \beta_{i-1}\), \( \beta_{i+1}\),..., \( \beta_d\) \( \rangle{}\)(<em>d0</em>).</p>
<p>There is a special case for vertices. Given a dart <em>d0</em>, the set of darts contained in the same vertex as <em>d0</em> are the darts that can be reached from <em>d0</em> by using any combination of \(\beta_i \circ\) \( \beta_j\), \( \forall \) <em>i</em>,<em>j</em>, 1 \( \leq \) <em>i</em> \( &lt; \) <em>j</em> \( \leq \) <em>d</em>, and their inverse. The 0-cell containing <em>d0</em> is defined in terms of orbit by \( \langle{}\){ \( \beta_i\) \( \circ\) \( \beta_j\) \( |\) \( \forall \) <em>i,j</em>: 1 \( \leq \) <em>i</em> \( &lt; \) <em>j</em> \( \leq \) <em>d</em>} \( \rangle{}\)(<em>d0</em>).</p>
<p>Orbit \( \langle{}\) \( \beta_1\),..., \( \beta_d\) \( \rangle{}\)(<em>d0</em>) is the <em>connected component</em> containing dart <em>d0</em>. A combinatorial map is <em>connected</em> if this set is equal to the set of all the darts of the combinatorial map.</p>
<p>A last important property of cells is that for all dimensions <em>i</em> the set of <em>i</em>-cells forms a partition of the set of darts <em>D</em>, i.e. for any <em>i</em>, the union of the sets of darts of all the <em>i</em>-cells is equal to <em>D</em>, and the sets of darts of two different <em>i</em>-cells are disjoint.</p>
<p>Let us give some examples of cells in 3D, for the 3D combinatorial map of <a class="el" href="index.html#fig__fig_cmap_detailed_example">Figure 29.4</a> : </p><ul>
<li>
All the darts belonging to the same edge can be obtained by any combination of \( \beta_2\) and \( \beta_3\): for example edge <em>e</em> of the object corresponds in the combinatorial map to the set of darts {1,5,9,10}. Given any dart belonging to this edge, we retrieve all the other darts by, for example, a breadth-first traversal. In terms of orbits, this 1-cell corresponds to \( \langle{}\) \( \beta_2\), \( \beta_3\) \( \rangle{}\)(1). </li>
<li>
All the darts belonging to the same facet can be obtained by any combination of \( \beta_1\) and \( \beta_3\): for example facet <em>f2</em> corresponds in the combinatorial map to the set of darts {1,2,3,4,5,6,7,8}. Facet <em>f1</em> corresponds to the set of darts {10,11,12,13}. Note that these last darts are 3-free since there is no other volume sharing this facet. In terms of orbits, <em>f2</em> corresponds to \( \langle{}\) \( \beta_1\), \( \beta_3\) \( \rangle{}\)(1) and <em>f1</em> corresponds to \( \langle{}\) \( \beta_1\), \( \beta_3\) \( \rangle{}\)(10). </li>
<li>
All the darts belonging to the same volume can be obtained by any combination of \( \beta_1\) and \( \beta_2\): for example volume <em>vol1</em> corresponds in the combinatorial map to the set of the twenty-four darts belonging to the cube. In terms of orbits, <em>vol1</em> corresponds to \( \langle{}\) \( \beta_1\), \( \beta_2\) \( \rangle{}\)(1). </li>
<li>
All the darts belonging to the same vertex can be obtained by any combination of \( \beta_1\) \( \circ\) \( \beta_2\), \( \beta_1\) \( \circ\) \( \beta_3\) and \( \beta_2\) \( \circ\) \( \beta_3\) and their inverse functions. In our example, vertex <em>v</em> of the object corresponds in the combinatorial map to the set of darts {1,6,9,11,14,15}. Starting from dart 1, we obtain for example dart 14=( \( \beta_1\) \( \circ\) \( \beta_2\)) \( ^{-1}\)(1)= \( \beta_2\) \( \circ\) \( \beta_0\)(1), dart 11= \( \beta_1\) \( \circ\) \( \beta_2\)(1), and dart 9= \( \beta_2\) \( \circ\) \( \beta_3\)(1). Intuitively, the set of darts corresponding to a vertex contains all the darts represented by arrows starting from this vertex. In terms of orbits, <em>v</em> corresponds to \( \langle{}\) \( \beta_1\) \( \circ\) \( \beta_2\), \( \beta_1\) \( \circ\) \( \beta_3\), \( \beta_2\) \( \circ\) \( \beta_3\) \( \rangle{}\)(1). </li>
</ul>
<p>Using this definition of cells as sets of darts, we can retrieve all the incidence and adjacency relations between the cells of the subdivision in a combinatorial map. Two cells are <em>incident</em> if the intersection of their two sets of darts is non empty (whatever the dimension of the two cells). Two <em>i</em>-cells <em>c1</em> and <em>c2</em>, 1 \( \leq \) <em>i</em> \( \leq \)<em>d</em>, are <em>adjacent</em> if there is <em>d1</em> \( \in \) <em>c1</em> and <em>d2</em> \( \in \) <em>c2</em> such that <em>d1</em> and <em>d2</em> belong to the same <em>(i-1)</em>-cell.</p>
<p>In the example of <a class="el" href="index.html#fig__fig_cmap_detailed_example">Figure 29.4</a>, vertex <em>v</em> and edge <em>e</em> are incident since the intersection of the two corresponding sets of darts is {1,9} \( \neq \) \( \emptyset\). Vertex <em>v</em> is incident to facet <em>f2</em> since the intersection of the two corresponding sets of darts is {1,6} \( \neq \) \( \emptyset\). Edge <em>e</em> and facet <em>f1</em> are incident since the intersection of the two corresponding sets of darts is {10} \( \neq \) \( \emptyset\). Finally, facets <em>f1</em> and <em>f2</em> are adjacent because 10 \( \in \) <em>f1</em>, 1 \( \in \) <em>f2</em> and 1 and 10 belong to the same edge.</p>
<p>We can consider <em>i</em>-cells in a dimension <em>d'</em> with <em>i</em> \( \leq \) <em>d'</em> \( \leq\) <em>d</em>. The idea is to consider the <em>i</em>-cells as if the combinatorial map was in <em>d'</em> dimension. For that, we only take into account the \( \beta_j \)s for <em>j</em> \( \leq \) <em>d'</em>. The <em>i</em>-cell containing <em>d0</em> in dimension <em>d'</em> is the orbit \( \langle{}\) \( \beta_1\),..., \( \beta_{i-1}\), \( \beta_{i+1}\),..., \( \beta_{d'}\) \( \rangle{}\)(<em>d0</em>), and the 0-cell is the orbit \( \langle{}\){ \( \beta_i\) \( \circ\) \( \beta_j\) \( |\) \( \forall \) <em>i,j</em>: 2 \( \leq \) <em>i</em> \( &lt; \) <em>j</em> \( \leq \) <em>d'</em>} \( \rangle{}\)(<em>d0</em>). By default, <em>i</em>-cells are considered in dimension <em>d</em>, the dimension of the combinatorial map.</p>
<p>In the example of <a class="el" href="index.html#fig__fig_cmap_detailed_example">Figure 29.4</a>, the 2-cell containing dart 1 is facet <em>f2</em> which is the set of darts {1,2,3,4,5,6,7,8}. If we consider the same 2-cell in dimension 2, we obtain the set of darts {1,2,3,4}. Intuitively we <em>forget</em> \( \beta_3\) and we obtain the set of darts of the facet containing dart 1 restricted to the volume containing this dart.</p>
<h2><a class="anchor" id="ssecassociateattributes"></a>
How to Associate Information to Cells</h2>
<p>Combinatorial maps only describe the cells of the subdvision, and all the incidence and adjacency relations between these cells. This is not enough for many applications which need to associate <em>information</em> to cells. This can be geometric or non-geometric information, such as 3D points associated to vertices, the edge length associated to edges, or a color or normal to a facet.</p>
<p>To answer this need, a combinatorial map allows to create <em>attributes</em> which are able to store any information, and to associate attributes to cells of the combinatorial map. We denote <em>i</em>-attributes for the attributes associated with <em>i</em>-cells. Attributes may exist for only some of the dimensions, and if they exist for dimension <em>i</em>, they do not necessarily exist for each of the <em>i</em>-cells. More precisely, <em>i</em>-attributes are associated to <em>i</em>-cells by an injection: </p><ul>
<li>
two different <em>i</em>-cells are associated to two different <em>i</em>-attributes; </li>
<li>
an <em>i</em>-cell may have no associated <em>i</em>-attribute. </li>
</ul>
<p>Since <em>i</em>-cells are not explicitly represented in combinatorial maps, the association between <em>i</em>-cells and <em>i</em>-attributes is transferred to darts: if attribute <em>a</em> is associated to <em>i</em>-cell <em>c</em>, all the darts belonging to <em>c</em> are associated to <em>a</em>.</p>
<p>We can see two examples of combinatorial maps having some attributes in <a class="el" href="index.html#fig__fig_cmap_with_attribs">Figure 29.5</a>. In the first example (Left), a 2D combinatorial map has 1-attributes containing a float, for example corresponding to the length of the associated 1-cell, and 2-attributes containing a color in RGB format. In the second example (Right), a 3D combinatorial map has 2-attributes containing a color in RGB format.</p>
<p><a class="anchor" id="fig__fig_cmap_with_attribs"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_with_attribs.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_with_attribs">Figure 29.5</a> Example of combinatorial maps with attributes. Attributes are represented by black rectangles containing an information, and association between darts and attributes are represented by small red lines. Left: A 2D combinatorial map with 1-attributes containing a double, for example corresponding to the length of the 1-cell, and 2-attributes containing a color in RGB format. Only three edges of the combinatorial map, among the nine, are associated to a 1-attribute. All the 2-cells are associated to a 2-attribute. Right: A 3D combinatorial map with 2-attributes containing a color in RGB format. Only three 2-cells of the combinatorial map, among the ten, are associated to a 2-attribute. </p> </div> <p> <br>
</p>
<h2><a class="anchor" id="sseccombimapvalidity"></a>
Combinatorial Map Properties</h2>
<p>There are some conditions that a combinatorial map must satisfy to be valid. Some of them have already been given about the \( \beta\) pointers (see Section <a class="el" href="index.html#sseccombimapanddarts">Combinatorial Map and Darts</a>) and about the association between darts and attributes (see Section <a class="el" href="index.html#ssecassociateattributes">How to Associate Information to Cells</a>).</p>
<p>There is an additional condition related to the type of represented objects, which are <em>quasi-manifold</em> orientable <em>d</em>D objects. A <em>d</em>D quasi-manifold is an object obtained by taking some isolated <em>d</em>-cells, and allowing to glue <em>d</em>-cells along <em>(d-1)</em>-cells. It is orientable if it is possible to embed it in the Euclidean space and to define a global "left" and "right" direction in each point of the embedded object. In 2D, quasi-manifolds are manifolds, but this is no longer true in higher dimension as we can see in the example presented in <a class="el" href="index.html#fig__fig_cmap_quasi_manifold">Figure 29.6</a>. In this example, the object to the right is not a manifold since the neighborhood of the point <em>p</em> in the object is not homeomorphic to a 3D ball (intuitively, two objects are homeomorphic if each object can be continuously deformed into the second one; in such a case, the two objects have exactly the same topological properties).</p>
<p><a class="anchor" id="fig__fig_cmap_quasi_manifold"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_quasi_manifold.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_quasi_manifold">Figure 29.6</a> Example of a 3D quasi-manifold which is not a manifold. The object to the right is made of the four pyramids (shown to the left) glued together along facets, thus it is a quasi-manifold. </p> </div> <p> <br>
</p>
<p>Combinatorial maps can only represent quasi-manifolds due to the definition of \( \beta\) pointers. As we have seen in Section <a class="el" href="index.html#sseccellsinmap">Cells as Sets of Darts</a>, \( \beta_i\)(<em>d0</em>) (with 1 \( \leq \) <em>i</em> \( \leq \) <em>d</em>) belongs to the same cells as <em>d0</em>, only the <em>i</em>-cell and 0-cell are different. In other words, \( \beta_i\) links two <em>i</em>-cells that share a common <em>(i-1)</em>-cell: it is not possible to link more than two <em>i</em>-cells along a same <em>(i-1)</em>-cell. For this reason, it is not possible to describe non quasi-manifold objects as those shown in <a class="el" href="index.html#fig__fig_cmap_non_manifolds">Figure 29.7</a> by combinatorial maps.</p>
<p><a class="anchor" id="fig__fig_cmap_non_manifolds"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_non_manifolds.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_non_manifolds">Figure 29.7</a> Three examples of non quasi-manifold objects. Left: A 2D object which is not a quasi-manifold since the two 2-cells share a common vertex but no common 1-cell. Middle: A 3D object which is not a quasi-manifold since is it not only composed by 3D cells glued together (there is an isolated 2-cell in dark gray). Right: A 3D object which is not a quasi-manifold since the two 3-cells share a common edge but no common 2-cell. </p> </div> <p> <br>
</p>
<p>Due to this additional condition, any objects can not be represented by a combinatorial map but only orientable quasi-manifolds. We need to study now the inverse relation. Does any set of darts linked together by \( \beta_i\)'s, with 0 \( \leq \) <em>i</em> \( \leq \) <em>d</em> correspond to a quasi-manifold? As we can see in <a class="el" href="index.html#fig__fig_cmap_non_valid">Figure 29.8</a>, the answer is no.</p>
<p><a class="anchor" id="fig__fig_cmap_non_valid"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_non_valid.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_non_valid">Figure 29.8</a> Two examples of darts linked together by some \( \beta_1\), \( \beta_2\) and \( \beta_3\) which does not represent a 3D quasi-manifold, and thus which are not 3D combinatorial map. Left: In this example, all the darts are 3-free except \( \beta_3\)(1)=5 and \( \beta_3\)(4)=6 (and vice-versa). Right: In this example, darts linked by \( \beta_3\) are not in the same order in both 3-cells. </p> </div> <p> <br>
</p>
<p>In the first example (Left), there are two 3-cells (one to the left for the cube, a second to the right for the pyramid) which are <em>partially adjacent</em> along one 2-cell. Indeed, only two darts of the 2-cell are linked by \( \beta_3\). We have \( \beta_3\)(1)=5 and \( \beta_3\)(4)=6 (and reciprocally). This configuration is not possible in a quasi-manifold: two <em>d</em>-cells are always glue along an <em>entire</em> <em>(d-1)</em>-cells.</p>
<p>But as we can see in the second example (Right), the condition that all the darts of the cell are linked in not sufficient. Indeed, in this example, all the darts of the 2-cell between the cube and the pyramid are linked together by \( \beta_3\). However, this configuration does not correspond to an orientable 3D quasi-manifold. Indeed, the operation of gluing two <em>d</em>-cells along one <em>(d-1)</em>-cell must preserve the structure of the initial <em>(d-1)</em>-cell.</p>
<p>To avoid these two kinds of configurations, conditions are added on \( \beta\) pointers compositions (see Section <a class="el" href="index.html#sec_definition">Mathematical Definitions</a>, condition (4) of the definition of combinatorial maps). Intuitively these conditions say that if two darts are linked by \( \beta_i\), then all the required darts are linked by \( \beta_i\) two by two in such a way that neighborhood relations are preserved.</p>
<p>We say that a combinatorial map is <em>valid</em> if it satisfies all the conditions on \( \beta\) pointers and on association between darts and attributes. High level operations provided on combinatorial maps ensure that these conditions are always satisfied. Sometimes, it can be useful to use low level operations in a specific algorithm, for example to modify locally a combinatorial map in a really fast way. In such a case, additional operations may be needed to restore these validity conditions.</p>
<h2><a class="anchor" id="ssec-comparison-cmaps-with-gmaps"></a>
Comparison with Generalized Maps</h2>
<p>Combinatorial maps and <a class="elRef" href="../Generalized_map/index.html#ChapterGeneralizedMap">generalized maps</a> are very similar: they are both based on darts and functions, and they both allow to represent quasi-manifold <em>n</em>D objects. This explains that they share their main concepts.</p>
<p>However, they have three main differences. Firstly, generalized maps allow to represent non-orientable and orientable objects while combinatorial maps allow only to represent orientable objects. Secondly, generalized maps are homogeneous in each dimension since all functions are involutions, while combinatorial maps are not homogeneous since one function is a permutation while other ones are involutions. This homogeneity simplifies algorithms for generalized maps since it allows to avoid a specific case for the first dimension. Thirdly, a generalized map requires twice the number of darts of a combinatorial map in order to represent an orientable object.</p>
<p>Considering these different advantages and drawbacks, you can choose to use generalized maps or combinatorial maps depending on the needs of your application.</p>
<h1><a class="anchor" id="secsoftwaredesign"></a>
Software Design</h1>
<p>The diagram in <a class="el" href="index.html#fig__fig_cmap_diagramme_class">Figure 29.9</a> shows the different classes of the package. <code><a class="el" href="classCGAL_1_1Combinatorial__map.html" title="The class Combinatorial_map represents a dD combinatorial map.">Combinatorial_map</a></code> is the main class (see Section <a class="el" href="index.html#sseccombinatorialmap">Combinatorial Maps</a>). It allows to manage darts and attributes (see Section <a class="el" href="index.html#ssecattributes">Cell Attributes</a>). Users can customize a combinatorial map thanks to an items class (see Section <a class="el" href="index.html#ssecitem">Combinatorial Map Items</a>), which defines the information associated with darts and the attribute types. These types may be different for different dimensions, and they may also be void (note that the main concepts of <code><a class="el" href="classGenericMap.html" title="The concept GenericMap defines a d-dimensional generic map. This concept is defined only to factorize...">GenericMap</a></code>, <code><a class="el" href="classGenericMapItems.html" title="The concept GenericMapItems allows to customize a dD generic map by choosing the information associat...">GenericMapItems</a></code> and <code><a class="el" href="classCellAttribute.html" title="The concept CellAttribute represents a non void attribute associated with a cell of a generic map....">CellAttribute</a></code> are shared between combinatorial maps and generalized maps).</p>
<p>The darts and attributes are accessed through <em>descriptors</em> (either Indices or Handles). A handle is a model of the <code><a class="elRef" href="../Circulator/classHandle.html">Handle</a></code> concept, thus supporting the two dereference operators <code>operator*</code> and <code>operator-&gt;</code>. All handles are model of <code><a class="elRef" href="../Manual/classLessThanComparable.html">LessThanComparable</a></code> and <code><a class="elRef" href="../STL_Extension/classHashable.html">Hashable</a></code>, that is they can be used as keys in containers such as <code>std::map</code> and <code>std::unordered_map</code>. An index is a model of the <code><a class="elRef" href="../STL_Extension/classIndex.html">Index</a></code> concept, which is mainly an integer which is convertible from and to std::size_t. Indices can be used as index into vectors which store properties (cf. one example in Section <a class="el" href="index.html#ssecexample3DCMWI">3D Combinatorial Map Using Indices</a>).</p>
<p><a class="anchor" id="fig__fig_cmap_diagramme_class"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_diagramme_class.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_diagramme_class">Figure 29.9</a> UML diagram of the main classes of the package. k is the number of non void attributes. </p> </div> <p> <br>
</p>
<h2><a class="anchor" id="sseccombinatorialmap"></a>
Combinatorial Maps</h2>
<p>The class <code><a class="el" href="classCGAL_1_1Combinatorial__map.html" title="The class Combinatorial_map represents a dD combinatorial map.">Combinatorial_map</a>&lt;d,Items,Alloc&gt;</code> is a model of the <code><a class="el" href="classCombinatorialMap.html" title="The concept CombinatorialMap defines a d-dimensional combinatorial map.">CombinatorialMap</a></code> concept which refines the generic concept of <code><a class="el" href="classGenericMap.html" title="The concept GenericMap defines a d-dimensional generic map. This concept is defined only to factorize...">GenericMap</a></code>. It has three template parameters standing for the dimension of the combinatorial map (an <code>unsigned int</code>), an items class (a model of the <code><a class="el" href="classGenericMapItems.html" title="The concept GenericMapItems allows to customize a dD generic map by choosing the information associat...">GenericMapItems</a></code> concept), and an allocator which must be a model of the allocator concept of the STL. Default classes are provided for the items and the allocator classes.</p>
<p>The main role of the class <code><a class="el" href="classCGAL_1_1Combinatorial__map.html" title="The class Combinatorial_map represents a dD combinatorial map.">Combinatorial_map</a></code> is the storage and the management of darts. It allows to create or remove an isolated dart from the combinatorial map. The <a class="el" href="classGenericMap.html#aa8c25f5c9ea2af0f7d13744aed8cbc8a"><code>Dart_descriptor</code></a> type defines a descriptor to the type of used darts (given in the items class). <code><a class="el" href="classCGAL_1_1Combinatorial__map.html" title="The class Combinatorial_map represents a dD combinatorial map.">Combinatorial_map</a></code> provides several <em>ranges</em> which allow to iterate over specific subsets of darts of the combinatorial map (see Section <a class="el" href="index.html#ssecrange">Iterating over Orbits, Cells, and Attributes</a>). It also defines several methods to link and to unlink darts by \( \beta_i\)s (see Section <a class="el" href="index.html#sseclinkdarts">Sewing Orbits and Linking Darts</a>). We said that a dart <em>d0</em> is <em>i</em>-free if \( \beta_i\)(<em>d0</em>)= \( \varnothing\). The \( \varnothing\) constant is represented in the class <code><a class="el" href="classCGAL_1_1Combinatorial__map.html" title="The class Combinatorial_map represents a dD combinatorial map.">Combinatorial_map</a></code> through a <code>Dart_descriptor</code> called <a class="el" href="classCombinatorialMap.html#ac84ba0cfc4de9f6caf6479b76d35c520"><code>null_dart_descriptor</code></a>. Finally, some high level operations are defined as global functions taking a <code><a class="el" href="classCGAL_1_1Combinatorial__map.html" title="The class Combinatorial_map represents a dD combinatorial map.">Combinatorial_map</a></code> as argument (see Section <a class="el" href="index.html#ssecoperations">Removal and Insertion Operations</a>)</p>
<p>The second role of the class <code><a class="el" href="classCGAL_1_1Combinatorial__map.html" title="The class Combinatorial_map represents a dD combinatorial map.">Combinatorial_map</a></code> is the storage and the management of attributes. It allows to create or remove an attribute, and provides methods to associate attributes and cells. A range is defined for each <em>i</em>-attribute allowing to iterate over all the <em>i</em>-attributes of the combinatorial map. Finally, <code><a class="el" href="classCGAL_1_1Combinatorial__map.html" title="The class Combinatorial_map represents a dD combinatorial map.">Combinatorial_map</a></code> defines several types allowing to manage the attributes. We can use <a class="el" href="classGenericMap.html#a6d4c52ca2bdf5965cba6b48fa2ccf0e4"><code>Combinatorial_map::Attribute_descriptor&lt;i&gt;::type</code></a> for a descriptor to the <em>i</em>-attributes (and the const version <a class="el" href="classGenericMap.html#a4f403052ae83b1d85efcc91e99e61fbd"><code>Combinatorial_map::Attribute_const_descriptor&lt;i&gt;::type</code> </a>) and <a class="el" href="classGenericMap.html#a01213a6b36324a8e006d18afc57fc551"><code>Combinatorial_map::Attribute_type&lt;i&gt;::type</code> </a> for the type of the <em>i</em>-attributes.</p>
<p>All information associated to darts (information, \( \beta\) links and attributes) are accessed through member functions in <code><a class="el" href="classCombinatorialMap.html" title="The concept CombinatorialMap defines a d-dimensional combinatorial map.">CombinatorialMap</a></code>.</p>
<h2><a class="anchor" id="ssecitem"></a>
Combinatorial Map Items</h2>
<p>The <code><a class="el" href="classGenericMapItems.html" title="The concept GenericMapItems allows to customize a dD generic map by choosing the information associat...">GenericMapItems</a></code> concept defines information associated with darts, and attribute types of a combinatorial map. It contains one inner class named <a class="el" href="classGenericMapItems.html#ae25d6c2751d48c79de9f92f106eed684"><code>Dart_wrapper</code></a>, having one template parameter, <code>Map</code>, a model of <code><a class="el" href="classGenericMap.html" title="The concept GenericMap defines a d-dimensional generic map. This concept is defined only to factorize...">GenericMap</a></code> concept. The <a class="el" href="classGenericMapItems.html#ae25d6c2751d48c79de9f92f106eed684"><code>Dart_wrapper&lt;Map&gt;</code></a> class can provide two local types: <code>Dart_info</code> for the information associated with darts, and <code>Attributes</code> which defines the attributes and their types.</p>
<p>If <code>Dart_info</code> is not defined or if it is equal to <code>void</code>, no information is associated with darts.</p>
<p>The <code>Attributes</code> tuple must contain at most <em>d</em>+1 types (one for each possible cell dimension of the combinatorial map). Each type of the tuple must be either a model of the <code><a class="el" href="classCellAttribute.html" title="The concept CellAttribute represents a non void attribute associated with a cell of a generic map....">CellAttribute</a></code> concept or <code>void</code>. The first type corresponds to 0-attributes, the second to 1-attributes and so on. If the <em>i <sup>th</sup></em> type in the tuple is <code>void</code>, <em>(i-1)</em>-attributes are disabled: we say that <em>(i-1)</em>-attributes are <em>void</em>. Otherwise, <em>(i-1)</em>-attributes are enabled and have the given type: we say <em>(i-1)</em>-attributes are <em>non void</em>. If the size of the tuple is <em>k</em>, with <em>k</em> \( &lt; \) <a class="el" href="classGenericMap.html#a3480ee52e53430cd773cbc941d7ad9e8"><code>dimension</code></a> +1, \( \forall \) <em>i</em>: <em>k</em> \( \leq \) <em>i</em> \( \leq \) <a class="el" href="classGenericMap.html#a3480ee52e53430cd773cbc941d7ad9e8"><code>dimension</code></a>, <em>i</em>-attributes are void. If this type is not defined, all attributes are disabled.</p>
<p>The class <code><a class="el" href="structCGAL_1_1Generic__map__min__items.html" title="The class Generic_map_min_items defines void as the information associated with darts,...">Generic_map_min_items</a></code> is a model of the <code><a class="el" href="classGenericMapItems.html" title="The concept GenericMapItems allows to customize a dD generic map by choosing the information associat...">GenericMapItems</a></code> concept which can be used for default behaviors. It defines <code>void</code> as type of information associated with darts, and <code>Attributes</code> as empty tuple.</p>
<h2><a class="anchor" id="ssecattributes"></a>
Cell Attributes</h2>
<p>The class <code><a class="el" href="classCGAL_1_1Cell__attribute.html" title="The class Cell_attribute represents an attribute containing (or not) an information.">Cell_attribute</a>&lt;Map,Info_,Tag,OnMerge,OnSplit&gt;</code>, a model of the <code><a class="el" href="classCellAttribute.html" title="The concept CellAttribute represents a non void attribute associated with a cell of a generic map....">CellAttribute</a></code> concept, represents an attribute associated with a cell of a combinatorial map. The template parameter <code>Map</code> must be a model of the <code><a class="el" href="classGenericMap.html" title="The concept GenericMap defines a d-dimensional generic map. This concept is defined only to factorize...">GenericMap</a></code> concept. The attribute stores a descriptor to one dart of its associated cell when the template parameter <code>Tag</code> is <a class="elRef" href="../STL_Extension/group__PkgSTLExtensionUtilities.html#gab3e2296107b5d26c32c8183028a217f1"><code>Tag_true</code></a>. <code>Info_</code> is the type of information stored in the attribute. It may be <code>void</code>. <code>OnMerge</code> and <code>OnSplit</code> must be either <code><a class="elRef" href="../STL_Extension/structCGAL_1_1Null__functor.html">Null_functor</a></code>, or models of the <code>Binary Function</code> concept having two references to a model of <code><a class="el" href="classCellAttribute.html" title="The concept CellAttribute represents a non void attribute associated with a cell of a generic map....">CellAttribute</a></code> as type of both parameters and <code>void</code> as return type. There are two default parameters for <code>OnMerge</code> and <code>OnSplit</code>, which are <code><a class="elRef" href="../STL_Extension/structCGAL_1_1Null__functor.html">Null_functor</a></code>, a default parameter for <code>Tag</code> which is <code>Tag_true</code>, and a default parameter for <code>Info_</code> which is <code>void</code>.</p>
<p>If <code>Info_</code> is different from <code>void</code>, the class <code><a class="el" href="classCGAL_1_1Cell__attribute.html" title="The class Cell_attribute represents an attribute containing (or not) an information.">Cell_attribute</a></code> contains two methods <code>info()</code> returning the information contained in the attribute (const and non const version). The information is returned by reference, thus the non const version allows the modification of the information.</p>
<p>Two attributes are merged when their corresponding cells are merged into one cell during some operation. In this case, the functor <code>OnMerge</code> is called, unless it is equal to <code><a class="elRef" href="../STL_Extension/structCGAL_1_1Null__functor.html">Null_functor</a></code>. This functor allows the user to define its own custom behavior when two attributes are merged (for example if the information is a color, we can compute the average color of the two initial attributes, and affect this value to the first attribute, see example in Section <a class="el" href="index.html#sseccombimapwithcolor">Combinatorial Map With Attributes</a>). Similarly, the functor <code>OnSplit</code> is called when one attribute is split in two, because its corresponding cell is split in two during some operation, unless it is equal to <code><a class="elRef" href="../STL_Extension/structCGAL_1_1Null__functor.html">Null_functor</a></code>. In any high level operation, <code>OnMerge</code> is called before to start the operation (i.e. before modifying the combinatorial map), and <code>OnSplit</code> is called when the operation is finished (i.e. after all the modifications were made).</p>
<p>In addition, there are dynamic onmerge and onsplit functions that can be associated to i-attributes, and modified, thanks to the <a class="el" href="classGenericMap.html#a78f64e84673b62c619c8ed8c15b01a6b"><code>onmerge_function()</code></a> and <a class="el" href="classGenericMap.html#a6274b69df80ba8488e6aa5f142a8e634"><code>onsplit_function()</code></a>. When these functions are set, they are also called in addition to the previous mechanism when two attributes are merged or one attribute is split into two (see example in Section <a class="el" href="index.html#sseccombimapdynamicattibute">Use of Dynamic Onmerge and Onsplit Functors</a>).</p>
<p>What we said for the dart also holds for the cell attribute. The combinatorial map can be used with any user defined model of the <code><a class="el" href="classCellAttribute.html" title="The concept CellAttribute represents a non void attribute associated with a cell of a generic map....">CellAttribute</a></code> concept.</p>
<h2><a class="anchor" id="ssecexampledef"></a>
Example of Combinatorial Map Definition</h2>
<p>Here comes an example of two combinatorial map definitions. The first case <code>Example_cmap4</code> defines a 4D combinatorial map which uses all the default values (<code><a class="el" href="structCGAL_1_1Generic__map__min__items.html" title="The class Generic_map_min_items defines void as the information associated with darts,...">Generic_map_min_items</a></code>). The second example <code>Example_custom_cmap3</code> uses its own model of the <code><a class="el" href="classGenericMapItems.html" title="The concept GenericMapItems allows to customize a dD generic map by choosing the information associat...">GenericMapItems</a></code> concept. In this model, a <code>double</code> is associated as information on darts, and an attribute containing an integer is associated to edges.</p>
<div class="fragment"><div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;4&gt;</a> Example_cmap4;</div>
<div class="line"> </div>
<div class="line"><span class="keyword">struct </span>Example_items_3</div>
<div class="line">{</div>
<div class="line">  <span class="keyword">template</span> &lt;<span class="keyword">class</span> CMap&gt;</div>
<div class="line">  <span class="keyword">struct </span>Dart_wrapper</div>
<div class="line">  {</div>
<div class="line">    <span class="keyword">typedef</span> <span class="keywordtype">double</span> Dart_info;</div>
<div class="line">    <span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Cell__attribute.html">CGAL::Cell_attribute&lt;CMap, int&gt;</a> Edge_attrib;</div>
<div class="line">    <span class="keyword">typedef</span> std::tuple&lt;void,Edge_attrib&gt; Attributes;</div>
<div class="line">  };</div>
<div class="line">};</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3, Example_items_3&gt;</a> Example_custom_cmap3;</div>
<div class="ttc" id="aclassCGAL_1_1Cell__attribute_html"><div class="ttname"><a href="classCGAL_1_1Cell__attribute.html">CGAL::Cell_attribute</a></div><div class="ttdoc">The class Cell_attribute represents an attribute containing (or not) an information.</div><div class="ttdef"><b>Definition:</b> Cell_attribute.h:26</div></div>
<div class="ttc" id="aclassCGAL_1_1Combinatorial__map_html"><div class="ttname"><a href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map</a></div><div class="ttdoc">The class Combinatorial_map represents a dD combinatorial map.</div><div class="ttdef"><b>Definition:</b> Combinatorial_map.h:39</div></div>
</div><!-- fragment --><h2><a class="anchor" id="ssecCMapIndicesHandles"></a>
Indices or Handles</h2>
<p>By default, descriptors used to access darts and attributes are handles, and the darts and attributes are stored in a <code><a class="elRef" href="../STL_Extension/classCGAL_1_1Compact__container.html">Compact_container</a></code>. To use the index version, you should define the type <code>Use_index</code> to <code><a class="elRef" href="../STL_Extension/group__PkgSTLExtensionUtilities.html#gab3e2296107b5d26c32c8183028a217f1">CGAL::Tag_true</a></code> in the item class like in the code below. You can also define the type <code>Index_type</code> used to store indices (<code>std::uint32_t</code> by default when this type is not defined).</p>
<div class="fragment"><div class="line"><span class="keyword">struct </span>Items_with_indices</div>
<div class="line">{</div>
<div class="line">  <span class="keyword">typedef</span> <a class="code hl_structRef" href="../STL_Extension/structCGAL_1_1Boolean__tag.html">CGAL::Tag_true</a> Use_index; <span class="comment">// CGAL::Tag_false by default</span></div>
<div class="line">  <span class="keyword">typedef</span> std::uint16_t Index_type; <span class="comment">// std::uint32_t by default</span></div>
<div class="line">  <span class="keyword">template</span> &lt;<span class="keyword">class</span> CMap&gt;</div>
<div class="line">  <span class="keyword">struct </span>Dart_wrapper</div>
<div class="line">  {</div>
<div class="line">    <span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Cell__attribute.html">CGAL::Cell_attribute&lt;CMap, int&gt;</a> Edge_attrib;</div>
<div class="line">    <span class="keyword">typedef</span> std::tuple&lt;void,Edge_attrib&gt; Attributes;</div>
<div class="line">  };</div>
<div class="line">};</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3, Items_with_indices&gt;</a> Cmap3_with_index;</div>
<div class="ttc" id="astructCGAL_1_1Boolean__tag_html"><div class="ttname"><a href="../STL_Extension/structCGAL_1_1Boolean__tag.html">CGAL::Boolean_tag</a></div></div>
</div><!-- fragment --><p>The two main interests of the index version comparing to the handle ones are: (1) it has a lower memory footprint than a 64-bit pointer based version; (2) indices are contiguous, they can be used as index into vectors which store properties. The main interest of the handle version is the fact that handles can be dereferenced, which can simplify some code.</p>
<h1><a class="anchor" id="Combinatorial_mapIteration"></a>
Iteration and Creation Operations</h1>
<p>An important operation in combinatorial maps consists in iterating over specific subsets of darts or over attributes. For that, several <em>ranges</em> are offered (see Section <a class="el" href="index.html#ssecrange">Iterating over Orbits, Cells, and Attributes</a>). A range is a model of the <code><a class="elRef" href="../Circulator/classRange.html">Range</a></code> concept, thus supporting the two methods <code>begin()</code> and <code>end()</code> allowing to iterate over all the elements in the range. Several functions allow to create specific configurations of darts into a combinatorial map (see Section <a class="el" href="index.html#ssecconstruction">Construction Operations</a>). Darts can be marked during operations, for example when performing a breadth-first search traversal, thanks to Boolean marks (see Sections <a class="el" href="index.html#ssecadvmarks">Boolean Marks</a>). In the following, we denote by <code>d0</code>, <code>d1</code>, <code>d2</code> for dart descriptors, and identify in explanations the descriptor and the object it describes.</p>
<h2><a class="anchor" id="ssecrange"></a>
Iterating over Orbits, Cells, and Attributes</h2>
<p>The combinatorial map offers iterators to traverse the darts of a specific orbit, to traverse all darts of one cell, or one dart per cell, and to traverse all <em>i</em>-attributes.</p>
<p>Instead of the <code>begin()/end()</code> member function pair as we know it from STL containers, and from most CGAL data structures, the combinatorial map defines range classes which are all models of the <code><a class="elRef" href="../Circulator/classRange.html">Range</a></code> concept.</p>
<p>There are three different categories of dart range classes: </p><ul>
<li>
<p class="startli"><a class="el" href="classGenericMap.html#a3f67e5f77a6a61281054ee9c1d619c58"><code>Dart_range</code></a>: range of all the darts of a combinatorial map;</p>
<p class="endli"></p>
</li>
<li>
<p class="startli"><a class="el" href="classGenericMap.html#abf73974dbf5e7d9e01c7d8912f58edd3"><code>Dart_of_orbit_range&lt;Beta...&gt;</code></a>: range of all the darts of the orbit \( \langle{}\)<code>Beta...</code> \( \rangle{}\)(<em>d0</em>) for a given <em>d0</em>. <code>Beta...</code> is a sequence of integers \( i_1\),..., \( i_k\), each \( i_j\) \( \in \){0, ..., <em>d</em>}. These integers must satisfy: \( i_1\) \( &lt;\) \( i_2\) \( &lt;\)... \( &lt;\) \( i_k\), and ( \( i_1\) \( \neq \) 0 or \( i_2 \) \( \neq \) 1) (for example <a class="el" href="classGenericMap.html#abf73974dbf5e7d9e01c7d8912f58edd3"><code>Dart_of_orbit_range&lt;1,2&gt;</code></a> for the orbit \( \langle{}\) \( \beta_1\), \( \beta_2\) \( \rangle{}\)(<em>d0</em>));</p>
<p class="endli"></p>
</li>
<li>
<a class="el" href="classGenericMap.html#ab598f5933eb3662863c2e33ae9320d93"><code>Dart_of_cell_range&lt;i,dim&gt;</code></a>: range of all the darts of the <em>i</em>-cell containing a given dart. The <em>i</em>-cell is considered in dimension <code>dim</code> (with 0 \(  \leq \) <em>dim</em> \( \leq \) <em>d</em>, <em>dim</em>=<em>d</em> by default), with 0 \( \leq \) <em>i</em> \( \leq \) <em>dim+1</em>. If <em>i</em>=<em>dim+1</em>, <a class="el" href="classGenericMap.html#ab598f5933eb3662863c2e33ae9320d93"><code>Dart_of_cell_range&lt;i,dim&gt;</code></a> is the range of all the darts of the connected component containing a given dart. </li>
</ul>
<p>There are also two different classes of ranges containing one dart per <em>i</em>-cell. Note that in these classes, the dart of each <em>i</em>-cell can be any dart of the cell. Moreover, each <em>i</em>-cell (and <em>j</em>-cell in the second case) is considered in dimension <code>dim</code> (with 0 \( \leq \) <em>dim</em> \( \leq \) <em>d</em>, <em>dim=d</em> by default). </p><ul>
<li>
<p class="startli"><a class="el" href="classGenericMap.html#ae9588233426a0e74848af1c8c79cede9"><code>One_dart_per_cell_range&lt;i,dim&gt;</code></a>: range containing one dart of each <em>i</em>-cell of the combinatorial map, 0 \( \leq \) <em>i</em> \( \leq \) <em>dim+1</em> (for example <a class="el" href="classGenericMap.html#ae9588233426a0e74848af1c8c79cede9"><code>One_dart_per_cell_range&lt;2&gt;</code></a> for the range of one dart per 2-cell of the combinatorial map);</p>
<p class="endli"></p>
</li>
<li>
<a class="el" href="classGenericMap.html#a6d6212f4fc539c0054a2cfc3387ca096"><code>One_dart_per_incident_cell_range&lt;i,j,dim&gt;</code></a>: range containing one dart of each <em>i</em>-cell incident to the <em>j</em>-cell containing a given dart, with 0 \( \leq \) <em>i</em> \( \leq \) <em>dim+1</em> and 0 \( \leq \) <em>j</em> \( \leq \) <em>dim+1</em> (for example <a class="el" href="classGenericMap.html#a6d6212f4fc539c0054a2cfc3387ca096"><code>One_dart_per_incident_cell_range&lt;0,3&gt;</code></a> for the range of one dart per vertex of the volume incident to the starting dart). If <em>i</em>=<em>j</em>, the range contains only the given dart. </li>
</ul>
<p>The iterators of the <a class="el" href="classGenericMap.html#a3f67e5f77a6a61281054ee9c1d619c58"><code>Dart_range</code></a> are bidirectional iterators, while the iterators of the other four ranges are forward iterators. The value type of all these iterators is <code>Dart</code> thus all these iterators can be directly used as <a class="el" href="classGenericMap.html#aa8c25f5c9ea2af0f7d13744aed8cbc8a"><code>Dart_descriptor</code></a>.</p>
<p>Additionally, there is a range over non void <em>i</em>-attributes: <a class="el" href="classGenericMap.html#ae567e6737eb1577fb34e43bb257d8776"><code>Attribute_range&lt;i&gt;::type</code></a>, having a bidirectional iterator with value type <a class="el" href="classGenericMap.html#a01213a6b36324a8e006d18afc57fc551"><code>Attribute_type&lt;i&gt;::type</code></a>.</p>
<p>For each range, there is an associated const range, a model of the <code><a class="elRef" href="../Circulator/classConstRange.html">ConstRange</a></code> concept. You can find some examples of ranges in Section <a class="el" href="index.html#ssecexample3DCM">A 3D Combinatorial Map</a>.</p>
<h2><a class="anchor" id="ssecconstruction"></a>
Construction Operations</h2>
<p>Several functions allow to create specific configurations of darts into a combinatorial map. Existing darts in the combinatorial map are not modified. Note that the dimension of the combinatorial map must be large enough: darts must contain all the \( \beta\) pointers used by the operation. All these functions return a <a class="el" href="classGenericMap.html#aa8c25f5c9ea2af0f7d13744aed8cbc8a"><code>Dart_descriptor</code></a> to a new dart created during the operation.</p>
<ul>
<li>
<code>cm.</code><a class="el" href="classGenericMap.html#a36761de5cfdf71157a7f12d328aabc18"><code>make_edge()</code></a>: creates an isolated edge (two darts linked by \( \beta_2\)); dimension must be greater or equal than two; </li>
<li>
<code>cm.</code><a class="el" href="classGenericMap.html#aeceb0c0e90e168d887358a3994d90b94"><code>make_combinatorial_polygon(lg)</code></a>: creates an isolated combinatorial polygon of length <code>lg</code> (<code>lg</code> darts linked by \( \beta_1\)), for <code>lg&gt;0</code>; dimension must be greater or equal than one; </li>
<li>
<code>cm.</code><a class="el" href="classGenericMap.html#a128310cc4302aae6438e6b83147c6f9c"><code>make_combinatorial_tetrahedron()</code></a>: creates an isolated combinatorial tetrahedron (four combinatorial triangles linked together by \( \beta_2\)); dimension must be greater or equal than two; </li>
<li>
<code>cm.</code><a class="el" href="classGenericMap.html#a05a72f31a317f85f41ed0f3522c56179"><code>make_combinatorial_hexahedron()</code></a>: creates an isolated combinatorial hexahedron (six combinatorial quadrangles linked together by \( \beta_2\)); dimension must be greater or equal than two. </li>
</ul>
<h2><a class="anchor" id="ssecadvmarks"></a>
Boolean Marks</h2>
<p>It is often necessary to mark darts, for example to retrieve in \(O(1)\) if a given dart was already processed during a specific algorithm, for example, iteration over a given range. Users can also mark specific parts of a combinatorial map (for example mark all the darts belonging to objects having specific semantics). To answer these needs, a <code><a class="el" href="classGenericMap.html" title="The concept GenericMap defines a d-dimensional generic map. This concept is defined only to factorize...">GenericMap</a></code> has a certain number of Boolean marks (fixed by the constant <a class="el" href="classGenericMap.html#a6e4ee8b525afeb9bbaed065623e26e68"><code>NB_MARKS</code></a>). When one wants to use a Boolean mark, the following methods are available (with <code>cm</code> an instance of a combinatorial map): </p><ul>
<li>
get a new free mark: <code>size_type m = cm.</code><a class="el" href="classGenericMap.html#a8c66e1d43055fe732354eedb0f1a780b"><code>get_new_mark()</code></a> (throws the exception Exception_no_more_available_mark if no mark is available); </li>
<li>
set mark <code>m</code> for a given dart <code>d0</code>: <code>cm.</code><a class="el" href="classGenericMap.html#a4a8768db94c131e7990d0c54a332a53d"><code>mark(d0,m)</code></a>; </li>
<li>
unset mark <code>m</code> for a given dart <code>d0</code>: <code>cm.</code><a class="el" href="classGenericMap.html#a6da9830c54d8bed8b9f259667b07b285"><code>unmark(d0,m)</code></a>; </li>
<li>
test if a given dart <code>d0</code> is marked for <code>m</code>: <code>cm.</code><a class="el" href="classGenericMap.html#ab0b8f232cc2cc1177e281f00b2c77478"><code>is_marked(d0,m)</code></a>; </li>
<li>
unmark all the darts of <code>cm</code> for <code>m</code>: <code>cm.</code><a class="el" href="classGenericMap.html#ab63ba9e899d2c231ba06a95030ecbd2e"><code>unmark_all(m)</code></a>; </li>
<li>
negate mark <code>m</code> of all the darts of <code>cm</code>: <code>cm.</code><a class="el" href="classGenericMap.html#a9996d3fe87eb7cb6ecaae192312eae89"><code>negate_mark(m)</code></a>. All the marked darts become unmarked and all the unmarked darts become marked; </li>
<li>
free mark <code>m</code>: <code>cm.</code><a class="el" href="classGenericMap.html#a7feb8a3d9e53f8c863acf3767886e4c2"><code>free_mark(m)</code></a>. This method unmarks all the darts of <code>cm</code> for <code>m</code> before freeing it. </li>
</ul>
<p>It is important to free a mark when it is no longer needed, otherwise you may at some point run out of marks.</p>
<p>The following example illustrates how to use marks. Two combinatorial tetrahedra are created and 3-sewn (see Section <a class="el" href="index.html#sseclinkdarts">Sewing Orbits and Linking Darts</a> for a detailed description of the sew operation). Then a mark is reserved and used to mark all the darts belonging to the first combinatorial tetrahedron. Finally, these tetrahedron are merged. The marks allow us to know which darts come from the first and second tetrahedron.</p>
<p><br>
<b>File</b> <a class="el" href="Combinatorial_map_2map_3_marks_8cpp-example.html">Combinatorial_map/map_3_marks.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;CGAL/Combinatorial_map.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;iostream&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cstdlib&gt;</span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3&gt;</a> CMap_3;</div>
<div class="line"><span class="keyword">typedef</span> CMap_3::Dart_descriptor Dart_descriptor;</div>
<div class="line"><span class="keyword">typedef</span> CMap_3::size_type size_type;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line">  CMap_3 cm;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 1) Reserve a mark.</span></div>
<div class="line">  size_type amark;</div>
<div class="line">  <span class="keywordflow">try</span></div>
<div class="line">  {</div>
<div class="line">    amark = cm.get_new_mark();</div>
<div class="line">  }</div>
<div class="line">  <span class="keywordflow">catch</span> (CMap_3::Exception_no_more_available_mark)</div>
<div class="line">  {</div>
<div class="line">    std::cerr&lt;&lt;<span class="stringliteral">"No more free mark, exit."</span>&lt;&lt;std::endl;</div>
<div class="line">    exit(-1);</div>
<div class="line">  }</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 2) Create two tetrahedra.</span></div>
<div class="line">  Dart_descriptor d1 = cm.make_combinatorial_tetrahedron();</div>
<div class="line">  Dart_descriptor d2 = cm.make_combinatorial_tetrahedron();</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 3) 3-sew them.</span></div>
<div class="line">  cm.sew&lt;3&gt;(d1, d2);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 4) Mark the darts belonging to the first tetrahedron.</span></div>
<div class="line">  <span class="keywordflow">for</span>  (CMap_3::Dart_of_cell_range&lt;3&gt;::iterator</div>
<div class="line">          it(cm.darts_of_cell&lt;3&gt;(d1).begin()),</div>
<div class="line">          itend(cm.darts_of_cell&lt;3&gt;(d1).end()); it!=itend; ++it)</div>
<div class="line">    cm.mark(it, amark);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 4) Remove the common 2-cell between the two cubes:</span></div>
<div class="line">  <span class="comment">//    the two tetrahedra are merged.</span></div>
<div class="line">  cm.remove_cell&lt;2&gt;(d1);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 5) Thanks to the mark, we know which darts come from the first tetrahedron.</span></div>
<div class="line">  <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> res=0;</div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::Dart_range::iterator it(cm.darts().begin()),</div>
<div class="line">         itend(cm.darts().end()); it!=itend; ++it)</div>
<div class="line">  {</div>
<div class="line">    <span class="keywordflow">if</span> ( cm.is_marked(it, amark) )</div>
<div class="line">      ++res;</div>
<div class="line">  }</div>
<div class="line"> </div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">"Number of darts from the first tetrahedron: "</span>&lt;&lt;res&lt;&lt;std::endl;</div>
<div class="line">  cm.free_mark(amark);</div>
<div class="line"> </div>
<div class="line">  <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
<div class="line"> </div>
</div><!-- fragment --><h1><a class="anchor" id="ssecmodoperations"></a>
Modification Operations</h1>
<p>Several operations allow to modify a given combinatorial map. There are two main categories of modification operations: </p><ul>
<li>
<a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277">Sew</a>, <a class="el" href="classCombinatorialMap.html#ad6912d5a7a5cde0dfd23e50ee9ceb8a9">link_beta</a>, <a class="el" href="classCombinatorialMap.html#a010d501010343a071acc8155bd8417b3">unsew</a> and <a class="el" href="classCombinatorialMap.html#a7fe978a29730008c2230972f7ac56a6b">unlink_beta</a> which modify some existing \( \beta\) pointers, without creating or removing darts (see Section <a class="el" href="index.html#sseclinkdarts">Sewing Orbits and Linking Darts</a>); </li>
<li>
Removal and insertion of cells which modify both darts and \( \beta\) pointers (see Section <a class="el" href="index.html#ssecoperations">Removal and Insertion Operations</a>). </li>
</ul>
<h2><a class="anchor" id="sseclinkdarts"></a>
Sewing Orbits and Linking Darts</h2>
<p>The <code><a class="el" href="classCombinatorialMap.html" title="The concept CombinatorialMap defines a d-dimensional combinatorial map.">CombinatorialMap</a></code> defines two groups of methods to modify the \( \beta\) pointers of existing darts.</p>
<p>The sew and unsew methods iterate over two orbits in order to link or unlink specific darts two by two. Intuitively, a <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;i&gt;</code></a> operation glues two <em>i</em>-cells by identifying two of their <em>(i-1)</em>-cells (see example in <a class="el" href="index.html#fig__fig_cmap_example_3d_sew">Figure 29.10</a> where <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;</code></a> is used to glue two 3-cells along one 2-cell). Reciprocally, a <a class="el" href="classCombinatorialMap.html#a010d501010343a071acc8155bd8417b3"><code>unsew&lt;i&gt;</code></a> operation un-glues two <em>i</em>-cells which were glued along one of their <em>(i-1)</em>-cells. These methods guarantee that given a valid combinatorial map and a possible operation we obtain a valid combinatorial map as result of the operation.</p>
 <div class="CGALAdvanced"> <div>Advanced</div> <p>The <a class="el" href="classCombinatorialMap.html#ad6912d5a7a5cde0dfd23e50ee9ceb8a9"><code>link_beta</code></a> and <a class="el" href="classCombinatorialMap.html#a7fe978a29730008c2230972f7ac56a6b"><code>unlink_beta</code></a> methods only modify the pointer of two darts: the obtained combinatorial maps may be not valid. These operations can be useful to use low level operations in a specific algorithm, for example to modify locally a combinatorial map in a really fast way. In such a case, additional operations may be needed to restore the validity conditions. </p> </div> <p>Linking two darts <em>d1</em> and <em>d2</em> by \( \beta_i\), with 2 \( \leq \) <em>i</em> \( \leq \) <em>d</em> and <em>d1</em> \( \neq \) <em>d2</em>, consists in modifying two \( \beta_i\) pointers such that \( \beta_i\)(<em>d1</em>)=<em>d2</em> and \( \beta_i\)(<em>d2</em>)=<em>d1</em>. For <em>i</em>=1, the modification is \( \beta_1\)(<em>d1</em>)=<em>d2</em> (and thus \( \beta_0\)(<em>d2</em>)=<em>d1</em> by definition of \( \beta_0\)); in this case we can have <em>d1=d2</em> (a dart linked with itself corresponds to an edge which is a loop).</p>
<p>Reciprocally, unlinking a given dart <em>d0</em> by \( \beta_i\), with 2 \( \leq \) <em>i</em> \( \leq \) <em>d</em>, consists in modifying two \( \beta_i\) pointers such that \( \beta_i\)( \( \beta_i\)(<em>d0</em>))= \( \varnothing\) and \( \beta_i\)(<em>d0</em>)= \( \varnothing\). For <em>i=1</em>, the modification is \( \beta_1\)(<em>d0</em>)= \( \varnothing\) (and thus \( \beta_0\)( \( \beta_1\)(<em>d0</em>))= \( \varnothing\) by definition of \( \beta_0\)). Note that is it possible to unlink a given dart for \( \beta_i\) only if it is not <em>i</em>-free.</p>
<p><a class="anchor" id="fig__fig_cmap_example_3d_sew"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_example_3d_sew.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_example_3d_sew">Figure 29.10</a> Example of 3-sew operation. Left: A 3D combinatorial map containing two volumes that are not connected, with 2-attributes. Each attribute contains a color in RGB format, and there are four 2-cells associated with attributes. Associations between darts and attributes are drawn with red segments. Right: The 3D combinatorial map obtained as result of <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;(1,5)</code></a> (or <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;(2,8)</code></a>, or <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;(3,7)</code></a>, or <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;(4,6)</code></a>). Darts (1,5), (2,8), (3,7) and (4,6) are linked together by \( \beta_3\). The two 2-cells <em>c1</em>={1,2,3,4} and <em>c2</em>={5,6,7,8} are merged after the sew into the 2-cell {1,2,3,4,5,6,7,8}. We are in the case where the two attributes are non <code>nullptr</code>, thus the first one is kept, and all the darts of <em>c2</em> are associated with the first attribute. </p> </div> <p> <br>
</p>
<p>The <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;i&gt;(d1,d2)</code></a> method consists mainly to link two by two several darts by \( \beta_i\). This operation is possible only if there is a bijection <em>f</em> between all the darts of the orbit <em>D1</em>= \( \langle{}\) \( \beta_1\),..., \( \beta_{i-2}\), \( \beta_{i+2}\),..., \( \beta_d\) \( \rangle{}\)(<em>d1</em>) and <em>D2</em>= \( \langle{}\) \( \beta_1\),..., \( \beta_{i-2}\), \( \beta_{i+2}\),..., \( \beta_d\) \( \rangle{}\)(<em>d2</em>) satisfying: <em>f</em>(<em>d1</em>)=<em>d2</em>, and for all <em>e</em> \( \in \) <em>D1</em>, for all <em>j</em> \( \in \){1,..., i-2,i+2,...,<em>d</em>}, <em>f</em>( \( \beta_j\)(<em>e</em>))= \( \beta_j^{-1}\)(<em>f</em>(<em>e</em>)). Intuitively, this condition ensures the validity of the combinatorial map by verifying that condition discussed in Section <a class="el" href="index.html#sseccombimapvalidity">Combinatorial Map Properties</a> will be satisfied after the operation. This condition can be tested by using the method <a class="el" href="classCombinatorialMap.html#acd460e597c9690587d5c19d01edc38d6"><code>is_sewable&lt;i&gt;(d1,d2)</code></a>. For example, the function <a class="el" href="classCombinatorialMap.html#acd460e597c9690587d5c19d01edc38d6"><code>is_sewable&lt;3&gt;</code></a> would return <code>false</code> if we tried to 3-sew a triangular facet with a quad facet. Note that given two darts <em>d1</em> and <em>d2</em>, if there is such a bijection, it is uniquely defined. So giving the two darts as arguments of the <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;i&gt;</code></a> is enough to retrieve all the pairs of darts to link. If such a bijection exists, the <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;i&gt;(d1,d2)</code></a> operation consists only in linking by \( \beta_i\) each couple of darts <em>d3</em> and <em>d4</em> such that <em>d3</em>=<em>f</em>(<em>d4</em>).</p>
<p>In addition, the sew operation updates the associations between darts and non void attributes in order to guarantee that all the darts belonging to a given cell are associated with the same attribute (which is a condition of combinatorial map validity). For each couple of <em>j</em>-cells <em>c1</em> and <em>c2</em> that are merged into one <em>j</em>-cell during the sew, we have to update the two associated attributes <em>attr1</em> and <em>attr2</em>. If both are <code>nullptr</code>, there is nothing to do. If one is <code>nullptr</code> and the other not, we only associate the non <code>nullptr</code> attribute to all the darts of the resulting cell. When the two attributes are non <code>nullptr</code>, we first apply functor <a class="el" href="classCellAttribute.html#a31081515f9da08876797a998f7199b27"><code>On_merge</code></a> on the two attributes <em>attr1</em> and <em>attr2</em> (see Section <a class="el" href="index.html#ssecattributes">Cell Attributes</a>). Then, we associate the attribute <em>attr1</em> to all darts of the resulting <em>j</em>-cell. Finally, attribute <em>attr2</em> is removed from the combinatorial map.</p>
<p>Note that when the two attributes are non <code>nullptr</code>, the first one is kept. But user can customize this behavior in order to update the information contained in the attributes according to its needs. For that, we can define a specific functor, and use it as template argument for <a class="el" href="classCellAttribute.html#a31081515f9da08876797a998f7199b27"><code>On_merge</code></a> parameter of the <code><a class="el" href="classCGAL_1_1Cell__attribute.html" title="The class Cell_attribute represents an attribute containing (or not) an information.">Cell_attribute</a></code> definition. This functor can for example copy the information of the second attribute in the information of the first one to make as if the second attribute is kept.</p>
<p>For example, in <a class="el" href="index.html#fig__fig_cmap_example_3d_sew">Figure 29.10</a>, we want to 3-sew the two initial volumes. <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;(1,5)</code></a> links by \( \beta_3\) the pairs of darts (1,5), (2,8), (3,7) and (4,6), thus the combinatorial map obtained is valid. 2-attributes are updated so that all the darts belonging to the 2-cell containing dart 1 become associated to the same 2-attribute after the operation.</p>
<p>Similarly, <a class="el" href="classCombinatorialMap.html#a010d501010343a071acc8155bd8417b3"><code>unsew&lt;i&gt;(d0)</code></a> operation unlinks \( \beta_i\) for all the darts in the orbit \( \langle{}\) \( \beta_1\),..., \( \beta_{i-2}\), \( \beta_{i+2}\),..., \( \beta_d\) \( \rangle{}\)(<em>d0</em>), and thus guarantees to obtain a valid combinatorial map. This operation is possible for any non <em>i</em>-free dart.</p>
<p>As for the sew operations, attributes are updated to guarantee that two darts belonging to two different <em>j</em>-cells are associated to two different <em>j</em>-attributes. If the unsew operation splits a <em>j</em>-cell <em>c</em> in two <em>j</em>-cells <em>c1</em> and <em>c2</em>, and if <em>c</em> is associated to a <em>j</em>-attribute <em>attr1</em>, then this attribute is duplicated into <em>attr2</em>, and all the darts belonging to <em>c2</em> are associated with this new attribute. Finally, we call the functor <a class="el" href="classCellAttribute.html#a3b4b722747fa2e6f52331bf92ea4f92f"><code>On_split</code></a> on the two attributes <em>attr1</em> and <em>attr2</em> (see Section <a class="el" href="index.html#ssecattributes">Cell Attributes</a>).</p>
<p>Let us consider the combinatorial map given in <a class="el" href="index.html#fig__fig_cmap_example_3d_sew">Figure 29.10</a> (Right). If we call <a class="el" href="classCombinatorialMap.html#a010d501010343a071acc8155bd8417b3"><code>unsew&lt;3&gt;(2)</code></a>, we obtain the combinatorial map in <a class="el" href="index.html#fig__fig_cmap_example_3d_sew">Figure 29.10</a> (Left) (except for the color of the attribute associated to the 2-cell {5,6,7,8} which would be <code>#00ff00</code>). The <a class="el" href="classCombinatorialMap.html#a010d501010343a071acc8155bd8417b3"><code>unsew&lt;3&gt;</code></a> operation has duplicated the 2-attribute associated to the 2-cell {1,2,3,4,5,6,7,8} since this 2-cell is split in two after the unsew operation.</p>
 <div class="CGALAdvanced"> <div>Advanced</div> <p>If one wants to modify a combinatorial map <em>manually</em>, it is possible to switch off the updating between darts and attributes by calling <a class="el" href="classGenericMap.html#af7fcbe383d43efece8525654b45741bf"><code>set_automatic_attributes_management(false)</code></a> before to call <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;i&gt;(d1,d2)</code></a> and <a class="el" href="classCombinatorialMap.html#a010d501010343a071acc8155bd8417b3"><code>unsew&lt;i&gt;(d0)</code></a>. In these cases, the combinatorial map obtained may be no longer valid due to incorrect associations between darts and attributes. A call later to <a class="el" href="classGenericMap.html#af7fcbe383d43efece8525654b45741bf"><code>set_automatic_attributes_management(true)</code></a> will correct the invalid non void attributes.</p>
<p>In <a class="el" href="index.html#fig__fig_cmap_example_3d_sew">Figure 29.10</a> (Left), if we call <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;(1,5)</code></a>, the resulting combinatorial map is similar to the combinatorial map of <a class="el" href="index.html#fig__fig_cmap_example_3d_sew">Figure 29.10</a> (Right) (we have linked by \( \beta_3\) the pairs of darts (1,5), (2,8), (3,7) and (4,6)), but associations between darts and attributes are not valid. Indeed, we have kept the four initial attributes and all the associations between darts and attributes, thus two darts belonging to the same 2-cell (for example darts 1 and 5) are associated with two different attributes.</p>
<p>We can also use the <a class="el" href="classCombinatorialMap.html#ad6912d5a7a5cde0dfd23e50ee9ceb8a9"><code>link_beta&lt;i&gt;(d1,d2)</code></a> which links <code>d1</code> and <code>d2</code> by \( \beta_i\) without modifying the other links. Association between darts and attributes are only modified for darts <code>d1</code> and <code>d2</code>, and similarly as for <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;i&gt;</code></a>, this updating can be avoided by calling <a class="el" href="classGenericMap.html#af7fcbe383d43efece8525654b45741bf"><code>set_automatic_attributes_management(false)</code></a> before to call <a class="el" href="classCombinatorialMap.html#ad6912d5a7a5cde0dfd23e50ee9ceb8a9"><code>link_beta&lt;i&gt;(d1,d2)</code></a>. Lastly, we can use <a class="el" href="classCombinatorialMap.html#a7fe978a29730008c2230972f7ac56a6b"><code>unlink_beta&lt;i&gt;(d0)</code></a> to unlink <code>d0</code> for \( \beta_i\). In this last case, there is no modification of association between darts and attributes.</p>
<p>In <a class="el" href="index.html#fig__fig_cmap_example_3d_sew">Figure 29.10</a> (Left), if we call <a class="el" href="classCombinatorialMap.html#ad6912d5a7a5cde0dfd23e50ee9ceb8a9"><code>link_beta&lt;3&gt;(1,5)</code></a>, in the resulting combinatorial map we have now \( \beta_3\)(1)=5 and \( \beta_3\)(5)=1. This combinatorial map is no longer valid (for example dart 2 is 3-free and we should have \( \beta_3\)(2)=8). </p> </div> <h2><a class="anchor" id="ssecoperations"></a>
Removal and Insertion Operations</h2>
<p>The following high level operations are defined. All these methods ensure that given a valid combinatorial map and a possible operation, the modified combinatorial map is also valid.</p>
<p>The first one is <code>cm.</code><a class="el" href="classGenericMap.html#a05eceea6b822faf2e1f8105b6dea6839"><code>remove_cell&lt;i&gt;(d0)</code></a> which modifies the combinatorial map to remove the <em>i</em>-cell containing dart <code>d0</code>, with 0 \( \leq \) <em>i</em> \( \leq \) <em>d</em>. This operation is possible if <em>i</em>=<em>d</em> or if the given <em>i</em>-cell is incident to at most two <em>(i+1)</em>-cells which can be tested thanks to <code>cm.</code><a class="el" href="classGenericMap.html#a1e69dc8444a93599084cc5bb41df56f3"><code>is_removable&lt;i&gt;(d0)</code></a>. If the removed <em>i</em>-cell was incident to two different <em>(i+1)</em>-cells, these two cells are merged into one <em>(i+1)</em>-cell. In this case, the <a class="el" href="classCellAttribute.html#a31081515f9da08876797a998f7199b27"><code>On_merge</code></a> functor is called if two <em>(i+1)</em>-attributes are associated to the two <em>(i+1)</em>-cells. If the <em>i</em>-cell is associated with a non void attribute, it is removed from the combinatorial map (see three examples on <a class="el" href="index.html#fig__fig_cmap_insert_vertex">Figure 29.11</a>, <a class="el" href="index.html#fig__fig_cmap_insert_edge">Figure 29.13</a> and <a class="el" href="index.html#fig__fig_cmap_insert_facet">Figure 29.14</a>).</p>
<p><a class="anchor" id="fig__fig_cmap_insert_vertex"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_insert_vertex.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_insert_vertex">Figure 29.11</a> Example of <a class="el" href="classGenericMap.html#a952f7336e4ec9e54704c2c787172c76f"><code>insert_cell_0_in_cell_1</code></a> and <a class="el" href="classGenericMap.html#a05eceea6b822faf2e1f8105b6dea6839"><code>remove_cell&lt;0&gt;</code></a> operations. Left: Initial combinatorial map. Right: After the insertion of a 0-cell in the 1-cell containing dart <code>d1</code>. Now if we remove the 0-cell containing dart <code>d2</code>, we obtain the initial combinatorial map. </p> </div> <p> <br>
</p>
<p>The inverse operation of the removal is the insertion operation. Several versions exist, sharing a common principle. They consist in adding a new <em>i</em>-cell <em>inside</em> an existing <em>j</em>-cell, <em>i</em> \( &lt;\)<em>j</em>, by splitting the <em>j</em>-cell into several <em>j</em>-cells. Contrary to <code>remove_cell&lt;i&gt;</code>, is it not possible to define a unique <code>insert_cell_i_in_cell_j&lt;i,j&gt;</code> function because parameters are different depending on <code>i</code> and <code>j</code>.</p>
<p><code>cm.</code><a class="el" href="classGenericMap.html#a952f7336e4ec9e54704c2c787172c76f"><code>insert_cell_0_in_cell_1(d0)</code></a> adds a 0-cell in the 1-cell containing dart <code>d0</code>. The 1-cell is split in two. This operation is possible if <code>d0</code> \( \in \) <a class="el" href="classGenericMap.html#a584baf3448de6df4a78bc2081b7dacf4"><code>cm.darts()</code></a> (see example on <a class="el" href="index.html#fig__fig_cmap_insert_vertex">Figure 29.11</a>).</p>
<p><code>cm.</code><a class="el" href="classGenericMap.html#a5ad8a7e3bdee15f1d8c63f6ac1e4ec7c"><code>insert_cell_0_in_cell_2(d0)</code></a> adds a 0-cell in the 2-cell containing dart <code>d0</code>. The 2-cell is split in triangles, one for each initial edge of the facet. This operation is possible if <code>d0</code> \( \in \) <a class="el" href="classGenericMap.html#a584baf3448de6df4a78bc2081b7dacf4"><code>cm.darts()</code></a> (see example on <a class="el" href="index.html#fig__fig_cmap_triangulation">Figure 29.12</a>).</p>
<p><a class="anchor" id="fig__fig_cmap_triangulation"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_triangulation.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_triangulation">Figure 29.12</a> Example of <a class="el" href="classGenericMap.html#a5ad8a7e3bdee15f1d8c63f6ac1e4ec7c"><code>insert_cell_0_in_cell_2</code></a> operation. </p> </div> <p> <br>
</p>
<p><code>cm.</code><a class="el" href="classGenericMap.html#a66719c2a8394b7aceffe731a78c0e180"><code>insert_cell_1_in_cell_2(d1,d2)</code></a> adds a 1-cell in the 2-cell containing darts <code>d1</code> and <code>d2</code>, between the two 0-cells containing darts <code>d1</code> and <code>d2</code>. The 2-cell is split in two. This operation is possible if <em>d1</em> \( \in \) \( \langle{}\) \( \beta_1\) \( \rangle{}\)(<em>d2</em>) which can be tested thanks to <code>cm.</code><a class="el" href="classGenericMap.html#a9d10b927daef2313ff6e19e9aa6abb15"><code>is_insertable_cell_1_in_cell_2(d1,d2)</code></a>. In the example on <a class="el" href="index.html#fig__fig_cmap_insert_edge">Figure 29.13</a>, it is possible to insert an edge between darts <em>d2</em> and <em>d3</em>, but it is not possible to insert an edge between <em>d1</em> and <em>d3</em>.</p>
<p><a class="anchor" id="fig__fig_cmap_insert_edge"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_insert_edge.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_insert_edge">Figure 29.13</a> Example of <a class="el" href="classGenericMap.html#a66719c2a8394b7aceffe731a78c0e180"><code>insert_cell_1_in_cell_2</code></a> and <a class="el" href="classGenericMap.html#a05eceea6b822faf2e1f8105b6dea6839"><code>remove_cell&lt;1&gt;</code></a> operations. Left: Initial combinatorial map. Right: After the insertion of two 1-cells: a first one between the two 0-cells containing darts <code>d2</code> and <code>d3</code>, and a second one incident to the 0-cell containing dart <code>d1</code>. Now if we remove the two 1-cells containing darts <code>d4</code> and <code>d5</code>, we obtain the initial combinatorial map. </p> </div> <p> <br>
</p>
<p><code>cm.</code><a class="el" href="classGenericMap.html#aae94bd088e2b657780727c8ea91e6b45"><code>insert_dangling_cell_1_in_cell_2(d0)</code></a> adds a 1-cell in the 2-cell containing dart <code>d0</code>, the 1-cell being attached by only one of its vertex to the 0-cell containing dart <code>d0</code>. This operation is possible if <code>d0</code> \( \in \) <a class="el" href="classGenericMap.html#a584baf3448de6df4a78bc2081b7dacf4"><code>cm.darts()</code></a>.</p>
<p><code>cm.</code><a class="el" href="classGenericMap.html#aa29570a0812094c7876e24a228373f12"><code>insert_cell_1_between_two_cells_2(d1,d2)</code></a> adds a 1-cell between the two faces containing containing darts <code>d1</code> and <code>d2</code>, between the two 0-cells containing darts <code>d1</code> and <code>d2</code>. The 2-cells are merged in one. This operation is possible if <em>d1</em> \( \not \in \) \( \langle{}\) \( \beta_1\) \( \rangle{}\)(<em>d2</em>) which can be tested thanks to <code>cm.</code><a class="el" href="classGenericMap.html#ac7c32df255c4adf227ad02e0c5567bf1"><code>is_insertable_cell_1_between_two_cells_2(d1,d2)</code></a>.</p>
<p><code>cm.</code><a class="el" href="classGenericMap.html#a4dccb224e80ed640445ce8a5ce564099"><code>insert_cell_2_in_cell_3(itbegin,itend)</code></a> adds a 2-cell in the 3-cell containing all the darts between <code>itbegin</code> and <code>itend</code>, along the path of 1-cells containing darts in [<code>itbegin</code>,<code>itend</code>). The 3-cell is split in two. This operation is possible if all the darts in [<code>itbegin</code>,<code>itend</code>) form a closed path inside a same 3-cell which can be tested thanks to <code>cm.</code><a class="el" href="classGenericMap.html#ab7cf6baf7cfeb73597a1e4be4df5ec36"><code>is_insertable_cell_2_in_cell_3(itbegin,itend)</code></a> (see example on <a class="el" href="index.html#fig__fig_cmap_insert_facet">Figure 29.14</a>).</p>
<p><a class="anchor" id="fig__fig_cmap_insert_facet"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_insert_facet.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_insert_facet">Figure 29.14</a> Example of <a class="el" href="classGenericMap.html#a4dccb224e80ed640445ce8a5ce564099"><code>insert_cell_2_in_cell_3</code></a> and <a class="el" href="classGenericMap.html#a05eceea6b822faf2e1f8105b6dea6839"><code>remove_cell&lt;2&gt;</code></a> operations. Left: Initial combinatorial map. Right: After the insertion of a 2-cell along the path of 1-cells containing respectively <code>d1,d2,d3,d4</code>. Now if we remove the 2-cell containing dart <code>d5</code>, we obtain the initial combinatorial map. </p> </div> <p> <br>
</p>
<p>Some examples of use of these operations are given in Section <a class="el" href="index.html#ssecexempleoperations">High Level Operations</a>.</p>
 <div class="CGALAdvanced"> <div>Advanced</div> <p>If <a class="el" href="classGenericMap.html#af7fcbe383d43efece8525654b45741bf"><code>set_automatic_attributes_management(false)</code></a> is called, all the future insertion or removal operations will not update non void attributes. These attributes will be updated later by the call to <a class="el" href="classGenericMap.html#af7fcbe383d43efece8525654b45741bf"><code>set_automatic_attributes_management(true)</code></a>. This can be useful to speed up an algorithm which uses several successive insertion and removal operations. See example <a class="elRef" href="../Linear_cell_complex/index.html#ssecAttributesManagement">Automatic attributes management</a>. </p> </div> <h1><a class="anchor" id="Combinatorial_mapExamples"></a>
Examples</h1>
<h2><a class="anchor" id="ssecexample3DCM"></a>
A 3D Combinatorial Map</h2>
<p>In this example, a 3-dimensional combinatorial map is constructed. Two combinatorial tetrahedra are created, then the numbers of cells of the combinatorial map are displayed, and the validity of the combinatorial map is checked. Then, we illustrate the use of ranges to iterate over specific darts. The first loop enumerates all the darts of the first tetrahedron by using the range <a class="el" href="classGenericMap.html#abf73974dbf5e7d9e01c7d8912f58edd3"><code>Dart_of_orbit_range&lt;1,2&gt;</code></a>, and the second loop enumerates all the darts of the facet containing dart <code>d2</code> by using the range <a class="el" href="classGenericMap.html#abf73974dbf5e7d9e01c7d8912f58edd3"><code>Dart_of_orbit_range&lt;1&gt;</code></a>.</p>
<p><br>
<b>File</b> <a class="el" href="Combinatorial_map_2map_3_simple_example_8cpp-example.html">Combinatorial_map/map_3_simple_example.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;CGAL/Combinatorial_map.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;iostream&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cstdlib&gt;</span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3&gt;</a> CMap_3;</div>
<div class="line"><span class="keyword">typedef</span> CMap_3::Dart_const_descriptor Dart_const_descriptor;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line">  CMap_3 cm;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Create two tetrahedra.</span></div>
<div class="line">  Dart_const_descriptor d1 = cm.make_combinatorial_tetrahedron();</div>
<div class="line">  Dart_const_descriptor d2 = cm.make_combinatorial_tetrahedron();</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Display the combinatorial map characteristics.</span></div>
<div class="line">  cm.display_characteristics(std::cout);</div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">", valid="</span>&lt;&lt;cm.is_valid()&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> res = 0;</div>
<div class="line">  <span class="comment">// Iterate over all the darts of the first tetrahedron.</span></div>
<div class="line">  <span class="comment">// Note that CMap_3::Dart_of_orbit_range&lt;1,2&gt; in 3D is equivalent to</span></div>
<div class="line">  <span class="comment">// CMap_3::Dart_of_cell_range&lt;3&gt;.</span></div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::Dart_of_orbit_range&lt;1,2&gt;::const_iterator</div>
<div class="line">       it(cm.darts_of_orbit&lt;1,2&gt;(d1).begin()),</div>
<div class="line">       itend(cm.darts_of_orbit&lt;1,2&gt;(d1).end()); it!=itend; ++it)</div>
<div class="line">    ++res;</div>
<div class="line"> </div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">"Number of darts of the first tetrahedron: "</span>&lt;&lt;res&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  res = 0;</div>
<div class="line">  <span class="comment">// Iterate over all the darts of the facet containing d2.</span></div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::Dart_of_orbit_range&lt;1&gt;::const_iterator</div>
<div class="line">       it(cm.darts_of_orbit&lt;1&gt;(d2).begin()),</div>
<div class="line">       itend(cm.darts_of_orbit&lt;1&gt;(d2).end()); it!=itend; ++it)</div>
<div class="line">    ++res;</div>
<div class="line"> </div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">"Number of darts of the facet containing d2: "</span>&lt;&lt;res&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
<div class="line"> </div>
</div><!-- fragment --><p>The output is: </p><pre class="fragment">#Darts=24, #0-cells=8, #1-cells=12, #2-cells=8, #3-cells=2, #ccs=2, valid=1
Number of darts of the first tetrahedron: 12
Number of darts of the facet containing d2: 3
</pre><p>which gives the number of darts of the combinatorial map, the numbers of different cells, the number of connected components, and finally a Boolean showing the validity of the combinatorial map (a tetrahedron is made up of 12 darts because there are 3 darts per facet and there are 4 facets).</p>
<p>Note the creation in the for loops of the two instances of <a class="el" href="classGenericMap.html#abf73974dbf5e7d9e01c7d8912f58edd3"><code>Dart_of_orbit_range</code></a>::<code>const_iterator</code>: <code>it</code> is the current iterator, and <code>itend</code> an iterator to the end of the range. Having <code>itend</code> avoids calling <a class="el" href="classGenericMap.html#add641c506b6ad44b3165c5116eb83946"><code>cm.darts_of_orbit&lt;1,2&gt;(d1)</code></a><code>.end()</code> again and again as in the following example (which is a bad solution):</p>
<div class="fragment"><div class="line"><span class="keywordflow">for</span> (CMap_3::Dart_of_orbit_range&lt;1,2&gt;::const_iterator</div>
<div class="line">     it(cm.darts_of_orbit&lt;1,2&gt;(d1).begin());</div>
<div class="line">     it!=cm.darts_of_orbit&lt;1,2&gt;(d1).end()); ++it)</div>
<div class="line">{...}</div>
</div><!-- fragment --><h2><a class="anchor" id="Combinatorial_mapHighLevelOperations"></a>
High Level Operations</h2>
<p><a class="anchor" id="ssecexempleoperations"></a> This example shows some uses of high level operations. First we create a combinatorial hexahedron, the combinatorial map obtained is shown in <a class="el" href="index.html#fig__fig_cmap_example_insertions">Figure 29.15</a> (Left). Then we insert two 1-cells along two opposite 2-cells of the hexahedron. The combinatorial map obtained is shown in <a class="el" href="index.html#fig__fig_cmap_example_insertions">Figure 29.15</a> (Middle). Finally, we insert a 2-cell in the diagonal of the hexahedron in order to split it into two parts. We obtain the combinatorial map shown in <a class="el" href="index.html#fig__fig_cmap_example_insertions">Figure 29.15</a> (Right). We display the characteristics of the combinatorial map and check its validity.</p>
<p>The second part of this example removes the inserted elements. First we remove the inserted 2-cell, then the two inserted 1-cells. We get back the initial combinatorial hexahedron, which is verified by displaying once again the characteristics of the combinatorial map.</p>
<p><br>
<b>File</b> <a class="el" href="Combinatorial_map_2map_3_operations_8cpp-example.html">Combinatorial_map/map_3_operations.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;CGAL/Combinatorial_map.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;iostream&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cstdlib&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cassert&gt;</span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3&gt;</a> CMap_3;</div>
<div class="line"><span class="keyword">typedef</span> CMap_3::Dart_descriptor    Dart_descriptor;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line">  CMap_3 cm;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Create one combinatorial hexahedron.</span></div>
<div class="line">  Dart_descriptor d1 = cm.make_combinatorial_hexahedron();</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Add two edges along two opposite facets.</span></div>
<div class="line">  assert( cm.is_insertable_cell_1_in_cell_2</div>
<div class="line">          (cm.beta(d1,1),cm.beta(d1,0)) );</div>
<div class="line"> </div>
<div class="line">  cm.insert_cell_1_in_cell_2(cm.beta(d1,1), cm.beta(d1,0));</div>
<div class="line">  assert( cm.is_valid() );</div>
<div class="line"> </div>
<div class="line">  Dart_descriptor d2=cm.beta(d1,2,1,1,2);</div>
<div class="line"> </div>
<div class="line">  assert( cm.is_insertable_cell_1_in_cell_2</div>
<div class="line">          (d2,cm.beta(d2,1,1)) );</div>
<div class="line"> </div>
<div class="line">  cm.insert_cell_1_in_cell_2(d2, cm.beta(d2,1,1));</div>
<div class="line">  assert( cm.is_valid() );</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Insert a facet along these two new edges plus two initial edges</span></div>
<div class="line">  <span class="comment">// of the hexahedron.</span></div>
<div class="line">  std::vector&lt;Dart_descriptor&gt; path;</div>
<div class="line">  path.push_back(cm.beta(d1,1));</div>
<div class="line">  path.push_back(cm.beta(d1,0,2,1));</div>
<div class="line">  path.push_back(cm.beta(d2,0));</div>
<div class="line">  path.push_back(cm.beta(d2,2,1));</div>
<div class="line"> </div>
<div class="line">  assert( (cm.is_insertable_cell_2_in_cell_3</div>
<div class="line">                               (path.begin(),path.end())) );</div>
<div class="line"> </div>
<div class="line">  Dart_descriptor d3=cm.insert_cell_2_in_cell_3(path.begin(),path.end());</div>
<div class="line">  assert( cm.is_valid() );</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Display the combinatorial map characteristics.</span></div>
<div class="line">  cm.display_characteristics(std::cout) &lt;&lt; <span class="stringliteral">", valid="</span> &lt;&lt;</div>
<div class="line">    cm.is_valid() &lt;&lt; std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// We use the removal operations to get back to the initial hexahedron.</span></div>
<div class="line">  assert( (cm.is_removable&lt;2&gt;(d3)) );</div>
<div class="line">  cm.remove_cell&lt;2&gt;(d3);</div>
<div class="line">  assert( cm.is_valid() );</div>
<div class="line"> </div>
<div class="line">  assert( (cm.is_removable&lt;1&gt;(cm.beta(d1,1))) );</div>
<div class="line">  cm.remove_cell&lt;1&gt;(cm.beta(d1,1));</div>
<div class="line">  assert( cm.is_valid() );</div>
<div class="line"> </div>
<div class="line">  assert( (cm.is_removable&lt;1&gt;(cm.beta(d2,0))) );</div>
<div class="line">  cm.remove_cell&lt;1&gt;(cm.beta(d2,0));</div>
<div class="line">  assert( cm.is_valid() );</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Display the combinatorial map characteristics.</span></div>
<div class="line">  cm.display_characteristics(std::cout) &lt;&lt; <span class="stringliteral">", valid="</span></div>
<div class="line">                                        &lt;&lt; cm.is_valid() &lt;&lt; std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
</div><!-- fragment --><p>The output is: </p><pre class="fragment">#Darts=36, #0-cells=8, #1-cells=14, #2-cells=9, #3-cells=2, #ccs=1, valid=1
#Darts=24, #0-cells=8, #1-cells=12, #2-cells=6, #3-cells=1, #ccs=1, valid=1
</pre><p>The first line gives the characteristics of the combinatorial map after all the insertions (the combinatorial map drawn in <a class="el" href="index.html#fig__fig_cmap_example_insertions">Figure 29.15</a> (Right)). There are two 3-cells (since the combinatorial hexahedron was split in two by the 2-cell insertion), nine 2-cells (since two 2-cells of the original hexahedron were split in two by the two 1-cell insertions, and a new 2-cell was created during the 2-cell insertion), fourteen 1-cells (since there are two new 1-cells created by the 1-cell insertion) while the number of 0-cells remains unchanged.</p>
<p>The second line is the result after the removal operations. We retrieve the original combinatorial hexahedron since we have removed all the inserted elements.</p>
<p><a class="anchor" id="fig__fig_cmap_example_insertions"></a> </p><div class="image">
<object type="image/svg+xml" data="cmap_example_insertions.svg" style="pointer-events: none;"></object>
</div>
   <div class="cgal_figure_caption"> <p>  <a class="el" href="index.html#fig__fig_cmap_example_insertions">Figure 29.15</a> Example of high level operations. Left: Initial 3D combinatorial map after the creation of the combinatorial hexahedron. Middle: Combinatorial map obtained after the two 1-cell insertions. The two 2-cells were split in two. Right: Combinatorial map obtained after the 2-cell insertion. The 3-cell was split in two. </p> </div> <p> <br>
</p>
<h2><a class="anchor" id="Combinatorial_mapInsertion"></a>
Insert an Edge Between Two Different Faces</h2>
<p><a class="anchor" id="ssecexempleinsertion"></a> This example shows the use of <a class="el" href="classGenericMap.html#aa29570a0812094c7876e24a228373f12"><code>insert_cell_1_between_two_cells_2</code></a> operation. First we create a combinatorial hexahedron and a face with 4 edges. This face is inserted in the face of the hexahedron containing dart d1. We display the characteristics of the combinatorial map and check its validity. Then we count and display the number of 2-free darts.</p>
<p><br>
<b>File</b> <a class="el" href="Combinatorial_map_2map_3_insert_8cpp-example.html">Combinatorial_map/map_3_insert.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;CGAL/Combinatorial_map.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;iostream&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cstdlib&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cassert&gt;</span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3&gt;</a> CMap_3;</div>
<div class="line"><span class="keyword">typedef</span> CMap_3::Dart_descriptor    Dart_descriptor;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line">  CMap_3 cm;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Create one combinatorial hexahedron</span></div>
<div class="line">  Dart_descriptor d1 = cm.make_combinatorial_hexahedron();</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Create one square face</span></div>
<div class="line">  Dart_descriptor d2=cm.make_combinatorial_polygon(4);</div>
<div class="line"> </div>
<div class="line">  assert(cm.is_insertable_cell_1_between_two_cells_2(d1,d2));</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Insert the square face as a hole of the face of the hexahedron containing d1</span></div>
<div class="line">  cm.insert_cell_1_between_two_cells_2(d1, d2);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Display the combinatorial map characteristics.</span></div>
<div class="line">  cm.display_characteristics(std::cout)&lt;&lt;<span class="stringliteral">", valid="</span></div>
<div class="line">                                       &lt;&lt;cm.is_valid()&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  std::size_t nb=0;</div>
<div class="line">  <span class="keywordflow">for</span>(Dart_descriptor dh=cm.darts().begin(); dh!=cm.darts().end(); ++dh)</div>
<div class="line">  { <span class="keywordflow">if</span> (cm.is_free&lt;2&gt;(dh)) ++nb; }</div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">"Number of 2-free darts: "</span>&lt;&lt;nb&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
</div><!-- fragment --><p>The output is: </p><pre class="fragment">#Darts=30, #0-cells=12, #1-cells=17, #2-cells=6, #3-cells=1, #ccs=1, valid=1
Number of 2-free darts: 4
</pre><p>We can verify that there are 6 2-cells after the insertion since the squared face was inserted as a hole in one face of the hexahedron. We can also see that there are 4 2-free darts, which are the darts of the squared face. Since they bound an hole, there is no face filling the hole and thus 4 darts are 2-free.</p>
<p>See also a similar example for Linear cell complex <a class="elRef" href="../Linear_cell_complex/index.html#Linear_cell_complexInsert">Insert an Edge Between Two Different Faces</a>.</p>
<h2><a class="anchor" id="Combinatorial_mapA4DGenericMap"></a>
A 4D Combinatorial Map</h2>
<p>In this example, a 4-dimensional combinatorial map is used. Two tetrahedral cells are created and sewn by \( \beta_4\). Then the numbers of cells of the combinatorial map are displayed, and its validity is checked.</p>
<p>By looking at these numbers of cells, we can see that the 4D combinatorial map contains only one 3-cell. Indeed, the <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;4&gt;</code></a> operation has identified by pairs all the darts of the two 3-cells by definition of the sew operation (see Section <a class="el" href="index.html#sseclinkdarts">Sewing Orbits and Linking Darts</a>) which, in 4D, links by \( \beta_3\) all the darts in \( \langle{}\) \( \beta_1\), \( \beta_2\) \( \rangle{}\)(<em>d1</em>) and in \( \langle{}\) \( \beta_1\), \( \beta_2\) \( \rangle{}\)(<em>d2</em>). The situation is similar (but in higher dimension) to the configuration where we have two triangles in a 3D combinatorial map, and you use <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;</code></a> between these two triangles. The two triangles are identified since all their darts are linked by \( \beta_3\), thus we obtain a 3D combinatorial map containing only one 3-cell. Note that this 3-cell is unbounded since the darts of the two triangles are all 2-free. In the 4D case, the 4-cell is unbounded since all its darts are 3-free.</p>
<p>In this example, we also illustrate how to use the basic methods to build <em>by hand</em> some specific configuration in a combinatorial map. In fact, these functions are already present in the package: function <code>make_triangle(cm)</code> is equivalent to <a class="el" href="classGenericMap.html#aeceb0c0e90e168d887358a3994d90b94"><code>cm.make_combinatorial_polygon(3)</code></a> and <code>make_tetrahedral(cm)</code> is equivalent to <a class="el" href="classGenericMap.html#a128310cc4302aae6438e6b83147c6f9c"><code>cm.make_combinatorial_tetrahedron()</code></a>. If we want to create a 4D simplex, we must create five 3D simplexes, and sew them correctly two by two by \( \beta_3\) (and so on if you want to create higher dimensional combinatorial map).</p>
<p><br>
<b>File</b> <a class="el" href="Combinatorial_map_2map_4_simple_example_8cpp-example.html">Combinatorial_map/map_4_simple_example.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;CGAL/Combinatorial_map.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;iostream&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cstdlib&gt;</span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;4&gt;</a> CMap_4;</div>
<div class="line"><span class="keyword">typedef</span> CMap_4::Dart_descriptor Dart_descriptor;</div>
<div class="line"> </div>
<div class="line">Dart_descriptor make_triangle(CMap_4&amp; amap)</div>
<div class="line">{</div>
<div class="line"> Dart_descriptor d1 = amap.create_dart();</div>
<div class="line"> Dart_descriptor d2 = amap.create_dart();</div>
<div class="line"> Dart_descriptor d3 = amap.create_dart();</div>
<div class="line"> amap.link_beta&lt;1&gt;(d1,d2);</div>
<div class="line"> amap.link_beta&lt;1&gt;(d2,d3);</div>
<div class="line"> amap.link_beta&lt;1&gt;(d3,d1);</div>
<div class="line"> <span class="keywordflow">return</span> d1;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line">Dart_descriptor make_tetrahedral(CMap_4&amp; amap)</div>
<div class="line">{</div>
<div class="line">  Dart_descriptor d1 = make_triangle(amap);</div>
<div class="line">  Dart_descriptor d2 = make_triangle(amap);</div>
<div class="line">  Dart_descriptor d3 = make_triangle(amap);</div>
<div class="line">  Dart_descriptor d4 = make_triangle(amap);</div>
<div class="line">  amap.link_beta&lt;2&gt;(d1, d2);</div>
<div class="line">  amap.link_beta&lt;2&gt;(d3, amap.beta(d2,0));</div>
<div class="line">  amap.link_beta&lt;2&gt;(amap.beta(d1,1), amap.beta(d3,0));</div>
<div class="line">  amap.link_beta&lt;2&gt;(d4, amap.beta(d2,1));</div>
<div class="line">  amap.link_beta&lt;2&gt;(amap.beta(d4,0), amap.beta(d3,1));</div>
<div class="line">  amap.link_beta&lt;2&gt;(amap.beta(d4,1), amap.beta(d1,0));</div>
<div class="line">  <span class="keywordflow">return</span> d1;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line">  CMap_4 cm;</div>
<div class="line">  Dart_descriptor d1 = make_tetrahedral(cm);</div>
<div class="line">  Dart_descriptor d2 = make_tetrahedral(cm);</div>
<div class="line"> </div>
<div class="line">  cm.sew&lt;4&gt;(d1,d2);</div>
<div class="line"> </div>
<div class="line">  cm.display_characteristics(std::cout);</div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">", valid="</span>&lt;&lt;cm.is_valid()&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
</div><!-- fragment --><p>The output is: </p><pre class="fragment">#Darts=24, #0-cells=4, #1-cells=6, #2-cells=4, #3-cells=1, #4-cells=2, #ccs=1, valid=1
</pre><h2><a class="anchor" id="sseccombimapwithcolor"></a>
Combinatorial Map With Attributes</h2>
<p>In the following example, we illustrate how to specify the 2-attributes in a 3D combinatorial map. For that, we define our own item class using <a class="el" href="classCGAL_1_1Cell__attribute.html"><code>Cell_attribute&lt;CMap,int,Tag_true,Sum_functor,Divide_by_two_functor&gt;</code></a> as attributes which contain an <code>int</code> and which are associated to 2-cells of the combinatorial map.</p>
<p>Functors <code>Sum_functor</code> and <code>Divide_by_two_functor</code> define a custom behavior: when two attributes <code>ca1</code> and <code>ca2</code> are merged into <code>ca1</code>, the value of <code>ca1</code> is the sum of the two initial values. When an attribute <code>ca1</code> is split in the two attributes <code>ca1</code> and <code>ca2</code>, the value of each attribute is half of the first value.</p>
<p><br>
<b>File</b> <a class="el" href="Combinatorial_map_2map_3_with_colored_facets_8cpp-example.html">Combinatorial_map/map_3_with_colored_facets.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;CGAL/Combinatorial_map.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;CGAL/Cell_attribute.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;iostream&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;algorithm&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cstdlib&gt;</span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">struct </span>Sum_functor</div>
<div class="line">{</div>
<div class="line">  <span class="keyword">template</span>&lt;<span class="keyword">class</span> Cell_attribute&gt;</div>
<div class="line">  <span class="keywordtype">void</span> operator()(Cell_attribute&amp; ca1,Cell_attribute&amp; ca2)</div>
<div class="line">  { ca1.info()=ca1.info()+ca2.info(); }</div>
<div class="line">};</div>
<div class="line"><span class="keyword">struct </span>Divide_by_two_functor</div>
<div class="line">{</div>
<div class="line">  <span class="keyword">template</span>&lt;<span class="keyword">class</span> Cell_attribute&gt;</div>
<div class="line">  <span class="keywordtype">void</span> operator()(Cell_attribute&amp; ca1,Cell_attribute&amp; ca2)</div>
<div class="line">  {</div>
<div class="line">    ca1.info()=(ca1.info()/2);</div>
<div class="line">    ca2.info()=(ca1.info());</div>
<div class="line">  }</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="keyword">struct </span>Myitem</div>
<div class="line">{</div>
<div class="line">  <span class="keyword">template</span>&lt;<span class="keyword">class</span> CMap&gt;</div>
<div class="line">  <span class="keyword">struct </span>Dart_wrapper</div>
<div class="line">  {</div>
<div class="line">    <span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Cell__attribute.html">CGAL::Cell_attribute</a>&lt;CMap, int, <a class="code hl_typedefRef" href="../STL_Extension/group__PkgSTLExtensionUtilities.html#gab3e2296107b5d26c32c8183028a217f1">CGAL::Tag_true</a>,</div>
<div class="line">     Sum_functor, Divide_by_two_functor&gt; Facet_attribute;</div>
<div class="line">    <span class="keyword">typedef</span> std::tuple&lt;void,void,Facet_attribute&gt; Attributes;</div>
<div class="line">  };</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3,Myitem&gt;</a> CMap_3;</div>
<div class="line"><span class="keyword">typedef</span> CMap_3::Dart_descriptor           Dart_descriptor;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line">  CMap_3 cm;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Create 2 hexahedra.</span></div>
<div class="line">  Dart_descriptor d1 = cm.make_combinatorial_hexahedron();</div>
<div class="line">  Dart_descriptor d2 = cm.make_combinatorial_hexahedron();</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 1) Create all 2-attributes and associated them to darts.</span></div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::Dart_range::iterator</div>
<div class="line">       it=cm.darts().begin(), itend=cm.darts().end();</div>
<div class="line">       it!=itend; ++it)</div>
<div class="line">  {</div>
<div class="line">    <span class="keywordflow">if</span> ( cm.attribute&lt;2&gt;(it)==CMap_3::null_descriptor )</div>
<div class="line">      cm.set_attribute&lt;2&gt;(it, cm.create_attribute&lt;2&gt;());</div>
<div class="line">  }</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 2) Set the color of all facets of the first hexahedron to 7.</span></div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::One_dart_per_incident_cell_range&lt;2, 3&gt;::iterator</div>
<div class="line">       it=cm.one_dart_per_incident_cell&lt;2,3&gt;(d1).begin(),</div>
<div class="line">       itend=cm.one_dart_per_incident_cell&lt;2,3&gt;(d1).end(); it!=itend; ++it)</div>
<div class="line">  { cm.info&lt;2&gt;(it)=7; }</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 3) Set the color of all facets of the second hexahedron to 13.</span></div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::One_dart_per_incident_cell_range&lt;2, 3&gt;::iterator it=</div>
<div class="line">       cm.one_dart_per_incident_cell&lt;2,3&gt;(d2).begin(),</div>
<div class="line">       itend=cm.one_dart_per_incident_cell&lt;2,3&gt;(d2).end(); it!=itend; ++it)</div>
<div class="line">  { cm.info&lt;2&gt;(it)=13; }</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 4) 3-Sew the two hexahedra along one facet.</span></div>
<div class="line">  cm.sew&lt;3&gt;(d1, d2);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 5) Display all the values of 2-attributes.</span></div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::Attribute_range&lt;2&gt;::type::iterator</div>
<div class="line">       it=cm.attributes&lt;2&gt;().begin(), itend=cm.attributes&lt;2&gt;().end();</div>
<div class="line">       it!=itend; ++it)</div>
<div class="line">  {</div>
<div class="line">    std::cout&lt;&lt;cm.info_of_attribute&lt;2&gt;(it)&lt;&lt;<span class="stringliteral">"; "</span>;</div>
<div class="line">  }</div>
<div class="line">  std::cout&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 6) Insert a vertex in the facet between the two hexahedra.</span></div>
<div class="line">  cm.insert_cell_0_in_cell_2(d2);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 7) Display all the values of 2-attributes.</span></div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::Attribute_range&lt;2&gt;::type::iterator</div>
<div class="line">       it=cm.attributes&lt;2&gt;().begin(), itend=cm.attributes&lt;2&gt;().end();</div>
<div class="line">       it!=itend; ++it)</div>
<div class="line">  {</div>
<div class="line">    std::cout&lt;&lt;cm.info_of_attribute&lt;2&gt;(it)&lt;&lt;<span class="stringliteral">"; "</span>;</div>
<div class="line">  }</div>
<div class="line">  std::cout&lt;&lt;std::endl;</div>
<div class="line">  cm.display_characteristics(std::cout);</div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">", valid="</span>&lt;&lt;cm.is_valid()&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
<div class="ttc" id="agroup__PkgSTLExtensionUtilities_html_gab3e2296107b5d26c32c8183028a217f1"><div class="ttname"><a href="../STL_Extension/group__PkgSTLExtensionUtilities.html#gab3e2296107b5d26c32c8183028a217f1">CGAL::Tag_true</a></div><div class="ttdeci">CGAL::Boolean_tag&lt; true &gt; Tag_true</div></div>
</div><!-- fragment --><p>The output is: </p><pre class="fragment">20; 7; 7; 7; 7; 7; 13; 13; 13; 13; 13;
2; 7; 7; 7; 7; 7; 2; 13; 13; 13; 13; 13; 5; 10;
#Darts=64, #0-cells=13, #1-cells=24, #2-cells=14, #3-cells=2, #ccs=1, valid=1
</pre><p>Before the <code>cm.</code><a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;</code></a>, each 2-cell of the first cube is associated with an attribute having 7 as value, and each 2-cell of the second cube with an attribute having 13 as value. During the <code>cm.</code><a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;</code></a>, two 2-cells are merged, thus the functor <code>Sum_functor</code> is called on the two associated 2-attributes, and the value of the new 2-cell is the sum of the two previous one: 20.</p>
<p>Then we call <a class="el" href="classGenericMap.html#a5ad8a7e3bdee15f1d8c63f6ac1e4ec7c"><code>insert_cell_0_in_cell_2</code></a> on a dart which belong to this 2-cell. This method splits the existing 2-cell in <em>k</em> 2-cells, <em>k</em> being the number of 1-cells of the initial 2-cell (4 in this example). These splits are made consecutively, thus for the first split, we create a new attribute as copy of the initial one and call functor <code>Divide_by_two_functor</code> on these two attributes: the value of each attribute is thus 20/2=10. For the second split, the value of each attribute is thus 10/2=5, and for the last split the value of each attribute is thus 5/2=2 (remember that information contained in 2-attributes in an <code>int</code>). At the end, we obtain five 2-attributes with 7 as value, five 2-attributes with 13 as value, and four 2-attributes having respectively 2, 2, 5 and 10 as values.</p>
<h2><a class="anchor" id="sseccombimapdynamicattibute"></a>
Use of Dynamic Onmerge and Onsplit Functors</h2>
<p>In the following example, we show an example of use of dynamic onmerge and onsplit functor. We define our 3D combinatorial map with 2-attributes. Then we create two hexahedra and create all the 2-attributes, having their info initialized to 1.</p>
<p>Step 2 defines the onsplit and onmerge dynamic functors. We can see here that with this mechanism, functors can store data member. This is the case in the example for <code>Split_functor</code> which stores a reference to the combinatorial map.</p>
<p>The next operations will call these functors when 2-cells are split or merged. The <a class="el" href="classCombinatorialMap.html#abcf4d1e585900825c54dd375e02a7277"><code>sew&lt;3&gt;</code></a> operation calls 1 onmerge as two faces are identified; the <a class="el" href="classGenericMap.html#a5ad8a7e3bdee15f1d8c63f6ac1e4ec7c"><code>insert_cell_0_in_cell_2</code></a> operation calls 3 onsplit as one face is split in 4.</p>
<p>Lastly we remove the dynamic onmerge functor (step 7). This is done by initializing the functor to a default boost::function. After this initialization, no dynamic merge functor is called when two faces are merged.</p>
<p><br>
<b>File</b> <a class="el" href="Combinatorial_map_2map_3_dynamic_onmerge_8cpp-example.html">Combinatorial_map/map_3_dynamic_onmerge.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;CGAL/Combinatorial_map.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;CGAL/Cell_attribute.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;iostream&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cstdlib&gt;</span></div>
<div class="line"> </div>
<div class="line"><span class="comment">// My item class: no functor is associated with Face_attribute.</span></div>
<div class="line"><span class="keyword">struct </span>Myitem</div>
<div class="line">{</div>
<div class="line">  <span class="keyword">template</span>&lt;<span class="keyword">class</span> CMap&gt;</div>
<div class="line">  <span class="keyword">struct </span>Dart_wrapper</div>
<div class="line">  {</div>
<div class="line">    <span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Cell__attribute.html">CGAL::Cell_attribute&lt;CMap, double&gt;</a> Face_attribute; <span class="comment">// A weight</span></div>
<div class="line">    <span class="keyword">typedef</span> std::tuple&lt;void,void,Face_attribute&gt; Attributes;</div>
<div class="line">  };</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="comment">// Definition of my combinatorial map.</span></div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3,Myitem&gt;</a> CMap_3;</div>
<div class="line"><span class="keyword">typedef</span> CMap_3::Dart_descriptor           Dart_descriptor;</div>
<div class="line"><span class="keyword">typedef</span> CMap_3::Attribute_type&lt;2&gt;::type   Face_attribute;</div>
<div class="line"> </div>
<div class="line"><span class="comment">// Functor called when two faces are merged.</span></div>
<div class="line"><span class="keyword">struct </span>Merge_functor</div>
<div class="line">{</div>
<div class="line">  <span class="comment">// operator() automatically called before a merge.</span></div>
<div class="line">  <span class="keywordtype">void</span> operator()(Face_attribute&amp; ca1, Face_attribute&amp; ca2)</div>
<div class="line">  {</div>
<div class="line">    ca1.info()=ca1.info()+ca2.info(); <span class="comment">// Update can be done incrementally.</span></div>
<div class="line">    std::cout&lt;&lt;<span class="stringliteral">"After on merge faces: info of face1="</span>&lt;&lt;ca1.info()</div>
<div class="line">             &lt;&lt;<span class="stringliteral">", info of face2="</span>&lt;&lt;ca2.info()&lt;&lt;std::endl;</div>
<div class="line">  }</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="comment">// Functor called when one face is split in two.</span></div>
<div class="line"><span class="keyword">struct </span>Split_functor</div>
<div class="line">{</div>
<div class="line">  Split_functor(CMap_3&amp; amap) : mmap(amap)</div>
<div class="line">  {}</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// operator() automatically called after a split.</span></div>
<div class="line">  <span class="keywordtype">void</span> operator()(Face_attribute&amp; ca1, Face_attribute&amp; ca2)</div>
<div class="line">  {</div>
<div class="line">     <span class="comment">// We need to reinitialize the weight of the two faces</span></div>
<div class="line">    CMap_3::size_type nb1=mmap.darts_of_cell&lt;2&gt;(ca1.dart()).size();</div>
<div class="line">    CMap_3::size_type nb2=mmap.darts_of_cell&lt;2&gt;(ca2.dart()).size();</div>
<div class="line">    mmap.info&lt;2&gt;(ca1.dart())*=(<span class="keywordtype">double</span>(nb1)/(nb1+nb2));</div>
<div class="line">    mmap.info&lt;2&gt;(ca2.dart())*=(<span class="keywordtype">double</span>(nb2)/(nb1+nb2));</div>
<div class="line">    std::cout&lt;&lt;<span class="stringliteral">"After on split faces: info of face1="</span>&lt;&lt;ca1.info()</div>
<div class="line">             &lt;&lt;<span class="stringliteral">", info of face2="</span>&lt;&lt;ca2.info()&lt;&lt;std::endl;</div>
<div class="line">  }</div>
<div class="line"> </div>
<div class="line"><span class="keyword">private</span>:</div>
<div class="line">  CMap_3&amp; mmap;</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="comment">// Function allowing to display all the 2-attributes, and the characteristics</span></div>
<div class="line"><span class="comment">// of a given combinatorial map.</span></div>
<div class="line"><span class="keywordtype">void</span> display_map_and_2attributes(CMap_3&amp; cm)</div>
<div class="line">{</div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::Attribute_range&lt;2&gt;::type::iterator</div>
<div class="line">       it=cm.attributes&lt;2&gt;().begin(), itend=cm.attributes&lt;2&gt;().end();</div>
<div class="line">       it!=itend; ++it)</div>
<div class="line">  { std::cout&lt;&lt;cm.info_of_attribute&lt;2&gt;(it)&lt;&lt;<span class="stringliteral">"; "</span>; }</div>
<div class="line">  std::cout&lt;&lt;std::endl;</div>
<div class="line">  cm.display_characteristics(std::cout);</div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">", valid="</span>&lt;&lt;cm.is_valid()&lt;&lt;std::endl;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line">  CMap_3 cm;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 0) Create 2 hexahedra.</span></div>
<div class="line">  Dart_descriptor d1 = cm.make_combinatorial_hexahedron();</div>
<div class="line">  Dart_descriptor d2 = cm.make_combinatorial_hexahedron();</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 1) Create and initialize 2-attributes.</span></div>
<div class="line">  <span class="keywordflow">for</span> (CMap_3::One_dart_per_cell_range&lt;2&gt;::iterator</div>
<div class="line">       it=cm.one_dart_per_cell&lt;2&gt;().begin(),</div>
<div class="line">       itend=cm.one_dart_per_cell&lt;2&gt;().end(); it!=itend; ++it)</div>
<div class="line">  { cm.set_attribute&lt;2&gt;(it, cm.create_attribute&lt;2&gt;(1)); }</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 2) Set the onsplit and onmerge functors.</span></div>
<div class="line">  cm.onsplit_functor&lt;2&gt;()=Split_functor(cm);</div>
<div class="line">  cm.onmerge_functor&lt;2&gt;()=Merge_functor();</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 3) 3-Sew the two hexahedra along one face. This calls 1 onmerge.</span></div>
<div class="line">  cm.sew&lt;3&gt;(d1, d2);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 4) Display all the values of 2-attributes.</span></div>
<div class="line">  display_map_and_2attributes(cm);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 5) Insert a vertex in the face between the two hexahedra.</span></div>
<div class="line">  <span class="comment">//    This calls 3 onsplit.</span></div>
<div class="line">  Dart_descriptor resdart=cm.insert_cell_0_in_cell_2(d2);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 6) Display all the values of 2-attributes.</span></div>
<div class="line">  display_map_and_2attributes(cm);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 7) "Remove" the dynamic onmerge functor.</span></div>
<div class="line">  cm.onmerge_functor&lt;2&gt;()=boost::function&lt;<span class="keywordtype">void</span>(Face_attribute&amp;,</div>
<div class="line">                                               Face_attribute&amp;)&gt;();</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 8) Remove one edge: this merges two faces, however no dynamic</span></div>
<div class="line">  <span class="comment">//    functor is called (because it was removed).</span></div>
<div class="line">  cm.remove_cell&lt;1&gt;(resdart);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// 9) Display all the values of 2-attributes.</span></div>
<div class="line">  display_map_and_2attributes(cm);</div>
<div class="line"> </div>
<div class="line">  <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
</div><!-- fragment --><h2><a class="anchor" id="ssecexample3DCMWI"></a>
3D Combinatorial Map Using Indices</h2>
<p>In this example, a 3-dimensional combinatorial map is used, but using indices instead of handles. Two vectors are created to store some external information associated with darts and 3-attributes. Since descriptors are indices, they can directly be used to access elements of the vector.</p>
<p><br>
<b>File</b> <a class="el" href="Combinatorial_map_2map_3_index_8cpp-example.html">Combinatorial_map/map_3_index.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include &lt;CGAL/Combinatorial_map.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;CGAL/Cell_attribute.h&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;vector&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;algorithm&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;string&gt;</span></div>
<div class="line"><span class="preprocessor">#include &lt;cstdlib&gt;</span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">struct </span>Myitem</div>
<div class="line">{</div>
<div class="line">  <span class="keyword">using </span>Use_index=<a class="code hl_typedefRef" href="../STL_Extension/group__PkgSTLExtensionUtilities.html#gab3e2296107b5d26c32c8183028a217f1">CGAL::Tag_true</a>; <span class="comment">// use indices</span></div>
<div class="line">  <span class="keyword">using </span>Index_type=std::uint16_t; <span class="comment">// 16 bits</span></div>
<div class="line">  <span class="keyword">template</span>&lt;<span class="keyword">class</span> CMap&gt;</div>
<div class="line">  <span class="keyword">struct </span>Dart_wrapper</div>
<div class="line">  {</div>
<div class="line">    <span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Cell__attribute.html">CGAL::Cell_attribute&lt;CMap&gt;</a> Vol_attrib;</div>
<div class="line">    <span class="keyword">typedef</span> std::tuple&lt;void,void,void,Vol_attrib&gt; Attributes;</div>
<div class="line">  };</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="keyword">using </span>CMap_3=<a class="code hl_class" href="classCGAL_1_1Combinatorial__map.html">CGAL::Combinatorial_map&lt;3,Myitem&gt;</a>;</div>
<div class="line"><span class="keyword">using </span>Dart_descriptor=CMap_3::Dart_descriptor;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main()</div>
<div class="line">{</div>
<div class="line">  CMap_3 cm;</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Create 2 hexahedra.</span></div>
<div class="line">  Dart_descriptor d1=cm.make_combinatorial_hexahedron();</div>
<div class="line">  Dart_descriptor d2=cm.make_combinatorial_hexahedron();</div>
<div class="line">  cm.sew&lt;3&gt;(d1, d2); <span class="comment">// 3-Sew the two hexahedra along one facet.</span></div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Create two 3-attributes and associated them to darts.</span></div>
<div class="line">  cm.set_attribute&lt;3&gt;(d1, cm.create_attribute&lt;3&gt;());</div>
<div class="line">  cm.set_attribute&lt;3&gt;(d2, cm.create_attribute&lt;3&gt;());</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Associate a vector of size_t to darts</span></div>
<div class="line">  std::vector&lt;std::size_t&gt; array_for_darts(cm.upper_bound_on_dart_ids());</div>
<div class="line">  std::generate(array_for_darts.begin(), array_for_darts.end(), std::rand);</div>
<div class="line"> </div>
<div class="line">  <span class="comment">// Associate a vector of string to 3-attributes</span></div>
<div class="line">  std::vector&lt;std::string&gt; array_for_vols(cm.upper_bound_on_attribute_ids&lt;3&gt;());</div>
<div class="line">  std::size_t i=0;</div>
<div class="line">  <span class="keywordflow">for</span>(<span class="keyword">auto</span>&amp; e: array_for_vols)</div>
<div class="line">  { e=<span class="stringliteral">"vol"</span>+std::to_string(i++); }</div>
<div class="line"> </div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">"Value in array for darts d1 and d2: "</span></div>
<div class="line">           &lt;&lt;array_for_darts[d1]&lt;&lt;<span class="stringliteral">" and "</span>&lt;&lt;array_for_darts[d2]&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  std::cout&lt;&lt;<span class="stringliteral">"Value in array for volumes of dart d1 and d2: "</span></div>
<div class="line">           &lt;&lt;array_for_vols[cm.attribute&lt;3&gt;(d1)]&lt;&lt;<span class="stringliteral">" and "</span></div>
<div class="line">           &lt;&lt;array_for_vols[cm.attribute&lt;3&gt;(d2)]&lt;&lt;std::endl;</div>
<div class="line"> </div>
<div class="line">  <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
</div><!-- fragment --><h1><a class="anchor" id="sec_definition"></a>
Mathematical Definitions</h1>
<p>The initial definition of combinatorial map in any dimension is given in <a class="el" href="citelist.html#CITEREF_cgal:l-tmbrc-91">[3]</a>, <a class="el" href="citelist.html#CITEREF_l-ndgcm-94">[4]</a>. But it allows only to represent objects without boundaries. This definition was extended <a class="el" href="citelist.html#CITEREF_cgal:pabl-cco-07">[5]</a>, <a class="el" href="citelist.html#CITEREF_cgal:d-ccccg-10">[2]</a> in order to allow to represent objects with boundaries, based on the notions of partial permutations and partial involutions. See also the book <a class="el" href="citelist.html#CITEREF_cgal:dl-cmeds-14">[1]</a> which regroups many definitions, operations and algorithms about combinatorial and generalized maps.</p>
<p>Intuitively, a <em>partial permutation</em> on a finite set <em>E</em> is a mapping from <em>E</em> \( \cup\{\varnothing\}\) to <em>E</em> \( \cup\{\varnothing\}\) which is injective on the subset of the domain that does not map to \(\varnothing\). More precisely, a mapping <em>p</em>: <em>E</em> \( \cup\{\varnothing\} \rightarrow\) <em>E</em> \( \cup\{\varnothing\}\) is a <em>partial permutation</em> defined on <em>E</em> if: </p><ol>
<li>
<em>p</em> \((\varnothing)=\varnothing\); </li>
<li>
\( \forall \) <em>e1</em> \( \in \) <em>E</em>, \( \forall \) <em>e2</em> \( \in \) <em>E</em>, <em>p</em>(<em>e1</em>)=<em>p</em>(<em>e2</em>) \( \neq \) \( \varnothing\) \( \Rightarrow\) <em>e1</em>=<em>e2</em>. </li>
</ol>
<p>The inverse \( p^{-1}\) of this partial permutation is also a partial permutation and is defined by: </p><ol>
<li>
\( p^{-1}(\varnothing)=\varnothing\); </li>
<li>
\( \forall \) <em>e</em> \( \in \) <em>E</em>, if it exists <em>a</em> \( \in \) <em>E</em> such that <em>p</em>(<em>a</em>)=<em>e</em>, then \( p^{-1}\)(<em>e</em>)=a, otherwise \( p^{-1}\)(<em>e</em>) \(= \varnothing\). </li>
</ol>
<p>Let <em>E</em> be a set, and <em>p</em> a partial permutation on <em>E</em>. An element <em>e</em> is called a <em>fixed point</em> for <em>p</em> if <em>p(e)=e</em>. <em>p</em> is a <em>partial involution</em> if \( \forall \) <em>e</em> \( \in \) <em>E</em>: <em>p</em>(<em>e</em>) \( \neq \) \( \varnothing\) \( \Rightarrow\) <em>p</em>(<em>p</em>(<em>e</em>))=<em>e</em>.</p>
<p>Now we can give the definition of a combinatorial map in any dimension. Let <em>d</em> \( \geq\) 0. A <em>d</em>-dimensional combinatorial map (or <em>d</em>-map) is a (d+1)-tuple <em>M</em>=(<em>D</em>, \( \beta_1\),..., \( \beta_d\)) where: </p><ol>
<li>
<em>D</em> is a finite set of darts; </li>
<li>
\( \beta_1\) is a partial permutation on <em>D</em>; let \( \beta_0\) denote \( \beta_1^{-1}\); </li>
<li>
\( \forall \) <em>i</em>, 2 \( \leq \) <em>i</em> \( \leq \) <em>d</em>, \( \beta_i\) is a partial involution on <em>D</em> without fixed point; </li>
<li>
<a class="anchor" id="condcomposition"></a>\( \forall \) <em>i</em>: 0 \( \leq \) <em>i</em> \( \leq\) <em>d</em>-2, \( \forall \) <em>j</em>: 3 \( \leq \)<em>j</em> \( \leq \) <em>d</em>, <em>i</em>+2 \( \leq \) <em>j</em>, \( \beta_i \) \( \circ \) \( \beta_j \) is a partial involution. </li>
</ol>
<p>A <em>d</em>-dimensional combinatorial map represents a subdivision of an orientable <em>d</em>-dimensional quasi-manifold. A dart is an abstract element which is only required to define partial permutations. The last line of the definition fixes constraints which guarantee the topological validity of the represented object, i.e., the fact that it is a quasi-manifold. This definition allows us to verify the validity of a given combinatorial map by checking if each item of the definition is satisfied.</p>
<p>Given a set of partial permutations <em>S</em>= \(\{f_1\),..., \( f_k\}\), we denote by \( \langle{}\) <em>S</em> \( \rangle{}\) the <em>permutation group</em> generated by \(\{f_1\),..., \( f_k\}\) and whose group operation is the composition of partial permutations. The orbit \( \langle{}\) \( f_1\),..., \( f_k\) \( \rangle{}\)(<em>a</em>) is the set of darts which can be obtained from <em>a</em> by elements of \( \langle{}\) <em>S</em> \( \rangle{}\): \( \langle{}\) \( f_1\),..., \( f_k\) \( \rangle{}\)(<em>a</em>)= \(\{ \phi\)(<em>a</em>) \( |\) \( \phi\) \( \in \) \( \langle{}\)<em>S</em> \( \rangle{}\}\setminus\{\varnothing\}\).</p>
<p>Let <em>d0</em> \( \in \) <em>D</em> be a dart. Given <em>i</em>, 1 \( \leq \) <em>i</em> \( \leq \) <em>d</em>, the <em>i</em>-cell containing <em>d0</em> is \( \langle{}\) \( \beta_1\),..., \( \beta_{i-1}\), \( \beta_{i+1}\),..., \( \beta_d\) \( \rangle{}\)(<em>d0</em>). The <em>0</em>-cell containing <em>d0</em> is \( \langle{}\){ \( \beta_i\) \( \circ\) \( \beta_j\) \( |\) \( \forall \) <em>i,j</em>: 1 \( \leq \) <em>i</em> \( &lt; \) <em>j</em> \( \leq \) <em>d</em>} \( \rangle{}\)(<em>d0</em>).</p>
<h1><a class="anchor" id="Combinatorial_mapDesign"></a>
Design and Implementation History</h1>
<p>The code of this package is inspired by Moka, a 3D topological modeler mainly developed by Frédéric Vidil and Guillaume Damiand (see <a href="https://projet.liris.cnrs.fr/moka/index.php">https://projet.liris.cnrs.fr/moka/index.php</a> and <a href="https://github.com/gdamiand/moka">https://github.com/gdamiand/moka</a>). However, Moka was based on Generalized maps (and not Combinatorial maps), and the design was not CGAL "compatible". Thus, Guillaume Damiand started to develop a totally new package by mixing ideas taken from Moka with the design of the Halfedge data structure package of CGAL. Andreas Fabri and Sébastien Loriot contributed to the design, the coding, and to the documentation of the package, and Laurent Rineau helped for the design. Emma Michel contributed to the manual. Monique Teillaud and Bernd Gärtner contributed to the manual by giving useful remarks, really numerous and detailed for Monique. Ken Arroyo Ohori contributed to the two reverse orientation functions. </p>
</div></div><!-- PageDoc -->
</div><!-- contents -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.9.6-->
<!-- start footer part -->
<!-- The footer div is not part of the default but we require it to
move the footer to the bottom of the page. -->
<div id="footer">
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="footer">Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"></a> 1.9.6 </li>
  </ul>
</div>
</div>
</body>


</html>