CGAL 6.2 - Polygon Mesh Processing

Loading...
Searching...
No Matches
Functions
Connected Components
Reference Manual

##

Two faces are in the same connected component if there is a path of adjacent faces such that all edges between two consecutive faces of the path are not marked as constrained.

## Functions
template<typename PolygonMesh , typename FaceOutputIterator , typename NamedParameters = parameters::Default_named_parameters>
FaceOutputIterator | CGAL::Polygon_mesh_processing::connected_component (typename boost::graph_traits< PolygonMesh >::face_descriptor seed_face, const PolygonMesh &pmesh, FaceOutputIterator out, const NamedParameters &np=parameters::default_values())
| discovers all the faces in the same connected component as `seed_face` and records them in `out`.
template<typename PolygonMesh , typename FaceComponentMap , typename NamedParameters = parameters::Default_named_parameters>
boost::property_traits< FaceComponentMap >::value_type | CGAL::Polygon_mesh_processing::connected_components (const PolygonMesh &pmesh, FaceComponentMap fcm, const NamedParameters &np=parameters::default_values())
| computes for each face the index of the corresponding connected component.
template<typename PolygonMesh , typename NamedParameters = parameters::Default_named_parameters>
std::size_t | CGAL::Polygon_mesh_processing::keep_largest_connected_components (PolygonMesh &pmesh, std::size_t nb_components_to_keep, const NamedParameters &np=parameters::default_values())
| removes all but a user-defined number of connected components.
template<typename PolygonMesh , typename ThresholdValueType , typename NamedParameters = parameters::Default_named_parameters>
std::size_t | CGAL::Polygon_mesh_processing::keep_large_connected_components (PolygonMesh &pmesh, const ThresholdValueType threshold_value, const NamedParameters &np=parameters::default_values())
| removes connected components whose size is (strictly) smaller than a given threshold value, where the size of a connected component is computed as the sum of the individual sizes of all the faces of the connected component.
template<typename PolygonMesh , typename ComponentRange , typename FaceComponentMap , typename NamedParameters = parameters::Default_named_parameters>
void | CGAL::Polygon_mesh_processing::keep_connected_components (PolygonMesh &pmesh, const ComponentRange &components_to_keep, const FaceComponentMap &fcm, const NamedParameters &np)
| keeps the connected components designated by theirs ids in `components_to_keep`, and removes the other connected components as well as all isolated vertices.
template<typename PolygonMesh , typename ComponentRange , typename FaceComponentMap , typename NamedParameters = parameters::Default_named_parameters>
void | CGAL::Polygon_mesh_processing::remove_connected_components (PolygonMesh &pmesh, const ComponentRange &components_to_remove, const FaceComponentMap &fcm, const NamedParameters &np=parameters::default_values())
| removes in `pmesh` the connected components designated by theirs ids in `components_to_remove`, as well as all isolated vertices.
template<typename PolygonMesh , typename FaceRange , typename NamedParameters = CGAL::parameters::Default_named_parameters>
void | CGAL::Polygon_mesh_processing::remove_connected_components (PolygonMesh &pmesh, const FaceRange &components_to_remove, const NamedParameters &np=parameters::default_values())
| keeps the connected components not designated by the faces in `components_to_remove`, and removes the other connected components and all isolated vertices.
template<typename PolygonMesh , typename FaceRange , typename NamedParameters = CGAL::parameters::Default_named_parameters>
void | CGAL::Polygon_mesh_processing::keep_connected_components (PolygonMesh &pmesh, const FaceRange &components_to_keep, const NamedParameters &np=parameters::default_values())
| keeps the connected components designated by the faces in `components_to_keep`, and removes the other connected components and all isolated vertices.
template<class PolygonMesh , class PolygonMeshRange , class NamedParameters = parameters::Default_named_parameters>
void | CGAL::Polygon_mesh_processing::split_connected_components (const PolygonMesh &pmesh, PolygonMeshRange &cc_meshes, const NamedParameters &np=parameters::default_values())
| identifies the connected components of `pmesh` and pushes back a new `PolygonMesh` for each connected component in `cc_meshes`.

## Function Documentation

## ◆ connected_component()

template<typename PolygonMesh , typename FaceOutputIterator , typename NamedParameters = parameters::Default_named_parameters>

FaceOutputIterator CGAL::Polygon_mesh_processing::connected_component | ( | typename boost::graph_traits< PolygonMesh >::face_descriptor | seed_face,
|  | const PolygonMesh & | pmesh,
|  | FaceOutputIterator | out,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

discovers all the faces in the same connected component as `seed_face` and records them in `out`.

`seed_face` will also be added in `out`.

Template Parameters

  PolygonMesh | a model of `FaceGraph`
  FaceOutputIterator | a model of `OutputIterator` with value type `boost::graph_traits<PolygonMesh>::face_descriptor`.
  NamedParameters | a sequence of Named Parameters

Parameters

  seed_face | a face of `pmesh` from which exploration starts to detect the connected component that contains it
  pmesh | the polygon mesh
  out | the output iterator that collects faces from the same connected component as `seed_face`
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map containing the constrained-or-not status of each edge of `pmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: a constant property map returning `false` for any edge key |

Returns
  the output iterator.

See also
  `connected_components()`

Examples
  Polygon_mesh_processing/connected_components_example.cpp.

## ◆ connected_components()

template<typename PolygonMesh , typename FaceComponentMap , typename NamedParameters = parameters::Default_named_parameters>

boost::property_traits< FaceComponentMap >::value_type CGAL::Polygon_mesh_processing::connected_components | ( | const PolygonMesh & | pmesh,
|  | FaceComponentMap | fcm,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

computes for each face the index of the corresponding connected component.

Template Parameters

  PolygonMesh | a model of `FaceListGraph`
  FaceComponentMap | a model of `WritablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `boost::graph_traits<PolygonMesh>::faces_size_type` as value type.
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh
  fcm | the property map with indices of components associated to faces in `pmesh`
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map containing the constrained-or-not status of each edge of `pmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: a constant property map returning `false` for any edge |
  a property map associating to each face of `pmesh` a unique index between `0` and `num_faces(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |

Returns
  the number of connected components.

See also
  `connected_component()`

Examples
  Polygon_mesh_processing/connected_components_example.cpp, and Polygon_mesh_processing/face_filtered_graph_example.cpp.

## ◆ keep_connected_components() [1/2]

template<typename PolygonMesh , typename ComponentRange , typename FaceComponentMap , typename NamedParameters = parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::keep_connected_components | ( | PolygonMesh & | pmesh,
|  | const ComponentRange & | components_to_keep,
|  | const FaceComponentMap & | fcm,
|  | const NamedParameters & | np
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

keeps the connected components designated by theirs ids in `components_to_keep`, and removes the other connected components as well as all isolated vertices.

The connected component id of a face is given by `fcm`.

Note
  If the removal of the connected components makes `pmesh` a non-manifold surface, then the behavior of this function is undefined.

Template Parameters

  PolygonMesh | a model of `VertexListGraph`, `FaceListGraph`, and `MutableFaceGraph`
  ComponentRange | a range of ids convertible to `std::size`
  FaceComponentMap | a model of `ReadWritePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `boost::graph_traits<PolygonMesh>::faces_size_type` as value type.
  NamedParameters | a sequence of Named Parameters

Parameters

  components_to_keep | the range of ids of connected components to keep
  pmesh | the polygon mesh
  fcm | the property map with indices of components associated to faces in `pmesh`. After calling this function, the values of `fcm` are undefined.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating to each vertex of `pmesh` a unique index between `0` and `num_vertices(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |

See also
  `remove_connected_components()`

## ◆ keep_connected_components() [2/2]

template<typename PolygonMesh , typename FaceRange , typename NamedParameters = CGAL::parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::keep_connected_components | ( | PolygonMesh & | pmesh,
|  | const FaceRange & | components_to_keep,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

keeps the connected components designated by the faces in `components_to_keep`, and removes the other connected components and all isolated vertices.

Note
  If the removal of the connected components makes `pmesh` a non-manifold surface, then the behavior of this function is undefined.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` and `MutableFaceGraph`
  NamedParameters | a sequence of Named Parameters
  FaceRange | a range of `boost::graph_traits<PolygonMesh>::face_descriptor` indicating the connected components to be kept.

Parameters

  pmesh | the polygon mesh
  components_to_keep | a face range, including one face or more on each component to be kept
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map containing the constrained-or-not status of each edge of `pmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: a constant property map returning `false` for any edge |
  a property map associating to each vertex of `pmesh` a unique index between `0` and `num_vertices(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map associating to each face of `pmesh` a unique index between `0` and `num_faces(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |

See also
  `remove_connected_components()`

## ◆ keep_large_connected_components()

template<typename PolygonMesh , typename ThresholdValueType , typename NamedParameters = parameters::Default_named_parameters>

std::size_t CGAL::Polygon_mesh_processing::keep_large_connected_components | ( | PolygonMesh & | pmesh,
|  | const ThresholdValueType | threshold_value,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

removes connected components whose size is (strictly) smaller than a given threshold value, where the size of a connected component is computed as the sum of the individual sizes of all the faces of the connected component.

By default, the size of a face is `1` (and thus the size of a connected component is the number of faces it contains), but it is also possible to pass custom sizes, such as the area of the face.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` and `MutableFaceGraph`
  ThresholdValueType | the type of the threshold value. If a face size property map is passed by the user, `ThresholdValueType` must be the same type as the value type of the property map. Otherwise, `ThresholdValueType` must be `std::size_t`.
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh
  threshold_value | any connected component with a size (strictly) smaller than this value will be discarded
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map containing the constrained-or-not status of each edge of `pmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: a constant property map returning `false` for any edge |
  a property map associating to each vertex of `pmesh` a unique index between `0` and `num_vertices(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map associating to each face of `pmesh` a unique index between `0` and `num_faces(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map associating to each face of `pmesh` a size Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type. The value type is chosen by the user, but must be constructible from `0` and support summation and comparisons. Default: A constant property map returning `1` for any face |
  If set to `true`, the mesh will not be altered, but the number of components that would be removed is returned. Type: Boolean Default: `false` |
  an output iterator to collect the faces that would be removed by the algorithm, when using the "dry run" mode (see parameter `dry_run`) Type: a model of `OutputIterator` with value type `face_descriptor` Default: unused |

Returns
  the number of connected components removed (ignoring isolated vertices).

See also
  `keep_largest_connected_components()`

Examples
  Polygon_mesh_processing/connected_components_example.cpp.

## ◆ keep_largest_connected_components()

template<typename PolygonMesh , typename NamedParameters = parameters::Default_named_parameters>

std::size_t CGAL::Polygon_mesh_processing::keep_largest_connected_components | ( | PolygonMesh & | pmesh,
|  | std::size_t | nb_components_to_keep,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

removes all but a user-defined number of connected components.

All isolated vertices are also removed.

Keep the `nb_components_to_keep` largest connected components, where the size of a connected component is computed as the sum of the individual sizes of all the faces of the connected component. By default, the size of a face is `1` (and thus the size of a connected component is the number of faces it contains), but it is also possible to pass custom sizes, such as the area of the face.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` and `MutableFaceGraph`
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh
  nb_components_to_keep | the number of components to be kept. If this number is larger than the number of components in the mesh, all components are kept.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map containing the constrained-or-not status of each edge of `pmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: a constant property map returning `false` for any edge |
  a property map associating to each vertex of `pmesh` a unique index between `0` and `num_vertices(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map associating to each face of `pmesh` a unique index between `0` and `num_faces(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map associating to each face of `pmesh` a size Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type. The value type is chosen by the user, but must be constructible from `0` and support summation and comparisons. Default: A constant property map returning `1` for any face |
  If set to `true`, the mesh will not be altered, but the number of components that would be removed is returned. Type: Boolean Default: `false` |
  an output iterator to collect the faces that would be removed by the algorithm, when using the "dry run" mode (see parameter `dry_run`) Type: a model of `OutputIterator` with value type `face_descriptor` Default: unused |

Returns
  the number of connected components removed (ignoring isolated vertices).

See also
  `keep_large_connected_components()`

Examples
  Polygon_mesh_processing/connected_components_example.cpp.

## ◆ remove_connected_components() [1/2]

template<typename PolygonMesh , typename ComponentRange , typename FaceComponentMap , typename NamedParameters = parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::remove_connected_components | ( | PolygonMesh & | pmesh,
|  | const ComponentRange & | components_to_remove,
|  | const FaceComponentMap & | fcm,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

removes in `pmesh` the connected components designated by theirs ids in `components_to_remove`, as well as all isolated vertices.

The connected component id of a face is given by `fcm`.

Note
  If the removal of the connected components makes `pmesh` a non-manifold surface, then the behavior of this function is undefined.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` and `MutableFaceGraph`
  ComponentRange | a range of ids convertible to `std::size`
  FaceComponentMap | a model of `ReadWritePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `boost::graph_traits<PolygonMesh>::faces_size_type` as value type.
  NamedParameters | a sequence of Named Parameters

Parameters

  components_to_remove | the range of ids of connected components to remove
  pmesh | the polygon mesh
  fcm | the property map with indices of components associated to faces in `pmesh`. After calling this function, the values of `fcm` are undefined.
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map associating to each vertex of `pmesh` a unique index between `0` and `num_vertices(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |

See also
  `keep_connected_components()`

## ◆ remove_connected_components() [2/2]

template<typename PolygonMesh , typename FaceRange , typename NamedParameters = CGAL::parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::remove_connected_components | ( | PolygonMesh & | pmesh,
|  | const FaceRange & | components_to_remove,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

keeps the connected components not designated by the faces in `components_to_remove`, and removes the other connected components and all isolated vertices.

Note
  If the removal of the connected components makes `pmesh` a non-manifold surface, then the behavior of this function is undefined.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` and `MutableFaceGraph`
  FaceRange | a range of `boost::graph_traits<PolygonMesh>::face_descriptor` indicating the connected components to be removed.
  NamedParameters | a sequence of Named Parameters

Parameters

  components_to_remove | a face range, including one face or more on each component to be removed
  pmesh | the polygon mesh
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map containing the constrained-or-not status of each edge of `pmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: a constant property map returning `false` for any edge |
  a property map associating to each vertex of `pmesh` a unique index between `0` and `num_vertices(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map associating to each face of `pmesh` a unique index between `0` and `num_faces(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |

See also
  `keep_connected_components()`

## ◆ split_connected_components()

template<class PolygonMesh , class PolygonMeshRange , class NamedParameters = parameters::Default_named_parameters>

void CGAL::Polygon_mesh_processing::split_connected_components | ( | const PolygonMesh & | pmesh,
|  | PolygonMeshRange & | cc_meshes,
|  | const NamedParameters & | np = `parameters::default_values()`
| ) |  |

`#include <CGAL/Polygon_mesh_processing/connected_components.h>`

identifies the connected components of `pmesh` and pushes back a new `PolygonMesh` for each connected component in `cc_meshes`.

Template Parameters

  PolygonMesh | a model of `FaceListGraph` and `MutableFaceGraph`
  PolygonMeshRange | a model of `SequenceContainer` with `PolygonMesh` as value type
  NamedParameters | a sequence of Named Parameters

Parameters

  pmesh | the polygon mesh
  cc_meshes | container that is filled with the extracted connected components
  np | an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

  a property map containing the constrained-or-not status of each edge of `pmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::edge_descriptor` as key type and `bool` as value type Default: a constant property map returning `false` for any edge |
  a property map associating to each vertex of `pmesh` a unique index between `0` and `num_vertices(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::vertex_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map associating to each halfedge of `pmesh` a unique index between `0` and `num_halfedges(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::halfedge_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map associating to each face of `pmesh` a unique index between `0` and `num_faces(pmesh) - 1` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and `std::size_t` as value type Default: an automatically indexed internal map |
  a property map with the patch id's associated to the faces of `pmesh` Type: a class model of `ReadablePropertyMap` with `boost::graph_traits<PolygonMesh>::face_descriptor` as key type and the desired property, model of `CopyConstructible` as value type. Default: a default property map where each face is associated with the ID of the connected component it belongs to. Connected components are computed with respect to the constrained edges listed in the property map `edge_is_constrained_map` Extra: The map is updated during the remeshing process while new faces are created. |