DGtal 1.3.0
|
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>
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 |
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.
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. |
Definition at line 82 of file LatticePolytope2D.h.
typedef TSequence DGtal::LatticePolytope2D< TSpace, TSequence >::ClockwiseVertexSequence |
Definition at line 90 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::const_iterator DGtal::LatticePolytope2D< TSpace, TSequence >::const_iterator |
Definition at line 104 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::const_pointer DGtal::LatticePolytope2D< TSpace, TSequence >::const_pointer |
Definition at line 105 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::const_reference DGtal::LatticePolytope2D< TSpace, TSequence >::const_reference |
Definition at line 102 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::const_iterator DGtal::LatticePolytope2D< TSpace, TSequence >::ConstIterator |
Definition at line 111 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::difference_type DGtal::LatticePolytope2D< TSpace, TSequence >::difference_type |
Definition at line 107 of file LatticePolytope2D.h.
typedef HyperRectDomain< Space > DGtal::LatticePolytope2D< TSpace, TSequence >::Domain |
Definition at line 97 of file LatticePolytope2D.h.
typedef ClosedIntegerHalfPlane< Space > DGtal::LatticePolytope2D< TSpace, TSequence >::HalfSpace |
Definition at line 98 of file LatticePolytope2D.h.
typedef Space::Integer DGtal::LatticePolytope2D< TSpace, TSequence >::Integer |
Definition at line 93 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::iterator DGtal::LatticePolytope2D< TSpace, TSequence >::iterator |
Definition at line 103 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::iterator DGtal::LatticePolytope2D< TSpace, TSequence >::Iterator |
Definition at line 110 of file LatticePolytope2D.h.
typedef IntegerComputer<Integer> DGtal::LatticePolytope2D< TSpace, TSequence >::MyIntegerComputer |
Definition at line 96 of file LatticePolytope2D.h.
typedef Space::Point DGtal::LatticePolytope2D< TSpace, TSequence >::Point |
Definition at line 94 of file LatticePolytope2D.h.
typedef MyIntegerComputer::Point2I DGtal::LatticePolytope2D< TSpace, TSequence >::Point2I |
Definition at line 120 of file LatticePolytope2D.h.
typedef MyIntegerComputer::Point3I DGtal::LatticePolytope2D< TSpace, TSequence >::Point3I |
Definition at line 122 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::reference DGtal::LatticePolytope2D< TSpace, TSequence >::reference |
Definition at line 101 of file LatticePolytope2D.h.
typedef LatticePolytope2D<TSpace,TSequence> DGtal::LatticePolytope2D< TSpace, TSequence >::Self |
Definition at line 89 of file LatticePolytope2D.h.
typedef std::size_t DGtal::LatticePolytope2D< TSpace, TSequence >::Size |
Definition at line 112 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::size_type DGtal::LatticePolytope2D< TSpace, TSequence >::size_type |
Definition at line 106 of file LatticePolytope2D.h.
typedef std::pair<Size,Size> DGtal::LatticePolytope2D< TSpace, TSequence >::SizeCouple |
Definition at line 113 of file LatticePolytope2D.h.
typedef TSpace DGtal::LatticePolytope2D< TSpace, TSequence >::Space |
Definition at line 92 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::value_type DGtal::LatticePolytope2D< TSpace, TSequence >::Value |
Definition at line 109 of file LatticePolytope2D.h.
typedef ClockwiseVertexSequence::value_type DGtal::LatticePolytope2D< TSpace, TSequence >::value_type |
Definition at line 100 of file LatticePolytope2D.h.
typedef Space::Vector DGtal::LatticePolytope2D< TSpace, TSequence >::Vector |
Definition at line 95 of file LatticePolytope2D.h.
typedef MyIntegerComputer::Vector2I DGtal::LatticePolytope2D< TSpace, TSequence >::Vector2I |
Definition at line 121 of file LatticePolytope2D.h.
typedef MyIntegerComputer::Vector3I DGtal::LatticePolytope2D< TSpace, TSequence >::Vector3I |
Definition at line 123 of file LatticePolytope2D.h.
DGtal::LatticePolytope2D< TSpace, TSequence >::~LatticePolytope2D | ( | ) |
Destructor.
DGtal::LatticePolytope2D< TSpace, TSequence >::LatticePolytope2D | ( | ) |
Constructor.
DGtal::LatticePolytope2D< TSpace, TSequence >::LatticePolytope2D | ( | const Self & | other | ) |
Copy constructor.
other | the object to clone. |
Iterator DGtal::LatticePolytope2D< TSpace, TSequence >::begin | ( | ) |
Useful to visit the list of vertices in order.
ConstIterator DGtal::LatticePolytope2D< TSpace, TSequence >::begin | ( | ) | const |
Useful to visit the list of vertices in order.
|
private |
|
private |
DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_STATIC_ASSERT | ( | (concepts::ConceptUtils::SameType< Point2I, Point >::value) | ) |
DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_STATIC_ASSERT | ( | (concepts::ConceptUtils::SameType< Value, Point >::value) | ) |
DGtal::LatticePolytope2D< TSpace, TSequence >::BOOST_STATIC_ASSERT | ( | (concepts::ConceptUtils::SameType< Vector2I, Vector >::value) | ) |
|
private |
Domain DGtal::LatticePolytope2D< TSpace, TSequence >::boundingBoxDomain | ( | ) | const |
Referenced by checkCut().
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).
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).
twice_area | the area*2 of this polygon. |
std::string DGtal::LatticePolytope2D< TSpace, TSequence >::className | ( | ) | const |
Referenced by checkCut().
void DGtal::LatticePolytope2D< TSpace, TSequence >::clear | ( | ) |
Clears the lattice polytope. Afterwards, it is composed of 0 vertices.
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.
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. |
bool DGtal::LatticePolytope2D< TSpace, TSequence >::cut | ( | const HalfSpace & | hs | ) |
Cuts the lattice polytope with the given half-space constraint.
hs | any half-space constraint. |
NB: complexity is O(N) for finding the involved edges, then log(D) for applying the cut.
Referenced by checkCut().
bool DGtal::LatticePolytope2D< TSpace, TSequence >::empty | ( | ) | const |
Iterator DGtal::LatticePolytope2D< TSpace, TSequence >::end | ( | ) |
Useful to visit the list of vertices in order.
ConstIterator DGtal::LatticePolytope2D< TSpace, TSequence >::end | ( | ) | const |
Useful to visit the list of vertices in order.
Iterator DGtal::LatticePolytope2D< TSpace, TSequence >::erase | ( | Iterator | it | ) |
Erases the vertex pointed by it.
it | an iterator pointing on the vertex to erase. |
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().
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. |
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.
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. |
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.
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. |
outPt | (returns) a point on hs1 not satisfying hs2. |
hs1 | The first half-space. |
hs2 | The second half-space. |
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).
aSet | (returns) the set that contains as output all the digital points of this polygon. |
Referenced by checkCut().
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.
A | any point. |
B | any point different from A. |
inP | any point not on the straight line (AB). |
NB: It is not a static method because this method uses the internal IntegerComputer object member.
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)).
it | an iterator on a point of this polygon. |
MyIntegerComputer & DGtal::LatticePolytope2D< TSpace, TSequence >::ic | ( | ) | const |
Iterator DGtal::LatticePolytope2D< TSpace, TSequence >::insertBefore | ( | const Iterator & | pos, |
const Point & | K | ||
) |
Inserts the point K to the lattice polytope before position "pos".
pos | any iterator |
K | the point to add |
bool DGtal::LatticePolytope2D< TSpace, TSequence >::isValid | ( | ) | const |
Checks the validity/consistency of the object.
Size DGtal::LatticePolytope2D< TSpace, TSequence >::max_size | ( | ) | const |
Integer DGtal::LatticePolytope2D< TSpace, TSequence >::numberBoundaryPoints | ( | ) | const |
Integer DGtal::LatticePolytope2D< TSpace, TSequence >::numberInteriorPoints | ( | ) | const |
Calls numberBoundaryPoints and twiceArea. Uses Pick's formula.
NB: complexity in O(n log(D) ), where n is the number of vertices.
Self & DGtal::LatticePolytope2D< TSpace, TSequence >::operator= | ( | const Self & | other | ) |
Assignment.
other | the object to copy. |
void DGtal::LatticePolytope2D< TSpace, TSequence >::purge | ( | ) |
Removes (duplicate) consecutive vertices. NB: complexity is O(N), where N is the number of vertices.
void DGtal::LatticePolytope2D< TSpace, TSequence >::push_back | ( | const Point & | K | ) |
Adds the point K to the end of the polygon (stl version for BackInsertable).
K | the point to add |
void DGtal::LatticePolytope2D< TSpace, TSequence >::push_front | ( | const Point & | K | ) |
void DGtal::LatticePolytope2D< TSpace, TSequence >::pushBack | ( | const Point & | K | ) |
adds the point K to the end of the polygon.
K | the point to add |
void DGtal::LatticePolytope2D< TSpace, TSequence >::pushFront | ( | const Point & | K | ) |
Adds the point K to the beginning of the polygon (stl version)
K | the point to add |
void DGtal::LatticePolytope2D< TSpace, TSequence >::selfDisplay | ( | std::ostream & | out | ) | const |
Writes/Displays the object on an output stream.
out | the output stream where the object is written. |
Size DGtal::LatticePolytope2D< TSpace, TSequence >::size | ( | ) | const |
Referenced by checkCut().
void DGtal::LatticePolytope2D< TSpace, TSequence >::swap | ( | LatticePolytope2D< TSpace, TSequence > & | other | ) |
Swaps the content of this object with other. O(1) complexity.
other | any other LatticePolytope2D. |
const Integer & DGtal::LatticePolytope2D< TSpace, TSequence >::twiceArea | ( | ) | const |
|
mutableprivate |
Definition at line 535 of file LatticePolytope2D.h.
|
mutableprivate |
Definition at line 536 of file LatticePolytope2D.h.
|
private |
Definition at line 536 of file LatticePolytope2D.h.
|
private |
Definition at line 536 of file LatticePolytope2D.h.
|
private |
Definition at line 535 of file LatticePolytope2D.h.
|
private |
Definition at line 536 of file LatticePolytope2D.h.
|
private |
Definition at line 536 of file LatticePolytope2D.h.
|
private |
Definition at line 536 of file LatticePolytope2D.h.
|
private |
Definition at line 535 of file LatticePolytope2D.h.
|
private |
Definition at line 535 of file LatticePolytope2D.h.
|
private |
Definition at line 535 of file LatticePolytope2D.h.
|
private |
Definition at line 535 of file LatticePolytope2D.h.
|
private |
Definition at line 535 of file LatticePolytope2D.h.
|
private |
Definition at line 537 of file LatticePolytope2D.h.
|
private |
Definition at line 535 of file LatticePolytope2D.h.
|
private |
Definition at line 535 of file LatticePolytope2D.h.
|
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.
|
mutableprivate |
Definition at line 538 of file LatticePolytope2D.h.
|
mutableprivate |
Definition at line 537 of file LatticePolytope2D.h.
|
private |
Definition at line 538 of file LatticePolytope2D.h.
|
private |
Definition at line 537 of file LatticePolytope2D.h.
|
private |
Definition at line 537 of file LatticePolytope2D.h.
|
protected |
Definition at line 527 of file LatticePolytope2D.h.