DGtal
0.9.3beta

Part of the Arithmetic package.
This module gathers classes and functions to represent lattice polytopes in 2D (otherwise saide, convex polygons with vertices at integer coordinates) and digital halfspaces. The main part of the module is the class LatticePolytope2D, which represents these polytopes. This module is a possible solution for solving integer linear programming in the plane. It is thus the basis for the COBA algorithm for recognizing digital planes (see COBANaivePlaneComputer).
The class LatticePolytope2D represents an arbitary convex polygon in the 2D plane whose vertices have integer coordinates. It is parameterized by a digital space TSpace (a model of CSpace with dimension 2) and by the container class TSequence for storing vertices (a model of [boost::Sequence http://www.sgi.com/tech/stl/Sequence.html] over TSpace::Point, default is std::list<TSpace::Point>). The class LatticePolytope2D contains as a data member some TSequence instance and you may use all the standard methods of sequences. All the useful data of a LatticePolytope2D are in the TSequence data member.
The class LatticePolytope2D is a model of boost::Sequence, but also of boost::DefaultConstructible, boost::CopyConstructible, boost::Assignable. This class is also a model of CDrawableWithBoard2D. You may therefore display it on a Board2D object.
Since a sequence is ordered, its order defines the order of vertices along the polygon, i.e. any vertex in the sequence forms an edge with the previous vertex and another edge with the next vertex. Note that the vertices must follow the clockwise ordering, i.e. the inside of the polygon is to the righthand side when moving along the polygon. The following example defines a triangle in the standard limited integer planes Z2i::Z2 (integer coordinates are int32_t
):
You may use any insertion/deletion methods of a sequence (insert, erase, push_back, push_front, etc). Be careful however, in order that the object has a correct behaviour in more elaborate methods like LatticePolytope2D::cut() or LatticePolytope2D::findCut, you must enforce that inserted or deleted vertices leave the polytope convex.
A LatticePolytope2D is a model of CDrawableWithBoard2D. Therefore it is displayable on a Board2D with the operator <<
. The following example displays a square in red over its domain.
You may choose colors with the usual CustomStyle / CustomColors mechanism. Furthermore, choosing Color::None for filling colors allows to draw only the boundary of the polygon.
It is sometimes useful to enumerate all the integer points lying within the polygon bounds. The method LatticePolytope2D::getIncludedDigitalPoints() is templated by the type TDigitalSet, which must be a model of CDigitalSet. It modifies the digital set given in parameter so as to holds these points. For now, the complexity is not optimal. If D is the size of the domain of TDigitalSet, N the number of vertices of the polygon, then the complexity is upper bounded by O(ND log(D)) (if TDigitalSet is DigitalSetBySTLSet).
Since a LatticePolytope2D is a sequence, you may iterate over the vertices with the usual LatticePolytope2D::begin()and LatticePolytope2D::end(), with two versions of iterators (Iterator and ConstIterator). To know if the polygon has no vertices, it is faster to use LatticePolytope2D::empty(). Otherwise you may obtain the following information:
A LatticePolytope2D P may have zero area (in this case it has at most two vertices). Thanks to Pick formula, you can also get the exact number b of points on the boundary and the exact number i of points in the interior of the polygon: \( A(P) = i + b/2  1 \).
A lattice polytope polygon may be defined by a list of vertices (with some properties) but also as the intersection of halfplanes. For instance, if \( (v_i)_{i=0..n1} \) are the vertices of the polytope, then the polytope is also the intersection of the halfplanes which contains the polytope centroid and whose boundary contains edges \((v_i,v_{i+1})\).
You may use the following methods:
You may also update a LatticePolytope2D by intersecting it with halfplanes, i.e. linear constraints of the form ax+by <= c. The polygon is updated so that all its vertices have integer coordinates and the constraints are fulfilled. This means for instance that a set of linear constraints may have a nonempty interior (in the Euclidean space sense), but the resulting polygon may be empty or have an empty interior. However, it is guaranteed that all integer solutions are kept.
This snippet is taken from example lowerintegerconvexhull.cpp. It cuts the polygon by calling LatticePolytope2D::cut. An halfplane is specified beforehands by instantiating a LatticePolytope2D::HalfSpace. Note that it is a redefinition of the class ClosedIntegerHalfPlane.
This shows the successive polygons obtained by cutting a square with constraints 5x+8y <= c.