Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Union_of_balls_medial_axis_3_builder< UnionOfBallsMedialAxis3 > Class Template Reference

Algorithm constructing the medial axis of an union of balls. More...

#include <Union_of_balls_medial_axis_3_builder.hpp>

Public Types

enum  Locate_type { NO_TAG = 0 , INSIDE_TAG , OUTSIDE_TAG }
 
typedef UnionOfBallsMedialAxis3::Weighted_alpha_complex_3 Weighted_alpha_complex_3
 
typedef UnionOfBallsMedialAxis3::Delaunay_triangulation_3 Delaunay_triangulation_3
 
typedef UnionOfBallsMedialAxis3::Vertex_handle Medial_axis_vertex_handle
 
typedef UnionOfBallsMedialAxis3::Halfedge_handle Medial_axis_halfedge_handle
 
typedef UnionOfBallsMedialAxis3::Face_handle Medial_axis_face_handle
 
typedef Weighted_alpha_complex_3::Cell_handle Weighted_alpha_complex_cell_handle
 
typedef Weighted_alpha_complex_3::Facet Weighted_alpha_complex_facet
 
typedef Weighted_alpha_complex_3::Edge Weighted_alpha_complex_edge
 
typedef Weighted_alpha_complex_3::Vertex_handle Weighted_alpha_complex_vertex_handle
 
typedef boost::tuple< Medial_axis_vertex_handle, Medial_axis_vertex_handleMedial_axis_edge_canonical
 
typedef Delaunay_triangulation_3::Cell_handle Delaunay_cell_handle
 
typedef Delaunay_triangulation_3::Facet Delaunay_facet
 
typedef Delaunay_triangulation_3::Edge Delaunay_edge
 
typedef Delaunay_triangulation_3::Vertex_handle Delaunay_vertex_handle
 

Public Member Functions

 T_Union_of_balls_medial_axis_3_builder (void)
 
 ~T_Union_of_balls_medial_axis_3_builder (void)
 

Functor

void operator() (UnionOfBallsMedialAxis3 &medial_axis)
 Functor constructing the medial axis of an union of balls. More...
 

Accessors

const Delaunay_facet_to_vertex_map & get_crossing_edges (void) const
 Return the map from crossing-edges to the incident alpha-shape vertices. More...
 
const Delaunay_facet_to_edge_map & get_alpha_complex_edges (void) const
 Return the map from alpha-shape edges to the corresponding edges in the alpha-shape. More...
 
const Delaunay_cell_to_locate_map & get_cells_location (void) const
 Return the map from dual of Voronoi vertices to their location wrt the alpha-shape. More...
 

Detailed Description

template<class UnionOfBallsMedialAxis3>
class SBL::GT::T_Union_of_balls_medial_axis_3_builder< UnionOfBallsMedialAxis3 >

Algorithm constructing the medial axis of an union of balls.

The medial axis of a closed surface is the set of centers of empty balls which touch the surface at more than one point. For an union of balls B, the medial axis is the intersection of the alpha-shape of B for alpha = 0, with the Voronoi diagram of the intersection points at the boundary of B.

The method for computing this medial axis follows the article The medial axis of a union of balls from Amenta et al in 2001. It consists on 8 steps:

  • Step 0: computing the weighted alpha-shape of the input balls.
  • Step 1: adding to the medial axis all singular faces of the 0-shape.
  • Step 2: computing the Delaunay triangulation of intersection points on the boundary of union of input balls.
  • Step 3: determining crossing and alpha-shape edges of dual of the Delaunay triangulation.
  • Step 4: tagging as inside of the medial axis all Voronoi vertices that are centers of input balls.
  • Step 5: tagging as outside of the medial axis all infinite Voronoi vertices.
  • Step 6: for each Voronoi cell with at least one labeled vertex not bounding an alpha-shape edge, labeling as inside or outside all bounding Voronoi vertices.
  • Step 7: adding all full / clipped Voronoi faces that are in the medial axis.

Note that all intermediate data structures are stored during the process and the class provides accessors for these data structures.

Template Parameters
KernelGeometric kernel for constant size objects, predicates and constructions from the CGAL library
RealTypeRepresentation of a real number for Delaunay computation

Member Typedef Documentation

◆ Delaunay_cell_handle

typedef Delaunay_triangulation_3::Cell_handle Delaunay_cell_handle

◆ Delaunay_edge

typedef Delaunay_triangulation_3::Edge Delaunay_edge

◆ Delaunay_facet

typedef Delaunay_triangulation_3::Facet Delaunay_facet

◆ Delaunay_triangulation_3

typedef UnionOfBallsMedialAxis3:: Delaunay_triangulation_3 Delaunay_triangulation_3

◆ Delaunay_vertex_handle

typedef Delaunay_triangulation_3::Vertex_handle Delaunay_vertex_handle

◆ Medial_axis_edge_canonical

◆ Medial_axis_face_handle

typedef UnionOfBallsMedialAxis3:: Face_handle Medial_axis_face_handle

◆ Medial_axis_halfedge_handle

typedef UnionOfBallsMedialAxis3:: Halfedge_handle Medial_axis_halfedge_handle

◆ Medial_axis_vertex_handle

typedef UnionOfBallsMedialAxis3:: Vertex_handle Medial_axis_vertex_handle

◆ Weighted_alpha_complex_3

typedef UnionOfBallsMedialAxis3:: Weighted_alpha_complex_3 Weighted_alpha_complex_3

◆ Weighted_alpha_complex_cell_handle

typedef Weighted_alpha_complex_3::Cell_handle Weighted_alpha_complex_cell_handle

◆ Weighted_alpha_complex_edge

typedef Weighted_alpha_complex_3::Edge Weighted_alpha_complex_edge

◆ Weighted_alpha_complex_facet

typedef Weighted_alpha_complex_3::Facet Weighted_alpha_complex_facet

◆ Weighted_alpha_complex_vertex_handle

typedef Weighted_alpha_complex_3::Vertex_handle Weighted_alpha_complex_vertex_handle

Member Enumeration Documentation

◆ Locate_type

Enumerator
NO_TAG 
INSIDE_TAG 
OUTSIDE_TAG 

Constructor & Destructor Documentation

◆ T_Union_of_balls_medial_axis_3_builder()

◆ ~T_Union_of_balls_medial_axis_3_builder()

Member Function Documentation

◆ get_alpha_complex_edges()

const Delaunay_facet_to_edge_map & get_alpha_complex_edges ( void  ) const
inline

Return the map from alpha-shape edges to the corresponding edges in the alpha-shape.

◆ get_cells_location()

const Delaunay_cell_to_locate_map & get_cells_location ( void  ) const
inline

Return the map from dual of Voronoi vertices to their location wrt the alpha-shape.

◆ get_crossing_edges()

const Delaunay_facet_to_vertex_map & get_crossing_edges ( void  ) const
inline

Return the map from crossing-edges to the incident alpha-shape vertices.

◆ operator()()

OutputIterator operator() ( UnionOfBallsMedialAxis3 &  medial_axis)
inline

Functor constructing the medial axis of an union of balls.

Given a set of spheres in the range [begin, end), this functor computes the medial axis of their union and store it in a data structure via the output iterator out. It is possible to set an output stream to collect high level information during the processing.