DGtal  1.2.beta
Digital convexity

Table of Contents

Author(s) of this documentation:
Jacques-Olivier Lachaud
Since
1.1

Part of the Geometry package.

This part of the manual describes how to define and check digital convexity, in such a way that digital convex set are digitally connected.

The following programs are related to this documentation: geometry/curves/exampleDigitalConvexity.cpp, geometry/curves/exampleRationalConvexity.cpp, testBoundedLatticePolytope.cpp, testCellGeometry.cpp, testDigitalConvexity.cpp

Introduction to digital 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. Let \( C^d \) be the usual regular cubical complex induced by the lattice \( \mathbb{Z}^d \), and let \( C^d_k \) be its k-cells, for \( 0 \le k \le d \). We have that the 0-cells of \( C^d_0 \) are exactly the lattice points, the 1-cells 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 k-cells of \( C^d \) whose closure have a non-empty 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^d-1 \)-connected (i.e. 8-connected in 2D, 26-connected in 3D). Furthermore its axis-aligned slices are connected (with the same kind of connectedness). It is also clear that digitally 0-convexity is the usual digital convexity.

non-fully-convex-triangles.png
Examples of non fully digitally convex triangles in Z2. Missing 1-cells for 1-digital convexity are in blue, Missing 2-cells for 2-digital convexity are in green.

A last useful notion is the subconvexity. 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.

Checking digital convexity

Three classes help to check digital convexity.

Lattice polytopes

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 half-spaces 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.

Note
Lattice point counting is done here in a naive way, by domain enumeration and constraint check. If m is the number of constraints and n the number of lattice points in the polytope domain, then complexity is in \( O(mn) \).
#include "DGtal/geometry/volumes/BoundedLatticePolytope.h"
...
using namespace DGtal::Z3i;
typedef BoundedLatticePolytope< Space > Simplex;
Simplex S( { Point(0,0,0), Point(3,0,0), Point(1,5,0), Point(-3,2,4) } );
std::cout << S.count() << std::endl;
simplex += Simplex::UnitSegment( 0 ); // Extend it along x
std::cout << S.count() << std::endl;

Last, you may compute Minkowski sums of a polytope with axis-aligned segments, squares or (hyper)-cubes (BoundedLatticePolytope::operator+=).

Note
You can check if the result of a Minkowski sum will be valid by calling BoundedLatticePolytope::canBeSummed before. The support is for now limited to polytopes built as simplices in 2D and 3D.
See also
DigitalConvexity::makeSimplex

Point check services:

Standard polytope services:

Enumeration services:

Lattice point retrieval services:

Building a set of lattice cells from digital points

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.

#include "DGtal/geometry/volumes/CellGeometry.h"
...
using namespace DGtal::Z3i;
K.init( Point(-5,-5,-5), Point(15,15,15) );
CellGeometry< KSpace > cell_geometry( K, 1, 2 ); // only 1-cells and 2-cells

Then you may add cells that touch a range of points, or cells intersected by a polytope, or cells belonging to another CellGeometry object.

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

Checking digital (sub-)convexity

Class DigitalConvexity is a helper class to build polytopes from digital sets and to check digital k-convexity. 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 k-convexity or k-subconvexity.

#include "DGtal/geometry/volumes/DigitalConvexity.h"
...
using namespace DGtal;
using namespace DGtal::Z3i;
typedef DigitalConvexity< KSpace > DConvexity;
// Create DigitalConvexity object with a domain.
DConvexity dconv( Point( -5, -5 ), Point( 10, 10 ) );
// Create a (fat) simplex within the domain
std::vector<Point> V = { Point(0,0), Point(4,-1), Point(2,5) };
auto fat_simplex = dconv.makeSimplex ( V.begin(), V.end() );
// Get all the points in the simplex
auto inside_pts = dconv.insidePoints ( fat_simplex );
// Get the lattice cells intersected by the simplex
auto simplex_cover = dconv.makeCellCover( fat_simplex );
// Get the lattice cells intersected by the lattice points in the simplex
auto point_cover = dconv.makeCellCover( inside_pts.begin(), inside_pts.end() );
// They are the same here since this simplex is fully convex.
bool ok = simplex_cover.subset( point_cover ); // one way to do it
bool ok2 = dconv.isFullyConvex ( fat_simplex ); // the other way to do it

Simplex services:

Polytope services:

Lattice cell geometry services:

Convexity services:

Rational polytopes

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.

#include "DGtal/geometry/volumes/BoundedRationalPolytope.h"
...
typedef SpaceND<2,int> Space;
typedef BoundedRationalPolytope< Space > Polytope;
// A thin triangle P at (4/4,2/4), (2/4,4/4), (9/4,9/4)
Point a( 4, 2 );
Point b( 2, 4 );
Point c( 9, 9 );
Polytope P { Point(4,4), a, b, c };

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

Polytope Q = Polytope::Rational( 10, 3 ) * P; // 10/3 * P

You may also check digital convexity and compute cell covers with bounded rational polytopes, exactly in the same way as with BoundedLatticePolytope.

Note
Big denominators increase with the same factor coefficients of half space constraints, hence the integer type should be chosen accordingly.

Further notes

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.