DGtal  0.9.3beta
Data Structures | Public Types | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes
DGtal::DSLSubsegment< TInteger, TNumber > Class Template Reference

#include <DGtal/geometry/curves/DSLSubsegment.h>

Collaboration diagram for DGtal::DSLSubsegment< TInteger, TNumber >:
[legend]

Data Structures

class  RayC
 

Public Types

typedef TNumber Number
 
typedef TInteger Integer
 
typedef long double LongDoubleType
 
typedef DGtal::PointVector< 2, IntegerRay
 
typedef DGtal::PointVector< 2, IntegerPoint
 
typedef DGtal::PointVector< 2, NumberPointF
 
typedef DGtal::PointVector< 2, IntegerVector
 
typedef DGtal::PointVector< 2, NumberVectorF
 

Public Member Functions

 ~DSLSubsegment ()
 
void selfDisplay (std::ostream &out) const
 
bool isValid () const
 
 BOOST_CONCEPT_ASSERT ((concepts::CEuclideanRing< Number >))
 
 BOOST_CONCEPT_ASSERT ((concepts::CInteger< Integer >))
 
 DSLSubsegment (Number a, Number b, Number mu, Point &A, Point &B, std::string type)
 
 DSLSubsegment (Number alpha, Number beta, Point &A, Point &B, Number precision=1e-10)
 
Integer computeMinRemainder (Number a, Number b, Number mu, Point A, Point B)
 
Integer computeMaxRemainder (Number a, Number b, Number mu, Point A, Point B)
 
Integer getA () const
 
Integer getB () const
 
Integer getMu () const
 

Protected Types

enum  Position { ABOVE, BELOW, ONTO }
 
typedef enum DGtal::DSLSubsegment::Position Position
 

Protected Member Functions

void DSLSubsegmentFareyFan (Number a, Number b, Number mu, Point &A, Point &B)
 
void DSLSubsegmentLocalCH (Number a, Number b, Number mu, Point &A, Point &B)
 
 DSLSubsegment ()
 
Integer intersectionVertical (Point &P, Vector &v, Integer n)
 
Integer intersection (Point &P, Vector &v, Vector &aL, Integer r)
 
Integer intersection (Point &P, Vector &v, Number s)
 
void update (Vector &u, Point &A, Vector &l, Integer r, Vector *v)
 
void update (Vector &u, Point &A, Number s, Vector *v)
 
void lowerConvexHull (Vector &l, Integer mu, Point &A, Point &B, Point *prevInfL, Point *infL, Point *infR, Point *prevInfR)
 
void convexHullApprox (Vector &l, Integer r, Integer n, Point *inf, Point *sup)
 
void convexHullApprox (Number s, Integer n, Point *inf, Point *sup)
 
void convexHullApproxTwoPoints (Vector &l, Integer r, Integer n, Point *inf, Point *sup, Point *prevInf, Point *prevSup, bool inv)
 
void convexHullHarPeled (Vector &l, Integer n, Point *inf, Point *sup)
 
Point nextTermInFareySeriesEuclid (Integer fp, Integer fq, Integer n)
 
RayC rayOfHighestSlope (Integer p, Integer q, Integer r, Integer smallestSlope, Integer n)
 
Integer slope (Integer p, Integer q, Integer r, Number a, Number b, Number mu)
 
Integer slope (Integer p, Integer q, Integer r, Number alpha, Number beta)
 
Position positionWrtRay (RayC &r, Number a, Number b, Number mu)
 
Position positionWrtRay (RayC &r, Number alpha, Number beta)
 
RayC smartRayOfSmallestSlope (Integer fp, Integer fq, Integer gp, Integer gq, Integer r)
 
Integer smartFirstDichotomy (Integer fp, Integer fq, Integer gp, Integer gq, Number a, Number b, Number mu, Integer n, bool *flagRayFound)
 
Integer smartFirstDichotomy (Integer fp, Integer fq, Integer gp, Integer gq, Number alpha, Number beta, Integer n, bool *flagRayFound)
 
RayC localizeRay (Integer fp, Integer fq, Integer gp, Integer gq, Integer r, Number a, Number b, Number mu, Integer n)
 
RayC localizeRay (Integer fp, Integer fq, Integer gp, Integer gq, Integer r, Number alpha, Number beta, Integer n)
 
RayC raySup (Integer fp, Integer fq, RayC r)
 
void findSolutionWithoutFractions (Integer fp, Integer fq, Integer gp, Integer gq, RayC r, Integer n, Integer *resAlphaP, Integer *resAlphaQ, Integer *resBetaP, bool found)
 
void shortFindSolution (Integer fp, Integer fq, Integer gp, Integer gq, RayC r, Integer n, Integer *resAlphaP, Integer *resAlphaQ, Integer *resBetaP)
 

Protected Attributes

Integer myA
 
Integer myB
 
Integer myMu
 
Number myPrecision
 

Detailed Description

template<typename TInteger, typename TNumber>
class DGtal::DSLSubsegment< TInteger, TNumber >

Aim: Given a Digital Straight line and two endpoints A and B on this line, compute the minimal characteristics of the digital subsegment [AB] in logarithmic time. Two algorithms are implemented: one is based on the local computation of lower and upper convex hulls, the other is based on a dual transformation and uses the Farey fan. Implementation requires that the DSL lies in the first octant (0 <= a <= b).

Description of class 'DSLSubsegment'

Template Parameters
TIntegeris the type of integer used
TNumberis the type of number used to represent the input DSL characteristics.
Examples:
geometry/curves/exampleDSLSubsegment.cpp.

Definition at line 75 of file DSLSubsegment.h.

Member Typedef Documentation

template<typename TInteger , typename TNumber >
typedef TInteger DGtal::DSLSubsegment< TInteger, TNumber >::Integer

Definition at line 104 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
typedef long double DGtal::DSLSubsegment< TInteger, TNumber >::LongDoubleType

Definition at line 105 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
typedef TNumber DGtal::DSLSubsegment< TInteger, TNumber >::Number

Number types

Definition at line 103 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
typedef DGtal::PointVector<2,Integer> DGtal::DSLSubsegment< TInteger, TNumber >::Point

2D integer point

Definition at line 117 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
typedef DGtal::PointVector<2,Number> DGtal::DSLSubsegment< TInteger, TNumber >::PointF

2D real point

Definition at line 122 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
typedef enum DGtal::DSLSubsegment::Position DGtal::DSLSubsegment< TInteger, TNumber >::Position
protected

Position of a point wrt a ray

template<typename TInteger , typename TNumber >
typedef DGtal::PointVector<2,Integer> DGtal::DSLSubsegment< TInteger, TNumber >::Ray

A ray is defined as a 2D integer vector (x,y) such that Ray(x,y) is the straight line beta = -x alpha +y in the (alpha,beta)-space.

Definition at line 112 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
typedef DGtal::PointVector<2,Integer> DGtal::DSLSubsegment< TInteger, TNumber >::Vector

2D integer vector

Definition at line 127 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
typedef DGtal::PointVector<2,Number> DGtal::DSLSubsegment< TInteger, TNumber >::VectorF

2D real vector

Definition at line 132 of file DSLSubsegment.h.

Member Enumeration Documentation

template<typename TInteger , typename TNumber >
enum DGtal::DSLSubsegment::Position
protected

Position of a point wrt a ray

Enumerator
ABOVE 
BELOW 
ONTO 

Definition at line 279 of file DSLSubsegment.h.

Constructor & Destructor Documentation

template<typename TInteger , typename TNumber >
DGtal::DSLSubsegment< TInteger, TNumber >::~DSLSubsegment ( )
inline

Destructor.

Definition at line 83 of file DSLSubsegment.h.

83 {};
template<typename TInteger , typename TNumber >
DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegment ( Number  a,
Number  b,
Number  mu,
Point A,
Point B,
std::string  type 
)

Constructor Given the parameters of a DSL 0 <= ax -by + mu < b, and two points A and B of this DSL, compute the parameters of the DSS [AB]. The algorithm used depends on the value of the boolean (Farey fan if true, local convex hull otherwise).

Parameters
[in]aDSL a parameter
[in]bDSL b parameter
[in]muDSL mu parameter
[in]Aleft-most point
[in]Bright-most point
[in]typea type
template<typename TInteger , typename TNumber >
DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegment ( Number  alpha,
Number  beta,
Point A,
Point B,
Number  precision = 1e-10 
)

Constructor Given a straight line of equation y = alpha x + beta, and two points A and B of the OBQ digitization of this line, compute the parameters of the DSS [AB]. The algorithm implemented uses the Farey fan. Requires a precision parameter for floating-point geometrical predicates

Parameters
[in]alphaslope of the line
[in]betaintercept of the line
[in]Aleft-most point
[in]Bright-most point
[in]precisionprecision
template<typename TInteger , typename TNumber >
DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegment ( )
protected

Constructor. Forbidden by default (protected to avoid g++ warnings).

Member Function Documentation

template<typename TInteger , typename TNumber >
DGtal::DSLSubsegment< TInteger, TNumber >::BOOST_CONCEPT_ASSERT ( (concepts::CEuclideanRing< Number >)  )

Check that Number type verifies the Euclidean Rign concept and Integer type verifies the Integer concept

template<typename TInteger , typename TNumber >
DGtal::DSLSubsegment< TInteger, TNumber >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< Integer >)  )
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::computeMaxRemainder ( Number  a,
Number  b,
Number  mu,
Point  A,
Point  B 
)
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::computeMinRemainder ( Number  a,
Number  b,
Number  mu,
Point  A,
Point  B 
)
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::convexHullApprox ( Vector l,
Integer  r,
Integer  n,
Point inf,
Point sup 
)
protected

Compute the left part of the upper and lower convex hulls of the line of directional vector l and intercept r, between x=0 and x=n. Returns the upper and lower closest points. Implementation of Charrier and Buzer algorithm [16]

Parameters
ldirectional vector of the line
rintercept of the line
nmaximal value of x-coordinate
[out]infclosest point below the line
[out]supclosest point above the line
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::convexHullApprox ( Number  s,
Integer  n,
Point inf,
Point sup 
)
protected

Compute the left part of the upper and lower convex hulls of the line of slope s, between x=0 and x=n. Returns the upper and lower closest points.

Parameters
sslope of the line (interpect is equal to zero here)
nmaximal value of x-coordinate
[out]infclosest point below the line
[out]supclosest point above the line
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::convexHullApproxTwoPoints ( Vector l,
Integer  r,
Integer  n,
Point inf,
Point sup,
Point prevInf,
Point prevSup,
bool  inv 
)
protected

Compute the left part of the upper and lower convex hulls of the line of slope s, between x=0 and x=n. Returns the last two points computed. Implementation of Charrier and Buzer algorithm [16]

Parameters
ldirectional vector of the line
rintercept of the line
nmaximal value of x-coordinate
[out]infclosest point below the line
[out]supclosest point above the line
[out]prevInfsecond-closest point below the line
[out]prevSupsecond-closest point above the line
invboolean used to know if the CH is computed from left-to-right (inv=false) or right-to-left (inv = true)
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::convexHullHarPeled ( Vector l,
Integer  n,
Point inf,
Point sup 
)
protected

Compute the left part of the upper and lower convex hulls of the line of directional vector l, between x=0 and x=n. Returns the last two points computed. Implementation of Har-Peled algorithm (Computational Geometry: Theory and Applications, 1998)

Parameters
ldirectional vector of the line (intercept is zero)
nmaximal value of x-coordinate
[out]infclosest point below the line
[out]supclosest point above the line
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegmentFareyFan ( Number  a,
Number  b,
Number  mu,
Point A,
Point B 
)
protected

Function called by the constructor when the input parameters are integers and the Farey Fan algorithm is used.

Parameters
aDSL a parameter
bDSL b parameter
muDSL mu parameter
Aleft-most point
Bright-most point
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::DSLSubsegmentLocalCH ( Number  a,
Number  b,
Number  mu,
Point A,
Point B 
)
protected

Function called by the constructor when the input parameters are integers and the local convex hull algorithm is used.

Parameters
aDSL a parameter
bDSL b parameter
muDSL mu parameter
Aleft-most point
Bright-most point
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::findSolutionWithoutFractions ( Integer  fp,
Integer  fq,
Integer  gp,
Integer  gq,
RayC  r,
Integer  n,
Integer resAlphaP,
Integer resAlphaQ,
Integer resBetaP,
bool  found 
)
protected

The two fractions f and g together with the ray r define a segment PQ. PQ is part of the lower boundary of exactly one cell of the FareyFan. This cell represents a DSS. This function computes the vertex of the cell that represents the minimal characteristics of the DSS. Optimized version of the algorithm presented in the paper [68] . Complexity of nextTermInFareySeriesEuclid

Parameters
fpnumerator of the smallest fraction of the ladder
fqdenominator of the smallest fraction of the ladder
gpnumerator of the greatest fraction of the ladder
gqdenominator of the greatest fraction of the ladder
ra ray
norder of the Farey Fan
[out]resAlphaPnumerator of the x-coordinate of the result
[out]resAlphaQdenominator of the x- and y- coordinates of the result
[out]resBetaPnumerator of the y-coordinate of the result
[in]foundused for optimization (true if r is the ray of smallest slope on point P, false otherwise). Its value comes from the smartFirstDichotomy function.
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::getA ( ) const
Returns
an Integer of value myA.
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::getB ( ) const
Returns
an Integer of value myB.
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::getMu ( ) const
Returns
an Integer of value myMu.
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::intersection ( Point P,
Vector v,
Vector aL,
Integer  r 
)
protected

Compute the intersection between the line of direction v passing through P and the line y = (aL[1]/aL[0])*x +r The intersection point is of the form P + α*v and the function returns the value floor(α).

Parameters
Pa point of the first line
vdirectional vector of the first line
aLslope of the second line is equal to aL[1]/aL[0]
rintercept of the second line
Returns
integer
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::intersection ( Point P,
Vector v,
Number  s 
)
protected

Compute the intersection between the line of direction v passing through P and the line y = s*x The intersection point is of the form P + α*v and the function returns the value floor(α).

Parameters
Pa point of the first line
vdirectional vector of the first line
sslope of the second line
Returns
integer
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::intersectionVertical ( Point P,
Vector v,
Integer  n 
)
protected

Compute the intersection between the line of direction v passing through P and the vertical line x = n. The intersection point is of the form P + α*v and the function returns the value floor(α).

Parameters
Pa point
vdirectional vector of the line
nmaximal value for x-coordinate
Returns
integer
template<typename TInteger , typename TNumber >
bool DGtal::DSLSubsegment< TInteger, TNumber >::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.
template<typename TInteger , typename TNumber >
RayC DGtal::DSLSubsegment< TInteger, TNumber >::localizeRay ( Integer  fp,
Integer  fq,
Integer  gp,
Integer  gq,
Integer  r,
Number  a,
Number  b,
Number  mu,
Integer  n 
)
protected

Compute the closest ray below the point (a/b,mu/b) passing through the point (fp/fq,r/fq) in the Farey fan of order n

Parameters
fpnumerator of the smallest fraction of the ladder
fqdenominator of the smallest fraction of the ladder
gpnumerator of the greatest fraction of the ladder
gqdenominator of the greatest fraction of the ladder
rnumerator of the point y-coordinate
aDSL a parameter
bDSL b parameter
muDSL my parameter
norder of the Farey Fan
Returns
a ray
template<typename TInteger , typename TNumber >
RayC DGtal::DSLSubsegment< TInteger, TNumber >::localizeRay ( Integer  fp,
Integer  fq,
Integer  gp,
Integer  gq,
Integer  r,
Number  alpha,
Number  beta,
Integer  n 
)
protected

Compute the closest ray below the point (alpha,beta) passing through the point (fp/fq,r/fq) in the Farey fan of order n

Parameters
fpnumerator of the smallest fraction of the ladder
fqdenominator of the smallest fraction of the ladder
gpnumerator of the greatest fraction of the ladder
gqdenominator of the greatest fraction of the ladder
rnumerator of the point y-coordinate
alphaDSL slope
betaDSL intercept
norder of the Farey Fan
Returns
a ray
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::lowerConvexHull ( Vector l,
Integer  mu,
Point A,
Point B,
Point prevInfL,
Point infL,
Point infR,
Point prevInfR 
)
protected

Compute the lower integer convex hull of the line of directional vector l and intercept mu between the points A and B. The algorithm works in two steps (from left to right and right to left). Each step returns the two closest points, and these four points are returned by the function.

Parameters
ldirectional vector of the straight line
muintercept of the straight line
Aleft-most bound of the CH
Bright-most bound of the CH
[out]prevInfLlast-but-one point of the CH from left to right
[out]infLlast point of the CH from left to right
[out]infRlast point of the CH from right to left
[out]prevInfRlast-but-one point of the CH from right to left
template<typename TInteger , typename TNumber >
Point DGtal::DSLSubsegment< TInteger, TNumber >::nextTermInFareySeriesEuclid ( Integer  fp,
Integer  fq,
Integer  n 
)
protected

Compute the term following fp/fq in the Farey series of order n.

Parameters
fpnumerator
fqdenominator
norder the the Farey Series
Returns
a point (q,p) such that p/q follows fp/fq in the Farey Series of order n
template<typename TInteger , typename TNumber >
Position DGtal::DSLSubsegment< TInteger, TNumber >::positionWrtRay ( RayC r,
Number  a,
Number  b,
Number  mu 
)
protected

Compute the position of the point (a/b,mu/b) with respect to a ray r. Number must be an Integer type

Parameters
ra ray
anumerator of x-coordinate
bdenominator of x- and y-coordinates
munumerator of x-coordinate
Returns
Position equal to BELOW, ABOVE or ONTO
template<typename TInteger , typename TNumber >
Position DGtal::DSLSubsegment< TInteger, TNumber >::positionWrtRay ( RayC r,
Number  alpha,
Number  beta 
)
protected

Compute the position of the floating-point point(alpha,beta) with respect to a ray r.

Parameters
ra ray
alphax-coordinate
betay-coordinate
Returns
Position equal to BELOW, ABOVE or ONTO
template<typename TInteger , typename TNumber >
RayC DGtal::DSLSubsegment< TInteger, TNumber >::rayOfHighestSlope ( Integer  p,
Integer  q,
Integer  r,
Integer  smallestSlope,
Integer  n 
)
protected

Compute the ray of highest slope passing through a given point (p/q,r/q) in O(1) knowing the ray of smallest slope and the order of the Farey fan

Parameters
pnumerator of x-coordinate
qdenominator of x- and y-coordinates
rnumerator of y-coordinate
smallestSlopesmallest slope of the rays passing through (p/q,r/q)
norder of the Farey fan
Returns
a ray
template<typename TInteger , typename TNumber >
RayC DGtal::DSLSubsegment< TInteger, TNumber >::raySup ( Integer  fp,
Integer  fq,
RayC  r 
)
protected

Compute the ray passing through from (f=fp/fq,h/fq) just above r. The knowledge of h is not necessary. Complexity O(1)

Parameters
fpnumerator
fqdenominator
ra ray
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::shortFindSolution ( Integer  fp,
Integer  fq,
Integer  gp,
Integer  gq,
RayC  r,
Integer  n,
Integer resAlphaP,
Integer resAlphaQ,
Integer resBetaP 
)
protected

Corresponds to the algorithm presented in [68].

Parameters
fpnumerator of the smallest fraction of the ladder
fqdenominator of the smallest fraction of the ladder
gpnumerator of the greatest fraction of the ladder
gqdenominator of the greatest fraction of the ladder
ra ray
norder of the Farey Fan
[out]resAlphaPnumerator of the x-coordinate of the result
[out]resAlphaQdenominator of the x- and y- coordinates of the result
[out]resBetaPnumerator of the y-coordinate of the result
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::slope ( Integer  p,
Integer  q,
Integer  r,
Number  a,
Number  b,
Number  mu 
)
protected

Compute the ceil of the slope of the line through (f=p/q,r/q) and point (a/b,mu/b) - O(1) - Number must be an Integer type.

Parameters
pnumerator of x-coordinate of the first point
qdenominator of x- and y-coordinates of the first point
rnumerator of y-coordinate of the first point
anumerator of x-coordinate of the second point
bdenominator of x- and y-coordinates of the second point
munumerator of y-coordinate of the second point
Returns
the ceil of the slope of the line passing through the two points
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::slope ( Integer  p,
Integer  q,
Integer  r,
Number  alpha,
Number  beta 
)
protected

Compute the ceil of the slope of the line through (f=p/q,r/q) and floating-point point (alpha,beta) - O(1)

Parameters
pnumerator of x-coordinate of the first point
qdenominator of x- and y-coordinates of the first point
rnumerator of y-coordinate of the first point
alphax-coordinate of the second point
betay-coordinate of the second point
Returns
the ceil of the slope of the line passing through the two points
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::smartFirstDichotomy ( Integer  fp,
Integer  fq,
Integer  gp,
Integer  gq,
Number  a,
Number  b,
Number  mu,
Integer  n,
bool *  flagRayFound 
)
protected

Performs a dichotomy among the rays of smallest slope passing through the points (fp/fq,r/fq), r in [0,fq] in order to locate the point lambda(a/b,mu/b) in the ladder. Implements line 3 of Algorithm 1 in [68]. Return an integer h such that either i) lambda is in between the rays passing through the point (fp/fq,h/fq) and flagRayFound is set to false or ii) lambda is below all the rays passing through the point (fp/fq,h+1/fq) and above all the rays passing through the point (fp/fq,h/fq) and flagRayFound is set to false. In case i), function localizeRay is used afterwards to localize lambda in between the rays. In case ii), the ray under lambda has been found and no further search is needed. The Number type must verify the CInteger concept (otherwise, see overloaded function).

Parameters
fpnumerator of the smallest fraction of the ladder
fqdenominator of the smallest fraction of the ladder
gpnumerator of the greatest fraction of the ladder
gqdenominator of the greatest fraction of the ladder
aDSL a parameter
bDSL b parameter
muDSL mu parameter
norder of the Farey Fan
[out]flagRayFoundpointer on a boolean, used to check whether localizeRay should be called ot not
Returns
an integer
template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::smartFirstDichotomy ( Integer  fp,
Integer  fq,
Integer  gp,
Integer  gq,
Number  alpha,
Number  beta,
Integer  n,
bool *  flagRayFound 
)
protected

Performs a dichotomy among the rays of smallest slope passing through the points (fp/fq,r/fq), r in [0,fq] in order to locate the point lambda(alpha,beta) in the ladder. Implements line 3 of Algorithm 1 in [68]. Return an integer h such that either i) lambda is in between the rays passing through the point (fp/fq,h/fq) and flagRayFound is set to false or ii) lambda is below all the rays passing through the point (fp/fq,h+1/fq) and above all the rays passing through the point (fp/fq,h/fq) and flagRayFound is set to false. In case i), function localizeRay is used afterwards to localize lambda in between the rays. In case ii), the ray under lambda has been found and no further search is needed.

Parameters
fpnumerator of the smallest fraction of the ladder
fqdenominator of the smallest fraction of the ladder
gpnumerator of the greatest fraction of the ladder
gqdenominator of the greatest fraction of the ladder
alphaDSL slope
betaDSL intercept
norder of the Farey Fan
[out]flagRayFoundpointer on a boolean, used to check whether localizeRay should be called ot not
Returns
an integer
template<typename TInteger , typename TNumber >
RayC DGtal::DSLSubsegment< TInteger, TNumber >::smartRayOfSmallestSlope ( Integer  fp,
Integer  fq,
Integer  gp,
Integer  gq,
Integer  r 
)
protected

Computes the ray of smallest slope emanating from the point (f=p/q, r/q) using the knowledge of the next fraction g in the Farey Series. Complexity O(1)

Parameters
fpnumerator of the point x-coordinate
fqdenominator of the point x- and y-coordinates
gpnumerator of the fraction following fp/fq in the Farey Series
gqdenominator of the fraction following fp/fq in the Farey Series
rnumerator of the point y-coordinate
Returns
the ray of smallest slope passing through the point
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::update ( Vector u,
Point A,
Vector l,
Integer  r,
Vector v 
)
protected

Update the Bezout vector v of u according to the new point A in the case of integer parameters. Follows algorithm presented in [16]

Parameters
ua vector
Aa point
ldirectional vector of the line
rintercept of the line
[in,out]vbezout vector updated in this function
template<typename TInteger , typename TNumber >
void DGtal::DSLSubsegment< TInteger, TNumber >::update ( Vector u,
Point A,
Number  s,
Vector v 
)
protected

Update the Bezout vector v of u according to the new point A in the case of floating-point parameters. Follows algorithm presented in [16]

Parameters
ua vector
Aa point
sslope of the line
[in,out]vbezout vector updated in this function

Field Documentation

template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::myA
protected

The minimal characteristics of the subsegment AB of the DSL(a,b,mu) are (myA,myB,myMu).

Definition at line 147 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::myB
protected

The minimal characteristics of the subsegment AB of the DSL(a,b,mu) are (myA,myB,myMu).

Definition at line 154 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
Integer DGtal::DSLSubsegment< TInteger, TNumber >::myMu
protected

The minimal characteristics of the subsegment AB of the DSL(a,b,mu) are (myA,myB,myMu).

Definition at line 161 of file DSLSubsegment.h.

template<typename TInteger , typename TNumber >
Number DGtal::DSLSubsegment< TInteger, TNumber >::myPrecision
protected

Precision used for floating-point geometrical predicates (when TNumber is not an integer type)

Definition at line 167 of file DSLSubsegment.h.


The documentation for this class was generated from the following file: