CGAL 5.1 - CGAL and the Boost Graph Library

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
InputGrapha model of VertexAndEdgeListGraph
EdgeCostMapa model of ReadablePropertyMap with boost::graph_traits<InputGraph>::edge_descriptor as key and double as value
VertexLabelCostMapa model of ReadablePropertyMap with boost::graph_traits<InputGraph>::vertex_descriptor as key and std::vector<double> as value
VertexLabelMapa model of ReadWritePropertyMap with boost::graph_traits<InputGraph>::vertex_descriptor as key and std::size_t as value
NamedParametersa sequence of named parameters
Parameters
input_graphthe input graph.
edge_cost_mapa property map providing the weight of each edge.
vertex_label_mapa 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_mapa 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.
npoptional sequence of named parameters among the ones listed below
Named Parameters
vertex_index_mapa property map providing the index of each vertex
implementation_tagtag 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
tma triangle mesh
npartsthe number of parts in the final partition
npoptional Named Parameters described below
Template Parameters
TriangleMeshis a model of the FaceListGraph concept.
NamedParametersa sequence of Named Parameters
Named Parameters
vertex_index_mapis a property map containing for each vertex of tm a unique index between 0 and num_vertices(tm)-1.
METIS_optionsis 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_mapis a property map that contains (after the function has been run) the ID of the subpart for each vertex of tm.
face_partition_id_mapis 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
tma triangle mesh
npartsthe number of parts in the final partition
npoptional Named Parameters described below
Template Parameters
TriangleMeshis a model of the FaceListGraph concept.
NamedParametersa sequence of Named Parameters
Named Parameters
vertex_index_mapis a property map containing for each vertex of tm a unique index between 0 and num_vertices(tm)-1.
METIS_optionsis 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_mapis a property map that contains (after the function has been run) the ID of the subpart for each vertex of tm.
face_partition_id_mapis 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.