Partitioning Operations

Methods to split a mesh into subdomains, using the library METIS or a graphcut implementation.

Functions
template<typename TriangleMesh , typename NamedParameters >
void	CGAL::METIS::partition_graph (const TriangleMesh &tm, int nparts, const NamedParameters &np)
	computes a partition of the input triangular mesh into nparts parts, based on the mesh's nodal graph. More...
template<typename TriangleMesh , typename NamedParameters >
void	CGAL::METIS::partition_dual_graph (const TriangleMesh &tm, int nparts, const NamedParameters &np)
	computes a partition of the input triangular mesh into nparts parts, based on the mesh's dual graph. More...
template<typename InputGraph , typename EdgeCostMap , typename VertexLabelCostMap , typename VertexLabelMap , typename NamedParameters >
double	CGAL::alpha_expansion_graphcut (const InputGraph &input_graph, EdgeCostMap edge_cost_map, VertexLabelCostMap vertex_label_cost_map, VertexLabelMap vertex_label_map, const NamedParameters &np)
	regularizes a partition of a graph into n labels using the alpha expansion algorithm [1]. More...

Function Documentation

alpha_expansion_graphcut()

template<typename InputGraph , typename EdgeCostMap , typename VertexLabelCostMap , typename VertexLabelMap , typename NamedParameters >

double CGAL::alpha_expansion_graphcut	(	const InputGraph &	input_graph,
		EdgeCostMap	edge_cost_map,
		VertexLabelCostMap	vertex_label_cost_map,
		VertexLabelMap	vertex_label_map,
		const NamedParameters &	np
	)

#include <CGAL/boost/graph/alpha_expansion_graphcut.h>

regularizes a partition of a graph into n labels using the alpha expansion algorithm [1].

For a graph \((V,E)\), this function computes a partition f that minimizes the following cost function:

\[ \mathrm{C}(f) = \sum_{\{v0,v1\} \in E} C_E(v0,v1) + \sum_{v \in V} C_V(f_v) \]

where \(C_E(v0,v1)\) is the edge cost of assigning a different label to \(v0\) and \(v1\), and \(C_V(f_v)\) is the vertex cost of assigning the label \(f\) to the vertex \(v\).

Template Parameters

InputGraph	a model of VertexAndEdgeListGraph
EdgeCostMap	a model of ReadablePropertyMap with boost::graph_traits<InputGraph>::edge_descriptor as key and double as value
VertexLabelCostMap	a model of ReadablePropertyMap with boost::graph_traits<InputGraph>::vertex_descriptor as key and std::vector<double> as value
VertexLabelMap	a model of ReadWritePropertyMap with boost::graph_traits<InputGraph>::vertex_descriptor as key and std::size_t as value
NamedParameters	a sequence of named parameters

Parameters

input_graph	the input graph.
edge_cost_map	a property map providing the weight of each edge.
vertex_label_map	a property map providing the label of each vertex. This map will be updated by the algorithm with the regularized version of the partition.
vertex_label_cost_map	a property map providing, for each vertex, an std::vector containing the cost of this vertex to belong to each label. Each std::vector should have the same size n (which is the number of labels), each label being indexed from 0 to n-1. For example, get(vertex_label_cost_map, vd)[label_idx] returns the cost of vertex vd to belong to the label label_idx.
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 input_graph a unique index between 0 and num_vertices(input_graph) - 1 Type: a class model of ReadablePropertyMap with boost::graph_traits<InputGraph>::vertex_descriptor as key type and std::size_t as value type Default: an automatically indexed internal map Extra: If this parameter is not passed, internal machinery will create and initialize a face index property map, either using the internal property map if it exists or using an external map. The latter might result in - slightly - worsened performance in case of non-constant complexity for index access.

implementation_tag a tag used to select which implementation of the alpha expansion should be used. Available implementation tags are: CGAL::Alpha_expansion_boost_adjacency_list CGAL::Alpha_expansion_boost_compressed_sparse_row_tag CGAL::Alpha_expansion_MaxFlow_tag Default: CGAL::Alpha_expansion_boost_adjacency_list

Note

The MaxFlow implementation is provided by the Triangulated Surface Mesh Segmentation Reference under GPL license. The header <CGAL/boost/graph/Alpha_expansion_MaxFlow_tag.h> must be included if users want to use this implementation.

Examples:

BGL_graphcut/alpha_expansion_example.cpp.

partition_dual_graph()

template<typename TriangleMesh , typename NamedParameters >

void CGAL::METIS::partition_dual_graph	(	const TriangleMesh &	tm,
		int	nparts,
		const NamedParameters &	np
	)

#include <CGAL/boost/graph/METIS/partition_dual_graph.h>

computes a partition of the input triangular mesh into nparts parts, based on the mesh's dual graph.

The resulting partition is stored in the vertex and/or face property maps that are passed as parameters using Named Parameters.

Parameters

tm	a triangle mesh
nparts	the number of parts in the final partition
np	an optional sequence of Named Parameters among the ones listed below

Template Parameters

TriangleMesh	is a model of the FaceListGraph concept
NamedParameters	a sequence of Named Parameters

Optional Named Parameters

vertex_index_map a property map associating to each vertex of tm a unique index between 0 and num_vertices(tm) - 1 Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and std::size_t as value type Default: an automatically indexed internal map Extra: If this parameter is not passed, internal machinery will create and initialize a face index property map, either using the internal property map if it exists or using an external map. The latter might result in - slightly - worsened performance in case of non-constant complexity for index access.
METIS_options a parameter used in to pass options to the METIS mesh partitioner Type: an array of size METIS_NOPTIONS with value type idx_t (an integer type defined by METIS) Default: an array of size METIS_NOPTIONS with value type idx_t, initialized using the function METIS_SetDefaultOptions() Extra: The many options of METIS are not described here. Instead, users should refer to the documentation of METIS directly.
vertex_partition_id_map a property map that contains (after the function has been run) the ID of the subpart for each vertex of tm Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and int as value type Default: unused
face_partition_id_map a property map that contains (after the function has been run) the ID of the subpart for each face of tm Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::face_descriptor as key type and int as value type Default: unused

Precondition

tm is a pure triangular surface mesh: there are no edges without at least one incident face

Examples:

BGL_surface_mesh/surface_mesh_partition.cpp.

partition_graph()

template<typename TriangleMesh , typename NamedParameters >

void CGAL::METIS::partition_graph	(	const TriangleMesh &	tm,
		int	nparts,
		const NamedParameters &	np
	)

#include <CGAL/boost/graph/METIS/partition_graph.h>

computes a partition of the input triangular mesh into nparts parts, based on the mesh's nodal graph.

The resulting partition is stored in the vertex and/or face property maps that are passed as parameters using Named Parameters.

Parameters

tm	a triangle mesh
nparts	the number of parts in the final partition
np	an optional sequence of Named Parameters among the ones listed below

Template Parameters

TriangleMesh	is a model of the FaceListGraph concept.
NamedParameters	a sequence of Named Parameters

Optional Named Parameters

vertex_index_map a property map associating to each vertex of tm a unique index between 0 and num_vertices(tm) - 1 Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and std::size_t as value type Default: an automatically indexed internal map Extra: If this parameter is not passed, internal machinery will create and initialize a face index property map, either using the internal property map if it exists or using an external map. The latter might result in - slightly - worsened performance in case of non-constant complexity for index access.
METIS_options a parameter used in to pass options to the METIS mesh partitioner Type: an array of size METIS_NOPTIONS with value type idx_t (an integer type defined by METIS) Default: an array of size METIS_NOPTIONS with value type idx_t, initialized using the function METIS_SetDefaultOptions() Extra: The many options of METIS are not described here. Instead, users should refer to the documentation of METIS directly.
vertex_partition_id_map a property map that contains (after the function has been run) the ID of the subpart for each vertex of tm Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and int as value type Default: unused
face_partition_id_map a property map that contains (after the function has been run) the ID of the subpart for each face of tm Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::face_descriptor as key type and int as value type Default: unused

Precondition

tm is a pure triangular surface mesh: there are no edges without at least one incident face

Examples:

BGL_polyhedron_3/polyhedron_partition.cpp.