#include <LatticePolytope2D.h>

Inheritance diagram for DGtal::LatticePolytope2D< TSpace, TSequence >:

Collaboration diagram for DGtal::LatticePolytope2D< TSpace, TSequence >:

Public Types
typedef LatticePolytope2D < TSpace, TSequence >	Self
typedef TSequence	ClockwiseVertexSequence
typedef TSpace	Space
typedef Space::Integer	Integer
typedef Space::Point	Point
typedef Space::Vector	Vector
typedef IntegerComputer< Integer >	MyIntegerComputer
typedef HyperRectDomain< Space >	Domain
typedef ClosedIntegerHalfPlane < Space >	HalfSpace
typedef ClockwiseVertexSequence::value_type	value_type
typedef ClockwiseVertexSequence::reference	reference
typedef ClockwiseVertexSequence::const_reference	const_reference
typedef ClockwiseVertexSequence::iterator	iterator
typedef ClockwiseVertexSequence::const_iterator	const_iterator
typedef ClockwiseVertexSequence::const_pointer	const_pointer
typedef ClockwiseVertexSequence::size_type	size_type
typedef ClockwiseVertexSequence::difference_type	difference_type
typedef ClockwiseVertexSequence::value_type	Value
typedef ClockwiseVertexSequence::iterator	Iterator
typedef ClockwiseVertexSequence::const_iterator	ConstIterator
typedef std::size_t	Size
typedef std::pair< Size, Size >	SizeCouple
typedef MyIntegerComputer::Point2I	Point2I
typedef MyIntegerComputer::Vector2I	Vector2I
typedef MyIntegerComputer::Point3I	Point3I
typedef MyIntegerComputer::Vector3I	Vector3I

Public Member Functions
	BOOST_STATIC_ASSERT ((ConceptUtils::SameType< Value, Point >::value))
	BOOST_STATIC_ASSERT ((ConceptUtils::SameType< Point2I, Point >::value))
	BOOST_STATIC_ASSERT ((ConceptUtils::SameType< Vector2I, Vector >::value))
	~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
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
bool	getFirstPointsOfHull (Vector &v, Point &inPt, 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)
void	selfDisplay (std::ostream &out) const
bool	isValid () const
std::string	className () const

Protected Attributes
ClockwiseVertexSequence	myVertices

Private Member Functions
	BOOST_CONCEPT_ASSERT ((CSpace< TSpace >))
	BOOST_STATIC_ASSERT ((TSpace::dimension==2))
	BOOST_CONCEPT_ASSERT ((boost::Sequence< TSequence >))

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

Detailed Description

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>
class DGtal::LatticePolytope2D< TSpace, TSequence >

Aim: Represents a 2D polytope, i.e. a convex polygon, in the two-dimensional digital plane. The list of points must follow the clockwise ordering.

Description of template class 'LatticePolytope2D'

It is a model of boost::CopyConstructible, boost::DefaultConstructible, boost::Assignable. It is also a model of boost::Container (it contains the sequence of points). It is also a model of CDrawableWithBoard2D, and is displayable on a Board2D object.

It contains no more data than the sequence of points, except mutable data for intermediate computations.

It is a backport of ImaGene.

Template Parameters:

TSpace	an arbitrary 2-dimensional model of CSpace.
TSequence	a model of boost::Sequence whose elements are points (TSpace::Point). Default is list of points.

Examples:: arithmetic/lower-integer-convex-hull.cpp.

Definition at line 83 of file LatticePolytope2D.h.

Member Typedef Documentation

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef TSequence DGtal::LatticePolytope2D< TSpace, TSequence >::ClockwiseVertexSequence

Definition at line 91 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::const_iterator DGtal::LatticePolytope2D< TSpace, TSequence >::const_iterator

Definition at line 105 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::const_pointer DGtal::LatticePolytope2D< TSpace, TSequence >::const_pointer

Definition at line 106 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::const_reference DGtal::LatticePolytope2D< TSpace, TSequence >::const_reference

Definition at line 103 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::const_iterator DGtal::LatticePolytope2D< TSpace, TSequence >::ConstIterator

Definition at line 112 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::difference_type DGtal::LatticePolytope2D< TSpace, TSequence >::difference_type

Definition at line 108 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef HyperRectDomain< Space > DGtal::LatticePolytope2D< TSpace, TSequence >::Domain

Definition at line 98 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClosedIntegerHalfPlane< Space > DGtal::LatticePolytope2D< TSpace, TSequence >::HalfSpace

Definition at line 99 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef Space::Integer DGtal::LatticePolytope2D< TSpace, TSequence >::Integer

Definition at line 94 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::iterator DGtal::LatticePolytope2D< TSpace, TSequence >::iterator

Definition at line 104 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::iterator DGtal::LatticePolytope2D< TSpace, TSequence >::Iterator

Definition at line 111 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef IntegerComputer<Integer> DGtal::LatticePolytope2D< TSpace, TSequence >::MyIntegerComputer

Definition at line 97 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef Space::Point DGtal::LatticePolytope2D< TSpace, TSequence >::Point

Definition at line 95 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef MyIntegerComputer::Point2I DGtal::LatticePolytope2D< TSpace, TSequence >::Point2I

Definition at line 121 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef MyIntegerComputer::Point3I DGtal::LatticePolytope2D< TSpace, TSequence >::Point3I

Definition at line 123 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::reference DGtal::LatticePolytope2D< TSpace, TSequence >::reference

Definition at line 102 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef LatticePolytope2D<TSpace,TSequence> DGtal::LatticePolytope2D< TSpace, TSequence >::Self

Definition at line 90 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef std::size_t DGtal::LatticePolytope2D< TSpace, TSequence >::Size

Definition at line 113 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::size_type DGtal::LatticePolytope2D< TSpace, TSequence >::size_type

Definition at line 107 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef std::pair<Size,Size> DGtal::LatticePolytope2D< TSpace, TSequence >::SizeCouple

Definition at line 114 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef TSpace DGtal::LatticePolytope2D< TSpace, TSequence >::Space

Definition at line 93 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::value_type DGtal::LatticePolytope2D< TSpace, TSequence >::Value

Definition at line 110 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef ClockwiseVertexSequence::value_type DGtal::LatticePolytope2D< TSpace, TSequence >::value_type

Definition at line 101 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef Space::Vector DGtal::LatticePolytope2D< TSpace, TSequence >::Vector

Definition at line 96 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef MyIntegerComputer::Vector2I DGtal::LatticePolytope2D< TSpace, TSequence >::Vector2I

Definition at line 122 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

typedef MyIntegerComputer::Vector3I DGtal::LatticePolytope2D< TSpace, TSequence >::Vector3I

Definition at line 124 of file LatticePolytope2D.h.

Constructor & Destructor Documentation

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::~LatticePolytope2D ( )

inline

Destructor.

Definition at line 48 of file LatticePolytope2D.ih.

{ // Nothing to do.

}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::LatticePolytope2D ( )

inline

Constructor.

Definition at line 54 of file LatticePolytope2D.ih.

{ // Nothing to do.

}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::LatticePolytope2D ( const Self & other )

inline

Copy constructor.

Parameters:

other the object to clone.

Definition at line 61 of file LatticePolytope2D.ih.

  : myVertices( other.myVertices )
{ // Nothing to do.
}

Member Function Documentation

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::ConstIterator DGtal::LatticePolytope2D< TSpace, TSequence >::begin ( ) const

inline

Useful to visit the list of vertices in order.

Returns:: a const iterator (a forward iterator) pointing on the first vertex.

Definition at line 81 of file LatticePolytope2D.ih.

Referenced by DGtal::Display2DFactory::draw().

{
  return myVertices.begin();
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Iterator DGtal::LatticePolytope2D< TSpace, TSequence >::begin ( )

inline

Useful to visit the list of vertices in order.

Returns:: an iterator (a forward iterator) pointing on the first vertex.

Definition at line 99 of file LatticePolytope2D.ih.

{
  return myVertices.begin();
}

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_CONCEPT_ASSERT ( (CSpace< TSpace >) )

private

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_CONCEPT_ASSERT ( (boost::Sequence< TSequence >) )

private

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_STATIC_ASSERT ( (TSpace::dimension==2) )

private

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Value, Point >::value) )

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Point2I, Point >::value) )

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_STATIC_ASSERT ( (ConceptUtils::SameType< Vector2I, Vector >::value) )

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Domain DGtal::LatticePolytope2D< TSpace, TSequence >::boundingBoxDomain ( ) const

Returns:: the bounding domain of this polygon, i.e. the smallest bounding box containing all the points of this polygon.

Definition at line 181 of file LatticePolytope2D.ih.

{
  ConstIterator it = begin();
  ConstIterator it_end = end();
  Point infimum = *it;
  Point supremum = *it;
  for ( ++it; it != it_end; ++it )
    {
      infimum = infimum.inf( *it );
      supremum = supremum.sup( *it );
    }
  return Domain( infimum, supremum );
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Point3I DGtal::LatticePolytope2D< TSpace, TSequence >::centroid ( ) const

inline

if the area of this polygon is not 0, computes centroid, else, if the polygon is reduced to 2 points, computes the middle of the straight line segment, else returns the point itself.

The centroid is a 2D rational point but it is represented as a 3D integer point (a/d,b/d) corresponds to (a,b,d).

Returns:: the centroid. The centroid is not in reduced form.

Precondition:: The polygon should not be empty.

See also:: centroid( const Integer & ) const

Definition at line 284 of file LatticePolytope2D.ih.

Referenced by DGtal::COBANaivePlane< TSpace, TInternalInteger >::computeCentroidAndNormal().

{
  _a = twiceArea();
  return centroid( _a );
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Point3I DGtal::LatticePolytope2D< TSpace, TSequence >::centroid ( const Integer & twice_area ) const

inline

This form is faster than centroid if you have already computed the area.

if the area of this polygon is not 0, computes centroid, else, if the polygon is reduced to 2 points, computes the middle of the straight line segment, else returns the point itself.

The centroid is a 2D rational point but it is represented as a 3D integer point (a/d,b/d) corresponds to (a,b,d).

Parameters:

twice_area the area*2 of this polygon.

Returns:: the centroid. The centroid is not in reduced form.

Precondition:: The polygon should not be empty.

See also:: centroid() const

Definition at line 294 of file LatticePolytope2D.ih.

{
  _a = _b = NumberTraits<Integer>::ZERO;
  _A = Point( NumberTraits<Integer>::ZERO, NumberTraits<Integer>::ZERO );
  ConstIterator it_begin = begin();
  ConstIterator it = it_begin;
  ConstIterator it_end = end();
  if( twice_area > NumberTraits<Integer>::ZERO )
    {
      _den = 3 * twice_area;
      ConstIterator it_next = it; ++it_next;
      while ( it_next != it_end )
        {
          _ic.getCrossProduct( _c, *it, *it_next );
          _B = *it + *it_next;
          _B *= _c;
          _A += _B;
          it = it_next; ++it_next;
        }
      _ic.getCrossProduct( _c, *it, *it_begin );
      _B = *it + *it_begin;
      _B *= _c;
      _A += _B;
    }
  else
    {
      _den = NumberTraits<Integer>::ZERO;
      for ( ; it != it_end; ++it )
        {
          _A += *it;
          ++_den;
        }
    }
  return Point3I( _A[ 0 ], _A[ 1 ], _den );
}

template<typename TSpace , typename TSequence >

std::string DGtal::LatticePolytope2D< TSpace, TSequence >::className ( ) const

inline

Returns:: the style name used for drawing this object.

Definition at line 889 of file LatticePolytope2D.ih.

Referenced by DGtal::Display2DFactory::draw().

{ 
  return "LatticePolytope2D";
}

template<typename TSpace , typename TSequence >

void DGtal::LatticePolytope2D< TSpace, TSequence >::clear ( )

inline

Clears the lattice polytope. Afterwards, it is composed of 0 vertices.

Definition at line 144 of file LatticePolytope2D.ih.

{
  myVertices.clear();
}

template<typename TSpace , typename TSequence >

template<typename OutputIterator >

OutputIterator DGtal::LatticePolytope2D< TSpace, TSequence >::computeConvexHullBorder	(	OutputIterator	itOut,
		const Point &	pointRefC1,
		const Point &	pointRefC3,
		const HalfSpace &	hs1,
		const HalfSpace &	hs2,
		const HalfSpace &	hs3
	)		const

Compute the convex hull of grid points satisfying the constraints N1.P<=c1, N2.P<=c2 and N3.P>=c3.

N2.P<=c2 corresponds to the cut two parts of computation: from constraint 1 to constraint 3 and from constraint 3 to constraint 1.

The computed vertices are outputed with the output iterator [itOut].

Parameters:

pointRefC1	and pointRefC3 corresponds to grid point lying on the supporting lines of C1 and of C3 resp.
pos	corresponds to an iterator in the list of vertices of the polytope, to add the next new vertices

NB: the method also computes grid point satisfying N1.P<=c1 and N3.P>=c3 but not satisfying N2.P<=c2. The algorithm uses these points that's why they appear in the code.

compute the convex hull of grid points satisfying the constraints N1.P<=c1, N2.P<=c2 and N3.P>=c3.

N2.P<=c2 corresponds to the cut two parts of computation: from constraint 1 to constraint 3 and from constraint 3 to constraint 1.

The computed vertices are inserted at position [pos] in some list.

Parameters:

pointRefC1	and pointRefC3 corresponds to grid point lying on the supporting lines of C1 and of C3 resp.
pos	corresponds to an iterator in the list of vertices of the convex, to add the next new vertices

NB: the method also computes grid point satisfying N1.P<=c1 and N3.P>=c3 but not satisfying N2.P<=c2. They are stored in "resultdown" of size "nbverticesdown". the algorithm uses these points that's why they appear in the code.

Definition at line 805 of file LatticePolytope2D.ih.

{
  // _u, _v: vectors u and v to determine the next vertex
  bool exactIntersection;
  // initializes A, B, u, v and the two first vertices of resultup and
  // resultdown.
  _inPts.resize( 1 );    //to store half convex hull border
  _outPts.resize( 1 );  //to store half convex hull border
  _inPts[ 0 ] = pointRefC1;
  // exactIntersection is equal to one when the intersection of the
  // supporting lines of C1 and C2 corresponds to an integer point
  exactIntersection = getFirstPointsOfHull( _v, _inPts[ 0 ], _outPts[ 0 ],
                                            hs1, hs2 );
  if ( ! exactIntersection ) // not integer intersection
    {
      //computation of the first part of the border
      getAllPointsOfHull( _inPts, _outPts, _v, hs2, hs3 );
    }
  // fill in convexup
  for( Size i = 0; i < _inPts.size(); ++i )
    *itOut++ = _inPts[ i ];
  // second part
  // initializes A, B, u, v and the two first vertices of resultup and
  // resultdown.
  _inPts.resize( 1 );
  _outPts.resize( 1 );
  _inPts[0] = pointRefC3;
  // exactIntersection is equal to one when the intersection of the
  // supporting lines of C3 and C2 corresponds to an integer point
  exactIntersection = getFirstPointsOfHull( _v, _inPts[ 0 ], _outPts[ 0 ],
                                            hs3, hs2 );
  if ( ! exactIntersection ) // not integer intersection
  {
    //computation of the second part of the border
    getAllPointsOfHull( _inPts, _outPts, _v, hs2, hs1 ); // check not hs1.
  }
  //fill in convexup
  for( Size i = _inPts.size(); i != 0; --i ) 
    {
      *itOut++ = _inPts[ i - 1 ];
    }
  return itOut;
}

template<typename TSpace , typename TSequence >

bool DGtal::LatticePolytope2D< TSpace, TSequence >::cut ( const HalfSpace & hs )

inline

Cuts the lattice polytope with the given half-space constraint.

Parameters:

hs	any half-space constraint.

Returns:: 'true' if the polygon was modified, 'false' otherwise.

NB: complexity is O(N) for finding the involved edges, then log(D) for applying the cut.

Definition at line 414 of file LatticePolytope2D.ih.

References DGtal::ClosedIntegerHalfPlane< TSpace >::c, and DGtal::ClosedIntegerHalfPlane< TSpace >::N.

Referenced by DGtal::COBANaivePlane< TSpace, TInternalInteger >::doubleCut().

{
  Iterator it_next_is_outside;
  Iterator it_next_is_inside;
  SizeCouple nbs = findCut( it_next_is_outside, it_next_is_inside, hs );
  // Take care of easy cases.
  if ( nbs.first == nbs.second )               { return false; }
  if ( nbs.first == NumberTraits<Size>::ZERO ) { clear(); return true; }
  
  // Otherwise, determines A1B1 and A2B2.
  twiceArea(); // result in _a;
  HalfSpace hs1 = halfSpace( it_next_is_outside );
  HalfSpace hs3 = halfSpace( it_next_is_inside );
  //hs3.negate();
  _A1 = *it_next_is_outside;
  ++it_next_is_outside; 
  if ( it_next_is_outside == end() ) it_next_is_outside = begin();
  _B1 = *it_next_is_outside;
  _B2 = *it_next_is_inside;
  ++it_next_is_inside;
  if ( it_next_is_inside == end() ) it_next_is_inside = begin();
  _A2 = *it_next_is_inside;
  // Erases outside vertices.
  while ( it_next_is_outside != it_next_is_inside )
    {
      it_next_is_outside = erase( it_next_is_outside );
      if ( it_next_is_outside == end() ) it_next_is_outside = begin();
    }
  // Both iterators point on the right place.
  if ( _a > NumberTraits<Integer>::ZERO ) 
    { //convex not reduced to a straight line segment
      std::insert_iterator<ClockwiseVertexSequence> itOut 
        = std::inserter<ClockwiseVertexSequence,Iterator>( myVertices, it_next_is_outside );
      computeConvexHullBorder( itOut, _A1, _A2, hs1, hs, hs3 );
    }
  else //convex reduced to a straight line segment
    {
      //compute the new extremity of the straight line segment
      _v = _B1 - _A1;
      _ic.reduce( _v );
      _a = ( hs.c - hs.N.dot( _A1 ) ) / ( hs.N.dot( _v ) );
      _A1 += _v * _a;
      insertBefore( it_next_is_outside, _A1 );
    }
  purge(); // O(n)
  return true;
}

template<typename TSpace , typename TSequence >

bool DGtal::LatticePolytope2D< TSpace, TSequence >::empty ( ) const

inline

Returns:: 'true' if the lattice polytope has no vertex, false otherwise.

Definition at line 117 of file LatticePolytope2D.ih.

Referenced by DGtal::COBANaivePlane< TSpace, TInternalInteger >::computeCentroidAndNormal().

{
  return myVertices.empty();
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::ConstIterator DGtal::LatticePolytope2D< TSpace, TSequence >::end ( ) const

inline

Useful to visit the list of vertices in order.

Returns:: a const iterator (a forward iterator) pointing after the last vertex.

Definition at line 90 of file LatticePolytope2D.ih.

Referenced by DGtal::Display2DFactory::draw().

{
  return myVertices.end();
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Iterator DGtal::LatticePolytope2D< TSpace, TSequence >::end ( )

inline

Useful to visit the list of vertices in order.

Returns:: an iterator (a forward iterator) pointing after the last vertex.

Definition at line 108 of file LatticePolytope2D.ih.

{
  return myVertices.end();
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Iterator DGtal::LatticePolytope2D< TSpace, TSequence >::erase ( Iterator it )

inline

Erases the vertex pointed by it.

Parameters:

it	an iterator pointing on the vertex to erase.

Returns:: an iterator pointing on the next vertex (the one that follows it).

Definition at line 153 of file LatticePolytope2D.ih.

{
  return myVertices.erase( it );
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::SizeCouple DGtal::LatticePolytope2D< TSpace, TSequence >::findCut	(	Iterator &	it_next_is_outside,
		Iterator &	it_next_is_inside,
		const HalfSpace &	hs
	)

inline

Given some half-plane hs, finds the edges/vertices of this polygon that crosses/borders this half-plane.

Complexity is O(n), where n is size().

Parameters:

it_next_is_outside	(returns) either the vertex that is in hs and whose successor is not in hs, or end() if none exists.
it_next_is_inside	(returns) either the vertex that is not in hs and whose successor is in hs, or end() if none exists.

Returns:: the couple (number of vertices that are in hs, number of vertices).

Definition at line 370 of file LatticePolytope2D.ih.

{
  Size nbWithin = NumberTraits<Size>::ZERO;
  Size nb = NumberTraits<Size>::ZERO;
  Iterator it = begin();
  Iterator it_prev = it;
  Iterator it_end = end();
  it_next_is_outside = it_next_is_inside = it_end;
  if ( it == it_end ) 
    return std::make_pair( NumberTraits<Size>::ZERO, NumberTraits<Size>::ZERO );
  bool visibility_begin_vtx; // visibility of begin vertex.
  bool visibility_prev_vtx;  // visibility of previous vertex when visiting the list.
  bool visibility_vtx;       // visibility of current vertex when visiting the list.
  ++nb;
  if ( ( visibility_begin_vtx = hs( *it++ ) ) ) ++nbWithin; // Assignment
  visibility_prev_vtx = visibility_begin_vtx;
  for ( ; it != it_end; ++it, ++nb )
    {
      if ( ( visibility_vtx = hs( *it ) ) ) ++nbWithin; // Assignment
      if ( visibility_vtx != visibility_prev_vtx ) 
        {
          if ( visibility_prev_vtx )  it_next_is_outside = it_prev;
          else                        it_next_is_inside  = it_prev;
        }
      visibility_prev_vtx = visibility_vtx;
      it_prev = it;
    }
  if ( visibility_vtx != visibility_begin_vtx )
    {
      if ( visibility_vtx )  it_next_is_outside = it_prev;
      else                   it_next_is_inside  = it_prev;
    }
  ASSERT( ( nbWithin == 0 ) || ( nbWithin == size() )
          || ( ( it_next_is_outside != it_end ) && ( it_next_is_inside != it_end ) 
               && ( it_next_is_inside != it_next_is_outside ) ) );
  return std::make_pair( nbWithin, nb );
}

template<typename TSpace , typename TSequence >

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

Computes the border of the upper and of the lower convex hull from the starting points inPts[0] (up) and outPts[0] down, along the constraint N2.p <= c2 while the vertices satisfy the constraint N3.p <= c3. The vertices of the two borders are stored at the end of inPts and outPts.

Parameters:

inPts	(in, out) as input, contains the first point, as output the sequence of points satisfying hs2 and hs3.
outPts	(in, out) as input, contains the first point, as output the sequence of points not satisfying hs2 and satisfying hs3.
BV	the Bezout vector of the vector between inPts[ 0 ] and outPts[ 0 ].
hs2	the half-space that is approached by the two sequences of points.
hs3	the limiting half-space which defines the bounds of the approximation.

Definition at line 679 of file LatticePolytope2D.ih.

References DGtal::ClosedIntegerHalfPlane< TSpace >::c, DGtal::ClosedIntegerHalfPlane< TSpace >::isOnBoundary(), and DGtal::ClosedIntegerHalfPlane< TSpace >::N.

{
  ASSERT( hs2.N != hs3.N );
  // _A and _B represents the last computed vertex above and below the constraint resp.
  // _u, _v pair of Bezout vectors.
  _v = BV;
  // initialize A and B
  _A = inPts[0];
  _B = outPts[0];
  // while A and B do not lie on the supporting line of hs2
  // and satisfies hs3 and while v is not parallel to hs2
  while ( ( ! hs2.isOnBoundary( _A ) ) // stops if A reaches hs2.
          && ( hs3( _A ) )             // stops if A does not satisfy hs3.
          && ( ! hs2.isOnBoundary( _B ) ) // stops if B reaches hs2.
          && ( hs3( _B ) )             // stops if B does not satisfy hs3.
          && ( _ic.dotProduct( _v, hs2.N ) != NumberTraits<Integer>::ZERO ) )
    {
#ifdef DEBUG_LatticePolytope2D
      std::cerr << "[CIP::getAllPointsOfHull] A=" << _A
                << " B=" << _B << " v= " << _v << std::endl;
#endif // DEBUG_LatticePolytope2D
      if ( _ic.dotProduct( _v, hs2.N ) < NumberTraits<Integer>::ZERO ) 
        { //------ second configuration, we find a new B --------------------
          _ic.getCoefficientIntersection( _fl, _ce,
                                          _B, _v, hs2.N, hs2.c );
          _u = _B; _u += _v *_fl;
          if ( hs3( _u ) )
            { // Point is still within bounds.
              _B = _u;
              outPts.push_back( _B );
#ifdef DEBUG_LatticePolytope2D
              std::cerr << "[CIP::getAllPointsOfHull] add B=" << _B << std::endl;
#endif // ifdef DEBUG_LatticePolytope2D
            }
          else 
            { // Point is too far away. Check intersection with hs3 instead.
              _ic.getCoefficientIntersection( _fl, _ce,
                                              _B, _v, hs3.N, hs3.c );
              _B += _v * _fl;
              outPts.push_back( _B );
#ifdef DEBUG_LatticePolytope2D
              std::cerr << "[CIP::getAllPointsOfHull] add B=" << _B << std::endl;
#endif //ifdef DEBUG_LatticePolytope2D
              ASSERT( hs3( _B ) );
              break; // necessarily the last point.
            }
        }
      else 
        { //----- first configuration, we find a new A -----------------------
          _ic.getCoefficientIntersection( _fl, _ce,
                                          _A, _v, hs2.N, hs2.c );
          _u = _A; _u += _v *_fl;
          if ( hs3( _u ) )
            { // Point is still within bounds.
              _A = _u;
              inPts.push_back( _A );
#ifdef DEBUG_LatticePolytope2D
              std::cerr << "[CIP::getAllPointsOfHull] add A=" << _A << std::endl;
#endif //ifdef DEBUG_LatticePolytope2D
            }
          else
            { // Point is too far away. Check intersection with hs3 instead.
              _ic.getCoefficientIntersection( _fl, _ce,
                                              _A, _v, hs3.N, hs3.c );
              _A += _v * _fl;
              inPts.push_back( _A );
#ifdef DEBUG_LatticePolytope2D
              std::cerr << "[CIP::getAllPointsOfHull] add A=" << _A << std::endl;
#endif //ifdef DEBUG_LatticePolytope2D
              ASSERT( hs3( _A ) );
              break; // necessarily the last point.
            }
        }
      // update u and v
      _u = _B;
      _u -= _A;
      // From _ic.getValidBezout( _A, _u, _v, N2, c2, N2, c2, 0);
      // JOL: to check.
      _ic.getValidBezout( _v, _A, _u, hs2.N, hs2.c, hs2.N, hs2.c, false ); 
    }
  // when the loop finishes, we have to complete the computation
  // of each convex hull
  // if ( ! hs3( _A ) ) // A does not satisfy C3, we remove it.
  //   inPts.pop_back();
  // else if ( ! hs3( _B ) ) // B does not satisfy C3, we remove it
  //   outPts.pop_back();
  // else 
  if ( hs2.isOnBoundary( _A ) ) // A lies on C2 so A is also a vertex of outPts
    outPts.push_back( _A );
  else if ( hs2.isOnBoundary( _B ) ) // B lies on C2 so B is also a vertex of inPts
    inPts.push_back( _B );
}

template<typename TSpace , typename TSequence >

bool DGtal::LatticePolytope2D< TSpace, TSequence >::getFirstPointsOfHull	(	Vector &	v,
		Point &	inPt,
		Point &	outPt,
		const HalfSpace &	hs1,
		const HalfSpace &	hs2
	)		const

Given a point inPt on the boundary of hs1, computes the closest integer points along the boundary of hs1 that are separated by hs2. Either the intersection is exact and the returned points lies at this intersection, or inPt designates the point that satisfies hs2 while outPt does not satisfy hs2. The two points are then separated by the direction vector of the half-space.

Parameters:

v	(returns) the Bezout vector of the direction vector between inPt and outPt.
inPt	(in/out) as input, a point on hs1, as output, a point on hs1 satisfying hs2.

Precondition:: inPt must belong to hs1.

Parameters:

outPt (returns) a point on hs1 not satisfying hs2.

Returns:: 'true' iff the intersection oh hs1 and hs2 is exact. In this case, outPt is equal to inPt and is at the intersection of the two half-space boundaries.

Definition at line 593 of file LatticePolytope2D.ih.

References DGtal::ClosedIntegerHalfPlane< TSpace >::c, DGtal::ClosedIntegerHalfPlane< TSpace >::isOnBoundary(), DGtal::ClosedIntegerHalfPlane< TSpace >::N, and DGtal::ClosedIntegerHalfPlane< TSpace >::tangent().

{
  ASSERT( hs1.isOnBoundary( inPt ) );
  bool exactIntersection;
  // initialize vector directionVector (not definitive)
  _DV = hs1.tangent();
  //compute the intersection of ray (inPt, _DV) with constraint C2
  _ic.getCoefficientIntersection( _fl, _ce,
                                  inPt, _DV, hs2.N, hs2.c );
  // uses the intersection to compute the first vertex of the upper
  // convex hull (inside convex hull), i.e. the grid point closest to
  // C2 and satisfying C2
  _ic.getDotProduct( _a, inPt, hs2.N );
  // if ( ( _a > hs2.c ) && ( _fl == NumberTraits<Integer>::ZERO ) )
  //   {
  //     inPt += _DV * _ce;
  //     _DV.neg();
  //   }
  // else if ( ( ( _a <= hs2.c ) && ( _fl >= NumberTraits<Integer>::ZERO ) )
  //           || ( ( _a > hs2.c2 ) && ( _fl <= NumberTraits<Integer>::ZERO ) ) )
  if ( ( ( _a <= hs2.c ) && ( _fl >= NumberTraits<Integer>::ZERO ) )
       || ( ( _a > hs2.c ) && ( _fl < NumberTraits<Integer>::ZERO ) ) )
    {
      inPt += _DV * _fl;
    }
  else
    {
      inPt += _DV * _ce;
      _DV.negate();
    }
  // compute the first vertex of the lower convex hull
  if ( _fl == _ce )  //integer intersection
    {
      outPt = inPt;
      exactIntersection = true;
    }
  else
    {
      outPt = inPt + _DV;
      //initialization of v: valid Bezout vector of u
      _ic.getValidBezout( v, inPt, _DV, hs1.N, hs1.c, hs2.N, hs2.c, true ); 
      exactIntersection = false;
    }
#ifdef DEBUG_LatticePolytope2D
  std::cerr << "[CIP::getFirstPointsOfHull] in=" << inPt 
            << " out=" << outPt << " v=" << v << std::endl;
#endif //DEBUG_LatticePolytope2D
  ASSERT( hs1.isOnBoundary( inPt ) );
  ASSERT( hs1.isOnBoundary( outPt ) );
  ASSERT( hs2( inPt ) );
  ASSERT( ( exactIntersection && hs2( outPt ) ) || ( ! exactIntersection && ! hs2( outPt ) ) );
  return exactIntersection;
}

template<typename TSpace , typename TSequence >

template<typename DigitalSet >

void DGtal::LatticePolytope2D< TSpace, TSequence >::getIncludedDigitalPoints ( DigitalSet & aSet ) const

Computes the set aSet all the digital points that belongs to this polygon (interior plus boundary).

Parameters:

aSet	(returns) the set that contains as output all the digital points of this polygon.

Todo:: this method is for now not efficient and is just for visualization purposes.

Computes the set aSet all the digital points that belongs to this polygon.

Parameters:

aSet	(returns) the set that contains as output all the digital points of this polygon.

Returns:: the number of inserted points.

Todo:: this method is for now not efficient.

Definition at line 524 of file LatticePolytope2D.ih.

References DGtal::ClosedIntegerHalfPlane< TSpace >::N, and DGtal::ClosedIntegerHalfPlane< TSpace >::negate().

{
  BOOST_CONCEPT_ASSERT(( CDigitalSet< DigitalSet > ));
  typedef typename DigitalSet::Domain DigitalSetDomain;
  BOOST_STATIC_ASSERT(( ConceptUtils::SameType< DigitalSetDomain, Domain >::value ));
  typedef typename DigitalSetDomain::ConstIterator DomainConstIterator;
  typedef typename DigitalSet::Iterator DigitalSetIterator;
  aSet.clear();
  // case 1 : empty polygon.
  if ( empty() ) return;
  // case 2 : one vertex.
  size_t s = size();
  if ( s == 1 ) 
    {
      aSet.insert( *begin() );
      return;
    }
  // case 3 : 2 vertices
  if ( s == 2 )
    {
      ConstIterator it_vtx = begin();
      ConstIterator it_vtx2 = it_vtx; ++it_vtx2;
      HalfSpace hs = halfSpace( it_vtx );
      Vector orthN( -hs.N[ 1 ], hs.N[ 0 ] );
      HalfSpace hs_orth( orthN, _ic.dotProduct( orthN, *it_vtx ) );
      if ( ! hs_orth( *it_vtx2 ) ) hs_orth.negate();
      HalfSpace hs2 = halfSpace( it_vtx2 );
      Vector orthN2( -hs2.N[ 1 ], hs2.N[ 0 ] );
      HalfSpace hs2_orth( orthN2, _ic.dotProduct( orthN2, *it_vtx2 ) );
      if ( ! hs2_orth( *it_vtx ) ) hs2_orth.negate();
      for ( DomainConstIterator it = aSet.domain().begin(),
              it_end = aSet.domain().end(); it != it_end; ++it )
        if ( hs( *it ) ) aSet.insert( *it );
      for ( DigitalSetIterator it_set = aSet.begin(), it_set_end = aSet.end();
            it_set != it_set_end; )
        {
          DigitalSetIterator it_cur = it_set; ++it_set;
          if ( ! ( hs_orth( *it_cur ) 
                   && hs2( *it_cur )
                   && hs2_orth( *it_cur ) ) ) 
            aSet.erase( it_cur );
        }
      return;
    }
  // case 4 : >= 3 vertices
  ConstIterator it_vtx = begin();
  ConstIterator it_vtx_end = end();
  HalfSpace hs = halfSpace( it_vtx );
  for ( DomainConstIterator it = aSet.domain().begin(),
          it_end = aSet.domain().end(); it != it_end; ++it )
    if ( hs( *it ) ) aSet.insert( *it );
  ++it_vtx;
  for ( ; it_vtx != it_vtx_end; ++it_vtx )
    {
      hs = halfSpace( it_vtx );
      for ( DigitalSetIterator it_set = aSet.begin(), it_set_end = aSet.end();
            it_set != it_set_end; )
        {
          DigitalSetIterator it_cur = it_set; ++it_set;
          if ( ! hs( *it_cur ) ) aSet.erase( it_cur );
        }
    }
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::HalfSpace DGtal::LatticePolytope2D< TSpace, TSequence >::halfSpace ( ConstIterator it ) const

inline

Computes the constraint of the form N.P<=c whose supporting line passes through point *it and *(it+1), such that the other points of the polygon are inside. Parameters of the hafl-space are minimal. Complexity is O(log(D)).

Parameters:

it	an iterator on a point of this polygon.

Returns:: the corresponding half-space.

Precondition:: the polygon should have at least two vertices.

Definition at line 468 of file LatticePolytope2D.ih.

{
  Point A( *it ); ++it;
  if ( it == end() ) it = begin();
  Point B( *it ); ++it;
  if ( it == end() ) it = begin();
  _N[ 0 ] = A[ 1 ] - B[ 1 ];
  _N[ 1 ] = B[ 0 ] - A[ 0 ];
  _ic.getDotProduct( _c, _N, A );
  _ic.getDotProduct( _c1, _N, *it );
  if ( _c1 > _c )
    {
      _N.negate();
      _c = -_c;
    }
  //simplification of the constraint
  _ic.getGcd( _g, _N[ 0 ], _N[ 1 ] );
  _N /= _g;
  return HalfSpace( _N, _ic.floorDiv( _c, _g) );  
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::HalfSpace DGtal::LatticePolytope2D< TSpace, TSequence >::halfSpace	(	const Point &	A,
		const Point &	B,
		const Point &	inP
	)		const

inline

Computes the constraint of the form N.P<=c whose supporting line passes through A and B such that the point inP satisfies the constraint.

Parameters:

A	any point.
B	any point different from A.
inP	any point not on the straight line (AB).

Returns:: the corresponding half-space.

NB: It is not a static method because this method uses the internal IntegerComputer object member.

Definition at line 493 of file LatticePolytope2D.ih.

References DGtal::ClosedIntegerHalfPlane< TSpace >::negate().

{
  _N[ 0 ] = A[ 1 ] - B[ 1 ];
  _N[ 1 ] = B[ 0 ] - A[ 0 ];
  _ic.getDotProduct( _c, _N, A );
  _ic.getDotProduct( _c1, _N, inP );
  if ( _c1 > _c )
    {
      _N.negate();
      _c = -_c;
    }
  //simplification of the constraint
  _ic.getGcd( _g, _N[ 0 ], _N[ 1 ] );
  _N /= _g;
  return HalfSpace( _N, _ic.floorDiv( _c, _g) );  
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::MyIntegerComputer & DGtal::LatticePolytope2D< TSpace, TSequence >::ic ( ) const

inline

Returns:: the object that performs integer calculation.

Definition at line 172 of file LatticePolytope2D.ih.

{
  return _ic;
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Iterator DGtal::LatticePolytope2D< TSpace, TSequence >::insertBefore	(	const Iterator &	pos,
		const Point &	K
	)

inline

Inserts the point K to the lattice polytope before position "pos".

Parameters:

pos	any iterator
K	the point to add

Returns:: an iterator on the newly created element.

Precondition:: if C_1, ..., C_N is the lattice polytope, then C_1, C_pos-1, K ..., C_N should be the vertices of the output lattice polytope.

Definition at line 220 of file LatticePolytope2D.ih.

{
  return myVertices.insert( pos, K );
}

template<typename TSpace , typename TSequence >

bool DGtal::LatticePolytope2D< TSpace, TSequence >::isValid ( ) const

inline

Checks the validity/consistency of the object.

Returns:: 'true' if the object is valid, 'false' otherwise.

Definition at line 880 of file LatticePolytope2D.ih.

{
    return true;
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Size DGtal::LatticePolytope2D< TSpace, TSequence >::max_size ( ) const

inline

Returns:: the maximal possible number of vertices (or edges) that can be stored (here, greatest possible Size integer).

Definition at line 135 of file LatticePolytope2D.ih.

{
  return myVertices.max_size();
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Integer DGtal::LatticePolytope2D< TSpace, TSequence >::numberBoundaryPoints ( ) const

inline

Returns:: the exact number of digital points on the polygon boundary (greater or equal to the number of vertices. NB: complexity in O(n log(D) ), where n is the number of vertices.

Definition at line 334 of file LatticePolytope2D.ih.

{
  _a = NumberTraits<Integer>::ZERO;
  ConstIterator it = begin();
  ConstIterator it_end = end();
  ConstIterator it_next = it; ++it_next;
  while ( it_next != it_end )
    {
      _N = *it_next - *it;
      ic().getGcd( _g, _N[ 0 ], _N[ 1 ] );
      _a += _g;
      it = it_next; ++it_next;
    }
  _N = *it - *(begin());
  ic().getGcd( _g, _N[ 0 ], _N[ 1 ] );
  _a += _g;
  return _a;
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Integer DGtal::LatticePolytope2D< TSpace, TSequence >::numberInteriorPoints ( ) const

inline

Returns:: the exact number of digital points in the polygon interior.

Calls numberBoundaryPoints and twiceArea. Uses Pick's formula.

NB: complexity in O(n log(D) ), where n is the number of vertices.

Definition at line 357 of file LatticePolytope2D.ih.

{
  _c1 = numberBoundaryPoints();
  _c3 = twiceArea();
  _c = _c3 - _c1 + 2;
  ASSERT( ic().isZero( _c % 2 ) );
  return _c / 2;
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Self & DGtal::LatticePolytope2D< TSpace, TSequence >::operator= ( const Self & other )

inline

Assignment.

Parameters:

other the object to copy.

Returns:: a reference on 'this'.

Definition at line 70 of file LatticePolytope2D.ih.

References DGtal::LatticePolytope2D< TSpace, TSequence >::myVertices.

{ // Nothing to do.
  if ( this != &other )
    myVertices = other.myVertices;
  return *this;
}

template<typename TSpace , typename TSequence >

void DGtal::LatticePolytope2D< TSpace, TSequence >::purge ( )

Removes (duplicate) consecutive vertices. NB: complexity is O(N), where N is the number of vertices.

Definition at line 198 of file LatticePolytope2D.ih.

{
  Iterator it = begin();
  Iterator it_end = end();
  Iterator it_prev;
  while ( it != it_end )
    {
      _A = *it;
      it_prev = it;
      ++it;
      while ( ( it != it_end ) && ( _A == *it ) )
        it = erase( it );
    }
  // Checks case where first vertex is also last vertex.
  if ( ( size() > 1 ) && ( * begin() == *it_prev ) )
    erase( begin() );
}

template<typename TSpace , typename TSequence >

void DGtal::LatticePolytope2D< TSpace, TSequence >::push_back ( const Point & K )

inline

Adds the point K to the end of the polygon (stl version for BackInsertable).

Parameters:

K	the point to add

Precondition:: if C_1, ..., C_N is the lattice polytope, then C_1, ..., C_N, K should be the vertices of the output lattice polytope.

See also:: pushBack

Definition at line 247 of file LatticePolytope2D.ih.

{
  myVertices.push_back( K );
}

template<typename TSpace , typename TSequence >

void DGtal::LatticePolytope2D< TSpace, TSequence >::push_front ( const Point & K )

inline

Adds the point K to the beginning of the polygon (stl version)

Parameters:

K	the point to add

Precondition:: if C_1, ..., C_N is the lattice polytope, then K, C_1, ..., C_N should be the vertices of the output lattice polytope.

See also:: pushFront

Examples:: arithmetic/lower-integer-convex-hull.cpp.

Definition at line 256 of file LatticePolytope2D.ih.

{
  myVertices.push_front( K );
}

template<typename TSpace , typename TSequence >

void DGtal::LatticePolytope2D< TSpace, TSequence >::pushBack ( const Point & K )

inline

adds the point K to the end of the polygon.

Parameters:

K	the point to add

Precondition:: if C_1, ..., C_N is the lattice polytope, then C_1, ..., C_N, K should be the vertices of the output lattice polytope.

Definition at line 229 of file LatticePolytope2D.ih.

{
  myVertices.push_back( K );
}

template<typename TSpace , typename TSequence >

void DGtal::LatticePolytope2D< TSpace, TSequence >::pushFront ( const Point & K )

inline

Adds the point K to the beginning of the polygon (stl version)

Parameters:

K	the point to add

Precondition:: if C_1, ..., C_N is the lattice polytope, then K, C_1, ..., C_N should be the vertices of the output lattice polytope.

See also:: push_front

Definition at line 238 of file LatticePolytope2D.ih.

{
  myVertices.push_front( K );
}

template<typename TSpace , typename TSequence >

void DGtal::LatticePolytope2D< TSpace, TSequence >::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 868 of file LatticePolytope2D.ih.

{
  out << "[LatticePolytope2D #Vertices=" << size() << "]";
}

template<typename TSpace , typename TSequence >

DGtal::LatticePolytope2D< TSpace, TSequence >::Size DGtal::LatticePolytope2D< TSpace, TSequence >::size ( ) const

inline

Returns:: the number of vertices (or edges) of the lattice polytope.

Definition at line 126 of file LatticePolytope2D.ih.

{
  return myVertices.size();
}

template<typename TSpace , typename TSequence >

void DGtal::LatticePolytope2D< TSpace, TSequence >::swap ( LatticePolytope2D< TSpace, TSequence > & other )

inline

Swaps the content of this object with other. O(1) complexity.

Parameters:

other any other LatticePolytope2D.

Definition at line 162 of file LatticePolytope2D.ih.

References DGtal::LatticePolytope2D< TSpace, TSequence >::myVertices.

{
  myVertices.swap( other.myVertices );
}

template<typename TSpace , typename TSequence >

const DGtal::LatticePolytope2D< TSpace, TSequence >::Integer & DGtal::LatticePolytope2D< TSpace, TSequence >::twiceArea ( ) const

inline

Returns:: 2*area of polygon.

Definition at line 265 of file LatticePolytope2D.ih.

{
  _a = NumberTraits<Integer>::ZERO;
  ConstIterator it = begin();
  ConstIterator it_end = end();
  ConstIterator it_next = it; ++it_next;
  while ( it_next != it_end )
    {
      _a += _ic.crossProduct( *it, *it_next );
      it = it_next; ++it_next;
    }
  _a += _ic.crossProduct( *it, *(begin()) );
  return _a;
}

Field Documentation

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_a

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Point DGtal::LatticePolytope2D< TSpace, TSequence >::_A

mutableprivate

Definition at line 525 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Point DGtal::LatticePolytope2D< TSpace, TSequence >::_A1

mutableprivate

Definition at line 525 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Point DGtal::LatticePolytope2D< TSpace, TSequence >::_A2

mutableprivate

Definition at line 525 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_b

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Point DGtal::LatticePolytope2D< TSpace, TSequence >::_B

mutableprivate

Definition at line 525 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Point DGtal::LatticePolytope2D< TSpace, TSequence >::_B1

mutableprivate

Definition at line 525 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Point DGtal::LatticePolytope2D< TSpace, TSequence >::_B2

mutableprivate

Definition at line 525 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_c

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_c1

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_c3

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_ce

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_den

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Vector DGtal::LatticePolytope2D< TSpace, TSequence >::_DV

mutableprivate

Definition at line 526 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_fl

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Integer DGtal::LatticePolytope2D< TSpace, TSequence >::_g

mutableprivate

Definition at line 524 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

MyIntegerComputer DGtal::LatticePolytope2D< TSpace, TSequence >::_ic

mutableprivate

A utility object to perform computation on integers. Need not to be copied when cloning this object. Avoids many dynamic allocations when using big integers.

Definition at line 523 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

std::vector<Point> DGtal::LatticePolytope2D< TSpace, TSequence >::_inPts

mutableprivate

Definition at line 527 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Vector DGtal::LatticePolytope2D< TSpace, TSequence >::_N

mutableprivate

Definition at line 526 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

std::vector<Point> DGtal::LatticePolytope2D< TSpace, TSequence >::_outPts

mutableprivate

Definition at line 527 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Vector DGtal::LatticePolytope2D< TSpace, TSequence >::_u

mutableprivate

Definition at line 526 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

Vector DGtal::LatticePolytope2D< TSpace, TSequence >::_v

mutableprivate

Definition at line 526 of file LatticePolytope2D.h.

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>

ClockwiseVertexSequence DGtal::LatticePolytope2D< TSpace, TSequence >::myVertices

protected

Definition at line 516 of file LatticePolytope2D.h.

Referenced by DGtal::LatticePolytope2D< TSpace, TSequence >::operator=(), and DGtal::LatticePolytope2D< TSpace, TSequence >::swap().

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >> class DGtal::LatticePolytope2D< TSpace, TSequence >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation

template<typename TSpace, typename TSequence = std::list< typename TSpace::Point >>
class DGtal::LatticePolytope2D< TSpace, TSequence >