DGtal  1.3.beta
Public Types | Public Member Functions | Static Public Attributes
DGtal::ConvexityHelper< dim, TInteger, TInternalInteger > Struct Template Reference

Aim: Provides a set of functions to facilitate the computation of convex hulls and polytopes, as well as shortcuts to build cell complex representing a Delaunay complex. More...

#include <DGtal/geometry/volumes/ConvexityHelper.h>

Public Types

typedef TInteger Integer
 
typedef TInternalInteger InternalInteger
 
typedef SpaceND< dim, IntegerSpace
 
typedef Space::Point Point
 
typedef Space::Vector Vector
 
typedef Space::RealPoint RealPoint
 
typedef Space::RealVector RealVector
 
typedef std::size_t Size
 
typedef std::size_t Index
 
typedef std::vector< IndexIndexRange
 
typedef ConvexHullIntegralKernel< dim, Integer, InternalIntegerLatticeConvexHullKernel
 
typedef ConvexHullRationalKernel< dim, Integer, InternalIntegerRealConvexHullKernel
 
typedef DelaunayIntegralKernel< dim, Integer, InternalIntegerLatticeDelaunayKernel
 
typedef DelaunayRationalKernel< dim, Integer, InternalIntegerRealDelaunayKernel
 
typedef BoundedLatticePolytope< SpaceLatticePolytope
 
typedef BoundedRationalPolytope< SpaceRationalPolytope
 

Public Member Functions

 BOOST_STATIC_ASSERT (dim > 1)
 
 BOOST_CONCEPT_ASSERT ((concepts::CInteger< TInteger >))
 
 BOOST_CONCEPT_ASSERT ((concepts::CInteger< TInternalInteger >))
 

Static Public Member Functions

Lattice convex hull services
static LatticePolytope computeLatticePolytope (const std::vector< Point > &input_points, bool remove_duplicates=true, bool make_minkowski_summable=false)
 
template<typename TSurfaceMesh >
static bool computeConvexHullBoundary (TSurfaceMesh &mesh, const std::vector< Point > &input_points, bool remove_duplicates=true)
 
static bool computeConvexHullBoundary (PolygonalSurface< Point > &polysurf, const std::vector< Point > &input_points, bool remove_duplicates=true)
 
static bool computeConvexHullCellComplex (ConvexCellComplex< Point > &cell_complex, const std::vector< Point > &input_points, bool remove_duplicates=true)
 
static LatticePolytope computeSimplex (const std::vector< Point > &input_points, bool remove_duplicates=true)
 
static LatticePolytope computeDegeneratedLatticePolytope (std::vector< Point > &input_points)
 
Lattice Delaunay services
static bool computeDelaunayCellComplex (ConvexCellComplex< Point > &cell_complex, const std::vector< Point > &input_points, bool remove_duplicates=true)
 
Rational convex hull services
static RationalPolytope computeRationalPolytope (const std::vector< RealPoint > &input_points, Integer denominator, bool remove_duplicates=true, bool make_minkowski_summable=false)
 
template<typename TSurfaceMesh >
static bool computeConvexHullBoundary (TSurfaceMesh &mesh, const std::vector< RealPoint > &input_points, double precision=1024.0, bool remove_duplicates=true)
 
static bool computeConvexHullBoundary (PolygonalSurface< RealPoint > &polysurf, const std::vector< RealPoint > &input_points, double precision=1024.0, bool remove_duplicates=true)
 
static bool computeConvexHullCellComplex (ConvexCellComplex< RealPoint > &cell_complex, const std::vector< RealPoint > &input_points, double precision=1024.0, bool remove_duplicates=true)
 
Real Delaunay services
static bool computeDelaunayCellComplex (ConvexCellComplex< RealPoint > &cell_complex, const std::vector< RealPoint > &input_points, double precision=1024.0, bool remove_duplicates=true)
 
Utility services
template<typename QHull >
static void computeFacetAndRidgeVertices (const QHull &hull, std::vector< IndexRange > &cell_vertices, std::map< typename QHull::Ridge, Index > &r2f, std::vector< IndexRange > &face_vertices)
 

Static Public Attributes

static const Dimension dimension = dim
 

Detailed Description

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
struct DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >

Aim: Provides a set of functions to facilitate the computation of convex hulls and polytopes, as well as shortcuts to build cell complex representing a Delaunay complex.

Description of template class 'ConvexityHelper'

Template Parameters
dimthe dimension of the space where points and further objects live.
TIntegerthe integral type used to define the digital space, a model of concepts::CInteger. It sets the coordinate type of input lattice points as well as output integral convex hulls and lattice polytopes.
TInternalIntegerthe integer type that is used for internal computations of above/below plane tests, a model of concepts::CInteger. Must be at least as precise as TCoordinateInteger.
See also
QuickHull algorithm in arbitrary dimension for convex hull and Delaunay cell complex computation
Examples
geometry/tools/exampleQuickHull3D.cpp.

Definition at line 164 of file ConvexityHelper.h.

Member Typedef Documentation

◆ Index

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef std::size_t DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::Index

Definition at line 181 of file ConvexityHelper.h.

◆ IndexRange

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef std::vector< Index > DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::IndexRange

Definition at line 182 of file ConvexityHelper.h.

◆ Integer

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef TInteger DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::Integer

Definition at line 173 of file ConvexityHelper.h.

◆ InternalInteger

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef TInternalInteger DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::InternalInteger

Definition at line 174 of file ConvexityHelper.h.

◆ LatticeConvexHullKernel

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef ConvexHullIntegralKernel< dim, Integer, InternalInteger > DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::LatticeConvexHullKernel

Definition at line 184 of file ConvexityHelper.h.

◆ LatticeDelaunayKernel

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef DelaunayIntegralKernel< dim, Integer, InternalInteger > DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::LatticeDelaunayKernel

Definition at line 188 of file ConvexityHelper.h.

◆ LatticePolytope

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef BoundedLatticePolytope< Space > DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::LatticePolytope

Definition at line 191 of file ConvexityHelper.h.

◆ Point

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef Space::Point DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::Point

Definition at line 176 of file ConvexityHelper.h.

◆ RationalPolytope

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef BoundedRationalPolytope< Space > DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::RationalPolytope

Definition at line 192 of file ConvexityHelper.h.

◆ RealConvexHullKernel

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef ConvexHullRationalKernel< dim, Integer, InternalInteger > DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::RealConvexHullKernel

Definition at line 186 of file ConvexityHelper.h.

◆ RealDelaunayKernel

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef DelaunayRationalKernel< dim, Integer, InternalInteger > DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::RealDelaunayKernel

Definition at line 190 of file ConvexityHelper.h.

◆ RealPoint

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef Space::RealPoint DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::RealPoint

Definition at line 178 of file ConvexityHelper.h.

◆ RealVector

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef Space::RealVector DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::RealVector

Definition at line 179 of file ConvexityHelper.h.

◆ Size

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef std::size_t DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::Size

Definition at line 180 of file ConvexityHelper.h.

◆ Space

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef SpaceND< dim, Integer > DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::Space

Definition at line 175 of file ConvexityHelper.h.

◆ Vector

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
typedef Space::Vector DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::Vector

Definition at line 177 of file ConvexityHelper.h.

Member Function Documentation

◆ BOOST_CONCEPT_ASSERT() [1/2]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< TInteger >)  )

◆ BOOST_CONCEPT_ASSERT() [2/2]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< TInternalInteger >)  )

◆ BOOST_STATIC_ASSERT()

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::BOOST_STATIC_ASSERT ( dim  ,
 
)

◆ computeConvexHullBoundary() [1/4]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static bool DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeConvexHullBoundary ( PolygonalSurface< Point > &  polysurf,
const std::vector< Point > &  input_points,
bool  remove_duplicates = true 
)
static

Computes a polygonal surface representation of the boundary of the convex hull of the given lattice points.

Note
Since it builds a surface, this method is thus 3D.
Parameters
[out]polysurfthe output polygonal surface that represents the boundary of the convex hull of the given range of points. Its euler characteristic should be 0 in even dimension, 2 in odd dimension.
[in]input_pointsthe range of input lattice points.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
'true' if the input points were full dimensional and the output surface is correct, otherwise return 'false'.

◆ computeConvexHullBoundary() [2/4]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static bool DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeConvexHullBoundary ( PolygonalSurface< RealPoint > &  polysurf,
const std::vector< RealPoint > &  input_points,
double  precision = 1024.0,
bool  remove_duplicates = true 
)
static

Computes a polygonal surface representation of the boundary of the rational polytope that approximates the convex hull of the given real points.

Note
Since it builds a surface, this method is thus 3D.
Parameters
[out]polysurfthe output polygonal surface mesh that represents the boundary of the convex hull of the given range of points.
[in]input_pointsthe range of input real points.
[in]precisionthe scaling factor that is used to multiply each real coordinate before rounding it to an integer, a kind of common denominator if you think of the result as a rational number.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
'true' if the input points were full dimensional and the output mesh is correct, otherwise return 'false'.

◆ computeConvexHullBoundary() [3/4]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
template<typename TSurfaceMesh >
static bool DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeConvexHullBoundary ( TSurfaceMesh &  mesh,
const std::vector< Point > &  input_points,
bool  remove_duplicates = true 
)
static

Computes a surface mesh representation of the boundary of the convex hull of the given lattice points.

Note
Since it builds a surface, this method is thus 3D.
Template Parameters
TSurfaceMeshany model of surface that can be initialized with a range of input positions (cast as real coordinates) and a range of index ranges giving for each face its range of incident vertices. For instance, you may use class SurfaceMesh.
Parameters
[out]meshthe output surface mesh that represents the boundary of the convex hull of the given range of points.
[in]input_pointsthe range of input lattice points.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
'true' if the input points were full dimensional and the output mesh is correct, otherwise return 'false'.

◆ computeConvexHullBoundary() [4/4]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
template<typename TSurfaceMesh >
static bool DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeConvexHullBoundary ( TSurfaceMesh &  mesh,
const std::vector< RealPoint > &  input_points,
double  precision = 1024.0,
bool  remove_duplicates = true 
)
static

Computes a surface mesh representation of the boundary of the rational polytope that approximates the convex hull of the given real points.

Note
Since it builds a surface, this method is thus 3D.
Template Parameters
TSurfaceMeshany model of surface that can be initialized with a range of input positions (cast as real coordinates) and a range of index ranges giving for each face its range of incident vertices. For instance, you may use class SurfaceMesh.
Parameters
[out]meshthe output surface mesh that represents the boundary of the convex hull of the given range of points.
[in]input_pointsthe range of input real points.
[in]precisionthe scaling factor that is used to multiply each real coordinate before rounding it to an integer, a kind of common denominator if you think of the result as a rational number.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
'true' if the input points were full dimensional and the output mesh is correct, otherwise return 'false'.

◆ computeConvexHullCellComplex() [1/2]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static bool DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeConvexHullCellComplex ( ConvexCellComplex< Point > &  cell_complex,
const std::vector< Point > &  input_points,
bool  remove_duplicates = true 
)
static

Computes a cell complex representing the convex hull of the given lattice points, formed of one maximal dimension cell and as many cells of codimension 1 as the number of facets of the convex hull.

Parameters
[out]cell_complexthe output cell complex that represents the convex hull of the given lattice points.
[in]input_pointsthe range of input lattice points.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
'true' if the input points were full dimensional and the output complex is correct, otherwise return 'false'.

◆ computeConvexHullCellComplex() [2/2]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static bool DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeConvexHullCellComplex ( ConvexCellComplex< RealPoint > &  cell_complex,
const std::vector< RealPoint > &  input_points,
double  precision = 1024.0,
bool  remove_duplicates = true 
)
static

Computes a cell complex representing the convex hull of the given real points, formed of one maximal dimension cell and as many cells of codimension 1 as the number of facets of the convex hull.

Parameters
[out]cell_complexthe output cell complex that represents the convex hull of the given real points.
[in]input_pointsthe range of input real points.
[in]precisionthe scaling factor that is used to multiply each real coordinate before rounding it to an integer, a kind of common denominator if you think of the result as a rational number.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
'true' if the input points were full dimensional and the output complex is correct, otherwise return 'false'.

◆ computeDegeneratedLatticePolytope()

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static LatticePolytope DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeDegeneratedLatticePolytope ( std::vector< Point > &  input_points)
static

Computes the lattice polytope enclosing a range of distinct points, arranged such that they do not form a full dimensional polytope.

Note
Called internally by ConvexityHelper::computeLatticePolytope and ConvexityHelper::computeSimplex.
This function works for dimension no greater than 3.
Parameters
[in,out]input_pointsa range of distinct points, which may be changed by the method. More precisely a point may be added (in 3D) to complete the set of points so that it forms a full dimensional polytope.
Returns
the tightiest bounded lattice polytope (i.e. H-representation) including the given range of points, or an empty polytope if the given range of points was not full dimensional and dimension was greater than 3.

◆ computeDelaunayCellComplex() [1/2]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static bool DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeDelaunayCellComplex ( ConvexCellComplex< Point > &  cell_complex,
const std::vector< Point > &  input_points,
bool  remove_duplicates = true 
)
static

Computes the Delaunay cell complex associated to the given range of input points.

Parameters
[out]cell_complexthe output cell complex that represents the Delaunay complex of the given lattice points.
[in]input_pointsthe range of input lattice points.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
'true' if the input points were full dimensional and the output complex is correct, otherwise return 'false'.
Note
The Delaunay cell complex may not be simplicial if some points are cospherical.
Examples
geometry/tools/exampleLatticeBallDelaunay3D.cpp, and geometry/tools/exampleRationalBallDelaunay3D.cpp.

Referenced by main().

◆ computeDelaunayCellComplex() [2/2]

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static bool DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeDelaunayCellComplex ( ConvexCellComplex< RealPoint > &  cell_complex,
const std::vector< RealPoint > &  input_points,
double  precision = 1024.0,
bool  remove_duplicates = true 
)
static

Computes the Delaunay cell complex associated to the given range of input real points.

Parameters
[out]cell_complexthe output cell complex that represents the Delaunay complex of the given lattice points.
[in]input_pointsthe range of input real points.
[in]precisionthe scaling factor that is used to multiply each real coordinate before rounding it to an integer, a kind of common denominator if you think of the result as a rational number.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
'true' if the input points were full dimensional and the output complex is correct, otherwise return 'false'.
Note
The Delaunay cell complex may not be simplicial if some points are cospherical.

◆ computeFacetAndRidgeVertices()

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
template<typename QHull >
static void DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeFacetAndRidgeVertices ( const QHull &  hull,
std::vector< IndexRange > &  cell_vertices,
std::map< typename QHull::Ridge, Index > &  r2f,
std::vector< IndexRange > &  face_vertices 
)
static
Template Parameters
QHullany QuickHull concrete type.
Parameters
[in]hulla computed QuickHull object
[out]cell_verticesthe vector giving for each cell the indices of its vertices.
[out]r2fthe map giving for each ridge (i.e. the pair of cells defining each face) the index of its corresponding face.
[out]face_verticesthe vector giving for each face the indices of its vertices.
Precondition
hull.status() >= Status::VerticesCompleted and hull.status() <= Status::AllCompleted

◆ computeLatticePolytope()

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static LatticePolytope DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeLatticePolytope ( const std::vector< Point > &  input_points,
bool  remove_duplicates = true,
bool  make_minkowski_summable = false 
)
static

Computes and returns a halfspace representation of the tightiest lattice polytope enclosing all the given input lattice points.

Parameters
[in]input_pointsthe range of input lattice points.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
[in]make_minkowski_summableOther constraints are added so that we can perform axis aligned Minkowski sums on this polytope. Useful for checking full convexity (see moduleDigitalConvexity).
Returns
the tightiest bounded lattice polytope (i.e. H-representation) including the given range of points, or an empty polytope if the given range of points was not full dimensional.

◆ computeRationalPolytope()

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static RationalPolytope DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeRationalPolytope ( const std::vector< RealPoint > &  input_points,
Integer  denominator,
bool  remove_duplicates = true,
bool  make_minkowski_summable = false 
)
static

Computes and returns a halfspace representation of the tightiest rational polytope enclosing all the given input real points.

Parameters
[in]input_pointsthe range of input real points.
[in]denominatorthe denominator used in all rational approximations of points with real value coordinates, the higher the more precise.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
[in]make_minkowski_summableOther constraints are added so that we can perform axis aligned Minkowski sums on this polytope. Useful for checking full convexity (see moduleDigitalConvexity).
Returns
the tightiest bounded lattice polytope (i.e. H-representation) including the given range of points, or an empty polytope if the given range of points was not full dimensional.

◆ computeSimplex()

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
static LatticePolytope DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::computeSimplex ( const std::vector< Point > &  input_points,
bool  remove_duplicates = true 
)
static

Computes the lattice polytope enclosing a range of at most dimension+1 distinct points.

Note
Called internally by ConvexityHelper::computeLatticePolytope.
This function works for arbitrary full dimensional simplex. If the set of points is not full dimensional, it is able to build a non full dimensional simplex for dimensions <= 3.
Parameters
input_pointsa range of points, with at most dimension+1 distinct points.
[in]remove_duplicatesshould be set to 'true' if the input data has duplicates.
Returns
the tightiest bounded lattice polytope (i.e. H-representation) including the given range of points, or an empty polytope if the given range of points was not full dimensional and dimension was greater than 3.

Field Documentation

◆ dimension

template<int dim, typename TInteger = DGtal::int32_t, typename TInternalInteger = DGtal::int64_t>
const Dimension DGtal::ConvexityHelper< dim, TInteger, TInternalInteger >::dimension = dim
static

Definition at line 171 of file ConvexityHelper.h.


The documentation for this struct was generated from the following file: