LatticePolytope2D.h

#pragma once

#if defined(LatticePolytope2D_RECURSES)
#error Recursive header files inclusion detected in LatticePolytope2D.h
#else // defined(LatticePolytope2D_RECURSES)

#define LatticePolytope2D_RECURSES

#if !defined LatticePolytope2D_h

#define LatticePolytope2D_h

// Inclusions
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include "DGtal/base/Common.h"
#include "DGtal/kernel/CSpace.h"
#include "DGtal/kernel/domains/HyperRectDomain.h"
#include "DGtal/arithmetic/IntegerComputer.h"
#include "DGtal/arithmetic/ClosedIntegerHalfPlane.h"

namespace DGtal
{

  // template class LatticePolytope2D
  template < typename TSpace, 
             typename TSequence = std::list< typename TSpace::Point > >
  class LatticePolytope2D 
  {
    BOOST_CONCEPT_ASSERT(( CSpace< TSpace > ));
    BOOST_STATIC_ASSERT(( TSpace::dimension == 2 ));
    BOOST_CONCEPT_ASSERT(( boost::Sequence< TSequence > ));

  public:
    typedef LatticePolytope2D<TSpace,TSequence> Self;
    typedef TSequence ClockwiseVertexSequence;

    typedef TSpace Space;
    typedef typename Space::Integer Integer;
    typedef typename Space::Point Point;
    typedef typename Space::Vector Vector;
    typedef IntegerComputer<Integer> MyIntegerComputer;
    typedef HyperRectDomain< Space > Domain; 
    typedef ClosedIntegerHalfPlane< Space > HalfSpace;

    typedef typename ClockwiseVertexSequence::value_type value_type;
    typedef typename ClockwiseVertexSequence::reference reference;
    typedef typename ClockwiseVertexSequence::const_reference const_reference;
    typedef typename ClockwiseVertexSequence::iterator iterator;
    typedef typename ClockwiseVertexSequence::const_iterator const_iterator;
    typedef typename ClockwiseVertexSequence::const_pointer const_pointer;
    typedef typename ClockwiseVertexSequence::size_type size_type;
    typedef typename ClockwiseVertexSequence::difference_type difference_type;

    typedef typename ClockwiseVertexSequence::value_type Value;
    typedef typename ClockwiseVertexSequence::iterator Iterator;
    typedef typename ClockwiseVertexSequence::const_iterator ConstIterator;
    typedef typename std::size_t Size;
    typedef std::pair<Size,Size> SizeCouple;

    // The sequence must contain points.
    BOOST_STATIC_ASSERT
    (( ConceptUtils::SameType< Value, Point >::value ));
    
    // Point2I and Point should be the same type.
    typedef typename MyIntegerComputer::Point2I Point2I;
    typedef typename MyIntegerComputer::Vector2I Vector2I;
    typedef typename MyIntegerComputer::Point3I Point3I;
    typedef typename MyIntegerComputer::Vector3I Vector3I;
    BOOST_STATIC_ASSERT(( ConceptUtils::SameType< Point2I, Point >::value ));
    BOOST_STATIC_ASSERT(( ConceptUtils::SameType< Vector2I, Vector >::value ));

    // ----------------------- Standard services ------------------------------
  public:

    ~LatticePolytope2D();

    LatticePolytope2D();

    LatticePolytope2D ( const Self & other );

    Self & operator= ( const Self & other );

    MyIntegerComputer & ic() const;

    ConstIterator begin() const;

    ConstIterator end() const;

    Iterator begin();

    Iterator end();

    bool empty() const;

    Size size() const;

    Size max_size() const;

    void clear();

    Iterator erase( Iterator it );

    Domain boundingBoxDomain() const;

    void purge();

    Iterator insertBefore( const Iterator & pos, const Point & K );

    void pushBack( const Point & K );

    void pushFront( const Point & K );

    void push_back( const Point & K );

    void push_front( const Point & K );

    const Integer & twiceArea() const;

    Point3I centroid() const;
    
    Point3I centroid( const Integer & twice_area ) const;

    Integer numberBoundaryPoints() const;

    Integer numberInteriorPoints() const;
 
    // ----------------------- halfspace services -------------------------------
  public:

    SizeCouple findCut( Iterator & it_next_is_outside, Iterator & it_next_is_inside, 
                        const HalfSpace & hs );

    bool cut( const HalfSpace & hs );

    HalfSpace halfSpace( ConstIterator it ) const;

    HalfSpace halfSpace( const Point & A, const Point & B, const Point & inP ) const;


    template <typename DigitalSet>
    void getIncludedDigitalPoints( DigitalSet & aSet ) const;

    // ----------------------- Helper methods ----------------------------------
    
    bool getFirstPointsOfHull( Vector & v, 
                               Point & inPt, // must belong to hs1.
                               Point & outPt,
                               const HalfSpace & hs1,
                               const HalfSpace & hs2 ) const;

    void getAllPointsOfHull( std::vector<Point> & inPts,
                             std::vector<Point> & outPts,
                             const Vector & BV, 
                             const HalfSpace & hs2,
                             const HalfSpace & hs3 ) const;

    template <typename OutputIterator>
    OutputIterator computeConvexHullBorder( OutputIterator itOut,
                                            const Point & pointRefC1, 
                                            const Point & pointRefC3,
                                            const HalfSpace & hs1,
                                            const HalfSpace & hs2,
                                            const HalfSpace & hs3 ) const;

    void swap( LatticePolytope2D & other );

    // ----------------------- Interface --------------------------------------
  public:

    void selfDisplay ( std::ostream & out ) const;

    bool isValid() const;

    std::string className() const;


    // ------------------------- Protected Datas ------------------------------
  protected:
    // The (circular) sequence of vertices along the lattice polytope.
    // The vertices are ordered \b clockwise.
    ClockwiseVertexSequence myVertices;

    // ------------------------- Private Datas --------------------------------
  private:
    mutable MyIntegerComputer _ic;
    mutable Integer _a, _b, _c, _c1, _c3, _den, _g, _fl, _ce;
    mutable Point _A, _B, _A1, _B1, _A2, _B2;
    mutable Vector _N, _DV, _u, _v;
    mutable std::vector<Point> _inPts, _outPts;

    // ------------------------- Hidden services ------------------------------
  protected:

    // ------------------------- Internals ------------------------------------
  private:

  }; // end of class LatticePolytope2D


  template <typename TSpace, typename TSequence>
  std::ostream&
  operator<< ( std::ostream & out, 
               const LatticePolytope2D<TSpace,TSequence> & object );

} // namespace DGtal


// Includes inline functions.
#include "DGtal/arithmetic/LatticePolytope2D.ih"

//                                                                           //

#endif // !defined LatticePolytope2D_h

#undef LatticePolytope2D_RECURSES
#endif // else defined(LatticePolytope2D_RECURSES)