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)
template<typename TriangleMesh , typename NamedParameters >
void	CGAL::METIS::partition_dual_graph (const TriangleMesh &tm, int nparts, const NamedParameters &np)
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)

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	optional sequence of named parameters among the ones listed below

Named Parameters

vertex_index_map	a property map providing the index of each vertex
implementation_tag	tag used to select which implementation of the alpha expansion should be used. Available implementation tags are: CGAL::Alpha_expansion_boost_adjacency_list (default) CGAL::Alpha_expansion_boost_compressed_sparse_row_tag CGAL::Alpha_expansion_MaxFlow_tag

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	optional Named Parameters described below

Template Parameters

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

Named Parameters

vertex_index_map	is a property map containing for each vertex of tm a unique index between 0 and num_vertices(tm)-1.
METIS_options	is a parameter used in to pass options to the METIS mesh partitioner. The many options of METIS are not described here. Instead, users should refer to the documentation of METIS directly.
vertex_partition_id_map	is a property map that contains (after the function has been run) the ID of the subpart for each vertex of tm.
face_partition_id_map	is a property map that contains (after the function has been run) the ID of the subpart for each face of tm.

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	optional Named Parameters described below

Template Parameters

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

Named Parameters

vertex_index_map	is a property map containing for each vertex of tm a unique index between 0 and num_vertices(tm)-1.
METIS_options	is a parameter used in to pass options to the METIS mesh partitioner. The many options of METIS are not described here. Instead, users should refer to the documentation of METIS directly.
vertex_partition_id_map	is a property map that contains (after the function has been run) the ID of the subpart for each vertex of tm.
face_partition_id_map	is a property map that contains (after the function has been run) the ID of the subpart for each face of tm.

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.