DGtal
1.2.0

This part of the manual describes the DGtal kernel and its classes. More precisely, we define several key concepts in DGtal such as Space or Domain. All classes and utilities defined in the DGtal library require a specification of the digital space in which the objects are defined.
For DGtal users, the specification of the digital Space usually corresponds to the first lines of DGtal codes.
A DGtal Space parametrized by two things: a dimension (SpaceND::dimension) and a type for integers (SpaceND::Integer). Using these information, we aim at approximating the digital space \(Z^n\) by \(Integer^{dimension}\). Hence, we have several constraints these parameters:
Since the Space is obtained by direct product of the range associated to the type Integer. Such type is also used to characterized the coordinates of points lying in this space.
In DGtal, Space specification is addresses by the class DGtal::SpaceND. More precisely, this class is templated by two arguments (the static dimension and the Integer type) and provides types for several objects that can be deduced from the template parameters. For example, once the parameter are specified, the class provides a type Point for all points in the space.
For example, digital spaces can be defined as follows:
In the latter example, we construct a digital space using multiprecision intergers (implemented using the GMP arbitrary precision library). For details, see the documentation page Number and Integer Concepts.
Using the shortcuts provides in StdDefs.h, the types defined in the namespace DGtal::Z2i correspond to a digital space in dimension 2 based on int (int32_t
). Hence, we can simple define MySpace
as:
We can construct a point lying in this space as follows:
Beside the type Point
(defined as a specialization of the class PointVector), SpaceND (or Z2i::Space) provides several other types and methodes such as
Point
s and Vector
s are fundamental objects in the digital space. Indeed, they allow us to access to grid point location or to represent displacements between grid points. Many methods are defined for Point and Vector instances. For example we have
*
, 
, ...)<
,>
, ...)inf
, sup
, isLower
,...)Point
s/Vector
s.An element of a Point
has type Coordinate
and an element of a Vector
has type Component
. For instance, the following code is valid in terms of type.
However, we encourage the use of iterators as follows
Vector
and Space
are aliases, SpaceND::Point::Coordinate and SpaceND::Vector::Component are aliases of SpaceND::Integer. It does not lead to a strong typing of Point
and Vector
but it helps the user to design code as close as possible to a mathematical formulation.PointVector class is parametrized by the following template parameters:
boost::array
with static size equals to the space dimension). In fact, we consider a weaker concept than boost::RandomAccessContainer since we only need iterators and reverse_iterators (const
and nonconst
) to be defined, default/copy constructors and operator[]
. Models can be boost::array
, std::vector
or even std::array
(for C++11
enabled projects).Once we have defined the fundamental characteristics of our digital space, we can define a domain on which all the computations will done. A domain is characterized by a starting point A, an end point B and a way to scan all the point between A and B. In most situation, one may want the domain to be a finite isothetic subset of the digital space. Hence, an important model of the concept of domain (specified in the concepts::CDomain class) is the class HyperRectDomain. Since the domain lies on a digital space, the HyperRectDomain class has a template argument which correspond to the type of space we consider.
For example, let us consider the following code snippet
An instance of HyperRectDomain can be created as follows:
The instance is thus an isothetic domain lying on the space SpaceND<2,DGtal::uint32_t>
defined by the bounding box of the points a and b. Note that type Z2i::Domain in StdDefs.h exactly corresponds to HyperRectDomain on the Z2i::Space. We can visualise the domain using the Board2D stream mechanism (see Board2D: a stream mechanism for displaying 2D digital objects).
The HyperRectDomain class provides several methods such as HyperRectDomain::isInside to decide if a point is inside the domain or not.
An important feature of DGtal domain is based on iterators it defines to scan the grid points in various orders. For example, to scan the whole domain we can use
By default, HyperRectDomain iterators use the lexicographic order on the dimensions. To visualise this order in dimension 2, we can use the following code snippet in which we display each point by a color map from blue to red according to the order (blue point corresponds to the first point and the red one to the last point). Note that in this example, we use a specific drawing primitive (draw
) in order to draw a SpaceND::Vector as an arrow..
Again, for details on the Board2D mechanism, please refer to Board2D: a stream mechanism for displaying 2D digital objects.
For each iterator ̀ XXX, there is a corresponding
ReverseXXX` class allowing to run through the same elements but in reverse direction. For the whole domain, we wan use
Note that the HyperRectDomain::begin and HyperRectDomain::rbegin methods can take an optional Point
as parameter which is used as starting point for the iterator. In this case, the point must belongs to the domain.
There are some classes and methods to run through a given subdomain, and allowing to change the order in which dimension are considered. To facilitate their use, these subdomains use the range concept. A range provides iterators for accessing a halfopen range [first,one_past_last)
of elements. There iterators are accessible by begin()
and end()
methods of each range class. Moreover, a range can be iterated in reverse direction thanks to iterators returned by rbegin()
and rend()
methods. As for the begin
and rbegin
methods on the whole domain, the begin
and rbegin
range methods can have an optional point as parameter which is used as starting point for the iterator. In this case, the point must belongs to the given range.
To use these ranges, we need first to get a subrange thanks to one HyperRectDomain::subRange method. As illustrate below, the basic method take a std::vector<Dimension>
as first parameter, describing the dimensions of the subdomain, and a Point
as second parameter which give the position of the subdomain for the dimensions not in the vector. Other dimensions are not used. In the example below, Point c(3,1,1)
is only used for its first dimension. Thus we would have obtained the same subRange
by using for example Point d(3,2,4)
.
This example run through all the points in the plane X=3
(if we suppose that dimension 0 is X
, dimension 1 is Y
and dimension 2 is Z
) in reverse direction. Note that you can chose to instantiate domain.subRange(v, c)
only once before the loop, but the gain is negligible regarding the given example where the subrange is instantiated twice. However, the gain can be important comparing with the bad version where the range is instantiated at each step of the loop to compare it with domain.subRange(v, c).rend()
.
Note also that the vector gives not only the dimensions of the subrange but also the order in which these dimensions are considered. In the example above, we start to iterate through Z
, then to Y
since vector v={2,1}
. For this reason, the subrange class can also be used to run through a whole given domain but considering the dimensions in a different order.
There are some shortcuts for the HyperRectDomain::subRange method to facilitate the iteration through subrange having 1, 2, and 3 dimensions: subRange(Dimension adim, const Point & startingPoint)
; subRange(Dimension adim1, Dimension adim2, const Point & startingPoint)
; and subRange(Dimension adim1, Dimension adim2, Dimension adim3, const Point & startingPoint)
.
Lastly, if your compiler supports C++11
initializer list, there is a custom subRange
method taking an std::initializer_list<Dimension>
instead of the std::vector<Dimension>
. This simplifies the use as we can see in the following example since this avoid the creation of a std::vector
and its initialization:
Iterators of HyperRectDomain are randomaccess iterators thus allowing to easily split the scan of a domain in multiple parts, e.g. for parallelization purpose.
You first need to define how to split a range (begin and end iterators) given a total number of launched threads and the id of the current thread:
Now, if you want for example to sum the result of a function applied on each point of a domain, you can first initiate a bunch of threads using an OpenMP parallel region and then iterate over the appropriate part of the point range depending on the current thread id:
Going further, if you want to use such strategy to initialize or modify an image, you can do:
Additionally, if your image also provides randomaccess iterators (like ImageContainerBySTLVector), you can save the getter/setter overhead by using iterators (if the function is not too much CPU intensive):
You can find the complete example and a benchmark in exampleHyperRectDomainParallelScan.cpp
Since version 0.9 of DGtal, HyperRectDomain can model an empty domain and it is what the default constructor returns now.
An empty domain is so that the difference between his lower bound and his upper bound has every component equal to 1. For example, here is some equivalent definitions of an empty domain:
Furthermore, a new method, HyperRectDomain::isEmpty, returns true
if the domain is empty, false
otherwise.
As expected, the following properties are observed if domain
is an empty domain:
domain.size()
returns 0,domain.isInside(p)
returns false
for every point p
,domain.begin() == domain.end()
is true
, and similarly for the reverse iterators,domain.subRange(v, domain.lowerBound()).begin() == domain.subRange(v, domain.lowerBound()).end()
is true
for every subset v
of dimensions, and similarly for the reverse iterators.