Partitioning Operations

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

Files
file	partition.h
	Convenience header file including the headers for all the partitioning-related free functions of this package.

Functions
template<typename Graph , typename Visitor , typename IsTerminal >
void	CGAL::split_graph_into_polylines (const Graph &graph, Visitor &polyline_visitor, IsTerminal is_terminal)
	splits into polylines the graph g at vertices of degree greater than 2 and at vertices for which is_terminal(v,graph)==true.
template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
void	CGAL::METIS::partition_graph (const TriangleMesh &tm, int nparts, const NamedParameters &np=parameters::default_values())
	computes a partition of the input triangular mesh into nparts parts, based on the mesh's nodal graph.
template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
void	CGAL::METIS::partition_dual_graph (const TriangleMesh &tm, int nparts, const NamedParameters &np=parameters::default_values())
	computes a partition of the input triangular mesh into nparts parts, based on the mesh's dual graph.
template<typename InputGraph , typename EdgeCostMap , typename VertexLabelCostMap , typename VertexLabelMap , typename NamedParameters = parameters::Default_named_parameters>
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=parameters::default_values())
	regularizes a partition of a graph into n labels using the alpha expansion algorithm [1].

Function Documentation

alpha_expansion_graphcut()

template<typename InputGraph , typename EdgeCostMap , typename VertexLabelCostMap , typename VertexLabelMap , typename NamedParameters = parameters::Default_named_parameters>

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 = parameters::default_values()
	)

#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 = parameters::Default_named_parameters>

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

#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 = parameters::Default_named_parameters>

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

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

split_graph_into_polylines()

template<typename Graph , typename Visitor , typename IsTerminal >

void CGAL::split_graph_into_polylines	(	const Graph &	graph,
		Visitor &	polyline_visitor,
		IsTerminal	is_terminal
	)

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

splits into polylines the graph g at vertices of degree greater than 2 and at vertices for which is_terminal(v,graph)==true.

The polylines are reported using a visitor.

Template Parameters

Graph	a model of the boost concepts VertexListGraph and EdgeListGraph.
Visitor	a class that provides: void start_new_polyline() called when starting the description of a polyline. void add_node(typename boost::graph_traits<Graph>::vertex_descriptor v) called for each vertex v of the polyline currently described. If the polyline is closed this function will be called twice for the first vertex of the cycle picked (once after calling start_new_polyline() and once before the call to end_polyline(). void end_polyline() called when the description of a polyline is finished.
IsTerminal	A functor providing bool operator()(boost::graph_traits<Graph>::vertex_descriptor v, const Graph& g) const returning true if the vertex v of degree 2 is a polyline endpoint and false otherwise.

An overload without is_terminal is provided if no vertices but those of degree different from 2 are polyline endpoints.

Todo:

Document the version with four parameters

Examples

Surface_mesh_skeletonization/simple_mcfskel_example.cpp.