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

Inheritance diagram for DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >:

[legend]

Public Types
typedef ConvexHullIntegralKernel< K, TCoordinateInteger, TInternalInteger >	Kernel
typedef detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K-1 >	LowerKernels
typedef std::size_t	Size
typedef Kernel::CoordinatePoint	Point
typedef Point::Coordinate	Integer
typedef QuickHull< Kernel >	QHull
typedef SpaceND< K, Integer >	Space
typedef BoundedLatticePolytope< Space >	LatticePolytope
typedef GenericLatticeConvexHull< dim, TCoordinateInteger, TInternalInteger >	Computer
typedef Computer::OutputPoint	OutputPoint

Public Member Functions
	GenericLatticeConvexHullComputers (Computer *ptrGenQHull)
void	clear ()
	Clears the object as if no computations have been made.
template<typename TInputPoint>
bool	compute (const std::vector< Size > &I, const std::vector< TInputPoint > &X)
bool	makePolytope ()
Integer	count ()
Integer	countInterior ()
Integer	countBoundary ()
Integer	countUpTo (Integer max)

Data Fields
Computer *	ptr_gen_qhull
	the pointer on the parent computer
LowerKernels	lower_kernels
	the computers of lower dimension
QHull	hull
	the quick hull object that computes the convex hull
std::vector< Point >	proj_points
	the projected points, as points in lower dimension
LatticePolytope	polytope
	the polytope corresponding to the convex hull

Static Public Attributes
static const Dimension	dimension = K

Detailed Description

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>
struct DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >

Definition at line 69 of file GenericLatticeConvexHull.h.

Member Typedef Documentation

◆ Computer

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

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

Definition at line 83 of file GenericLatticeConvexHull.h.

◆ Integer

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef Point::Coordinate DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::Integer

Definition at line 77 of file GenericLatticeConvexHull.h.

◆ Kernel

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef ConvexHullIntegralKernel< K,TCoordinateInteger,TInternalInteger > DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::Kernel

Definition at line 72 of file GenericLatticeConvexHull.h.

◆ LatticePolytope

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef BoundedLatticePolytope< Space > DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::LatticePolytope

Definition at line 80 of file GenericLatticeConvexHull.h.

◆ LowerKernels

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K-1> DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::LowerKernels

Definition at line 74 of file GenericLatticeConvexHull.h.

◆ OutputPoint

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef Computer::OutputPoint DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::OutputPoint

Definition at line 84 of file GenericLatticeConvexHull.h.

◆ Point

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef Kernel::CoordinatePoint DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::Point

Definition at line 76 of file GenericLatticeConvexHull.h.

◆ QHull

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef QuickHull< Kernel > DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::QHull

Definition at line 78 of file GenericLatticeConvexHull.h.

◆ Size

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef std::size_t DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::Size

Definition at line 75 of file GenericLatticeConvexHull.h.

◆ Space

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

typedef SpaceND< K, Integer > DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::Space

Definition at line 79 of file GenericLatticeConvexHull.h.

Constructor & Destructor Documentation

◆ GenericLatticeConvexHullComputers()

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::GenericLatticeConvexHullComputers ( Computer * ptrGenQHull )

inline

Constructor.

Parameters

ptrGenQHull the pointer on the parent computer.

Definition at line 89 of file GenericLatticeConvexHull.h.

        : ptr_gen_qhull( ptrGenQHull ), lower_kernels( ptrGenQHull ),
          hull( Kernel(), ptrGenQHull->debug_level )
      {
        clear();
      }

Member Function Documentation

◆ clear()

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

void DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::clear ( )

inline

Clears the object as if no computations have been made.

Definition at line 97 of file GenericLatticeConvexHull.h.

      {
        hull.clear(); 
        proj_points.clear();
        polytope.clear();
        lower_kernels.clear();
      }

Referenced by DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, 1 >::GenericLatticeConvexHullComputers(), and DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K-1 >::GenericLatticeConvexHullComputers().

◆ compute()

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

template<typename TInputPoint>

bool DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::compute	(	const std::vector< Size > &	I,
		const std::vector< TInputPoint > &	X )

inline

Template Parameters

TInputPoint any type of input points.

Parameters

I	a range of indices specifying an affine subset of X.
X	the range of input points.

Copy back convex hull in initial space.

Definition at line 109 of file GenericLatticeConvexHull.h.

      {
        typedef TInputPoint InputPoint;
        typedef AffineGeometry< InputPoint > Affine;
        typedef AffineBasis< InputPoint >    Basis;
        hull.clear();
        polytope.clear();
        if ( (I.size()-1) != dimension )
          { // This kernel is not adapted => go to lower dimension
            return lower_kernels.compute( I, X );
          }
        ptr_gen_qhull->affine_dimension = dimension;
        auto& points    = ptr_gen_qhull->points;
        auto& ppoints   = ptr_gen_qhull->projected_points;
        auto& positions = ptr_gen_qhull->positions;
        auto& v2p       = ptr_gen_qhull->vertex2point;
        auto& facets    = ptr_gen_qhull->facets;
        auto& dilation  = ptr_gen_qhull->projected_dilation;
        auto& aff_basis = ptr_gen_qhull->affine_basis;
        
        Basis basis;
        if ( dimension != ptr_gen_qhull->dimension )
          { // Build the affine basis spanning the convex hull affine space.
            if ( dimension == ptr_gen_qhull->dimension-1 )
              { // codimension 1
                // builds orthogonal vector
                InputPoint normal;
                functions::getOrthogonalVector( normal, X, I );
                basis = Basis( X[0], normal, Basis::Type::ECHELON_REDUCED );
              }
            else
              { // Generic case
                basis = Basis( X, Basis::Type::SHORTEST_ECHELON_REDUCED );
              }
          }
        // Build projected points on affine basis
        dilation  = basis.projectPoints( proj_points, X );
          
        // Compute convex hull using quickhull.
        bool ok_input = hull.setInput( proj_points, false );
        bool ok_hull  = hull.computeConvexHull( QHull::Status::VerticesCompleted );
        if ( ! ok_hull || ! ok_input )
          {
            trace.error() << "[GenericLatticeConvexHullComputers::compute]"
                          << " Error in quick hull computation.\n"
                          << "qhull=" << hull << "\n";
            return false;
          }
        points.resize( X.size() );
        for ( Size i = 0; i < points.size(); i++ )
          points[ i ] = Affine::transform( X[ i ] );
        hull.getVertex2Point( v2p );
        hull.getFacetVertices( facets );
        positions.resize( v2p.size() );
        for ( Size i = 0; i < positions.size(); i++ )
          positions[ i ] = X[ v2p[ i ] ];
        ppoints.resize( proj_points.size() );
        for ( Size i = 0; i < ppoints.size(); i++ )
          {
            ppoints[ i ] = OutputPoint::zero;
            for ( Dimension j = 0; j < Point::dimension; j++ )
              ppoints[ i ][ j ] = proj_points[ i ][ j ];
          }
        aff_basis = AffineBasis<OutputPoint>( basis.origin(),
                                              basis.basis(),
                                              Basis::Type::SHORTEST_ECHELON_REDUCED,
                                              true );
        return true;
      }

◆ count()

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

Integer DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::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.

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

Definition at line 233 of file GenericLatticeConvexHull.h.

      {
        if ( ptr_gen_qhull->affine_dimension != dimension )
          { // This kernel is not adapted => go to lower dimension
            return lower_kernels.count();
          }
        // If polytope is not initialized returns error.
        if ( polytope.nbHalfSpaces() == 0 ) return -1;
        return polytope.count();
      }

◆ countBoundary()

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

Integer DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::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.

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

Definition at line 273 of file GenericLatticeConvexHull.h.

      {
        if ( ptr_gen_qhull->affine_dimension != dimension )
          { // This kernel is not adapted => go to lower dimension
            return lower_kernels.countBoundary();
          }
        // If polytope is not initialized returns error.
        if ( polytope.nbHalfSpaces() == 0 ) return -1;
        return polytope.countBoundary();
      }

◆ countInterior()

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

Integer DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::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.

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

Definition at line 253 of file GenericLatticeConvexHull.h.

      {
        if ( ptr_gen_qhull->affine_dimension != dimension )
          { // This kernel is not adapted => go to lower dimension
            return lower_kernels.countInterior();
          }
        // If polytope is not initialized returns error.
        if ( polytope.nbHalfSpaces() == 0 ) return -1;
        return polytope.countInterior();
      }

◆ countUpTo()

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

Integer DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::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 .

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

Definition at line 299 of file GenericLatticeConvexHull.h.

      {
        if ( ptr_gen_qhull->affine_dimension != dimension )
          { // This kernel is not adapted => go to lower dimension
            return lower_kernels.countUpTo( max );
          }
        // If polytope is not initialized returns error.
        if ( polytope.nbHalfSpaces() == 0 ) return -1;
        return polytope.countUpTo( max );
      }

◆ makePolytope()

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

bool DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::makePolytope ( )

inline

Constructs the polytope that is the F-representation of the convex hull.

Returns: 'true' iff the constructed polytope is valid.

Definition at line 183 of file GenericLatticeConvexHull.h.

      {
        typedef typename LatticePolytope::Domain     Domain;
        typedef typename LatticePolytope::HalfSpace  PolytopeHalfSpace;
        typedef typename QHull::HalfSpace            ConvexHullHalfSpace;
        typedef AffineGeometry< Point > Affine;
        if ( ptr_gen_qhull->affine_dimension != dimension )
          { // This kernel is not adapted => go to lower dimension
            return lower_kernels.makePolytope();
          }
        // If polytope is already initialized returns.
        if ( polytope.nbHalfSpaces() > 0 ) return true;
        // Compute domain
        Point l = proj_points[ 0 ];
        Point u = proj_points[ 0 ];
        for ( std::size_t i = 1; i < proj_points.size(); i++ )
          {
            const auto& p = proj_points[ i ];
            l = l.inf( p );
            u = u.sup( p );
          }
        Domain domain( l, u );
        
        // Initialize polytope
        std::vector< ConvexHullHalfSpace > HS;
        std::vector< PolytopeHalfSpace >   PHS;
        hull.getFacetHalfSpaces( HS );
        PHS.reserve( HS.size() );
        for ( auto& H : HS ) {
          Point  N;
          Integer nu;
          for ( Dimension i = 0; i < dimension; ++i )
            N[ i ] = IntegerConverter< dimension, Integer >
              ::cast( H.internalNormal()[ i ]  );
          Point   Ns = Affine::simplifiedVector( N );
          Integer g  = N.norm1() / Ns.norm1();
          nu = IntegerConverter< dimension, Integer >::cast( H.internalIntercept() );
          PHS.emplace_back( Ns, nu / g );
        }
        polytope = LatticePolytope( domain, PHS.cbegin(), PHS.cend(), false, true );
        return polytope.isValid();
      }

Field Documentation

◆ dimension

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

const Dimension DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::dimension = K

static

Definition at line 85 of file GenericLatticeConvexHull.h.

◆ hull

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

QHull DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::hull

the quick hull object that computes the convex hull

Definition at line 313 of file GenericLatticeConvexHull.h.

◆ lower_kernels

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

LowerKernels DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::lower_kernels

the computers of lower dimension

Definition at line 312 of file GenericLatticeConvexHull.h.

◆ polytope

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

LatticePolytope DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::polytope

the polytope corresponding to the convex hull

Definition at line 315 of file GenericLatticeConvexHull.h.

◆ proj_points

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

std::vector< Point > DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::proj_points

the projected points, as points in lower dimension

Definition at line 314 of file GenericLatticeConvexHull.h.

◆ ptr_gen_qhull

template<Dimension dim, typename TCoordinateInteger, typename TInternalInteger, Dimension K>

Computer* DGtal::detail::GenericLatticeConvexHullComputers< dim, TCoordinateInteger, TInternalInteger, K >::ptr_gen_qhull

the pointer on the parent computer

Definition at line 311 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

◆ Computer

◆ Integer

◆ Kernel

◆ LatticePolytope

◆ LowerKernels

◆ OutputPoint

◆ Point

◆ QHull

◆ Size

◆ Space

Constructor & Destructor Documentation

◆ GenericLatticeConvexHullComputers()

Member Function Documentation

◆ clear()

◆ compute()

◆ count()

◆ countBoundary()

◆ countInterior()

◆ countUpTo()

◆ makePolytope()

Field Documentation

◆ dimension

◆ hull

◆ lower_kernels

◆ polytope

◆ proj_points

◆ ptr_gen_qhull