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>

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

Kernel	Geometric kernel for constant size objects, predicates and constructions from the CGAL library
RealType	Representation of a real number for Delaunay computation

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.