Connected Components

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 >
FaceOutputIterator	CGAL::Polygon_mesh_processing::connected_component (typename boost::graph_traits< PolygonMesh >::face_descriptor seed_face, const PolygonMesh &pmesh, FaceOutputIterator out, const NamedParameters &np)
	discovers all the faces in the same connected component as seed_face and records them in out. More...
template<typename PolygonMesh , typename FaceComponentMap , typename NamedParameters >
boost::property_traits< FaceComponentMap >::value_type	CGAL::Polygon_mesh_processing::connected_components (const PolygonMesh &pmesh, FaceComponentMap fcm, const NamedParameters &np)
	computes for each face the index of the corresponding connected component. More...
template<typename PolygonMesh , typename NamedParameters >
std::size_t	CGAL::Polygon_mesh_processing::keep_largest_connected_components (PolygonMesh &pmesh, std::size_t nb_components_to_keep, const NamedParameters &np)
	removes the small connected components and all isolated vertices. More...
template<typename PolygonMesh , typename ThresholdValueType , typename NamedParameters >
std::size_t	CGAL::Polygon_mesh_processing::keep_large_connected_components (PolygonMesh &pmesh, const ThresholdValueType threshold_value, const NamedParameters &np)
	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. More...
template<typename PolygonMesh , typename ComponentRange , typename FaceComponentMap , typename NamedParameters >
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. More...
template<typename PolygonMesh , typename ComponentRange , typename FaceComponentMap , typename NamedParameters >
void	CGAL::Polygon_mesh_processing::remove_connected_components (PolygonMesh &pmesh, const ComponentRange &components_to_remove, const FaceComponentMap &fcm, const NamedParameters &np)
	removes in pmesh the connected components designated by theirs ids in components_to_remove as well as all isolated vertices. More...
template<typename PolygonMesh , typename FaceRange , typename NamedParameters >
void	CGAL::Polygon_mesh_processing::remove_connected_components (PolygonMesh &pmesh, const FaceRange &components_to_remove, const NamedParameters &np)
	keeps the connected components not designated by the faces in components_to_remove, and removes the other connected components and all isolated vertices. More...
template<typename PolygonMesh , typename FaceRange , typename NamedParameters >
void	CGAL::Polygon_mesh_processing::keep_connected_components (PolygonMesh &pmesh, const FaceRange &components_to_keep, const NamedParameters &np)
	keeps the connected components designated by the faces in components_to_keep, and removes the other connected components and all isolated vertices. More...
template<class PolygonMesh , class PolygonMeshRange , class NamedParameters >
void	CGAL::Polygon_mesh_processing::split_connected_components (const PolygonMesh &pmesh, PolygonMeshRange &cc_meshes, const NamedParameters &np)
	identifies the connected components of pmesh and pushes back a new PolygonMesh for each connected component in cc_meshes. More...

Function Documentation

connected_component()

template<typename PolygonMesh , typename FaceOutputIterator , typename NamedParameters >

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

#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

edge_is_constrained_map 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.

Examples:

Polygon_mesh_processing/connected_components_example.cpp.

connected_components()

template<typename PolygonMesh , typename FaceComponentMap , typename NamedParameters >

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

#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

edge_is_constrained_map 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
face_index_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

Returns

the number of connected components.

Examples:

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

keep_connected_components() [1/2]

template<typename PolygonMesh , typename ComponentRange , typename FaceComponentMap , typename NamedParameters >

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 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

vertex_index_map 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

keep_connected_components() [2/2]

template<typename PolygonMesh , typename FaceRange , typename NamedParameters >

void CGAL::Polygon_mesh_processing::keep_connected_components	(	PolygonMesh &	pmesh,
		const FaceRange &	components_to_keep,
		const NamedParameters &	np
	)

#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

edge_is_constrained_map 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
vertex_index_map 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
face_index_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

keep_large_connected_components()

template<typename PolygonMesh , typename ThresholdValueType , typename NamedParameters >

std::size_t CGAL::Polygon_mesh_processing::keep_large_connected_components	(	PolygonMesh &	pmesh,
		const ThresholdValueType	threshold_value,
		const NamedParameters &	np
	)

#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
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

edge_is_constrained_map 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
vertex_index_map 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
face_index_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
face_size_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
dry_run 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
output_iterator 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

Precondition

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.

Returns

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

Examples:

Polygon_mesh_processing/connected_components_example.cpp.

keep_largest_connected_components()

template<typename PolygonMesh , typename NamedParameters >

std::size_t CGAL::Polygon_mesh_processing::keep_largest_connected_components	(	PolygonMesh &	pmesh,
		std::size_t	nb_components_to_keep,
		const NamedParameters &	np
	)

#include <CGAL/Polygon_mesh_processing/connected_components.h>

removes the small connected components and all isolated vertices.

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

edge_is_constrained_map 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
vertex_index_map 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
face_index_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
face_size_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
dry_run 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
output_iterator 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).

Examples:

Polygon_mesh_processing/connected_components_example.cpp.

remove_connected_components() [1/2]

template<typename PolygonMesh , typename ComponentRange , typename FaceComponentMap , typename NamedParameters >

void CGAL::Polygon_mesh_processing::remove_connected_components	(	PolygonMesh &	pmesh,
		const ComponentRange &	components_to_remove,
		const FaceComponentMap &	fcm,
		const NamedParameters &	np
	)

#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

vertex_index_map 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

remove_connected_components() [2/2]

template<typename PolygonMesh , typename FaceRange , typename NamedParameters >

void CGAL::Polygon_mesh_processing::remove_connected_components	(	PolygonMesh &	pmesh,
		const FaceRange &	components_to_remove,
		const NamedParameters &	np
	)

#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
NamedParameters	a sequence of Named Parameters
FaceRange	a range of boost::graph_traits<PolygonMesh>::face_descriptor indicating the connected components to be removed.

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

edge_is_constrained_map 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
vertex_index_map 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
face_index_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

split_connected_components()

template<class PolygonMesh , class PolygonMeshRange , class NamedParameters >

void CGAL::Polygon_mesh_processing::split_connected_components	(	const PolygonMesh &	pmesh,
		PolygonMeshRange &	cc_meshes,
		const NamedParameters &	np
	)

#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
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

edge_is_constrained_map 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
vertex_index_map 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
halfedge_index_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
face_index_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
face_patch_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.