Aim: Implements the quickhull algorithm by Barber et al. [7], a famous arbitrary dimensional convex hull computation algorithm. It relies on dedicated geometric kernels for computing and comparing facet geometries. More...

#include <DGtal/geometry/tools/GenericLatticeConvexHull.h>

Inheritance diagram for DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >:

[legend]

Public Types
typedef ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger >	Kernel
typedef Kernel::CoordinatePoint	Point
typedef Kernel::CoordinateScalar	Integer
typedef Kernel::InternalScalar	InternalInteger
typedef Point	OutputPoint
typedef std::size_t	Index
typedef std::size_t	Size
typedef std::vector< Index >	IndexRange
typedef detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, dim >	GenericComputers

Public Member Functions
Standard services (construction, initialization, accessors)
	GenericLatticeConvexHull (const Kernel &K_=Kernel(), int dbg=0)
void	clear ()
	Clears the object as if no computations have been made.
convex hull services
template<typename InputPoint>
bool	compute (const std::vector< InputPoint > &input_points)
Integer	count ()
Integer	countInterior ()
Integer	countBoundary ()
Integer	countUpTo (Integer max)
Interface
void	selfDisplay (std::ostream &out) const
bool	isValid () const

Data Fields
public datas
Kernel	kernel
	The main quickhull kernel that is used for convex hull computations.
int	debug_level
	debug_level from 0:no to 2:verbose
GenericComputers	generic_computers
std::vector< OutputPoint >	points
	the set of input points, indexed as in the input
std::vector< OutputPoint >	projected_points
	the set of projected input points, indexed as in the input
int64_t	affine_dimension
	The affine dimension of the input set.
std::vector< OutputPoint >	positions
	The positions of the vertices (a subset of the input points).
std::vector< IndexRange >	facets
	The range giving for each facet the indices of its vertices.
IndexRange	vertex2point
	The indices of the vertices of the convex hull in the original set.
Integer	projected_dilation
	The factor of dilation d applied on every projected point coordinates.
AffineBasis< OutputPoint >	affine_basis
bool	polytope_computed { false }
	When 'true', the polytope has been computed.

Static Public Attributes
static const Size	dimension = Point::dimension

Detailed Description

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>
struct DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >

Aim: Implements the quickhull algorithm by Barber et al. [7], a famous arbitrary dimensional convex hull computation algorithm. It relies on dedicated geometric kernels for computing and comparing facet geometries.

Description of template class 'GenericLatticeConvexHull'

Template Parameters

dim	the dimension of the space of processed points.
TCoordinateInteger	the integer type that represents coordinates of lattice points, a model of concepts::CInteger.
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.

Examples: examples/io/external-viewers/polyscope/exampleGenericLatticeConvexHull3D.cpp, examples/io/external-viewers/polyscope/exampleGenericLatticeConvexHull4D.cpp, and geometry/tools/exampleGenericLatticeConvexHull.cpp.

Definition at line 521 of file GenericLatticeConvexHull.h.

Member Typedef Documentation

◆ GenericComputers

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, dim > DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::GenericComputers

Definition at line 534 of file GenericLatticeConvexHull.h.

◆ Index

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef std::size_t DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::Index

Definition at line 530 of file GenericLatticeConvexHull.h.

◆ IndexRange

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef std::vector< Index > DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::IndexRange

Definition at line 532 of file GenericLatticeConvexHull.h.

◆ Integer

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef Kernel::CoordinateScalar DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::Integer

Definition at line 527 of file GenericLatticeConvexHull.h.

◆ InternalInteger

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef Kernel::InternalScalar DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::InternalInteger

Definition at line 528 of file GenericLatticeConvexHull.h.

◆ Kernel

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef ConvexHullIntegralKernel< dim, TCoordinateInteger, TInternalInteger > DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::Kernel

Definition at line 525 of file GenericLatticeConvexHull.h.

◆ OutputPoint

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef Point DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::OutputPoint

Definition at line 529 of file GenericLatticeConvexHull.h.

◆ Point

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef Kernel::CoordinatePoint DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::Point

Definition at line 526 of file GenericLatticeConvexHull.h.

◆ Size

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

typedef std::size_t DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::Size

Definition at line 531 of file GenericLatticeConvexHull.h.

Constructor & Destructor Documentation

◆ GenericLatticeConvexHull()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::GenericLatticeConvexHull	(	const Kernel &	K_ = Kernel(),
		int	dbg = 0 )

inline

Default constructor

Parameters

[in]	K_	a kernel for computing facet geometries.
[in]	dbg	the trace level, from 0 (no) to 3 (very verbose).

Definition at line 547 of file GenericLatticeConvexHull.h.

      : kernel( K_ ), debug_level( dbg ), generic_computers( this )
    {
      clear();
    }

Member Function Documentation

◆ clear()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

void DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::clear ( )

inline

Clears the object as if no computations have been made.

Definition at line 554 of file GenericLatticeConvexHull.h.

    {
      generic_computers.clear();
      points.clear();
      projected_points.clear();
      affine_dimension  = -1;
      positions.clear();
      facets.clear();
      vertex2point.clear();
      affine_basis       = AffineBasis< OutputPoint >();
      projected_dilation = 1;
      polytope_computed  = false;
    }

Referenced by GenericLatticeConvexHull().

◆ compute()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

template<typename InputPoint>

bool DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::compute ( const std::vector< InputPoint > & input_points )

inline

Sets the input data for the QuickHull convex hull algorithm, which is a range of points.

Template Parameters

InputPoint a model of point that is convertible to Point datatype.

Parameters

[in] input_points the range of input points.

Returns: 'true' if the object is successfully initialized, status must be Status::InputInitialized, 'false' otherwise.

Definition at line 586 of file GenericLatticeConvexHull.h.

    {
      // Determine affine dimension of set of input points.
      typedef AffineGeometry< InputPoint > Affine;
      std::vector< Size > indices = Affine::affineSubset( input_points );
      bool ok = generic_computers.compute( indices, input_points );
      if ( ( ! ok ) || ( debug_level >= 1 ) )
        {
          std::cout << "Generic Convex hull #V=" << positions.size()
                    << " #F=" << facets.size() << "\n";
          for ( Size i = 0; i < facets.size(); i++ )
            {
              std::cout << "F_" << i << " = (";
              for ( auto v : facets[ i ] ) std::cout << " " << v;
              std::cout << " )\n";
            }
          for ( Size i = 0; i < positions.size(); i++ )
            std::cout << "V_" << i
                      << " pi(x)=" << projected_points[ vertex2point[ i ] ]
                      << " -> x=" << positions[ i ] << "\n";
        }
      return ok;
    }

◆ count()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

Integer DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::count ( )

inline

Computes the number of integer points lying within the polytope.

Returns: the number of integer points lying within the polytope, or -1 if their was a problem when computing the polytope.

Warning: The result is valid only if GenericLatticeConvexHull::projected_dilation is equal to 1 (i.e. the affine basis for the projection was obtained through an unimodular transformation). Otherwise the result is greater or equal to the expected number.

Note: Quite fast: obtained by line intersection, see BoundedLatticePolytopeCounter

Definition at line 623 of file GenericLatticeConvexHull.h.

    {
      if ( ! polytope_computed )
        polytope_computed = generic_computers.makePolytope();
      if ( ! polytope_computed ) return -1; 
      return generic_computers.count();
    }

◆ countBoundary()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

Integer DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::countBoundary ( )

inline

Computes the number of integer points lying on the boundary of the polytope.

Returns: the number of integer points lying on the boundary of the polytope.

Warning: The result is valid only if GenericLatticeConvexHull::projected_dilation is equal to 1 (i.e. the affine basis for the projection was obtained through an unimodular transformation). Otherwise the result is greater or equal to the expected number.

Note: Quite fast: obtained by line intersection, see BoundedLatticePolytopeCounter; count() <= countInterior() + countBoundary() with equality when the polytope is closed.

Definition at line 669 of file GenericLatticeConvexHull.h.

    {
      if ( ! polytope_computed )
        polytope_computed = generic_computers.makePolytope();
      if ( ! polytope_computed ) return -1; 
      return generic_computers.countBoundary();
    }

◆ countInterior()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

Integer DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::countInterior ( )

inline

Computes the number of integer points lying within the interior of the polytope.

Returns: the number of integer points lying within the interior of the polytope.

Warning: The result is valid only if GenericLatticeConvexHull::projected_dilation is equal to 1 (i.e. the affine basis for the projection was obtained through an unimodular transformation). Otherwise the result is greater or equal to the expected number.

Note: Quite fast: obtained by line intersection, see BoundedLatticePolytopeCounter; count() <= countInterior() + countBoundary() with equality when the polytope is closed.

Definition at line 646 of file GenericLatticeConvexHull.h.

    {
      if ( ! polytope_computed )
        polytope_computed = generic_computers.makePolytope();
      if ( ! polytope_computed ) return -1; 
      return generic_computers.countInterior();
      }

◆ countUpTo()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

Integer DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::countUpTo ( Integer max )

inline

Computes the number of integer points within the polytope up to some maximum number max.

Note: For instance, a d-dimensional simplex that contains no integer points in its interior contains only d+1 points. If there is more, you know that the simplex has a non empty interior.

Parameters

[in] max the maximum number of points that are counted, the method exists when this number of reached.

Returns: the number of integer points within the polytope up to .

Warning: The result is valid only if GenericLatticeConvexHull::projected_dilation is equal to 1 (i.e. the affine basis for the projection was obtained through an unimodular transformation). Otherwise the result is greater or equal to the expected number.

Note: Quite fast: obtained by line intersection, see BoundedLatticePolytopeCounter

Definition at line 698 of file GenericLatticeConvexHull.h.

    {
      if ( ! polytope_computed )
        polytope_computed = generic_computers.makePolytope();
      if ( ! polytope_computed ) return -1; 
      return generic_computers.countUpTo( max );
    }

◆ isValid()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

bool DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::isValid ( ) const

inline

Checks the validity/consistency of the object.

Returns: 'true' if the object has made a convex hull computation, 'false' otherwise.

Definition at line 729 of file GenericLatticeConvexHull.h.

    {
      return affine_dimension >= 0;
    }

◆ selfDisplay()

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

void DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::selfDisplay ( std::ostream & out ) const

inline

Writes/Displays the object on an output stream.

Parameters

out	the output stream where the object is written.

Definition at line 716 of file GenericLatticeConvexHull.h.

    {
      out << "[GenericLatticeConvexHull"
          << " dim=" << dimension
          << " #in=" << points.size()
          << " aff_dim=" << affine_dimension
          << " #V=" << positions.size()
          << " #F=" << facets.size()
          << "]";
    }

Field Documentation

◆ affine_basis

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

AffineBasis< OutputPoint > DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::affine_basis

The affine basis used for projection (identity if the convex hull is full dimensional, otherwise a basis in reduced echelon form).

Definition at line 766 of file GenericLatticeConvexHull.h.

◆ affine_dimension

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

int64_t DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::affine_dimension

The affine dimension of the input set.

Definition at line 754 of file GenericLatticeConvexHull.h.

◆ debug_level

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

int DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::debug_level

debug_level from 0:no to 2:verbose

Definition at line 744 of file GenericLatticeConvexHull.h.

◆ dimension

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

const Size DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::dimension = Point::dimension

static

Definition at line 536 of file GenericLatticeConvexHull.h.

◆ facets

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

std::vector< IndexRange > DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::facets

The range giving for each facet the indices of its vertices.

Definition at line 758 of file GenericLatticeConvexHull.h.

◆ generic_computers

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

GenericComputers DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::generic_computers

The delegate computation kernel that can take care of all kind of convex hulls, full dimensional or degenerated.

Definition at line 747 of file GenericLatticeConvexHull.h.

◆ kernel

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

Kernel DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::kernel

The main quickhull kernel that is used for convex hull computations.

Definition at line 742 of file GenericLatticeConvexHull.h.

◆ points

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

std::vector< OutputPoint > DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::points

the set of input points, indexed as in the input

Definition at line 750 of file GenericLatticeConvexHull.h.

◆ polytope_computed

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

bool DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::polytope_computed { false }

When 'true', the polytope has been computed.

Definition at line 768 of file GenericLatticeConvexHull.h.

768{ false };

◆ positions

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

std::vector< OutputPoint > DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::positions

The positions of the vertices (a subset of the input points).

Definition at line 756 of file GenericLatticeConvexHull.h.

◆ projected_dilation

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

Integer DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::projected_dilation

The factor of dilation d applied on every projected point coordinates.

Definition at line 762 of file GenericLatticeConvexHull.h.

◆ projected_points

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

std::vector< OutputPoint > DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::projected_points

the set of projected input points, indexed as in the input

Definition at line 752 of file GenericLatticeConvexHull.h.

◆ vertex2point

template<Dimension dim, typename TCoordinateInteger = DGtal::int64_t, typename TInternalInteger = DGtal::int64_t>

IndexRange DGtal::GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >::vertex2point

The indices of the vertices of the convex hull in the original set.

Definition at line 760 of file GenericLatticeConvexHull.h.

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

GenericLatticeConvexHull.h

Public Types

Public Member Functions

Data Fields

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ GenericComputers

◆ Index

◆ IndexRange

◆ Integer

◆ InternalInteger

◆ Kernel

◆ OutputPoint

◆ Point

◆ Size

Constructor & Destructor Documentation

◆ GenericLatticeConvexHull()

Member Function Documentation

◆ clear()

◆ compute()

◆ count()

◆ countBoundary()

◆ countInterior()

◆ countUpTo()

◆ isValid()

◆ selfDisplay()

Field Documentation

◆ affine_basis

◆ affine_dimension

◆ debug_level

◆ dimension

◆ facets

◆ generic_computers

◆ kernel

◆ points

◆ polytope_computed

◆ positions

◆ projected_dilation

◆ projected_points

◆ vertex2point