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, Integer >	Space

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< Index >	IndexRange

typedef ConvexHullIntegralKernel< dim, Integer, InternalInteger >	LatticeConvexHullKernel

typedef ConvexHullRationalKernel< dim, Integer, InternalInteger >	RealConvexHullKernel

typedef DelaunayIntegralKernel< dim, Integer, InternalInteger >	LatticeDelaunayKernel

typedef DelaunayRationalKernel< dim, Integer, InternalInteger >	RealDelaunayKernel

typedef BoundedLatticePolytope< Space >	LatticePolytope

typedef BoundedRationalPolytope< Space >	RationalPolytope

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)

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

dim	the dimension of the space where points and further objects live.
TInteger	the 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.
TInternalInteger	the 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

Definition at line 82 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 99 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 100 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 91 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 92 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 102 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 106 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 109 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 94 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 110 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 104 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 108 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 96 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 97 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 98 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 93 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 95 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	,
		1
	)

◆ 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]	polysurf	the 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_points	the range of input lattice points.
[in]	remove_duplicates	should 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]	polysurf	the output polygonal surface mesh that represents the boundary of the convex hull of the given range of points.
[in]	input_points	the range of input real points.
[in]	precision	the 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_duplicates	should 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

TSurfaceMesh any 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]	mesh	the output surface mesh that represents the boundary of the convex hull of the given range of points.
[in]	input_points	the range of input lattice points.
[in]	remove_duplicates	should 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

TSurfaceMesh any 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]	mesh	the output surface mesh that represents the boundary of the convex hull of the given range of points.
[in]	input_points	the range of input real points.
[in]	precision	the 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_duplicates	should 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_complex	the output cell complex that represents the convex hull of the given lattice points.
[in]	input_points	the range of input lattice points.
[in]	remove_duplicates	should 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_complex	the output cell complex that represents the convex hull of the given real points.
[in]	input_points	the range of input real points.
[in]	precision	the 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_duplicates	should 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'.

◆ 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_complex	the output cell complex that represents the Delaunay complex of the given lattice points.
[in]	input_points	the range of input lattice points.
[in]	remove_duplicates	should 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_complex	the output cell complex that represents the Delaunay complex of the given lattice points.
[in]	input_points	the range of input real points.
[in]	precision	the 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_duplicates	should 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

QHull any QuickHull concrete type.

Parameters

[in]	hull	a computed QuickHull object
[out]	cell_vertices	the vector giving for each cell the indices of its vertices.
[out]	r2f	the map giving for each ridge (i.e. the pair of cells defining each face) the index of its corresponding face.
[out]	face_vertices	the 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_points	the range of input lattice points.
[in]	remove_duplicates	should be set to 'true' if the input data has duplicates.
[in]	make_minkowski_summable	Other 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_points	the range of input real points.
[in]	denominator	the denominator used in all rational approximations of points with real value coordinates, the higher the more precise.
[in]	remove_duplicates	should be set to 'true' if the input data has duplicates.
[in]	make_minkowski_summable	Other 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.

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 89 of file ConvexityHelper.h.

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

ConvexityHelper.h

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

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

Member Typedef Documentation

◆ Index

◆ IndexRange

◆ Integer

◆ InternalInteger

◆ LatticeConvexHullKernel

◆ LatticeDelaunayKernel

◆ LatticePolytope

◆ Point

◆ RationalPolytope

◆ RealConvexHullKernel

◆ RealDelaunayKernel

◆ RealPoint

◆ RealVector

◆ Size

◆ Space

◆ Vector

Member Function Documentation

◆ BOOST_CONCEPT_ASSERT() [1/2]

◆ BOOST_CONCEPT_ASSERT() [2/2]

◆ BOOST_STATIC_ASSERT()

◆ computeConvexHullBoundary() [1/4]

◆ computeConvexHullBoundary() [2/4]

◆ computeConvexHullBoundary() [3/4]

◆ computeConvexHullBoundary() [4/4]

◆ computeConvexHullCellComplex() [1/2]

◆ computeConvexHullCellComplex() [2/2]

◆ computeDelaunayCellComplex() [1/2]

◆ computeDelaunayCellComplex() [2/2]

◆ computeFacetAndRidgeVertices()

◆ computeLatticePolytope()

◆ computeRationalPolytope()

Field Documentation

◆ dimension

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