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

◆ 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::edge_descriptor as key and double as value VertexLabelCostMap a model of ReadablePropertyMap with boost::graph_traits::vertex_descriptor as key and std::vector as value VertexLabelMap a model of ReadWritePropertyMap with boost::graph_traits::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.