DigitalConvexity.h

 
#pragma once
 
#if defined(DigitalConvexity_RECURSES)
#error Recursive header files inclusion detected in DigitalConvexity.h
#else // defined(DigitalConvexity_RECURSES)
#define DigitalConvexity_RECURSES
 
#if !defined DigitalConvexity_h
#define DigitalConvexity_h
 
// Inclusions
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <unordered_set>
#include "DGtal/base/Common.h"
#include "DGtal/base/Clone.h"
#include "DGtal/kernel/LatticeSetByIntervals.h"
#include "DGtal/topology/CCellularGridSpaceND.h"
#include "DGtal/topology/KhalimskySpaceND.h"
#include "DGtal/geometry/volumes/BoundedLatticePolytope.h"
#include "DGtal/geometry/volumes/BoundedLatticePolytopeCounter.h"
#include "DGtal/geometry/volumes/BoundedRationalPolytope.h"
#include "DGtal/geometry/volumes/CellGeometry.h"
 
namespace DGtal
{
 
  // template class DigitalConvexity
  template < typename TKSpace >
  class DigitalConvexity
  {
    BOOST_CONCEPT_ASSERT(( concepts::CCellularGridSpaceND< TKSpace > ));
 
  public:
    typedef DigitalConvexity<TKSpace>       Self;
    typedef TKSpace                         KSpace;
    typedef typename KSpace::Integer        Integer;
    typedef typename KSpace::Point          Point;
    typedef typename KSpace::Vector         Vector;
    typedef typename KSpace::Cell           Cell;
    typedef typename KSpace::Space          Space;
    typedef std::size_t                     Size;
    typedef DGtal::BoundedLatticePolytope < Space > Polytope;
    typedef DGtal::BoundedLatticePolytope < Space > LatticePolytope;
    typedef DGtal::BoundedRationalPolytope< Space > RationalPolytope;
    typedef DGtal::CellGeometry< KSpace >   CellGeometry;
    typedef std::vector<Point>              PointRange;
    typedef std::unordered_set<Point>       PointSet;
    typedef DGtal::BoundedLatticePolytopeCounter< Space > Counter;
    typedef typename Counter::Interval      Interval;
    typedef DGtal::LatticeSetByIntervals< Space > LatticeSet;
    
    static const Dimension dimension = KSpace::dimension;
 
 
 
    ~DigitalConvexity() = default;
 
    DigitalConvexity() = default;
 
    DigitalConvexity ( const Self & other ) = default;
 
    DigitalConvexity( Clone<KSpace> K, bool safe = false );
 
    DigitalConvexity( Point lo, Point hi, bool safe = false );
 
    Self & operator= ( const Self & other ) = default;
 
    const KSpace& space() const;
 
 
    // ----------------------- Simplex services --------------------------------------
  public:
 
    template <typename PointIterator>
    static
    LatticePolytope makeSimplex( PointIterator itB, PointIterator itE );
 
    static
    LatticePolytope makeSimplex( std::initializer_list<Point> l );
 
    template <typename PointIterator>
    static
    RationalPolytope makeRationalSimplex( Integer d,
                                          PointIterator itB, PointIterator itE );
 
    static
    RationalPolytope makeRationalSimplex( std::initializer_list<Point> l );
 
    template <typename PointIterator>
    static
    bool isSimplexFullDimensional( PointIterator itB, PointIterator itE );
 
    static
    bool isSimplexFullDimensional( std::initializer_list<Point> l );
 
    enum class SimplexType{
      INVALID,     
      DEGENERATED, 
      UNITARY,     
      COMMON       
    };
 
    template <typename PointIterator>
    static
    SimplexType simplexType( PointIterator itB, PointIterator itE );
 
    static
    SimplexType simplexType( std::initializer_list<Point> l );
 
    template <typename PointIterator>
    static
    void displaySimplex( std::ostream& out, PointIterator itB, PointIterator itE );
 
    static
    void displaySimplex( std::ostream& out, std::initializer_list<Point> l );
 
 
    // ----------------------- Polytope services --------------------------------------
  public:
 
    static
    PointRange insidePoints( const LatticePolytope& polytope );
 
    static
    PointRange interiorPoints( const LatticePolytope& polytope );
 
    static
    PointRange insidePoints( const RationalPolytope& polytope );
 
    static
    PointRange interiorPoints( const RationalPolytope& polytope );
 
 
 
    // ----------------------- Cell geometry services -----------------------------------
  public:
 
    template <typename PointIterator>
    CellGeometry makeCellCover( PointIterator itB, PointIterator itE,
                                Dimension i = 0,
                                Dimension k = KSpace::dimension ) const;
 
    CellGeometry makeCellCover( const LatticePolytope& P,
                                Dimension i = 0,
                                Dimension k = KSpace::dimension ) const;
 
    CellGeometry makeCellCover( const RationalPolytope& P,
                                Dimension i = 0,
                                Dimension k = KSpace::dimension ) const;
 
    // ----------------------- Morphological services --------------------------------
  public:
 
    LatticePolytope makePolytope( const PointRange& X,
                                  bool make_minkowski_summable = false ) const;
    
    PointRange U( Dimension i, const PointRange& X ) const;
 
    bool is0Convex( const PointRange& X ) const;
    
    bool isFullyConvex( const PointRange& X, bool convex0 = false ) const;
 
    bool isFullyConvexFast( const PointRange& X ) const;
    
    bool isFullySubconvex( const PointRange& Y, const LatticeSet& StarX ) const;
 
 
    bool isFullySubconvex( const Point& a, const Point& b, const Point& c,
                           const LatticeSet& StarX ) const;
 
    bool isFullyCovered( const Point& a, const Point& b, const Point& c,
                         const LatticeSet& cells ) const;
 
    bool isFullyCovered( const Point& a, const Point& b,
                         const LatticeSet& cells ) const;
    
    
    bool isOpenTriangleFullySubconvex( const Point& a, const Point& b, const Point& c,
                                       const LatticeSet& StarX ) const;
    
    
    bool isKSubconvex( const Point& a, const Point& b,
                       const CellGeometry& C, const Dimension k ) const;
 
    bool isFullySubconvex( const Point& a, const Point& b,
                           const CellGeometry& C ) const;
 
    bool isFullySubconvex( const Point& a, const Point& b,
                           const LatticeSet& StarX ) const;
    
    LatticePolytope CvxH( const PointRange& X ) const
    {
      return makePolytope( X );
    }
 
    PointRange ExtrCvxH( const PointRange& X ) const;
    
    LatticeSet StarCvxH( const PointRange& X,
                         Dimension axis = dimension ) const;
 
    LatticeSet StarCvxH( const Point& a, const Point& b, const Point& c,
                         Dimension axis = dimension ) const;
 
    LatticeSet StarOpenTriangle( const Point& a, const Point& b, const Point& c,
                                 Dimension axis = dimension ) const;
 
    
    Integer sizeStarCvxH( const PointRange& X ) const;
 
    LatticeSet Star( const PointRange& X,
                     Dimension axis = dimension ) const;
 
    LatticeSet StarCells( const PointRange& C,
                          Dimension axis = dimension ) const;
    
    PointRange Extr( const PointRange& C ) const;
 
    PointRange Extr( const LatticeSet& C ) const;
 
    LatticeSet Skel( const LatticeSet& C ) const;
 
    PointRange ExtrSkel( const LatticeSet& C ) const;
 
    LatticeSet CoverCvxH( const Point& a, const Point& b,
                          Dimension axis = dimension ) const;
 
    LatticeSet CoverCvxH( const Point& a, const Point& b, const Point& c,
                          Dimension axis = dimension ) const;
    
    
    LatticeSet toLatticeSet( const PointRange& X,
                             Dimension axis = dimension ) const;
 
    PointRange toPointRange( const LatticeSet& L ) const;
    
 
    // ----------------------- Convex envelope services -----------------------------
  public:
 
    enum class EnvelopeAlgorithm
      { DIRECT ,
        LATTICE_SET 
      };
    
    PointRange
    FC( const PointRange& Z,
        EnvelopeAlgorithm algo = EnvelopeAlgorithm::DIRECT ) const;
 
    PointRange
    envelope( const PointRange& Z,
              EnvelopeAlgorithm algo = EnvelopeAlgorithm::DIRECT ) const;
 
    PointRange
    relativeEnvelope( const PointRange& Z, const PointRange& Y,
                      EnvelopeAlgorithm algo = EnvelopeAlgorithm::DIRECT ) const;
 
    template <typename Predicate>
    PointRange
    relativeEnvelope( const PointRange& Z, const Predicate& PredY,
                      EnvelopeAlgorithm algo = EnvelopeAlgorithm::DIRECT ) const;
    
    Size depthLastEnvelope() const;
    
    
    // ----------------------- Convexity services for lattice polytopes --------------
  public:
 
 
    bool isKConvex( const LatticePolytope& P, const Dimension k ) const;
 
 
    bool isFullyConvex( const LatticePolytope& P ) const;
 
 
    bool isKSubconvex( const LatticePolytope& P, const CellGeometry& C, const Dimension k ) const;
 
 
    bool isFullySubconvex( const LatticePolytope& P, const CellGeometry& C ) const;
 
    bool isFullySubconvex( const LatticePolytope& P, const LatticeSet& StarX ) const;
    
    
 
    // ----------------------- Convexity services for rational polytopes ----------------
  public:
 
 
    bool isKConvex( const RationalPolytope& P, const Dimension k ) const;
 
 
    bool isFullyConvex( const RationalPolytope& P ) const;
 
 
    bool isKSubconvex( const RationalPolytope& P, const CellGeometry& C, const Dimension k ) const;
 
 
    bool isFullySubconvex( const RationalPolytope& P, const CellGeometry& C ) const;
 
 
    // ----------------------- Interface --------------------------------------
  public:
 
    void selfDisplay ( std::ostream & out ) const;
 
    bool isValid() const;
 
 
    // ------------------------- Protected Datas ------------------------------
  protected:
    KSpace myK;
 
    bool mySafe;
    
    mutable Size myDepthLastFCE;
    
    // ------------------------- Private Datas --------------------------------
  private:
 
 
    // ------------------------- Internals ------------------------------------
  private:
 
    PointRange FC_direct( const PointRange& Z ) const;
 
    PointRange FC_LatticeSet( const PointRange& Z ) const;
 
    static void eraseInterval( Interval I, std::vector< Interval > & V );
 
    template <typename Predicate>
    static PointRange filter( const PointRange& E, const Predicate& Pred );
 
    template <typename TPolytope>
    LatticeSet CoverPolytope( const TPolytope& P,
                              Dimension axis = dimension ) const;
 
 
    
  }; // end of class DigitalConvexity
 
 
  template <typename TKSpace>
  std::ostream&
  operator<< ( std::ostream & out,
               const DigitalConvexity<TKSpace> & object );
 
 
} // namespace DGtal
 
 
// Includes inline functions.
#include "DigitalConvexity.ih"
 
//                                                                           //
 
#endif // !defined DigitalConvexity_h
 
#undef DigitalConvexity_RECURSES
#endif // else defined(DigitalConvexity_RECURSES)