DGtal
1.3.beta

Part of the Geometry package.
This part of the manual describes tools associated to a new definition of digital convexity, called the full convexity [67] . This new definition solves many problems related to the usual definition of digital convexity, like possible non connectedness or non simple connectedness, while encompassing its desirable features. Fully convex sets are digitally convex, but are also connected and simply connected. They have a morphological characterisation, which induces a simple convexity test algorithm. As an important example, arithmetic planes are fully convex too.
The following programs are related to this documentation: geometry/curves/exampleDigitalConvexity.cpp, geometry/curves/exampleRationalConvexity.cpp, testBoundedLatticePolytope.cpp, testCellGeometry.cpp, testDigitalConvexity.cpp, testEhrhartPolynomial.cpp .
This module relies on module QuickHull algorithm in arbitrary dimension for convex hull and Delaunay cell complex computation for convex hull computations in arbitrary dimensions. You may also look at Applications of full digital convexity to see some applications of full convexity.
The usual definition for digital convexity is as follows. For some digital set \( S \subset \mathbb{Z}^d \), \( S \) is said to be digitally convex whenever \( \mathrm{Conv}(S) \cap \mathbb{Z}^d = S \). Otherwise said, the convex hull of all the digital points contains exactly these digital points and no other.
Although handy and easy to check, this definition lacks many properties related to (continuous) convexity in the Euclidean plane.
We extend this definition as follows (see [67] ). Let \( C^d \) be the usual regular cubical complex induced by the lattice \( \mathbb{Z}^d \), and let \( C^d_k \) be its kcells, for \( 0 \le k \le d \). We have that the 0cells of \( C^d_0 \) are exactly the lattice points, the 1cells of \( C^d_1 \) are the open unit segment joining 2 neighboring lattice points, etc.
Finally, for an arbitrary subset \( Y \subset \mathbb{R}^d \), we denote by \( C^d_k \lbrack Y \rbrack \) the set of kcells of \( C^d \) whose closure have a nonempty intersection with \( Y \), i.e. \( C^d_k \lbrack Y \rbrack := \{ c \in C^d_k,~\text{s.t.}~ \bar{c} \cap Y \neq \emptyset \} \).
A digital set \( S \subset \mathbb{Z}^d \) is said to be digitally k convex whenever \( C^d_k \lbrack \mathrm{Conv}(S) \rbrack = C^d_k \lbrack S \rbrack \). \( S \) is said to be fully (digitally) convex whenever it is digitally k convex for \( 0 \le k \le d \).
A fully convex set is always \( 3^d1 \)connected (i.e. 8connected in 2D, 26connected in 3D). Furthermore its axisaligned slices are connected (with the same kind of connectedness). It is also clear that digitally 0convexity is the usual digital convexity.
A last useful notion is the subconvexity, or tangency. Let \( X \subset \mathbb{Z}^d \) some arbitrary digital set. Then the digital set \( S \subset \mathbb{Z}^d \) is said to be digitally k subconvex to \( X \) whenever \( C^d_k \lbrack \mathrm{Conv}(S) \rbrack \subset C^d_k \lbrack X \rbrack \). And \( S \) is said to be fully (digitally) subconvex to \( X \) whenever it is digitally k subconvex to \( X \) for \( 0 \le k \le d \).
Subconvexity is a useful for notion for digital contour and surface analysis. It tells which subsets of these digital sets are tangent to them.
Three classes help to check digital convexity.
For now, the class is quite limited. You may build a polytope in dimension \( d \le 3 \) from a range of \( n \le d + 1 \) points in general position. The polytope is then a simplex. For dimensions higher than 3, you may only builds the polytope from a full dimensional simplex, i.e. \( n = d + 1 \) in general position. Alternatively, you may provide a domain and a range of halfspaces to create the polytope.
You may also cut a polytope by a new halfspace (BoundedLatticePolytope::cut), count the number of lattice points inside, interior or on the boundary (BoundedLatticePolytope::count, BoundedLatticePolytope::countInterior, BoundedLatticePolytope::countBoundary) or enumerate them.
Last, you may compute Minkowski sums of a polytope with axisaligned segments, squares or (hyper)cubes (BoundedLatticePolytope::operator+=).
Point check services:
Standard polytope services:
Enumeration services:
Lattice point retrieval services:
The class CellGeometry can compute and store set of lattice cells of different dimensions. You specify at construction a Khalimsky space (any model of concepts::CCellularGridSpaceND), as well as the dimensions of the cells you are interested in. Internally it uses a variant of unordered set of points (see UnorderedSetByBlock) to store the lattice cells in a compact manner.
Then you may add cells that touch a range of points, or cells intersected by a polytope, or cells belonging to another CellGeometry object.
minCellDim() <= k <= maxCellDim()
, to this cell geometry.With respect to full digital convexity, CellGeometry::addCellsTouchingPolytope is very important since it allows to compute \( C^d_k \lbrack P \rbrack \) for an arbitrary polytope \( P \) and for any \( k \).
Class DigitalConvexity is a helper class to build polytopes from digital sets and to check digital kconvexity. It provides methods for checking if a simplex is full dimensional, building the corresponding polytope, methods for getting the lattice points in a polytope, computing the cells touching lattice points or touching a polytope, and a set of methods to check kconvexity or ksubconvexity (i.e. tangency).
Here are two ways for checking full convexity. The first is the simplest (but hides some details):
Second way to do it, where we see the intermediate computations of points and cells.
Morphological services (since 1.3):
The following snippet shows that a 4D ball is indeed fully convex.
Simplex services:
Polytope services:
Lattice cell geometry services:
Convexity services:
Any lattice polytope has a unique Ehrhart polynomial that encodes the relationship between the volume of the polytope and the number of integer points the polytope contains. It is a kind of extension of 2D Pick's theorem. More precisely, if \( P \) is a (bounded) polytope in \( \mathbb{R}^d \) with vertices lying in \( \mathbb{Z}^d \), and for any positive integer \( t \), let \( tP \) denotes the dilation of \( P \) by a factor \( t \).
We denote \( L(P,t) := \#( tP \cap \mathbb{Z}^d ) \), i.e. the number of lattice points included in the dilation of this polytope.
Then \( L(P,t) \) is a polynomial in \( t \) of degree \( f \). Its monomial coefficients \( L_k(P) \) are rational numbers, and some coefficients have a clear geometric meaning, e.g.:
Note also that, by EhrhartMacDonald reciprocity, the polynomial \( (1)^d L(P,t) \) counts the number of interior lattice points to \( tP \).
Class EhrhartPolynomial provides an elementary method to determine the Ehrhart polynomial of any bounded lattice polytope.
See testEhrhartPolynomial.cpp for examples.
(1,2,...,d)
and counting by bruteforce the number of lattice points within these dilated polytopes. We then compute the Lagrange interpolating polynomial (using class LagrangeInterpolation) and we know that this must be the Ehrhart polynomial. There exists faster ways to compute it, which are however much more complex. See for instance LattE software: https://www.math.ucdavis.edu/~latte .You can also create bounded rational polytopes, i.e. polytopes with vertices with rational coordinates, with class BoundedRationalPolytope. You must give a common denominator for all rational coordinates.
Then the interface of BoundedRationalPolytope is almost the same as the one of BoundedLatticePolytope (see Lattice polytopes ).
The classs BoundedRationalPolytope offers dilatation by an arbitrary rational, e.g. as follows
You may also check digital convexity and compute cell covers with bounded rational polytopes, exactly in the same way as with BoundedLatticePolytope.
The class BoundedLatticePolytope is different from the class LatticePolytope2D for the following two reasons:
There are no simple conversion from one to the other. Class LatticePolytope2D is optimized for cuts and lattice points enumeration, and is very specific to 2D. Class BoundedLatticePolytope is less optimized than the previous one but works in nD and provides Minkowski sum and dilation services.