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. More...

#include <DGtal/arithmetic/LatticePolytope2D.h>

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

[legend]

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 ((concepts::ConceptUtils::SameType< Value, Point >::value))

	BOOST_STATIC_ASSERT ((concepts::ConceptUtils::SameType< Point2I, Point >::value))

	BOOST_STATIC_ASSERT ((concepts::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 ((concepts::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 displayable on a Board2D object with two modes: "" or "Transparent", "Filled".

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 82 of file LatticePolytope2D.h.

Member Typedef Documentation

◆ ClockwiseVertexSequence

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

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

Definition at line 90 of file LatticePolytope2D.h.

◆ const_iterator

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

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

Definition at line 104 of file LatticePolytope2D.h.

◆ const_pointer

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

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

Definition at line 105 of file LatticePolytope2D.h.

◆ const_reference

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

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

Definition at line 102 of file LatticePolytope2D.h.

◆ ConstIterator

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

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

Definition at line 111 of file LatticePolytope2D.h.

◆ difference_type

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

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

Definition at line 107 of file LatticePolytope2D.h.

◆ Domain

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

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

Definition at line 97 of file LatticePolytope2D.h.

◆ HalfSpace

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

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

Definition at line 98 of file LatticePolytope2D.h.

◆ Integer

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

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

Definition at line 93 of file LatticePolytope2D.h.

◆ Iterator

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

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

Definition at line 110 of file LatticePolytope2D.h.

◆ iterator

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

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

Definition at line 103 of file LatticePolytope2D.h.

◆ MyIntegerComputer

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

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

Definition at line 96 of file LatticePolytope2D.h.

◆ Point

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

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

Definition at line 94 of file LatticePolytope2D.h.

◆ Point2I

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

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

Definition at line 120 of file LatticePolytope2D.h.

◆ Point3I

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

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

Definition at line 122 of file LatticePolytope2D.h.

◆ reference

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

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

Definition at line 101 of file LatticePolytope2D.h.

◆ Self

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

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

Definition at line 89 of file LatticePolytope2D.h.

◆ Size

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

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

Definition at line 112 of file LatticePolytope2D.h.

◆ size_type

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

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

Definition at line 106 of file LatticePolytope2D.h.

◆ SizeCouple

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

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

Definition at line 113 of file LatticePolytope2D.h.

◆ Space

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

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

Definition at line 92 of file LatticePolytope2D.h.

◆ Value

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

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

Definition at line 109 of file LatticePolytope2D.h.

◆ value_type

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

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

Definition at line 100 of file LatticePolytope2D.h.

◆ Vector

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

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

Definition at line 95 of file LatticePolytope2D.h.

◆ Vector2I

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

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

Definition at line 121 of file LatticePolytope2D.h.

◆ Vector3I

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

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

Definition at line 123 of file LatticePolytope2D.h.

Constructor & Destructor Documentation

◆ ~LatticePolytope2D()

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

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

Destructor.

◆ LatticePolytope2D() [1/2]

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

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

Constructor.

◆ LatticePolytope2D() [2/2]

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

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

Copy constructor.

Parameters

other the object to clone.

Member Function Documentation

◆ begin() [1/2]

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

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

Useful to visit the list of vertices in order.

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

◆ begin() [2/2]

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

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

Useful to visit the list of vertices in order.

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

◆ BOOST_CONCEPT_ASSERT() [1/2]

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

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

private

◆ BOOST_CONCEPT_ASSERT() [2/2]

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

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

private

◆ BOOST_STATIC_ASSERT() [1/4]

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

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

◆ BOOST_STATIC_ASSERT() [2/4]

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

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

◆ BOOST_STATIC_ASSERT() [3/4]

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

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

◆ BOOST_STATIC_ASSERT() [4/4]

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

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

private

◆ boundingBoxDomain()

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

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.

Referenced by checkCut().

◆ centroid() [1/2]

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

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

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

◆ centroid() [2/2]

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

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

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

◆ className()

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

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

Returns: the class name. It is notably used for drawing this object.

Referenced by checkCut().

◆ clear()

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

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

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

◆ computeConvexHullBorder()

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

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.

pointRefC1 and pointRefC3 corresponds to grid point lying on the supporting lines of C1 and of C3 resp.

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.

Parameters

itOut	The output iterator.
pointRefC1	The grid point lying on C1.
pointRefC3	The grid point lying on C3.
hs1	The first half-space.
hs2	The second half-space.
hs3	The third half-space.

Todo: proper parameters documentation.

◆ cut()

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

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

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.

Referenced by checkCut().

◆ empty()

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

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

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

◆ end() [1/2]

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

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

Useful to visit the list of vertices in order.

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

◆ end() [2/2]

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

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

Useful to visit the list of vertices in order.

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

◆ erase()

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

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

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).

◆ findCut()

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

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

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.
hs	The half-plane.

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

◆ getAllPointsOfHull()

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

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.

◆ getFirstPointsOfHull()

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

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.
hs1	The first half-space.
hs2	The second half-space.

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.

◆ getIncludedDigitalPoints()

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

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.

Referenced by checkCut().

◆ halfSpace() [1/2]

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

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

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.

◆ halfSpace() [2/2]

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

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

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.

◆ ic()

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

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

Returns: the object that performs integer calculation.

◆ insertBefore()

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

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

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.

◆ isValid()

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

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

Checks the validity/consistency of the object.

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

◆ max_size()

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

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

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

◆ numberBoundaryPoints()

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

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

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.

◆ numberInteriorPoints()

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

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

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.

◆ operator=()

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

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

Assignment.

Parameters

other the object to copy.

Returns: a reference on 'this'.

◆ purge()

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

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

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

◆ push_back()

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

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

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

◆ push_front()

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

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

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.

Referenced by main().

◆ pushBack()

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

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

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.

◆ pushFront()

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

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

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

◆ selfDisplay()

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

void DGtal::LatticePolytope2D< TSpace, TSequence >::selfDisplay ( std::ostream & out ) const

Writes/Displays the object on an output stream.

Parameters

out	the output stream where the object is written.

◆ size()

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

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

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

Referenced by checkCut().

◆ swap()

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

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

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

Parameters

other any other LatticePolytope2D.

◆ twiceArea()

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

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

Returns: 2*area of polygon.

Field Documentation

◆ _A

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

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

mutableprivate

Definition at line 536 of file LatticePolytope2D.h.

◆ _a

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

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

mutableprivate

Definition at line 535 of file LatticePolytope2D.h.

◆ _A1

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

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

private

Definition at line 536 of file LatticePolytope2D.h.

◆ _A2

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

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

private

Definition at line 536 of file LatticePolytope2D.h.

◆ _B

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

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

private

Definition at line 536 of file LatticePolytope2D.h.

◆ _b

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

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

private

Definition at line 535 of file LatticePolytope2D.h.

◆ _B1

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

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

private

Definition at line 536 of file LatticePolytope2D.h.

◆ _B2

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

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

private

Definition at line 536 of file LatticePolytope2D.h.

◆ _c

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

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

private

Definition at line 535 of file LatticePolytope2D.h.

◆ _c1

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

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

private

Definition at line 535 of file LatticePolytope2D.h.

◆ _c3

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

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

private

Definition at line 535 of file LatticePolytope2D.h.

◆ _ce

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

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

private

Definition at line 535 of file LatticePolytope2D.h.

◆ _den

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

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

private

Definition at line 535 of file LatticePolytope2D.h.

◆ _DV

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

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

private

Definition at line 537 of file LatticePolytope2D.h.

◆ _fl

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

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

private

Definition at line 535 of file LatticePolytope2D.h.

◆ _g

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

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

private

Definition at line 535 of file LatticePolytope2D.h.

◆ _ic

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 534 of file LatticePolytope2D.h.

◆ _inPts

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

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

mutableprivate

Definition at line 538 of file LatticePolytope2D.h.

◆ _N

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

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

mutableprivate

Definition at line 537 of file LatticePolytope2D.h.

◆ _outPts

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

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

private

Definition at line 538 of file LatticePolytope2D.h.

◆ _u

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

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

private

Definition at line 537 of file LatticePolytope2D.h.

◆ _v

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

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

private

Definition at line 537 of file LatticePolytope2D.h.

◆ myVertices

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

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

protected

Definition at line 527 of file LatticePolytope2D.h.

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

LatticePolytope2D.h

Public Types

Public Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ClockwiseVertexSequence

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ ConstIterator

◆ difference_type

◆ Domain

◆ HalfSpace

◆ Integer

◆ Iterator

◆ iterator

◆ MyIntegerComputer

◆ Point

◆ Point2I

◆ Point3I

◆ reference

◆ Self

◆ Size

◆ size_type

◆ SizeCouple

◆ Space

◆ Value

◆ value_type

◆ Vector

◆ Vector2I

◆ Vector3I

Constructor & Destructor Documentation

◆ ~LatticePolytope2D()

◆ LatticePolytope2D() [1/2]

◆ LatticePolytope2D() [2/2]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ BOOST_CONCEPT_ASSERT() [1/2]

◆ BOOST_CONCEPT_ASSERT() [2/2]

◆ BOOST_STATIC_ASSERT() [1/4]

◆ BOOST_STATIC_ASSERT() [2/4]

◆ BOOST_STATIC_ASSERT() [3/4]

◆ BOOST_STATIC_ASSERT() [4/4]

◆ boundingBoxDomain()

◆ centroid() [1/2]

◆ centroid() [2/2]

◆ className()

◆ clear()

◆ computeConvexHullBorder()

◆ cut()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ findCut()

◆ getAllPointsOfHull()

◆ getFirstPointsOfHull()

◆ getIncludedDigitalPoints()

◆ halfSpace() [1/2]

◆ halfSpace() [2/2]

◆ ic()

◆ insertBefore()

◆ isValid()

◆ max_size()

◆ numberBoundaryPoints()

◆ numberInteriorPoints()

◆ operator=()

◆ purge()

◆ push_back()

◆ push_front()

◆ pushBack()

◆ pushFront()

◆ selfDisplay()

◆ size()

◆ swap()

◆ twiceArea()

Field Documentation