Table of Contents
- Author(s) of this documentation:
- Jacques-Olivier Lachaud
Part of the Arithmetic package.
This part of the manual describes digital straightness from a combinatoric and arithmetic point of view. It tells you how to create patterns, digital straight lines in the first quadrant, and how to compute subsegments in sublinear time (algorithms SmartDSS [Said, Lachaud, Feschet 2009 : [110] ] and ReversedSmartDSS [Said, Lachaud 2011 : [109]]). Full proofs and details on these two algorithms are given in [Lachaud, Said 2013 : [71] ].
Standard digital straight lines and patterns
A standard digital straight line in 2D (DSL) is the following subset of \( Z^2 \):
\( \{(x,y) \in Z^2, \mu \le a x - by < \mu + |a| +|b|-1 \} \)
where the integers \( (a,b,\mu) \), \( gcd(a,b)=1 \), are called the characteristics of the straight line [ Reveilles [102] , Debled and Reveilles [46] ].
It is well known that this set of digital points is a simple 4-connected curve. Here is a representation of the straight line (3,5,-5).
The slope of the DSL is \( a/b \), while \( \mu \) is the shift at origin. The remainder of the DSL is the value \( ax-by \). Upper leaning points have remainer \( \mu \) while lower leaning points have value \( \mu + |a| +|b|-1 \).
Patterns
Definition of patterns
A pattern of slope \( a/b \) is the freeman chaincode between two consecutive upper leaning points of any DSL with slope \( a/b \).
Patterns are specific subsegments of digital straight lines (DSL). They depend only on the slope of the DSL, i.e. the irreducible fraction \( a/b \).
Creating patterns in DGtal
Package Arithmetic provides the class Pattern to represent a pattern. Patterns are instantiated either by a fraction or two integers p and q. They are therefore parameterized by the type of irreducible fraction you wish to use (see Irreducible fraction, continued fractions). You may define patterns as follows:
- See also
- pattern.cpp
To get the freeman chaincode of the pattern, you may use the methods Pattern::rE and Pattern::rEs.
$ ./examples/arithmetic/pattern 11 17 0010010100101001010010100101 $ ./examples/arithmetic/pattern 11 17 SUB ((00|1)|(0|0101)(0|0101)(0|0101)(0|0101)(0|0101))
Recursive properties of patterns
Recursive definitions of pattern are related to the continued fraction of the slope. We choose here to present the Berstel recursive definition. If \( z=p/q=[u_0;u_1,\ldots,u_n] \) is the slope of the pattern, the pattern may be obtained from the following recursive formulas:
\( E(z_{-1})=1, E(z_{0})=0, E(z_{2k+1})=E(z_{2k})^{u_{2k+1}} E(z_{2k-1}), E(z_{2k})=E(z_{2k-2}) E(z_{2k-1})^{u_{2k}}. \)
Let us look again at the pattern of 11/17. First, the convergents are:
$ ./examples/arithmetic/convergents 11 17 z = [0,1,1,1,5] z_0 = 0 / 1 z_1 = 1 / 1 z_2 = 1 / 2 z_3 = 2 / 3 z_4 = 11 / 17
E(0/1) = 0 E(1/1) = E([0;1]) = E(0/1)^1 E(z_-1) = 0.1 E(1/2) = E([0;1,1]) = E(0/1) E(1/1)^1 = 0.01 E(2/3) = E([0;1,1,1]) = E(1/2)^1 E(1/1) = 001.01 E(11/17) = E([0;1,1,1,5]) = E(1/2) E(2/3)^5 = 001.(00101)^5
Which is exactly the sought pattern.
There are several methods to compute the Bézout vector of a pattern or the coordinates of its upper and lower leaning points (see reference of class Pattern).
Digital straight lines and subsegments
Creating a digital straight line
For now, you may only instantiate digital straight lines whose slope is in the first quadrant. If \( (a,b,\mu) \) are the characteristics of the line, then \( a \ge 0, b \ge 0 \).
A DSL is a sequence of points in the digital plane
A DSL provides the function operator StandardDSLQ0::operator(), taking a Point p and returning 'true' iff p belongs to the set of points of the DSL. It is indeed a model of concepts::CPointPredicate.
The Point type is PointVector<2,Fraction::Integer>.
You may visit the DSL from left to right with iterators of type StandardDSLQ0::ConstIterator. You just precise the starting point with StandardDSLQ0::begin and the point after the last with StandardDSLQ0::end.
You can compare if a point precedes another point (to the left) on the DSL with methods StandardDSLQ0::before and StandardDSLQ0::beforeOrEqual.
Getting several characteristics
You have access to the following information:
- characteristics \((a,b,\mu)\) with StandardDSLQ0::a, StandardDSLQ0::b, StandardDSLQ0::mu
- value \(\mu+a+b-1\) with StandardDSLQ0::mup
- slope as irreducible fraction with StandardDSLQ0::slope
- pattern of same slope with StandardDSLQ0::pattern
- vector of the pattern (i.e (b,a)) with StandardDSLQ0::v
- remainder of the DSL with StandardDSLQ0::r
- first upper leaning point with x>=0 with StandardDSLQ0::U
- first lower leaning point after the first upper leaning point with StandardDSLQ0::L
Getting points on a DSL
For convenience, you have the following methods to determine points belonging to a DSL:
- given an x-coordinate, find the point with lowest y-coordinate on the DSL with StandardDSLQ0::lowestY
- given an x-coordinate, find the point with uppermost y-coordinate on the DSL with StandardDSLQ0::uppermostY
- given a y-coordinate, find the point with lowest x-coordinate on the DSL with StandardDSLQ0::lowestX
- given a y-coordinate, find the point with uppermost x-coordinate on the DSL with StandardDSLQ0::uppermostX
Fast computation of subsegments
Given two points A and B on the DSL, you can determine the exact characteristics of the subsegment [A,B] in sublinear time with two algorithms: SmartDSS [Said, Lachaud, Feschet 2009 : [110] ] and ReversedSmartDSS [Said, Lachaud 2011 : [109]]. In fact, these algorithms return the DSL which covers [A,B] and whose characteristics are minimal.
- method StandardDSLQ0::smartDSS, given this DSL, A and B, returns this minimal DSL in time proportional to the sum of the quotients of the output DSL.
- method StandardDSLQ0::reversedSmartDSS, given this DSL, A and B, returns this minimal DSL in time proportional to the difference of depth between the input and the output slope.
You may have a look at the following programs to check these algorithms (the many variants come from the different choices for the algorithm and the fraction type):
