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_handle >	Medial_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

Kernel	Geometric kernel for constant size objects, predicates and constructions from the CGAL library
RealType	Representation 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

typedef boost::tuple<Medial_axis_vertex_handle, Medial_axis_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

enum 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 ( void  )

inline

~T_Union_of_balls_medial_axis_3_builder()

~T_Union_of_balls_medial_axis_3_builder ( void  )

inline

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.